Logical Approaches to Computational Barriers

Succinct NP Proofs from an Extractability Assumption

Speaker:
| Helger Lipmaa |

Author(s): |
Giovanni Di Crescenzo and Helger Lipmaa |

We prove, \emph{using a non-standard complexity assumption}, that any language in $\NP$ has a \emph{1-round} (that is, the verifier sends a message to the prover, and the prover sends a message to the verifier) argument system (that is, a proof system where soundness holds against polynomial-time provers) with communication complexity \emph{only polylogarithmic in the size of the $\NP$ instance}. We also show formal evidence that the nature of the non-standard complexity assumption we use is analogous to previous assumptions proposed in the cryptographic literature. The question of whether complexity assumptions of this nature can be considered acceptable or not remains of independent interest in complexity-theoretic cryptography as well as complexity theory.

websites: Arnold Beckmann | 2008-06-16 |