Paper 2019/877

Blind Schnorr Signatures and Signed ElGamal Encryption in the Algebraic Group Model

Georg Fuchsbauer, Antoine Plouviez, and Yannick Seurin

Abstract

The Schnorr blind signing protocol allows blind issuing of Schnorr signatures, one of the most widely used signatures. Despite its practical relevance, its security analysis is unsatisfactory. The only known security proof is rather informal and in the combination of the generic group model (GGM) and the random oracle model (ROM) assuming that the ``ROS problem'' is hard. The situation is similar for (Schnorr-)signed ElGamal encryption, a simple CCA2-secure variant of ElGamal. We analyze the security of these schemes in the algebraic group model (AGM), an idealized model closer to the standard model than the GGM. We first prove tight security of Schnorr signatures from the discrete logarithm assumption (DL) in the AGM+ROM. We then give a rigorous proof for blind Schnorr signatures in the AGM+ROM assuming hardness of the one-more discrete logarithm problem and ROS. As ROS can be solved in sub-exponential time using Wagner's algorithm, we propose a simple modification of the signing protocol, which leaves the signatures unchanged. It is therefore compatible with systems that already use Schnorr signatures, such as blockchain protocols. We show that the security of our modified scheme relies on the hardness of a problem related to ROS that appears much harder. Finally, we give tight reductions, again in the AGM+ROM, of the CCA2 security of signed ElGamal encryption to DDH and signed hashed ElGamal key encapsulation to DL.

Note: An abridged version appears in the proceedings of EUROCRYPT 2020. This is the full version. Please note that a polynomial-time attack against the ROS problem was recently discovered (Benhamouda, Lepoint, Orrù, and Raykova, ePrint report 2020/945). Minor correction to the proof of Theorem 1 (revised version of January 16, 2021).

Metadata
Available format(s)
PDF
Category
Public-key cryptography
Publication info
A major revision of an IACR publication in Eurocrypt 2020
Keywords
Schnorr signaturesblind signaturesalgebraic group modelElGamal encryptionblockchain protocols
Contact author(s)
georg fuchsbauer @ tuwien ac at
antoine plouviez @ ens fr
yannick seurin @ m4x org
History
2021-01-16: last of 3 revisions
2019-08-01: received
See all versions
Short URL
https://ia.cr/2019/877
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2019/877,
      author = {Georg Fuchsbauer and Antoine Plouviez and Yannick Seurin},
      title = {Blind Schnorr Signatures and Signed ElGamal Encryption in the Algebraic Group Model},
      howpublished = {Cryptology ePrint Archive, Paper 2019/877},
      year = {2019},
      note = {\url{https://eprint.iacr.org/2019/877}},
      url = {https://eprint.iacr.org/2019/877}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.