Security analysis of ZKPoK based on MQ problem in the multi-instance setting
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...
Saved in:
| Main Authors: | , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
De Gruyter
2025-04-01
|
| Series: | Journal of Mathematical Cryptology |
| Subjects: | |
| Online Access: | https://doi.org/10.1515/jmc-2024-0046 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| Summary: | 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. |
|---|---|
| ISSN: | 1862-2984 |