## CryptoDB

### Paper: Signatures from Sequential-OR Proofs

Authors: Marc Fischlin , Technische Universität Darmstadt Patrick Harasser , Technische Universität Darmstadt Christian Janson , Technische Universität Darmstadt DOI: 10.1007/978-3-030-45727-3_8 (login may be required) Search ePrint Search Google EUROCRYPT 2020 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, Damgaard, 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, highlighted 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.
##### BibTeX
@inproceedings{eurocrypt-2020-30229,
title={Signatures from Sequential-OR Proofs},
booktitle={39th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Zagreb, Croatia, May 10–14, 2020, Proceedings},
series={Lecture Notes in Computer Science},
publisher={Springer},
keywords={Sigma-protocols;OR-technique;digital signatures;non-programmable ROM},
volume={12105},
doi={10.1007/978-3-030-45727-3_8},
author={Marc Fischlin and Patrick Harasser and Christian Janson},
year=2020
}