[Resource Topic] 2024/465: Shorter VOLEitH Signature from Multivariate Quadratic

Welcome to the resource topic for 2024/465

Shorter VOLEitH Signature from Multivariate Quadratic

Authors: Dung Bui


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

ePrint: https://eprint.iacr.org/2024/465

See all topics related to this paper.

Feel free to post resources that are related to this paper below.

Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.

For more information, see the rules for Resource Topics .