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.
On the equivalence of two post-quantum cryptographic families / Meneghetti, A; Pellegrini, A; Sala, M. - In: ANNALI DI MATEMATICA PURA ED APPLICATA. - ISSN 0373-3114. - 2023, 202:2(2023), pp. 967-991. [10.1007/s10231-022-01267-x]
On the equivalence of two post-quantum cryptographic families
Meneghetti, A
;Sala, M
2023-01-01
Abstract
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.| File | Dimensione | Formato | |
|---|---|---|---|
|
s10231-022-01267-x.pdf
accesso aperto
Descrizione: articolo
Tipologia:
Versione editoriale (Publisher’s layout)
Licenza:
Creative commons
Dimensione
2.11 MB
Formato
Adobe PDF
|
2.11 MB | Adobe PDF | Visualizza/Apri |
I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione
