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

Carsten Baum; Lennart Braun; Cyprien Delpech de Saint Guilhem; Michael Klooß; Emmanuela Orsini; Lawrence Roy; Peter Scholl

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

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.

Metadata

Available format(s): PDF
Category: Cryptographic protocols
Publication info: A major revision of an IACR publication in CRYPTO 2023
Keywords: zero-knowledge post-quantum signatures VOLE-in-the-head MPC-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
History: 2023-06-27: approved; 2023-06-26: received; See all versions
Short URL: https://ia.cr/2023/996
License: CC BY

BibTeX

@misc{cryptoeprint:2023/996,
      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{https://eprint.iacr.org/2023/996}},
      url = {https://eprint.iacr.org/2023/996}
}