Paper 2023/996

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

Carsten Baum, Technical University of Denmark, Aarhus University
Lennart Braun, Aarhus University
Cyprien Delpech de Saint Guilhem, KU Leuven
Michael Klooß, Aalto University
Emmanuela Orsini, Bocconi University
Lawrence Roy, Aarhus University
Peter Scholl, Aarhus University

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.

Available format(s)
Cryptographic protocols
Publication info
A major revision of an IACR publication in CRYPTO 2023
zero-knowledgepost-quantum signaturesVOLE-in-the-headMPC-in-the-head
Contact author(s)
cabau @ dtu dk
braun @ cs au dk
cyprien delpechdesaintguilhem @ kuleuven be
michael klooss @ aalto fi
emmanuela orsini @ unibocconi it
ldr709 @ gmail com
peter scholl @ cs au dk
2023-06-27: approved
2023-06-26: received
See all versions
Short URL
Creative Commons Attribution


      author = {Carsten Baum and Lennart Braun and Cyprien Delpech de Saint Guilhem and Michael Klooß and Emmanuela Orsini and Lawrence Roy and Peter Scholl},
      title = {Publicly Verifiable Zero-Knowledge and Post-Quantum Signatures From VOLE-in-the-Head},
      howpublished = {Cryptology ePrint Archive, Paper 2023/996},
      year = {2023},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.