We show that one-way functions suffice for constructing very efficient argument systems for proving the correctness of bounded-space computations. Taking $\kappa$ to be a cryptographic security parameter and $n$ to be the input length, our argument system applies to general computations running in time $T$ and space $S$. The protocol ... more >>>

A robust combiner for a cryptographic primitive $P$ takes multiple candidate constructions of $P$ and produces a secure construction of $P$ provided that sufficiently many of the candidates are secure. A closely related notion is that of a security amplifier, where given a weakly secure construction of $P$, we aim ... more >>>

We introduce a new family of propositional proof systems, denoted $\langle EF, R \rangle$, for an arbitrary TFNP search problem $R$. Informally, a refutation of a CNF formula $F$ in $\langle EF, R \rangle$ is given by a polynomial-time mapping reduction from the false-clause search problem ${\mathrm{Search}}_F$ to $R$, combined ... more >>>