Search

The security of a broad family of coding‐based cryptographic techniques relies on the hardness of the Syndrome Decoding Problem (SDP). In this problem, the aim is to find a word with a given syndrome and of Hamming weight smaller than a prefixed bound. If this last condition is replaced by "of minimum weight," then we have the Coset Leader Problem (CLP), being Finding Low Weight Codewords (FLWC) a particular case (when the zero syndrome is considered). An algorithm that has been proposed in order to obtain approximate solutions of problems of these kind (NP‐complete) is the Quantum Approximate Optimization Algorithm (QAOA), a variational hybrid quantum‐classical algorithm. In this paper, we apply the QAOA to the CLP for binary linear codes. We model the problem, make the theoretical analysis the case of the first level, and introduce some experiments to test its performance. The experiments have been carried out on quantum computer simulators with codes of different lengths and QAOA of different depth. [ABSTRACT FROM AUTHOR]

The standard description of a quantum algorithm consists in three steps. First, encoding the data in a suitable initial quantum state. Second, driving such a state by a convenient sequence of unitary transformations until a final quantum state is reached. Third, measuring the final state and use such a measurement to solve the problem the quantum algorithm was designed for. An alternative description is provided by the stabilizer formalism, which was originally introduced in connection with quantum error correcting codes. In this paradigm, the focus is on the subgroup of elements of the Pauli group stabilizing the initial quantum state, and the transformations that such a subgroup experiments along the algorithm. In this work, we provide an explanation of two foundational quantum algorithms (Bernstein‐Vazinari and Deustch‐Josza) based on such a quantum stabilizer formalism. Doing so, we provide a better understanding and insight into both procedures which yield to see Bernstein‐Vazirani as a particular case of Deustch‐Josza, and to introduce a generalized version of Deustch‐Josza algorithm. [ABSTRACT FROM AUTHOR]

Symplectic finite semifields can be used to construct nonlinear binary codes of Kerdock type (i.e., with the same parameters of the Kerdock codes, a subclass of Delsarte–Goethals codes). In this paper, we introduce nonbinary Delsarte–Goethals codes of parameters (qm+1, qm(r+2)+2, q−1/q (qm+1 − qm+1/2 + r)) over a Galois field of order q = 2l, for all 0 ≤ r ≤ m−1/2, with m ≥ 3 odd, and show the connection of this construction to finite semifields. [ABSTRACT FROM AUTHOR]

In 1985, Gabidulin introduced the rank metric in coding theory over finite fields, and used this kind of codes in a McEliece cryptosystem, six years later. In this paper, we consider rank metric codes over Galois rings. We propose a suitable metric for codes over such rings, and show its main properties. With this metric, we define Gabidulin codes over Galois rings, propose an efficient decoding algorithm for them, and hint their cryptographic application. [ABSTRACT FROM AUTHOR]

In Goppa (1970), V. D. Goppa presents a new family of linear codes over finite fields. This family, now known as Goppa codes, has been studied for nearly 50 years, including efficient decoding algorithms (Patterson, 1975) and its applications in cryptography (McEliece, 1978). Moreover, in Andrade et al. (2005), de Andrade and Palazzo present a generalization of Goppa codes to finite rings. Motivated by cryptographic applications, in this article we focus on Goppa codes over Z ∕ 4 Z and study some of their properties. [ABSTRACT FROM AUTHOR]