Paper 2026/557

On Post-Quantum Signature with Message Recovery from Hash-and-Sign in QROM

Abstract

Post-quantum signatures have been suffering from their inefficiency compared to traditional signatures. To reduce space consumption, a promising approach is to design signature schemes with message recovery, which can embed part of the message into the signature without increasing its length. A notable example is the PSS-R signature scheme (probabilistic signature scheme with recovery) proposed by Bellare and Rogaway (EUROCRYPT 1996) in the classical ROM (random oracle model). However, there were few works considering post-quantum signature schemes with message recovery. In this work, we study the design of post-quantum signature scheme with message recovery in the QROM (quantum ROM). Specifically, we adapt the classic PSS-R signature scheme to the post-quantum setting and prove its security in the QROM. Our security proof is conceptually similar to the original proof of PSS-R, but faces challenges in QROM when we need to reprogram two random oracles with correlated inputs/outputs. To address these issues, we extend the tight adaptive reprogramming theorem (Grilo et al., ASIACRYPT 2021) and the measure-and-reprogram theorem (Don et al., CRYPTO 2020) to our setting, to support reprogramming two oracles successively, where the input to one oracle depends on the other oracle's output. With these extended proof techniques, we provide the first security proof of a PSS-R-like signature scheme with message recovery in the QROM.