×

Communication-efficient non-interactive proofs of knowledge with online extractors. (English) Zbl 1145.94467

Shoup, Victor (ed.), Advances in cryptology – CRYPTO 2005. 25th annual international cryptology conference, Santa Barbara, CA, USA, August 14–18, 2005. Proceedings. Berlin: Springer (ISBN 3-540-28114-2/pbk). Lecture Notes in Computer Science 3621, 152-168 (2005).
Summary: We show how to turn three-move proofs of knowledge into non-interactive ones in the random oracle model. Unlike the classical Fiat-Shamir transformation our solution supports an online extractor which outputs the witness from such a non-interactive proof instantaneously, without having to rewind or fork. Additionally, the communication complexity of our solution is significantly lower than for previous proofs with online extractors. We furthermore give a superlogarithmic lower bound on the number of hash function evaluations for such online extractable proofs, matching the number in our construction, and we also show how to enhance security of the group signature scheme suggested recently by D. Boneh, X. Boyen and H. Shacham [Crypto 2004, Lect. Notes Comput. Sci. 3152, 41–55 (2004; Zbl 1104.94044)] with our construction.
For the entire collection see [Zbl 1131.94006].

MSC:

94A62 Authentication, digital signatures and secret sharing
68Q17 Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)

Citations:

Zbl 1104.94044
PDFBibTeX XMLCite
Full Text: DOI