An Efficient MQ-based Signature with Tight Security Proof

Hiroki Furue, Dung Hoang Duong, Tsuyoshi Takagi


At PKC 2018, Chen et al. proposed SOFIA, the first MQ-based digital signature scheme having tight security in the quantum random oracle model (QROM). SOFIA is constructed by applying an extended version of the Unruh transform (EUROCRYPT 2015) to the mathcal MQ-based 5-pass identification scheme (IDS) proposed by Sakumoto et al. (CRYPTO 2011). In this paper, we propose an MQ-based 3-pass IDS with impersonation probability of 1/2 and apply the original version of the Unruh transform to it to obtain a more efficient MQ-based digital signature scheme tightly secure in the QROM. The signature size of our digital signature scheme decreases by about 35% compared with SOFIA in the level I of NIST PQC security category, and is supposed to be the shortest among that of MQ-based signatures tightly secure in the QROM.


Post-quantum cryptography; Multivariate public key cryptography; Identification scheme; QROM; Unruh transform

Full Text:



  • There are currently no refbacks.