Cryptology ePrint Archive: Report 2020/271

Signatures from Sequential-OR Proofs

Marc Fischlin and Patrick Harasser and Christian Janson

Abstract: OR-proofs enable a prover to show that it knows the witness for one of many statements, or that one out of many statements is true. OR-proofs are a remarkably versatile tool, used to strengthen security properties, design group and ring signature schemes, and achieve tight security. The common technique to build OR-proofs is based on an approach introduced by Cramer, Damgård, and Schoenmakers (CRYPTO’94), where the prover splits the verifier’s challenge into random shares and computes proofs for each statement in parallel. In this work we study a different, less investigated OR-proof technique, put forward by Abe, Ohkubo, and Suzuki (ASIACRYPT’02). The difference is that the prover now computes the individual proofs sequentially. We show that such sequential OR-proofs yield signature schemes which can be proved secure in the non-programmable random oracle model. We complement this positive result with a black-box impossibility proof, showing that the same is unlikely to be the case for signatures derived from traditional OR-proofs. We finally argue that sequential-OR signature schemes can be proved secure in the quantum random oracle model, albeit with very loose bounds and by programming the random oracle.

Category / Keywords: cryptographic protocols / Sequential-OR proofs, Zero-knowledge, Signatures, Non-programmable random oracle model, Quantum random oracle model

Original Publication (with major differences): IACR-EUROCRYPT-2020

Date: received 29 Feb 2020

Contact author: marc fischlin at cryptoplexity de, patrick harasser@cryptoplexity de, christian janson@cryptoplexity de

Available format(s): PDF | BibTeX Citation

Version: 20200304:080845 (All versions of this report)

Short URL:

[ Cryptology ePrint archive ]