Paper 2020/1361

Tight adaptive reprogramming in the QROM

Alex B. Grilo, Kathrin Hövelmanns, Andreas Hülsing, and Christian Majenz


The random oracle model (ROM) enjoys widespread popularity, mostly because it tends to allow for tight and conceptually simple proofs where provable security in the standard model is elusive or costly. While being the adequate replacement of the ROM in the post-quantum security setting, the quantum-accessible random oracle model (QROM) has thus far failed to provide these advantages in many settings. In this work, we focus on adaptive reprogrammability, a feature of the ROM enabling tight and simple proofs in many settings. We show that the straightforward quantum-accessible generalization of adaptive reprogramming is feasible by proving a bound on the adversarial advantage in distinguishing whether a random oracle has been reprogrammed or not. We show that our bound is tight by providing a matching attack. We go on to demonstrate that our technique recovers the mentioned advantages of the ROM in three QROM applications: 1) We give a tighter proof of security of the message compression routine as used by XMSS. 2) We show that the standard ROM proof of chosen-message security for Fiat-Shamir signatures can be lifted to the QROM, straightforwardly, achieving a tighter reduction than previously known. 3) We give the first QROM proof of security against fault injection and nonce attacks for the hedged Fiat-Shamir transform.

Note: *author name was spelled incorrectly

Available format(s)
Public-key cryptography
Publication info
Post-quantum securityQROMadaptive reprogrammingdigital signatureFiat-Shamir transformhedged Fiat-ShamirXMSS
Contact author(s)
authors-qrom-reprog @ huelsing net
2020-10-30: last of 2 revisions
2020-10-29: received
See all versions
Short URL
Creative Commons Attribution


      author = {Alex B.  Grilo and Kathrin Hövelmanns and Andreas Hülsing and Christian Majenz},
      title = {Tight adaptive reprogramming in the QROM},
      howpublished = {Cryptology ePrint Archive, Paper 2020/1361},
      year = {2020},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.