Security analysis of ZKPoK based on MQ problem in the multi-instance setting - Kahrobaei Delaram; Perret Ludovic; Vigorito Martina (Journal of Mathematical Cryptology)
Bidoux and Gaborit introduced a new general technique to improve zero-knowledge (ZK) proof-of-knowledge (PoK) schemes for a large set of well-known post-quantum hard computational problems such as the syndrome decoding, the permuted kernel, the rank syndrome decoding, and the multivariate quadratic (MQ) problems. In particular, the authors’ idea in the study of Bidoux and Gaborit was to use the structure of these problems in the multi-instance setting to minimize the communication complexity of the resulting ZK PoK schemes. The security of the new schemes is then related to new hard problems. In this article, we focus on the new multivariate-based ZK PoK and the corresponding new underlying problem: the so-called DiffMQH{{\mathtt{DiffMQ}}}_{{\rm{H}}}. We present a new efficient probabilistic algorithm for solving the DiffMQH{{\mathtt{DiffMQ}}}_{{\rm{H}}} which is polynomial-time if m−n∈O(1)m-n\in O\left(1). We also present experimental results showing that the algorithm is efficient in practice.