Representations of Elementary Vectors in VOLE-in-the-head-based Schemes

Tung Chou

Paper 2025/1336

Representations of Elementary Vectors in VOLE-in-the-head-based Schemes

Tung Chou

, Academia Sinica

Abstract

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%.

Metadata

Available format(s): PDF
Category: Public-key cryptography
Publication info: Preprint.
Keywords: post-quantum signature schemes VOLE-in-the-head regular syndrome decoding permuted kernel problem
Contact author(s): blueprint @ crypto tw
History: 2025-07-22: approved; 2025-07-22: received; See all versions
Short URL: https://ia.cr/2025/1336
License: CC BY

BibTeX

@misc{cryptoeprint:2025/1336,
      author = {Tung Chou},
      title = {Representations of Elementary Vectors in {VOLE}-in-the-head-based Schemes},
      howpublished = {Cryptology {ePrint} Archive, Paper 2025/1336},
      year = {2025},
      url = {https://eprint.iacr.org/2025/1336}
}