TENET : Sublogarithmic Proof, Sublinear Verifier Inner Product Argument without a Trusted Setup

Hyeonbum Lee, Jae Hong Seo

TL;DR

This paper introduces TENET, a novel inner product argument (IPA) that achieves both sublogarithmic proof size and sublinear verifier cost without requiring a trusted setup. This is a significant advancement for cryptographic primitives used in advanced proof systems, where trusted setups are often impractical.

What Problem Does This Paper Address?

In cryptography, particularly in areas like zero-knowledge proofs, verifiable computation, and confidential transactions, efficient argument systems are crucial. An "inner product argument" (IPA) is a fundamental building block for many of these systems. It allows a prover to convince a verifier that they know two vectors whose inner product matches a claimed value, without revealing the vectors themselves.

Existing IPAs often face a trade-off: they can achieve either a small proof size (sublogarithmic) or a fast verification process (sublinear), but not both simultaneously, especially when avoiding a "trusted setup." A trusted setup is a process where a trusted third party generates initial cryptographic parameters. This is often undesirable due to security and practical concerns. Previous work by Kim, Lee, and Seo (2022) proposed two IPAs that achieved one of these goals but left the simultaneous achievement as an open problem. This paper tackles that challenge.

Methods

The authors propose TENET by combining and optimizing techniques from previous work. Their approach involves:

  • Generalization of Pairing-Based IPAs: They build upon existing pairing-based IPAs (Protocol2 and Protocol3) that use bilinear pairings to enhance cryptographic properties. The core idea is to combine the "commit-and-prove" strategy of Protocol2 with the structure of Protocol3.
  • Optimization for Sublogarithmic Size: They introduce techniques to compress the prover's messages and intermediate computations. This involves cleverly structuring the prover's messages and using compressed vectors, reducing the complexity from quadratic to linear in certain parameters.
  • Commit-and-Prove Approach: To reduce communication costs, they employ a commit-and-prove strategy. Instead of sending all intermediate values, the prover commits to them and later provides proofs for these commitments.
  • Aggregation Techniques: They leverage aggregation techniques, specifically inspired by "aAggMEA" from prior work, to further reduce communication overhead by combining multiple proofs or computations.
  • Recursive Reduction: The protocol uses recursive reduction techniques, similar to those in BPip and Protocol3, to break down the problem into smaller, manageable steps.

Datasets

Not discussed in the paper.

Key Insights and Ideas

  • Bridging the Gap: The most significant insight is the successful combination of techniques to overcome the inherent trade-off between proof size and verifier cost in IPAs without a trusted setup.
  • Leveraging Bilinear Pairings: The paper demonstrates how the properties of bilinear pairings can be effectively utilized to achieve both sublogarithmic proof size and sublinear verifier cost simultaneously.
  • Compression is Key: The optimization techniques for compressing prover's messages and intermediate computations are crucial for achieving the desired efficiency. This highlights the importance of clever data representation in cryptographic protocols.
  • Decomposition for Efficiency: The strategy of decomposing commitment terms (like a and b) allows for more efficient processing and avoids the need for homomorphic commitments on target group elements, which are not readily available.

Key Results

TENET achieves:

  • Sublogarithmic Proof Size: The size of the proof generated by TENET is sublogarithmic in the size of the witness.
  • Sublinear Verifier Cost: The computational cost for the verifier to check the proof is sublinear.
  • No Trusted Setup: The protocol does not require a trusted third party to generate initial parameters.
  • Security Guarantees: The soundness of TENET is proven under the discrete logarithm (DL) assumption and the double pairing (DPair) assumption.

The paper provides a detailed complexity analysis in Table 2, showing the communication, prover computation, and verifier computation costs for different phases of TENET. For instance, the total communication cost is O(R + log nd), where R is related to the number of rounds.

Limitations and Future Work

  • Assumptions: The security of TENET relies on the discrete logarithm and double pairing assumptions. The practicality and security of these assumptions in specific cryptographic settings are always a consideration.
  • Parameter Choice: The paper discusses parameter settings to achieve the desired efficiency, noting that careful selection of parameters (like d, n, and m) is crucial for realizing the sublogarithmic and sublinear properties.
  • Future Work: The authors suggest that TENET can be used to construct sublogarithmic proof size and sublinear verifiable polynomial commitment schemes, which can then be applied to polynomial IOP systems like Sonic, Plonk, and Marlin, further enhancing their efficiency without a trusted setup. This opens avenues for building more efficient and practical zero-knowledge proof systems.

Summary updated

Abstract

We propose a new inner product argument (IPA), called TENET, which features sublogarithmic proof size and sublinear verifier without a trusted setup. IPA is a core primitive for various advanced proof systems including range proofs, circuit satisfiability, and polynomial commitment, particularly where a trusted setup is hard to apply. At ASIACRYPT 2022, Kim, Lee, and Seo showed that pairings can be utilized to exceed the complexity barrier of the previous discrete logarithm-based IPA without a trusted setup. More precisely, they proposed two pairing-based IPAs, one with sublogarithmic proof size and the other one with sublinear verifier cost, but they left achieving both complexities simultaneously as an open problem. We investigate the obstacles for this open problem and then provide our solution TENET, which achieves both sublogarithmic proof size and sublinear verifier. We prove the soundness of TENET under the discrete logarithm assumption and double pairing assumption.
BibTeX
@article{lee2023tenet,
  author = {Hyeonbum Lee and Jae Hong Seo},
  title = {{TENET : Sublogarithmic Proof, Sublinear Verifier Inner Product Argument without a Trusted Setup}},
  journal = {IACR Cryptol. ePrint Arch.},
  year = {2023},
  url = {https://openreview.net/forum?id=W269xWNSsw},
}

Loading related content...

Figure