SDitH in the QROM

Carlos Aguilar-Melchor; Andreas Hülsing; David Joseph; Christian Majenz; Eyal Ronen; Dongze Yue

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

Abstract

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

Metadata

Available format(s): PDF
Category: Public-key cryptography
Publication info: A minor revision of an IACR publication in ASIACRYPT 2023
Keywords: Post-Quantum Cryptography Digital Signature Code-based Cryptography SDitH Fiat-Shamir QROM Extractable QROM QROM+
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
History: 2023-09-20: revised; 2023-05-25: received; See all versions
Short URL: https://ia.cr/2023/756
License: CC BY

BibTeX

@misc{cryptoeprint:2023/756,
      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},
      url = {https://eprint.iacr.org/2023/756}
}