| Helger Lipmaa's publications |
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.
Page by Helger Lipmaa. Send your inqueries to <helger.lipmaa>">gmail.com.