Shorter keys for PEP-based cryptosystems through efficient representation of self-orthogonal codes

On input two linear codes, the Permutation Equivalence Problem (PEP) asks to find a permutation mapping one of the two codes into the other one. Codes with large hull, which is the intersection of a code with its dual, make for hard instances of PEP and are used in post-quantum cryptography. Codes with maximum hull, hence contained in their dual, are called self-orthogonal. In this paper, we propose a technique to compress the representation of self-orthogonal codes, taking advantage of the pairwise orthogonality of their codewords. The representation we propose is shown to be asymptotically optimal in terms of communication cost; furthermore, it comes with polynomial time compression and decompression algorithms. This technique is useful for reducing the public key size in cryptographic schemes based on PEP, such as the updatable public key encryption scheme recently proposed by Albrecht, Benčina and Lai, the SPECK signature scheme and instances of the LESS signature scheme that are based on PEP. Remarkably, for the two latter schemes, this nearly halves the public key size.