From 5-Pass $$\mathcal {MQ}$$-Based Identification to $$\mathcal {MQ}$$-Based Signatures

摘要: This paper presents MQDSS, the first signature scheme with a security reduction based on problem of solving multivariate system quadratic equations $$\mathcal {MQ}$$ problem. In order to construct this we give new for Fiat-Shamir transform from large class 5-pass identification schemes and show that previous attempt literature obtain such proof does not achieve desired goal. We concrete parameters MQDSS provide detailed analysis showing resulting instantiation MQDSS-31-64 achieves 128 bits post-quantum security. Finally, describe an optimized implementation recent Intel processors full protection against timing attacks report benchmarks implementation.