In the Random Oracle Model (ROM) all parties have oracle access to a common random function, and the parties are limited in the number of queries they can make to the oracle. The Merkle’s Puzzles protocol, introduced by Merkle [CACM ’78], is a key-agreement protocol in the ROM with a ... more >>>

We revisit the main result of Carmosino et al \cite{CILM18} which shows that an $\Omega(n^{\omega/2+\epsilon})$ size noncommutative arithmetic circuit size lower bound (where $\omega$ is the matrix multiplication exponent) for a constant-degree $n$-variate polynomial family $(g_n)_n$, where each $g_n$ is a noncommutative polynomial, can be ``lifted'' to an exponential size ... more >>>

We show that for any integer $d>0$, depth $d$ Frege systems are NP-hard to automate. Namely, given a set $S$ of depth $d$ formulas, it is NP-hard to find a depth $d$ Frege refutation of $S$ in time polynomial in the size of the shortest such a refutation. This extends ... more >>>