Communication-Efficient Non-Interactive Proofs of Knowledge with Online Extractors

Marc Fischlin

Advances in Cryptology — CRYPTO 2005, Lecture Notes in Computer Science, Springer-Verlag, vol. 3621, pp. 152–168, Aug 2005.

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 Boneh, Boyen and Shacham with our construction.

BibTeX Citation

@inproceedings{Fischl05b,
    author       = {Marc Fischlin},
    title        = {Communication-Efficient Non-Interactive Proofs of Knowledge with Online Extractors},
    editor       = {Victor Shoup},
    booktitle    = {Advances in Cryptology --- CRYPTO 2005},
    pages        = 152--168,
    series       = {Lecture Notes in Computer Science},
    volume       = 3621,
    year         = 2005,
    month        = 8,
    publisher    = {Springer-Verlag},
}