Cryptology ePrint Archive: Report 2019/877

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

Georg Fuchsbauer and 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.

Category / Keywords: public-key cryptography / Schnorr signatures, blind signatures, algebraic group model, ElGamal encryption, blockchain protocols

Original Publication (with major differences): IACR-EUROCRYPT-2020

Date: received 30 Jul 2019, last revised 16 Jan 2021

Contact author: georg fuchsbauer at tuwien ac at, antoine plouviez at ens fr, yannick seurin at m4x org

Available format(s): PDF | BibTeX Citation

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

Version: 20210116:134616 (All versions of this report)

Short URL:

[ Cryptology ePrint archive ]