ZK-for-Z2K: MPC-in-the-Head Zero-Knowledge Proofs for $\mathbb{Z}_{2^k}$

Lennart Braun; Cyprien Delpech de Saint Guilhem; Robin Jadoul; Emmanuela Orsini; Nigel P. Smart; Titouan Tanguy

Paper 2023/1057

ZK-for-Z2K: MPC-in-the-Head Zero-Knowledge Proofs for $\mathbb{Z}_{2^k}$

Lennart Braun

, Aarhus University

Cyprien Delpech de Saint Guilhem

, COSIC, KU Leuven

Robin Jadoul

, COSIC, KU Leuven

Emmanuela Orsini

, Bocconi University

Nigel P. Smart

, COSIC, KU Leuven, Zama

Titouan Tanguy

, COSIC, KU Leuven

Abstract

In this work, we extend the MPC-in-the-head framework, used in recent efficient zero-knowledge protocols, to work over the ring $\mathbb{Z}_{2^k}$, which is the primary operating domain for modern CPUs. The proposed schemes are compatible with any threshold linear secret sharing scheme and draw inspiration from MPC protocols adapted for ring operations. Additionally, we explore various batching methodologies, leveraging Shamir's secret sharing schemes and Galois ring extensions, and show the applicability of our approach in RAM program verification. Finally, we analyse different options for instantiating the resulting ZK scheme over rings and compare their communication costs.

Metadata

Available format(s): PDF
Category: Cryptographic protocols
Publication info: Published elsewhere. Minor revision. IMA Cryptography and Coding 2023
Contact author(s): braun @ cs au dk
cyprien delpechdesaintguilhem @ kuleuven be
robin jadoul @ esat kuleuven be
emmanuela orsini @ unibocconi it
nigel smart @ kuleuven be
titouan tanguy @ zama ai
History: 2023-09-18: revised; 2023-07-06: received; See all versions
Short URL: https://ia.cr/2023/1057
License: CC BY

BibTeX

@misc{cryptoeprint:2023/1057,
      author = {Lennart Braun and Cyprien Delpech de Saint Guilhem and Robin Jadoul and Emmanuela Orsini and Nigel P. Smart and Titouan Tanguy},
      title = {{ZK}-for-{Z2K}: {MPC}-in-the-Head Zero-Knowledge Proofs for $\mathbb{Z}_{2^k}$},
      howpublished = {Cryptology {ePrint} Archive, Paper 2023/1057},
      year = {2023},
      url = {https://eprint.iacr.org/2023/1057}
}