International Association for Cryptologic Research

International Association
for Cryptologic Research


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

Georg Fuchsbauer , TU Wien, Austria
Antoine Plouviez , Inria, ENS, and CNRS, France
Yannick Seurin , ANSSI, France
DOI: 10.1007/978-3-030-45724-2_3 (login may be required)
Search ePrint
Search Google
Conference: EUROCRYPT 2020
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 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.
Video from EUROCRYPT 2020
  title={Blind Schnorr Signatures and Signed ElGamal Encryption in the Algebraic Group Model},
  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},
  keywords={Schnorr signatures;blind signatures;algebraic group model;ElGamal encryption;blockchain protocols},
  author={Georg Fuchsbauer and Antoine Plouviez and Yannick Seurin},