SOFIA: MQ-based signatures in the QROM.

We propose SOFIA, the first \(\mathcal {MQ}\)-based signature scheme provably secure in the quantum-accessible random oracle model (QROM). Our construction relies on an extended version of Unruh’s transform for 5-pass identification schemes that we describe and prove secure both in the ROM and QROM.