Paper 2024/465

Shorter VOLEitH Signature from Multivariate Quadratic

Abstract

The VOLE-in-the-Head paradigm, recently introduced by Baum et al. (Crypto 2023), is a compiler that uses SoftspokenOT (Crypto 2022) to transfer any VOLE-based designated verifier zero-knowledge protocol into a publicly verifiable zero-knowledge protocol. Together with the Fiat-Shamir transformation, a new digital signature scheme FAEST (faest.info) is proposed, and it outperforms all MPC-in-the-Head signatures. We propose a new candidate post-quantum signature scheme from the Multivariate Quadratic (MQ) problem in the VOLE-in-the-Head framework, which significantly reduces the signature size compared to previous works. We achieve a signature size ranging from 3.5KB to 6KB for the 128-bit security level. Compared to the state-of-the-art MQ-based signature schemes and existing VOLE-in-the-Head signatures, our scheme achieves the smallest signature size (1.5 to 2 times compared to MQ-based schemes) while keeping the computational efficiency competitive.