Security analysis of ZKPoK based on MQ problem in the multi-instance setting

Abstract 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 <m:math xmlns:m="http://www.w3.org/1998/Math/MathML"> <m:msub> <m:mrow> <m:mi mathvariant="monospace">DiffMQ</m:mi> </m:mrow> <m:mrow> <m:mi mathvariant="normal">H</m:mi> </m:mrow> </m:msub> </m:math> {{\mathtt{DiffMQ}}}_{{\rm{H}}} . We present a new efficient probabilistic algorithm for solving the <m:math xmlns:m="http://www.w3.org/1998/Math/MathML"> <m:msub> <m:mrow> <m:mi mathvariant="monospace">DiffMQ</m:mi> </m:mrow> <m:mrow> <m:mi mathvariant="normal">H</m:mi> </m:mrow> </m:msub> </m:math> {{\mathtt{DiffMQ}}}_{{\rm{H}}} which is polynomial-time if <m:math xmlns:m="http://www.w3.org/1998/Math/MathML"> <m:mi>m</m:mi> <m:mo>−</m:mo> <m:mi>n</m:mi> <m:mo>∈</m:mo> <m:mi>O</m:mi> <m:mrow> <m:mo>(</m:mo> <m:mrow> <m:mn>1</m:mn> </m:mrow> <m:mo>)</m:mo> </m:mrow> </m:math> m-n\in O\left(1) . We also present experimental results showing that the algorithm is efficient in practice.