27th Conference of the International Linear Algebra Society (ILAS 2026)

Session

Code-based Cryptography

MS 14

May 20, 2026, 11:00 AM

Goodwin Hall 125

126. Decoding from the Other Side: Primal vs. Dual Attacks

Kévin Carrier (École Polytechnique (France))

5/20/26, 11:00 AM

Code-based Cryptography

Minisymposium Talk

The security of code-based cryptography relies fundamentally on the computational hardness of decoding random linear codes. Until recently, the most efficient known algorithms for the decoding problem were Information Set Decoding (ISD) algorithms, which we refer to as primal attacks in this presentation.

In 2001, a new class of decoding algorithms, known as dual attacks, was introduced and...

121. Post-Quantum Blind Signatures from Matrix Code Equivalence

Veronika Kuchta (Florida Atlantic University)

5/20/26, 11:25 AM

Code-based Cryptography

Minisymposium Talk

We construct a novel code-based blind signature scheme, using the Matrix Equivalence Digital Signature (MEDS) group action. The scheme is built using similar ideas to the Schnorr blind signature scheme and CSI-Otter, but uses additional public key and commitment information to overcome the difficulties that the MEDS group action faces: lack of module structure (present in Schnorr), lack of a...

178. Half is Enough: halving keys through optimal representation of self-orthogonal codes

Mr Rahmi El Mechri (Univeristà Politecnica delle Marche, Scuola IMT Alti Studi Lucca)

5/20/26, 11:50 AM

Code-based Cryptography

Minisymposium Talk

Given two linear codes, the Permutation Equivalence Problem (PEP) asks to find a permutation that maps one code onto the other.
The state-of-the-art solvers for PEP take time that is either exponential in the code length or in the dimension of the hull, which is the intersection between a code and its dual.
To avoid the latter type of attacks, PEP-based cryptosystems employ linear codes with...

200. Relative generalized Hamming weights and their applications in cryptography

Rodrigo San-José (Virginia Tech)

5/21/26, 11:00 AM

Code-based Cryptography

Minisymposium Talk

The relative generalized Hamming weights of a nested pair of linear codes are a generalization of the minimum distance. We will see how these parameters characterize the security of ramp secret sharing schemes, and how this can be adapted for private information retrieval. The computation of these parameters for a linear code is NP-hard in general, and we will study the most efficient current...

398. Code Rigidity in Characteristic 2

Adam Downs (Virginia Tech)

5/21/26, 11:25 AM

Code-based Cryptography

Minisymposium Talk

Two linear codes are equivalent if there exists a monomial matrix that transforms one to the other. The problem of finding a monomial transformation from one code to another underlies the Linear Equivalence Signature Scheme (LESS). An automorphism of a linear code is a monomial matrix which fixes the code. When a code has a large number of automorphisms, it is easier to solve the linear...

424. Sample Complexity of the Matrix Code Equivalence Problem

Wendi Gao

5/21/26, 11:50 AM

Code-based Cryptography

Minisymposium Talk

The Matrix Equivalence Digital Signature (MEDS) is a code-based digital signature that was submitted to the NIST call for quantum-resistant protocols. It is currently considered as a candidate for building advanced group action signatures schemes.

The hard problem behind this digital signature is the Matrix Code Equivalence problem. Namely, given two matrix codes $C_1$ and $C_2$, suppose...

459. Code-Based Arithmetic Circuits

Freeman Slaughter (University of South Florida)

5/22/26, 8:45 AM

Code-based Cryptography

Minisymposium Talk

Arithmetic circuits provide a versatile framework for demonstrating generic algebraic statements, expressible as a system of polynomials, in a zero-knowledge manner. While this primitive can be used to prove knowledge of solutions to NP-complete problems (graph 3-coloring, Sudoku, etc), existing implementations generally rely on discrete logarithm problem assumptions. In this talk, we...

466. Code distances: a new family of invariants of linear codes

Hiram López (Virginia Tech)

5/22/26, 9:10 AM

Code-based Cryptography

Minisymposium Talk

We introduce code distances, a new family of invariants for linear codes. We establish some properties and prove bounds on the code distances, and show that they are not invariants of the matroid (for a linear block code) or q-polymatroid (for a rank-metric code) associated to the code. By means of examples, we show that the code distances allow us to distinguish some inequivalent MDS or MRD...

473. An Elementary Analysis of Multivariate Goppa Codes

William Mahaney (Virginia Tech)

5/22/26, 9:35 AM

Code-based Cryptography

Minisymposium Talk

Goppa codes form a structured family of linear error-correcting codes introduced by Valery D. Goppa in 1970 and later interpreted within the framework of algebraic geometry as codes arising from algebraic curves over finite fields. Binary Goppa codes with irreducible Goppa polynomials are used in the Classic McEliece post-quantum key encapsulation mechanism (PQ-KEM), where their efficient...