Paper 2024/465
Shorter VOLEitH Signature from Multivariate Quadratic
Abstract
VOLE-in-the-head paradigm recently introduced by Baum et al. (Crypto 2023) allows transforming zero-knowledge protocols in the designated verifier setting into public-coin protocols, which can be made non-interactive and publicly verifiable. Our transformation applies to a large class of ZK protocols based on vector oblivious linear evaluation (VOLE) and leads to resulting ZK protocols that have linear proof size and are simpler, smaller, and faster than related approaches based on MPC-in-the-head. We propose a new candidate post-quantum signature scheme from the Multivariate Quadratic(MQ) problem based on a new protocol for the VOLE-in-the-head paradigm, which significantly reduces the signature size compared to previous works. We achieve a signature size of 2.5KB for a 128-bit security level. Compared to the state-of-the-art MQ-based signature schemes, our signature scheme achieves a factor from 3 to 4 improvement in terms of the signature size while keeping the computational efficiency competitive
Metadata
- Available format(s)
- Category
- Cryptographic protocols
- Publication info
- Preprint.
- Keywords
- Code-based cryptographyDesign of Symmetric PrimitivesPost-Quantum CryptographySignature Schemes
- Contact author(s)
- bui @ irif fr
- History
- 2024-03-22: approved
- 2024-03-19: received
- See all versions
- Short URL
- https://ia.cr/2024/465
- License
-
CC BY
BibTeX
@misc{cryptoeprint:2024/465, author = {Dung Bui}, title = {Shorter VOLEitH Signature from Multivariate Quadratic}, howpublished = {Cryptology ePrint Archive, Paper 2024/465}, year = {2024}, note = {\url{https://eprint.iacr.org/2024/465}}, url = {https://eprint.iacr.org/2024/465} }