You are looking at a specific version 20200304:080845 of this paper. See the latest version.

Paper 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.

Metadata
Available format(s)
PDF
Category
Cryptographic protocols
Publication info
A major revision of an IACR publication in EUROCRYPT 2020
Keywords
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
History
2020-03-04: received
Short URL
https://ia.cr/2020/271
License
Creative Commons Attribution
CC BY
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.