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

*Corresponding author for this work

Research output: Chapter in Book/Report/Conference proceedingConference article in proceedingsScientificpeer-review

3 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 - 43rd Annual International Cryptology Conference, CRYPTO 2023, Proceedings
EditorsHelena Handschuh, Anna Lysyanskaya
PublisherSpringer
Pages581-615
Number of pages35
ISBN (Print)978-3-031-38553-7
DOIs
Publication statusPublished - 2023
MoE publication typeA4 Conference publication
EventInternational Cryptology Conference - Santa Barbara, United States
Duration: 20 Aug 202324 Aug 2023
Conference number: 43

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
PublisherSpringer
Volume14085 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Conference

ConferenceInternational Cryptology Conference
Abbreviated titleCRYPTO
Country/TerritoryUnited States
CitySanta Barbara
Period20/08/202324/08/2023

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