1. On the equivalence of two post-quantum cryptographic families.
- Author
-
Meneghetti, Alessio, Pellegrini, Alex, and Sala, Massimiliano
- 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. [ABSTRACT FROM AUTHOR]
- Published
- 2023
- Full Text
- View/download PDF