Advancements in Zero-Knowledge Argument Systems Using Garbled Circuits
/ 4 min read
Quick take - A recent paper presents advancements in zero-knowledge argument systems using garbled circuits, extending previous research and introducing hybrid commit-and-prove systems that connect algebraic commitments with Boolean circuits, while enhancing efficiency and security through novel garbling schemes and techniques.
Fast Facts
- The paper advances zero-knowledge argument systems using garbled circuits, building on previous compilers and introducing hybrid commit-and-prove systems that link algebraic commitments with Boolean circuits.
- A novel “shuffled label commitment” scheme significantly reduces proof size by approximately 90% and lowers communication complexity, integrating Merkle trees and an NNL pseudo-random generator for efficiency.
- The research introduces new security properties for garbling schemes, including “output indistinguishability” and “verifiable correctness,” to enhance the reliability of cut-and-choose protocols.
- Generalized affine garbling is utilized to connect Boolean circuits with algebraic commitments, supporting privacy-preserving and privacy-free garbled circuits while optimizing cut-and-choose methods.
- The findings enable proving partial knowledge through monotone compositions of CP-ZKGC and demonstrate applications in cross-domain cryptographic contexts, including Pedersen and lattice-based commitments.
Advancements in Zero-Knowledge Argument Systems
A recent paper has introduced significant advancements in the construction of zero-knowledge argument systems through the use of garbled circuits. This work builds upon previous research, extending the GC-to-ZK compiler developed by Jawurek, Kerschbaum, and Orlandi in 2023, as well as the GC-to-Σ compiler by Hazay and Venkitasubramaniam from 2020.
Hybrid Commit-and-Prove Systems
The proposed systems are described as hybrid, commit-and-prove zero-knowledge argument systems. These systems establish a connection between secrets in algebraic commitments and relations represented by Boolean circuits. The approach supports a variety of cross-domain commitments, including both Pedersen-like and lattice-based commitments.
A key innovation is the development of circuit-represented compositions of Σ-protocols that accommodate access structures such as weighted thresholds. The authors address an open question from Abe et al. at TCC 2021 by constructing a Σ-protocol specifically for proving the relationship C(P1, …, Pn) = 1.
Innovations in Garbling Schemes
The paper introduces a generalized garbling scheme that integrates both Boolean and affine operations. Affine garbling is utilized to resolve input consistency issues between Boolean circuits and algebraic commitments. The research extends universally composable zero-knowledge from garbled circuits to commit-and-prove variants.
Cut-and-choose garbled-circuit compilers are incorporated to convert garbling schemes into Σ-protocols. The work employs MPC-in-the-Head paradigms with pre-processing for cut-and-choose zero-knowledge. To enhance efficiency, a shuffled label commitment scheme is developed, achieving a significant reduction in proof size—approximately 90%—and lowering communication complexity.
The integration of Merkle trees with an NNL pseudo-random generator facilitates efficient label commitments. A novel “shuffled label commitment” building block is introduced to tackle complexities arising from mixed domains.
Security Properties and Applications
The paper outlines a general circuit-represented composition of Σ-protocols that supports proving weighted threshold relationships for commitments. New security properties for garbling schemes, including “output indistinguishability,” are introduced. The concept of “verifiable correctness” is defined to ensure accuracy in cut-and-choose protocols, aiming to prevent the exploitation of correctness errors in garbling.
Additionally, a garbling scheme specifically for affine predicates is introduced, enabling support for affine functions over rings. Random invertible labels are utilized within the garbling scheme to maintain both privacy and correctness. The paper discusses both privacy-preserving and privacy-free garbling schemes.
The cut-and-choose strategy is employed in the CCZK framework to ensure correctness in garbled circuits. The Fiat-Shamir transformation is applied to derive non-interactive zero-knowledge proofs. Moreover, the paper introduces a commit-and-prove extension (CP-ZKGC) for zero-knowledge proofs, along with a conjunctive composition scheme applicable to both Boolean and algebraic circuits.
The study demonstrates privacy-free conjunctive composition for hybrid commit-and-prove garbling schemes, allowing for proving partial knowledge via monotone compositions of CP-ZKGC. Generalized affine garbling is employed to efficiently link Boolean circuits with algebraic commitments, while optimized cut-and-choose methods yield a 34% reduction in the number of evaluated circuits.
The findings support hybrid zero-knowledge statements that interconnect various cryptographic domains, with affine garbling applied to privacy-preserving garbled circuits. The paper outlines the use of affine commitments with generalized affine functions and provides a refined definition of soundness for garbling schemes. “Decode key extractability” is introduced to facilitate the use of garbled outputs in subsequent computations. The authors illustrate the applications of their findings to Σ-protocols using MPC-in-the-Head paradigms, highlighting the relevance for cross-domain secrets, including Pedersen commitments and lattice-based schemes.
Original Source: Read the Full Article Here
