Search

Freiman's $3k-4$ Theorem states that if a subset $A$ of $k$ integers has a Minkowski sum $A+A$ of size at most $3k-4$, then it must be contained in a short arithmetic progression. We prove a function field analogue that is also a generalisation: it states that if $K$ is a perfect field and if $S\supset K$ is a vector space of dimension $k$ inside an extension $F/K$ in which~$K$ is algebraically closed, and if the $K$-vector space generated by all products of pairs of elements of $S$ has dimension at most $3k-4$, then $K(S)$ is a function field of small genus, and $S$ is of small codimension inside a Riemann-Roch space of $K(S)$.

Given a fixpoint of a substitution, the associated Dumont-Thomas numeration system provides a convenient immediate way to describe the fixpoint as an automatic sequence. In order to study first-order properties of these fixpoints using B\"uchi-Bruy\`ere characterization, it is necessary for the numeration system to be addable. This means that its addition relation must be computable by a finite automaton. Dumont-Thomas numeration systems can be regarded as an extension of positional numeration systems with states where the greediness is state-dependent. We introduce sequence automata as a tool to extend the results of Bruy\`ere-Hansel and Frougny-Solomyak on the regularity of the addition of Bertrand numeration systems to the case of Dumont-Thomas numeration systems related to some Pisot number. We present a practical implementation of the addition compatible with the Walnut computation tool, along with some experimental results.

The McEliece scheme is a generic frame which allows to use any error correcting code of which there exists an efficient decoding algorithm to design an encryption scheme by hiding the generator matrix code. Similarly, the Niederreiter frame is the dual version of the McEliece scheme, and achieves smaller ciphertexts. We propose a generalization of the McEliece frame and the Niederreiter frame to matrix codes and the MinRank problem, that we apply to Gabidulin matrix codes (Gabidulin rank codes considered as matrix codes). The masking we consider consists in starting from a rank code C, to consider a matrix version of C and to concatenate a certain number of rows and columns to the matrix codes version of the rank code C and then apply to an isometry for matric codes. The security of the schemes relies on the MinRank problem to decrypt a ciphertext, and the structural security of the scheme relies on a new problem EGMC-Indistinguishability problem that we introduce and that we study in detail. The main structural attack that we propose consists in trying to recover the masked linearity over the extension field which is lost during the masking process. Overall, starting from Gabidulin codes we obtain a very appealing tradeoff between the size of ciphertext and the size of the public key. For 128b of security we propose parameters ranging from ciphertext of size 65 B (and public keys of size 98 kB) to ciphertext of size 138B (and public key of size 41 kB). Our new approach permits to achieve better trade-off between ciphertexts and public key than the classical McEliece scheme. Our new approach permits to obtain an alternative scheme to the classic McEliece scheme, to obtain very small ciphertexts, with moreover smaller public keys than in the classic McEliece scheme. For 256 bits of security, we can obtain ciphertext as low as 119B, or public key as low as 87kB.

We bring in here a novel algebraic approach for attacking the McEliece cryptosystem. It consists in introducing a subspace of matrices representing quadratic forms. Those are associated with quadratic relationships for the component-wise product in the dual of the code used in the cryptosystem. Depending on the characteristic of the code field, this space of matrices consists only of symmetric matrices or skew-symmetric matrices. This matrix space is shown to contain unusually low-rank matrices (rank $2$ or $3$ depending on the characteristic) which reveal the secret polynomial structure of the code. Finding such matrices can then be used to recover the secret key of the scheme. We devise a dedicated approach in characteristic $2$ consisting in using a Gr\"obner basis modeling that a skew-symmetric matrix is of rank $2$. This allows to analyze the complexity of solving the corresponding algebraic system with Gr\"obner bases techniques. This computation behaves differently when applied to the skew-symmetric matrix space associated with a random code rather than with a Goppa or an alternant code. This gives a distinguisher of the latter code family. We give a bound on its complexity which turns out to interpolate nicely between polynomial and exponential depending on the code parameters. A distinguisher for alternant/Goppa codes was already known [FGO+11]. It is of polynomial complexity but works only in a narrow parameter regime. This new distinguisher is also polynomial for the parameter regime necessary for [FGO+11] but contrarily to the previous one is able to operate for virtually all code parameters relevant to cryptography. Moreover, we use this matrix space to find a polynomial time attack of the McEliece cryptosystem provided that the Goppa code is distinguishable by the method of [FGO+11] and its degree is less than $q-1$, where $q$ is the alphabet size of the code., Comment: 68 pages

Secure computation often benefits from the use of correlated randomness to achieve fast, non-cryptographic online protocols. A recent paradigm put forth by Boyle $\textit{et al.}$ (CCS 2018, Crypto 2019) showed how pseudorandom correlation generators (PCG) can be used to generate large amounts of useful forms of correlated (pseudo)randomness, using minimal interactions followed solely by local computations, yielding silent secure two-party computation protocols (protocols where the preprocessing phase requires almost no communication). An additional property called programmability allows to extend this to build N-party protocols. However, known constructions for programmable PCG's can only produce OLE's over large fields, and use rather new splittable Ring-LPN assumption. In this work, we overcome both limitations. To this end, we introduce the quasi-abelian syndrome decoding problem (QA-SD), a family of assumptions which generalises the well-established quasi-cyclic syndrome decoding assumption. Building upon QA-SD, we construct new programmable PCG's for OLE's over any field $\mathbb{F}_q$ with $q>2$. Our analysis also sheds light on the security of the ring-LPN assumption used in Boyle $\textit{et al.}$ (Crypto 2020). Using our new PCG's, we obtain the first efficient N-party silent secure computation protocols for computing general arithmetic circuit over $\mathbb{F}_q$ for any $q>2$., Comment: This is a long version of a paper accepted at CRYPTO'23

In this article, we discuss the decoding of Gabidulin and related codes from a cryptographic point of view, and we observe that these codes can be decoded solely from the knowledge of a generator matrix. We then extend and revisit Gibson and Overbeck attacks on the generalized GPT encryption scheme (instantiated with the Gabidulin code) for different ranks of the distortion matrix. We apply our attack to the case of an instantiation with twisted Gabidulin codes.

These lecture notes have been written for a course at the Algebraic Coding Theory (ACT) summer school 2022 that took place in the university of Zurich. The objective of the course propose an in-depth presentation of the proof of one of the most striking results of coding theory: Tsfasman Vl\u{a}du\c{t} Zink Theorem, which asserts that for some prime power $q$, there exist sequences of codes over $\mathbb{F}_q$ whose asymptotic parameters beat random codes., Comment: Lecture notes for a course given at the Algebraic Coding Theory (ACT) summer school 2022

We consider the decoding of rank metric codes assuming the error matrix is symmetric. We prove two results. First, for rates $<1/2$ there exists a broad family of rank metric codes for which any symmetric error pattern, even of maximal rank can be corrected. Moreover, the corresponding family of decodable codes includes Gabidulin codes of rate $<1/2$. Second, for rates $>1/2$, we propose a decoder for Gabidulin codes correcting symmetric errors of rank up to $n-k$. The two mentioned decoders are deterministic and worst case.

In 1874 Brill and Noether designed a seminal geometric method for computing bases of Riemann-Roch spaces. From then, their method has led to several algorithms, some of them being implemented in computer algebra systems. The usual proofs often rely on abstract concepts of algebraic geometry and commutative algebra. In this paper we present a short self-contained and elementary proof that mostly needs Newton polygons, Hensel lifting, bivariate resultants, and Chinese remaindering., Comment: Final version

It is a long standing open problem to find search to decision reductions for structured versions of the decoding problem of linear codes. Such results in the lattice-based setting have been carried out using number fields: Polynomial-LWE, Ring-LWE, Module-LWE and so on. We propose a function field version of the LWE problem. This new framework leads to another point of view on structured codes, e.g. quasi-cyclic codes, strengthening the connection between lattice-based and code-based cryptography. In particular, we obtain the first search to decision reduction for structured codes. Following the historical constructions in lattice-based cryptography, we instantiate our construction with function fields analogues of cyclotomic fields, namely Carlitz extensions, leading to search to decision reductions on various versions of Ring-LPN, which have applications to secure multi party computation and to an authentication protocol.

We demonstrate that the matrix quantum group $SL_q(2)$ gives rise to nontrivial matrix product operator representations of the Lie group $SL(2)$, providing an explicit characterization of the nontrivial global $SU(2)$ symmetry of the XXZ model with periodic boundary conditions. The matrix product operators are non-injective and their set is closed under multiplication. This allows to calculate the fusion tensors acting on the virtual or quantum degrees of freedom and to obtain the recoupling coefficients, which satisfy a type of pentagon relation. We argue that the combination of this data with the well known $q$-deformed Clebsch-Gordan coefficients and 6j-symbols is consistent with a description of this quantum group in terms of bimodule categories., Comment: 5+3 pages, comments invited

We discuss the decoding of Gabidulin and interleaved Gabidulin codes. We give the full presentation of a decoding algorithm for Gabidulin codes, which as Loidreau's seminal algorithm consists in localizing errors in the spirit of Berlekamp-Welch algorithm for Reed-Solomon codes. On the other hand, this algorithm consists in acting on codewords on the right while Loidreau's algorithm considers an action on the left. This right-hand side decoder was already introduced by the authors in a previous work for cryptanalytic applications. We give here a generalised version which applies to the case of non-full length Gabidulin codes. Finally, we show that this algorithm turns out to provide a very clear and natural approach for the decoding of interleaved Gabidulin codes., Comment: 10 pages, Accepted at the conference WCC 2022

This note completes a talk given at the conference Curves over Finite Fields: past, present and future celebrating the publication the book {\em Rational Points on Curves over Finite Fields by J.-P. Serre and organised at Centro de ciencias de Benasque in june 2021. It discusses a part of the history of algebraic geometry codes together with some of their recent applications. A particular focus is done on the "multiplicative" structure of these codes, i.e. their behaviour with respect to the component wise product. Some open questions are raised and discussed.

This article discusses the decoding of Gabidulin codes and shows how to extend the usual decoder to any supercode of a Gabidulin code at the cost of a significant decrease of the decoding radius. Using this decoder, we provide polynomial time attacks on the rank-metric encryption schemes RAMESSES and LIGA., Comment: PQCrypto 2021. The Sage code is available on Github: https://github.com/mbombar/Attack_on_LIGA

Extended Affine (EA) equivalence is the equivalence relation between two vectorial Boolean functions $F$ and $G$ such that there exist two affine permutations $A$, $B$, and an affine function $C$ satisfying $G = A \circ F \circ B + C$. While the problem has a simple formulation, it is very difficult in practice to test whether two functions are EA-equivalent. This problem has two variants: {\em EA-partitioning} deals with partitioning a set of functions into disjoint EA-equivalence classes, and \emph{EA-recovery} is about recovering the tuple $(A,B,C)$ if it exists. In this paper, we present a new algorithm that efficiently solves the EA-recovery problem for quadratic functions. Although its worst-case complexity occurs when dealing with APN functions, it supersedes, in terms of performance, all previously known algorithms for solving this problem for all quadratic functions and in any dimension, even in the case of APN functions. This approach is based on the Jacobian matrix of the functions, a tool whose study in this context can be of independent interest. The best approach for EA-partitioning in practice mainly relies on class invariants. We provide an overview of the known invariants along with a new one based on the \emph{ortho-derivative}. This new invariant is applicable to quadratic APN functions, a specific type of functions that is of great interest, and of which tens of thousands need to be sorted into distinct EA-classes. Our ortho-derivative-based invariant is very fast to compute, and it practically always distinguishes between EA-inequivalent quadratic APN functions.

In the recent years, the notion of rank metric in the context of coding theory has known many interesting developments in terms of applications such as space time coding, network coding or public key cryptography. These applications raised the interest of the community for theoretical properties of this type of codes, such as the hardness of decoding in rank metric. Among classical problems associated to codes for a given metric, the notion of code equivalence (to decide if two codes are isometric) has always been of the greatest interest, for its cryptographic applications or its deep connexions to the graph isomorphism problem. In this article, we discuss the hardness of the code equivalence problem in rank metric for $\mathbb{F}_{q^m}$-linear and general rank metric codes. In the $\mathbb{F}_{q^m}$-linear case, we reduce the underlying problem to another one called {\em Matrix Codes Right Equivalence Problem}. We prove the latter problem to be either in $\mathcal{P}$ or in $\mathcal{ZPP}$ depending of the ground field size. This is obtained by designing an algorithm whose principal routines are linear algebra and factoring polynomials over finite fields. It turns out that the most difficult instances involve codes with non trivial {\em stabilizer algebras}. The resolution of the latter case will involve tools related to finite dimensional algebras and Wedderburn--Artin theory. It is interesting to note that 30 years ago, an important trend in theoretical computer science consisted to design algorithms making effective major results of this theory. These algorithmic results turn out to be particularly useful in the present article. Finally, for general matrix codes, we prove that the equivalence problem (both left and right) is at least as hard as the well--studied {\em Monomial Equivalence Problem} for codes endowed with the Hamming metric.

This article discusses the security of McEliece-like encryption schemes using subspace subcodes of Reed-Solomon codes, i.e. subcodes of Reed-Solomon codes over $\mathbb{F}_{q^m}$ whose entries lie in a fixed collection of $\mathbb{F}_q$-subspaces of $\mathbb{F}_{q^m}$. These codes appear to be a natural generalisation of Goppa and alternant codes and provide a broader flexibility in designing code based encryption schemes. For the security analysis, we introduce a new operation on codes called the twisted product which yields a polynomial time distinguisher on such subspace subcodes as soon as the chosen $\mathbb{F}_q$-subspaces have dimension larger than $m/2$. From this distinguisher, we build an efficient attack which in particular breaks some parameters of a recent proposal due to Khathuria, Rosenthal and Weger.

This article surveys the development of the theory of algebraic geometry codes since their discovery in the late 70's. We summarize the major results on various problems such as: asymptotic parameters, improved estimates on the minimum distance, and decoding algorithms. In addition, we present various modern applications of these codes such as public-key cryptography, algebraic complexity theory, multiparty computation or distributed storage., Comment: Survey chapter to appear in "A Concise Encyclopedia of Coding Theory", W.C. Huffman, J.-L. Kim, and P. Sole' Eds., CRC Press

This paper extends the study of rank-metric codes in extension fields $\mathbb{L}$ equipped with an arbitrary Galois group $G = \mathrm{Gal}(\mathbb{L}/\mathbb{K})$. We propose a framework for studying these codes as subspaces of the group algebra $\mathbb{L}[G]$, and we relate this point of view with usual notions of rank-metric codes in $\mathbb{L}^N$ or in $\mathbb{K}^{N\times N}$, where $N = [\mathbb{L} : \mathbb{K}]$. We then adapt the notion of error-correcting pairs to this context, in order to provide a non-trivial decoding algorithm for these codes. We then focus on the case where $G$ is abelian, which leads us to see codewords as elements of a multivariate skew polynomial ring. We prove that we can bound the dimension of the vector space of zeroes of these polynomials, depending of their degree. This result can be seen as an analogue of Alon-F\"uredi theorem -- and by means, of Schwartz-Zippel lemma -- in the rank metric. Finally, we construct the counterparts of Reed-Muller codes in the rank metric, and we give their parameters. We also show the connection between these codes and classical Reed-Muller codes in the case where $\mathbb{L}$ is a Kummer extension., Comment: 26 pages, 1 figure

We introduce in this article a new method to estimate the minimum distance of codes from algebraic surfaces. This lower bound is generic, i.e. can be applied to any surface, and turns out to be ``liftable'' under finite morphisms, paving the way toward the construction of good codes from towers of surfaces. In the same direction, we establish a criterion for a surface with a fixed finite set of closed points $\mathcal P$ to have an infinite tower of $\ell$--\'etale covers in which $\mathcal P$ splits totally. We conclude by stating several open problems. In particular, we relate the existence of asymptotically good codes from general type surfaces with a very ample canonical class to the behaviour of their number of rational points with respect to their $K^2$ and coherent Euler characteristic., Comment: In memory of Gilles Lachaud. This article has been submitted with an appendix by Alexander Schmidt previously posted on ArXiv with reference arXiv:1702.03701

We present a new decoding algorithm based on error locating pairs and correcting an amount of errors exceeding half the minimum distance. When applied to Reed--Solomon or algebraic geometry codes, the algorithm is a reformulation of the so--called {\em power decoding} algorithm. Asymptotically, it corrects errors up to Sudan's radius. In addition, this new framework applies to any code benefiting from an error locating pair. Similarly to Pellikaan's and K\"otter's approach for unique algebraic decoding, our algorithm provides a unified point of view for decoding codes with an algebraic structure beyond the half minimum distance. It permits to get an abstract description of decoding using only codes and linear algebra and without involving the arithmetic of polynomial and rational function algebras used for the definition of the codes themselves. Such algorithms can be valuable for instance for cryptanalysis to construct a decoding algorithm of a code without having access to the hidden algebraic structure of the code.

DAGS scheme is a key encapsulation mechanism (KEM) based on quasi-dyadic alternant codes that was submitted to NIST standardization process for a quantum resistant public key algorithm. Recently an algebraic attack was devised by Barelli and Couvreur (Asiacrypt 2018) that efficiently recovers the private key. It shows that DAGS can be totally cryptanalysed by solving a system of bilinear polynomial equations. However, some sets of DAGS parameters were not broken in practice. In this paper we improve the algebraic attack by showing that the original approach was not optimal in terms of the ratio of the number of equations to the number of variables. Contrary to the common belief that reducing at any cost the number of variables in a polynomial system is always beneficial, we actually observed that, provided that the ratio is increased and up to a threshold, the solving can be heavily improved by adding variables to the polynomial system. This enables us to recover the private keys in a few seconds. Furthermore, our experimentations also show that the maximum degree reached during the computation of the Gr\"obner basis is an important parameter that explains the efficiency of the attack. Finally, the authors of DAGS updated the parameters to take into account the algebraic cryptanalysis of Barelli and Couvreur. In the present article, we propose a hybrid approach that performs an exhaustive search on some variables and computes a Gr\"obner basis on the polynomial system involving the remaining variables. We then show that the updated set of parameters corresponding to 128-bit security can be broken with 2^83 operations., Comment: 16 pages, accepted for publication in the 7th Code-Based Cryptography Workshop 2019

We construct algebraic geometric codes from del Pezzo surfaces and focus on the ones having Picard rank one and the codes associated to the anticanonical class. We give explicit constructions of del Pezzo surfaces of degree 4, 5 and 6, compute the parameters of the associated anticanonical codes and study their isomorphisms arising from the automorphisms of the surface. We obtain codes with excellent parameters and some of them turn out to beat the best known codes listed on the database codetable.

We present a polynomial time attack of a rank metric code based encryption scheme due to Loidreau for some parameters., Comment: Long version of an article accepted at the conference WCC 2019

The supersymmetric reformulation of physical observables in the Chalker-Coddington model (CC) for the plateau transition in the integer quantum Hall effect leads to a reformulation of its critical properties in terms of a 2D non-compact loop model or a 1D non-compact $gl(2|2)$ spin chain. Following a proposal by Ikhlef, Fendley and Cardy, we define and study a series of truncations of these loop models and spin chains, involving a finite and growing number of degrees of freedom per site. The case of the first truncation is solved analytically using the Bethe-ansatz. It is shown to exhibit many of the qualitative features expected for the untruncated theory, including a quadratic spectrum of exponents with a continuous component, and a normalizable ground state below that continuum. Quantitative properties are however at odds with the results of simulations on the CC model. Higher truncations are studied only numerically. While their properties are found to get closer to those of the CC model, it is not clear whether this is a genuine effect, or the result of strong finite-size corrections., Comment: 47 pages, 12 figures, v2: corrected affiliation

Percolation, a paradigmatic geometric system in various branches of physical sciences, is known to possess logarithmic factors in its correlators. Starting from its definition, as the $Q\rightarrow1$ limit of the $Q$-state Potts model with $S_Q$ symmetry, in terms of geometrical clusters, its operator content as $N$-cluster observables has been classified. We extensively simulate critical bond percolation in two and three dimensions and determine with high precision the $N$-cluster exponents and non-scalar features up to $N \! =\! 4$ (2D) and $N \! =\! 3$ (3D). The results are in excellent agreement with the predicted exact values in 2D, while such families of critical exponents have not been reported in 3D, to our knowledge. Finally, we demonstrate the validity of predictions about the logarithmic structure between the energy and two-cluster operators in 3D., Comment: 10 pages, 7 figures

We present a key recovery attack against Y. Wang's Random Linear Code Encryption (RLCE) scheme recently submitted to the NIST call for post-quantum cryptography. This attack recovers the secret key for all the short key parameters proposed by the author.

We present an efficient key recovery attack on code based encryption schemes using some quasi-dyadic alternant codes with extension degree 2. This attack permits to break the proposal DAGS recently submitted to NIST.