Paper 2023/298

Hardening Signature Schemes via Derive-then-Derandomize: Stronger Security Proofs for EdDSA

Mihir Bellare, University of California San Diego
Hannah Davis, University of California San Diego
Zijing Di, Stanford University

We consider a transform, called Derive-then-Derandomize, that hardens a given signature scheme against randomness failure and implementation error. We prove that it works. We then give a general lemma showing indifferentiability of Shrink-MD, a class of constructions that apply a shrinking output transform to an MD-style hash function. Armed with these tools, we give new proofs for the widely standardized and used EdDSA signature scheme, improving prior work in two ways: (1) we give proofs for the case that the hash function is an MD-style one, reflecting the use of SHA512 in the NIST standard, and (2) we improve the tightness of the reduction so that one has guarantees for group sizes in actual use.

Available format(s)
Public-key cryptography
Publication info
A major revision of an IACR publication in PKC 2023
SchnorrEdDSAindifferentiabilitySHA-512SHA-256signature schemes
Contact author(s)
mbellare @ ucsd edu
h3davis @ ucsd edu
zidi @ stanford edu
2023-02-28: approved
2023-02-27: received
See all versions
Short URL
No rights reserved


      author = {Mihir Bellare and Hannah Davis and Zijing Di},
      title = {Hardening Signature Schemes via Derive-then-Derandomize: Stronger Security Proofs for EdDSA},
      howpublished = {Cryptology ePrint Archive, Paper 2023/298},
      year = {2023},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.