International Association
for Cryptologic Research

This paper presents a family of representations of elementary vectors, which covers existing representations as special cases. We make use of the family of representations to reduce signature size of existing signature schemes based on the VOLE-in-the-head framework. In particular, we use new representations to build modelings for the regular syndrome decoding problem in $\mathbb{F}_2$, which is used in the post-quantum signature scheme SDith, and for the permuted kernel problem in characteristic-2 fields, which is used in a post-quantum signature scheme recently proposed by Bettaieb, Bidoux, Gaborit, and Kulkarni. For the “short” parameter sets of SDith, which are designed for minimiz- ing signature size, we achieve a size reduction of 3.6% to 4.2%. For parameter sets of the Bettaieb-Bidoux-Gaborit-Kulkarni signature scheme, we achieve a size reduction of 9% to 12%.