## 3-Message NP Arguments in The BPK Model with Optimal Soundness And Zero-Knowledge

Giovanni Di Crescenzo and Helger Lipmaa. 3-Message NP Arguments in The BPK Model with Optimal Soundness And Zero-Knowledge. In Seok-Hee Hong, Hiroshi Nagamochi and Takuro Fukunaga, editors, *The 19th International Symposium on Algorithm and Computation, ISAAC 2008*, volume 5369 of *Lecture Notes in Computer Science*, pages 616--628, Gold Coast, Australia, December 15--17, 2008. Springer, Heidelberg.

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

**Abstract**:

Under sub-exponential time hardness assumptions, we show that any
language in NP has a 3-message argument system in the bare public key (BPK)
model, that satisfies resettable zero-knowledge (i.e., it reveals no information to
any cheating verifier that can even reset provers) and bounded-resettable soundness
(i.e., a verifier cannot be convinced of a false theorem, even if the cheating
prover resets the verifier up to a fixed polynomial number of sessions). Our protocol
has essentially optimal soundness among 3-message protocols (in that all
stronger known soundness notions cannot be achieved with only 3 messages) and
zero-knowledge (in that it achieves the strongest known zero-knowledge notion).
We also show an extension of this protocol so that it achieves polylogarithmic
communication complexity, although under very strong assumptions..

**Keywords:** Zero-knowledge arguments, resettable zero-knowledge, resettable
soundness, bare public-key model for zero-knowledge protocols.

**Authors:**

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