## Succinct NP Proofs from An Extractability Assumption

Giovanni Di Crescenzo and Helger Lipmaa. Succinct NP Proofs from An Extractability Assumption. In Arnold Beckmann, Costas Dimitracopoulos and Benedikt Löwe, editors, *Computability in Europe*, volume 5028 of *Lecture Notes in Computer Science*, pages 175--185, Athens, Greece, June 15--20, 2008. Springer, Heidelberg.

**File:**
[.pdf (93 KB)] __pdf recommended__.

**Abstract**:

We prove, using a non-standard complexity assumption, that any language in NP has a 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 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..

**Keywords:** NP, probabilistic proof systems, complexity-theoretic cryptography.

**Authors:**

Page by Helger Lipmaa. Send your inqueries to `<helger.lipmaa>gmail.com`.