Cryptology ePrint Archive: Report 2021/478

TurboIKOS: Improved Non-interactive Zero Knowledge and Post-Quantum Signatures

Yaron Gvili and Julie Ha and Sarah Scheffler and Mayank Varia and Ziling Yang and Xinyuan Zhang

Abstract: In this work, we present a zero knowledge argument for general arithmetic circuits that is public-coin and constant rounds, so it can be made non-interactive and publicly verifiable with the Fiat-Shamir heuristic. The construction is based on the MPC-in-the-head paradigm, in which the prover jointly emulates all MPC protocol participants and can provide advice in the form of Beaver triples whose accuracy must be checked by the verifier. Our construction follows the Beaver triple sacrificing approach used by Baum and Nof [PKC 2020]. Our improvements reduce the communication per multiplication gate from 4 to 2 field elements, matching the performance of the cut-and-choose approach taken by Katz, Kolesnikov, and Wang [CCS 2018] and with lower additive overhead for some parameter settings. We implement our protocol and analyze its cost on Picnic-style post-quantum digital signatures based on the AES family of circuits.

Category / Keywords: cryptographic protocols / zero knowledge, digital signatures

Original Publication (in the same form): ACNS 2021

Date: received 14 Apr 2021

Contact author: sscheff at bu edu

Available format(s): PDF | BibTeX Citation

Version: 20210415:092701 (All versions of this report)

Short URL:

[ Cryptology ePrint archive ]