International Association for Cryptologic Research

International Association
for Cryptologic Research


Publicly Verifiable Zero-Knowledge and Post-Quantum Signatures From VOLE-in-the-Head

Carsten Baum , Technical University of Denmark
Lennart Braun , Aarhus University
Cyprien Delpech de Saint Guilhem , imec-COSIC KU Leuven
Michael Klooß , Karlsruhe Institute of Technology
Emmanuela Orsini , Bocconi University
Lawrence Roy , Aarhus University
Peter Scholl , Aarhus University
DOI: 10.1007/978-3-031-38554-4_19 (login may be required)
Search ePrint
Search Google
Presentation: Slides
Conference: CRYPTO 2023
Abstract: We present a new method for 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 oblivious transfer. In particular, we show that it can be applied to recent, fast protocols based on vector oblivious linear evaluation (VOLE), with a technique we call VOLE-in-the-head, upgrading these protocols to support public verifiability. Our resulting ZK protocols have linear proof size, and are simpler, smaller and faster than related approaches based on MPC-in-the-head. To build VOLE-in-the-head while supporting both binary circuits and large finite fields, we develop several new technical tools. One of these is a new proof of security for the SoftSpokenOT protocol (Crypto 2022), which generalizes it to produce certain types of VOLE correlations over large fields. Secondly, we present a new ZK protocol that is tailored to take advantage of this form of VOLE, which leads to a publicly verifiable VOLE-in-the-head protocol with only 2x more communication than the best, designated-verifier VOLE-based protocols. We analyze the soundness of our approach when made non-interactive using the Fiat-Shamir transform, using round-by-round soundness. As an application of the resulting NIZK, we present FAEST, a post-quantum signature scheme based on AES. FAEST is the first AES-based signature scheme to be smaller than SPHINCS+, with signature sizes between 5.6 and 6.6kB at the 128-bit security level. Compared with the smallest version of SPHINCS+ (7.9kB), FAEST verification is slower, but the signing times are between 8x and 40x faster.
  title={Publicly Verifiable Zero-Knowledge and Post-Quantum Signatures From VOLE-in-the-Head},
  author={Carsten Baum and Lennart Braun and Cyprien Delpech de Saint Guilhem and Michael Klooß and Emmanuela Orsini and Lawrence Roy and Peter Scholl},