Cryptology ePrint Archive: Report 2019/877

Blind Schnorr Signatures in the Algebraic Group Model

Georg Fuchsbauer and Antoine Plouviez and Yannick Seurin

Abstract: We study the security of schemes related to Schnorr signatures in the algebraic group model (AGM) proposed by Fuchsbauer, Kiltz, and Loss (CRYPTO 2018), where the adversary can only compute new group elements by applying the group operation. Schnorr signatures can be proved secure in the random oracle model (ROM) under the discrete logarithm assumption (DL) by rewinding the adversary; but this security proof is loose. We start with giving a tight security proof under DL in the combination of the AGM and the ROM. Our main focus are blind Schnorr signatures, whose only known security proof is in the combination of the ROM and the generic group model, under the assumption that the so-called ROS problem is hard. We show that in the AGM+ROM the scheme is secure assuming hardness of the one-more discrete logarithm problem and the ROS problem. As the latter can be solved in sub-exponential time using Wagner's algorithm, this is not entirely satisfying. Hence, we then propose a very simple modification of the scheme (which leaves key generation and signature verification unchanged) and show that, instead of ROS, its security relies on the hardness of a related problem which appears much harder than ROS. Finally, we give a tight reduction of the CCA2 security of Schnorr-signed ElGamal key encapsulation to DL, again in the AGM+ROM.

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

Date: received 30 Jul 2019

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

Available format(s): PDF | BibTeX Citation

Version: 20190801:132245 (All versions of this report)

Short URL: ia.cr/2019/877


[ Cryptology ePrint archive ]