Violetta Weger

Michele Battagliola, Anna-Lena Horlemann, Abhinaba Mazumder et al.

Given two linear codes, the Linear Equivalence Problem (LEP) asks to find (if it exists) a linear isometry between them; as a special case, we have the Permutation Equivalence Problem (PEP), in which isometries must be permutations. LEP and PEP have recently gained renewed interest as the security foundations for several post-quantum schemes, including LESS. A recent paper has introduced the use of the Schur product to solve PEP, identifying many new easy-to-solve instances. In this paper, we extend this result to LEP. In particular, we generalize the approach and rely on the more general notion of power codes. Combining it with Frobenius automorphisms and Hermitian hulls, we identify many classes of easy LEP instances. To the best of our knowledge, this is the first work exploiting algebraic weaknesses for LEP. Finally we show an improved reduction to PEP whenever the coefficients of the monomial matrix are in a subgroup of the multiplicative group of the finite field.

Andreas Pyka, Violetta Weger

The homogeneous metric can be viewed as a natural extension of the Hamming metric to finite chain rings. It distinguishes between three types of elements: zero, non-zero elements in the socle, and elements outside the socle. Since the Singleton bound is one of the most fundamental and widely studied bounds in classical coding theory, we investigate its analogue for codes over finite chain rings equipped with the homogeneous metric. We provide a complete characterization of Maximum Homogeneous Distance (MHD) codes, showing that MHD codes coincide with lifted MDS codes and are contained within the socle at low rank. Exceptions arise from exceptional MDS codes or single-parity-check codes. We then shift our focus to the Plotkin-type bound in the homogeneous metric and close an existing gap in the theory of constant homogeneous-weight codes by identifying those of minimal length.

Luana Kurmann, Svenja Lage, Violetta Weger

In this paper we present an attack on a recently proposed code-based Private Information Retrieval (PIR) scheme. Indeed, the server can retrieve the index of the desired file with high probability in polynomial time. The attack relies on the fact that random codes over finite rings are free with high probability and that the dimension of the rowspan of the query matrix decreases when the rows corresponding to the desired index are removed.

Violetta Weger, Niklas Gassner, Joachim Rosenthal

The improvements on quantum technology are threatening our daily cybersecurity, as a capable quantum computer can break all currently employed asymmetric cryptosystems. In preparation for the quantum-era the National Institute of Standards and Technology (NIST) has initiated in 2016 a standardization process for public-key encryption (PKE) schemes, key-encapsulation mechanisms (KEM) and digital signature schemes. In 2023, NIST made an additional call for post-quantum signatures. With this chapter we aim at providing a survey on code-based cryptography, focusing on PKEs and signature schemes. We cover the main frameworks introduced in code-based cryptography and analyze their security assumptions. We provide the mathematical background in a lecture notes style, with the intention of reaching a wider audience.

Marco Baldi, Massimo Battaglioni, Franco Chiaraluce et al.

In this paper we introduce a variant of the Syndrome Decoding Problem (SDP), that we call Restricted SDP (R-SDP), in which the entries of the searched vector are defined over a subset of the underlying finite field. We prove the NP-completeness of R-SDP, via a reduction from the classical SDP, and describe algorithms which solve such new problem. We study the properties of random codes under this new decoding perspective, in the fashion of traditional coding theory results, and assess the complexity of solving a random R-SDP instance. As a concrete application, we describe how Zero-Knowledge Identification (ZK-ID) schemes based on SDP can be tweaked to rely on R-SDP, and show that this leads to compact public keys as well as significantly reduced communication costs. Thus, these schemes offer an improved basis for the construction of code-based digital signature schemes derived from identification schemes through the well-know Fiat-Shamir transformation.

Violetta Weger, Karan Khathuria, Anna-Lena Horlemann et al.

In this paper we study the hardness of the syndrome decoding problem over finite rings endowed with the Lee metric. We first prove that the decisional version of the problem is NP-complete, by a reduction from the $3$-dimensional matching problem. Then, we study the complexity of solving the problem, by translating the best known solvers in the Hamming metric over finite fields to the Lee metric over finite rings, as well as proposing some novel solutions. For the analyzed algorithms, we assess the computational complexity in the asymptotic regime and compare it to the corresponding algorithms in the Hamming metric.

Violetta Weger, Massimo Battaglioni, Paolo Santini et al.

Information set decoding (ISD) algorithms are the best known procedures to solve the decoding problem for general linear codes. These algorithms are hence used for codes without a visible structure, or for which efficient decoders exploiting the code structure are not known. Classically, ISD algorithms have been studied for codes in the Hamming metric. In this paper we switch from the Hamming metric to the Lee metric, and study ISD algorithms and their complexity for codes measured with the Lee metric over finite rings.

Karan Khathuria, Joachim Rosenthal, Violetta Weger

We present a code-based public-key cryptosystem, in which we use Reed-Solomon codes over an extension field as secret codes and disguise it by considering its shortened expanded code over the base field. Considering shortened expanded codes provides a safeguard against distinguisher attacks based on the Schur product. Moreover, without using a cyclic or a quasi-cyclic structure we obtain a key size reduction of nearly $45 \%$ compared to the classic McEliece cryptosystem proposed by Bernstein et al.

Anna-Lena Horlemann-Trautmann, Violetta Weger

We convert Stern's information set decoding (ISD) algorithm to the ring $\mathbb{Z}/4 \mathbb{Z}$ equipped with the Lee metric. Moreover, we set up the general framework for a McEliece and a Niederreiter cryptosystem over this ring. The complexity of the ISD algorithm determines the minimum key size in these cryptosystems for a given security level. We show that using Lee metric codes can drastically decrease the key size, compared to Hamming metric codes. In the end we explain how our results can be generalized to other Galois rings $\mathbb{Z}/p^s\mathbb{Z}$.

Carmelo Interlando, Karan Khathuria, Nicole Rohrer et al.

In this paper we generalize the Ball-Collision Algorithm by Bernstein, Lange, Peters from the binary field to a general finite field. We also provide a complexity analysis and compare the asymptotic complexity to other generalized information set decoding algorithms.

Karan Khathuria, Giacomo Micheli, Violetta Weger

In this paper we show that the $\mathbb Z/p^{m}\mathbb Z$-module structure of the ring $E_p^{(m)}$ is isomorphic to a $\mathbb Z/p^{m}\mathbb Z$-submodule of the matrix ring over $\mathbb Z/p^{m}\mathbb Z$. Using this intrinsic structure of $E_p^{(m)}$, solving a linear system over $E_p^{(m)}$ becomes computationally equivalent to solving a linear system over $\mathbb Z/p^{m}\mathbb Z$. As an application we break the protocol based on the Diffie-Hellman Decomposition problem and ElGamal Decomposition problem over $E_p^{(m)}$. Our algorithm terminates in a provable running time of $O(m^{6})$ $\mathbb Z/p^{m}\mathbb Z$-operations.