On the equivalence of two post-quantum cryptographic families
Fuente:
arXiv
Saved in:
| Main Authors: | , , |
|---|---|
| Format: | Preprint |
| Published: |
2021
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866929548210208768 |
|---|---|
| author | Meneghetti, Alessio Pellegrini, Alex Sala, Massimiliano |
| author_facet | Meneghetti, Alessio Pellegrini, Alex Sala, Massimiliano |
| contents | The Maximum Likelihood Decoding Problem (MLD) is known to be NP-hard and its complexity is strictly related to the security of some post-quantum cryptosystems, that is, the so-called code-based primitives. Analogously, the Multivariate Quadratic System Problem (MQ) is NP-hard and its complexity is necessary for the security of the so-called multivariate-based primitives. In this paper we present a closed formula for a polynomial-time reduction from any instance of MLD to an instance of MQ, and viceversa. We also show a polynomial-time isomorphism between MQ and MLD, thus demonstrating the direct link between the two post-quantum cryptographic families. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2109_05806 |
| institution | arXiv |
| publishDate | 2021 |
| record_format | arxiv |
| spellingShingle | On the equivalence of two post-quantum cryptographic families Meneghetti, Alessio Pellegrini, Alex Sala, Massimiliano Computational Complexity Discrete Mathematics The Maximum Likelihood Decoding Problem (MLD) is known to be NP-hard and its complexity is strictly related to the security of some post-quantum cryptosystems, that is, the so-called code-based primitives. Analogously, the Multivariate Quadratic System Problem (MQ) is NP-hard and its complexity is necessary for the security of the so-called multivariate-based primitives. In this paper we present a closed formula for a polynomial-time reduction from any instance of MLD to an instance of MQ, and viceversa. We also show a polynomial-time isomorphism between MQ and MLD, thus demonstrating the direct link between the two post-quantum cryptographic families. |
| title | On the equivalence of two post-quantum cryptographic families |
| topic | Computational Complexity Discrete Mathematics |
| url | https://arxiv.org/abs/2109.05806 |