Speaker
Description
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 large hull such as self-orthogonal codes, i.e., codes contained in their dual.
Due to the need of representing such codes, whose communication cost grows quadratically with their length, such cryptosystems suffer from large public keys.
We present an efficient compression technique that allows to represent self-orthogonal codes with fewer bits, taking advantage of the pairwise orthogonality of their codewords.
Among the cryptosystems that benefit from this work there are SPECK, LESS (and its threshold variant LEAST), which is a candidate in the ongoing NIST standardization process, and the updatable public key encryption scheme proposed by Albrecht, Benčina and Lai, which is based on a special instance of the Lattice Isomorphism Problem (LIP).
Remarkably, the compression technique nearly halves the public key for the former two schemes.