Paper 2025/1436
VOLE-in-the-Head Signatures Based on the Linear Code Equivalence Problem
, Marche Polytechnic University, Marche Polytechnic University, University of Bari Aldo MoroAbstract
The Vector Oblivious Linear Evaluation in the Head (VOLEitH) paradigm has proven to be a versatile tool to design zero-knowledge proofs and signatures in post-quantum cryptography. In this paper, we propose three VOLE-friendly modellings for Proofs of Knowledge (PoK) of a solution of an instance of the Linear Code Equivalence Problem (LEP). For the first two schemes, we propose two new reductions from LEP to the Multivariate Quadratic (MQ) problem, that may be of independent interest for the cryptanalysis of LEP. Instead, the last model is obtained by generalizing a recent work by Bettaieb et al. to the context of monomial matrices instead of permutation matrices. While our proposed schemes exhibit larger signature sizes compared to LESS, they improve the computational efficiency, reducing the overall complexity from $O(n^3)$ to $O(n^2\log n )$ and $O(n^2\log^2 n )$, where $n$ is the length of the code.
Metadata
- Available format(s)
-
PDF
- Category
- Cryptographic protocols
- Publication info
- Published elsewhere. Minor revision. Cryptography and Communications
- DOI
- 10.1007/s12095-026-00869-z
- Keywords
- Code-Based CryptographyDigital SignaturesVOLE-in-the-HeadCode Equivalence Problem
- Contact author(s)
-
battagliola michele @ proton me
lauramttiuz @ gmail com
alessio meneghetti @ uniba it - History
- 2026-02-17: last of 3 revisions
- 2025-08-07: received
- See all versions
- Short URL
- https://ia.cr/2025/1436
- License
-
CC BY
BibTeX
@misc{cryptoeprint:2025/1436,
author = {Michele Battagliola and Laura Mattiuz and Alessio Meneghetti},
title = {{VOLE}-in-the-Head Signatures Based on the Linear Code Equivalence Problem},
howpublished = {Cryptology {ePrint} Archive, Paper 2025/1436},
year = {2025},
doi = {10.1007/s12095-026-00869-z},
url = {https://eprint.iacr.org/2025/1436}
}
