Paper 2020/271

Signatures from Sequential-OR Proofs

Marc Fischlin, Patrick Harasser, and Christian Janson


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.

Available format(s)
Cryptographic protocols
Publication info
A major revision of an IACR publication in EUROCRYPT 2020
Sequential-OR proofsZero-knowledgeSignaturesNon-programmable random oracle modelQuantum random oracle model
Contact author(s)
marc fischlin @ cryptoplexity de
patrick harasser @ cryptoplexity de
christian janson @ cryptoplexity de
2020-03-04: received
Short URL
Creative Commons Attribution


      author = {Marc Fischlin and Patrick Harasser and Christian Janson},
      title = {Signatures from Sequential-{OR} Proofs},
      howpublished = {Cryptology ePrint Archive, Paper 2020/271},
      year = {2020},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.