Paper 2023/756

SDitH in the QROM

Carlos Aguilar-Melchor, SandboxAQ
Andreas Hülsing, Eindhoven University of Technology
David Joseph, SandboxAQ
Christian Majenz, Technical University of Denmark
Eyal Ronen, Tel Aviv University
Dongze Yue, SandboxAQ

The MPC in the Head (MPCitH) paradigm has recently led to significant improvements for signatures in the code-based setting. In this paper we consider some modifications to a recent twist of MPCitH, called Hypercube-MPCitH, that in the code-based setting provides the currently best known signature sizes. By compressing the Hypercube-MPCitH five-round code-based identification scheme into three-rounds we obtain two main benefits. On the one hand, it allows us to further develop recent techniques to provide a tight security proof in the quantum-accessible random oracle model (QROM), avoiding the catastrophic reduction losses incurred using generic QROM-results for Fiat-Shamir. On the other hand, we can reduce the already low-cost online part of the signature even further. In addition, we propose the use of proof-of-work techniques that allow to reduce the signature size. On the technical side, we develop generalizations of several QROM proof techniques and introduce a variant of the recently proposed extractable QROM.

Note: Revised version after implementing requested changes from Asiacrypt reviews

Available format(s)
Public-key cryptography
Publication info
A minor revision of an IACR publication in ASIACRYPT 2023
Post-Quantum CryptographyDigital SignatureCode-based CryptographySDitHFiat-ShamirQROMExtractable QROMQROM+
Contact author(s)
carlos aguilar @ sandboxquantum com
andreas @ huelsing net
david joseph @ sandboxquantum com
chmaj @ dtu dk
eyal ronen @ cs tau ac il
steven yue @ sandboxquantum com
2023-09-20: revised
2023-05-25: received
See all versions
Short URL
Creative Commons Attribution


      author = {Carlos Aguilar-Melchor and Andreas Hülsing and David Joseph and Christian Majenz and Eyal Ronen and Dongze Yue},
      title = {SDitH in the QROM},
      howpublished = {Cryptology ePrint Archive, Paper 2023/756},
      year = {2023},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.