Aarhus University Seal / Aarhus Universitets segl

Appenzeller to Brie: Efficient Zero-Knowledge Proofs for Mixed-Mode Arithmetic and Z2k

Publikation: Bidrag til bog/antologi/rapport/proceedingKonferencebidrag i proceedingsForskningpeer review


Zero-knowledge proofs are highly flexible cryptographic protocols that are an important building block for many secure systems. Typically, these are defined with respect to statements that are formulated as arithmetic operations over a fixed finite field. This inflexibility is a disadvantage when it comes to complex programs, as some fields are more amenable to express certain operations than others. At the same time, there do not seem to be many proofs with a programming model similar to those found in modern computer architectures that perform arithmetic with 32 or 64 bit integers. In this work, we present solutions to both of these problems. First, we show how to efficiently check consistency of secret values between different instances of zero-knowledge protocols based on the commit-and-prove paradigm. This allows a protocol user to easily switch to the most efficient representation for a given task. To achieve this, we modify the extended doubly-authenticated bits (edabits) approach by Escudero et al. (Crypto 2020), originally developed for MPC, and optimize it for the zero-knowledge setting. As an application of our consistency check, we also introduce protocols for efficiently verifying truncations and comparisons of shared values both modulo a large prime p and modulo 2k. Finally, we complement our conversion protocols with new protocols for verifying arithmetic statements in Z2k. Here, we build upon recent interactive proof systems based on information-theoretic MACs and vector oblivious linear evaluation (VOLE), and show how this paradigm can be adapted to the ring setting. In particular, we show that supporting such modular operations natively in a proof system can be almost as efficient as proofs over large fields or bits, and this also easily plugs into our framework for zero-knowledge conversions.

TitelCCS 2021 - Proceedings of the 2021 ACM SIGSAC Conference on Computer and Communications Security
Antal sider20
ForlagAssociation for Computing Machinery
Udgivelsesårnov. 2021
ISBN (Elektronisk)9781450384544
StatusUdgivet - nov. 2021
BegivenhedThe ACM Conference on Computer and Communications Security (CCS) - Virtual, Online, Sydkorea
Varighed: 15 nov. 202119 nov. 2021


KonferenceThe ACM Conference on Computer and Communications Security (CCS)
ByVirtual, Online
SponsorACM Special Interest Group on Security, Audit and Control (ACM SIGSAC), Korea Institute of Information Security and Cryptology (KIISC)
SerietitelProceedings of the ACM Conference on Computer and Communications Security

Bibliografisk note

Funding Information:
This work is supported by the European Research Council (ERC) under the European Unions’s Horizon 2020 research and innovation programme under grant agreement No. 803096 (SPEC), the Carlsberg Foundation under the Semper Ardens Research Project CF18-112 (BCM), and the Defense Advanced Research Projects Agency (DARPA) under Contract No. HR001120C0085. Any opinions, findings and conclusions or recommendations expressed in this material are those of the author(s) and do not necessarily reflect the views of the Defense Advanced Research Projects Agency (DARPA). Distribution Statement “A” (Approved for Public Release, Distribution Unlimited).

Publisher Copyright:
© 2021 ACM.

Se relationer på Aarhus Universitet Citationsformater

ID: 227091687