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 David Roy, Peter Scholl

*Corresponding author for this work

Research output: Contribution to book/anthology/report/proceedingArticle in proceedingsResearchpeer-review

20 Citations (Scopus)

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.
Original languageEnglish
Title of host publicationAdvances in Cryptology : CRYPTO 2023
EditorsHelena Handschuh, Anna Lysyanskaya
Number of pages35
Place of publicationCham
PublisherSpringer
Publication dateAug 2023
Pages581-615
ISBN (Print)978-3-031-38553-7
ISBN (Electronic)978-3-031-38554-4
DOIs
Publication statusPublished - Aug 2023
SeriesLecture Notes in Computer Science
Volume14085
ISSN0302-9743

Fingerprint

Dive into the research topics of 'Publicly Verifiable Zero-Knowledge and Post-Quantum Signatures from VOLE-in-the-Head'. Together they form a unique fingerprint.

Cite this