Paper 2020/735

Bulletproofs+: Shorter Proofs for Privacy-Enhanced Distributed Ledger

Heewon Chung, Kyoohyung Han, Chanyang Ju, Myungsun Kim, and Jae Hong Seo

Abstract

We present a new short zero-knowledge argument for the range proof and the arithmetic circuits without a trusted setup. In particular, the proof size of our protocol is the shortest of the category of proof systems with a trustless setup. More concretely, when proving a committed value is a positive integer less than 64 bits, except for negligible error in the $128$-bit security parameter, the proof size is $576$ byte long, which is of $85.7\%$ size of the previous shortest one due to Bünz et al.~(Bulletproofs, IEEE Security and Privacy 2018), while computational overheads in both proof generation and verification are comparable with those of Bulletproofs, respectively. Bulletproofs is established as one of important privacy enhancing technologies for distributed ledger, due to its trustless feature and short proof size. In particular, it has been implemented and optimized in various programming languages for practical usages by independent entities since it proposed. The essence of Bulletproofs is based on the logarithmic inner product argument with no zero-knowledge. In this paper, we revisit Bulletproofs from the viewpoint of the first sublinear zero-knowledge argument for linear algebra due to Groth~(CRYPTO 2009) and then propose Bulletproofs+, an improved variety of Bulletproofs. The main ingredient of our proposal is the zero-knowledge weighted inner product argument (zk-WIP) to which we reduce both the range proof and the arithmetic circuit proof. The benefit of reducing to the zk-WIP is a minimal transmission cost during the reduction process. Note the zk-WIP has all nice features of the inner product argument such as an aggregating range proof and batch verification.

Metadata
Available format(s)
PDF
Category
Cryptographic protocols
Publication info
Preprint. MINOR revision.
Keywords
Zero Knowledge ArgumentRange ProofInner Product
Contact author(s)
jhsbhs @ gmail com
heewonchung @ hanyang ac kr
History
2020-06-18: received
Short URL
https://ia.cr/2020/735
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2020/735,
      author = {Heewon Chung and Kyoohyung Han and Chanyang Ju and Myungsun Kim and Jae Hong Seo},
      title = {Bulletproofs+: Shorter Proofs for Privacy-Enhanced Distributed Ledger},
      howpublished = {Cryptology ePrint Archive, Paper 2020/735},
      year = {2020},
      note = {\url{https://eprint.iacr.org/2020/735}},
      url = {https://eprint.iacr.org/2020/735}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.