research-article

Caulk: Lookup Arguments in Sublinear Time

Authors:

Arantxa Zapico,

Vitalik Buterin,

Dmitry Khovratovich,

Anca Nitulescu,

Mark SimkinAuthors Info & Claims

CCS '22: Proceedings of the 2022 ACM SIGSAC Conference on Computer and Communications Security

Pages 3121 - 3134

https://doi.org/10.1145/3548606.3560646

Published: 07 November 2022 Publication History

Abstract

We present position-hiding linkability for vector commitment schemes: one can prove in zero knowledge that one or m values that comprise commitment \cm all belong to the vector of size N committed to in \com. Our construction \textsfCaulk can be used for membership proofs and lookup arguments and outperforms all existing alternatives in prover time by orders of magnitude.

For both single- and multi-membership proofs the \textsfCaulk protocol beats SNARKed Merkle proofs by the factor of 100 even if the latter is instantiated with Poseidon hash. Asymptotically our prover needs O(m^2 + młog N) time to prove a batch of m openings, whereas proof size is O(1) and verifier time is O(łog(łog N)). As a lookup argument, \textsfCaulk is the first scheme with prover time sublinear in the table size, assuming O(Nłog N) preprocessing time and O(N) storage. It can be used as a subprimitive in verifiable computation schemes in order to drastically decrease the lookup overhead.

Our scheme comes with a reference implementation and benchmarks.

References

[1]

M. R. Albrecht, L. Grassi, C. Rechberger, A. Roy, and T. Tiessen. MiMC: Efficient Encryption and Cryptographic Hashing with Minimal Multiplicative Complexity. In ASIACRYPT 2016, volume 10031 of LNCS, pages 191--219, 2016.

[2]

arkworks contributors. arkworks zksnark ecosystem, 2022.

[3]

S. Bayer and J. Groth. Zero-knowledge argument for polynomial evaluation with application to blacklists. In T. Johansson and P. Q. Nguyen, editors, Advances in Cryptology - EUROCRYPT 2013, 32nd Annual International Conference on the Theory and Applications of Cryptographic Techniques, Athens, Greece, May 26- 30, 2013. Proceedings, volume 7881 of Lecture Notes in Computer Science, pages 646--663. Springer, 2013.

[4]

E. Ben-Sasson, A. Chiesa, C. Garman, M. Green, I. Miers, E. Tromer, and M. Virza. Zerocash: Decentralized anonymous payments from bitcoin. In 2014 IEEE Symposium on Security and Privacy, SP 2014, Berkeley, CA, USA, May 18--21, 2014, pages 459--474. IEEE Computer Society, 2014.

Digital Library

[5]

D. Benarroch, M. Campanelli, D. Fiore, K. Gurkan, and D. Kolonelos. Zeroknowledge proofs for set membership: Efficient, succinct, modular. In N. Borisov and C. Díaz, editors, Financial Cryptography and Data Security - 25th International Conference, FC 2021, Virtual Event, March 1--5, 2021, Revised Selected Papers, Part I, volume 12674 of Lecture Notes in Computer Science, pages 393--414. Springer, 2021.

Digital Library

[6]

D. Boneh and X. Boyen. Short signatures without random oracles. In EUROCRYPT, volume 3027 of Lecture Notes in Computer Science, pages 56--73. Springer, 2004.

[7]

J. Bootle, A. Cerulli, P. Chaidos, E. Ghadafi, J. Groth, and C. Petit. Short accountable ring signatures based on DDH. In G. Pernul, P. Y. A. Ryan, and E. R. Weippl, editors, Computer Security - ESORICS 2015 - 20th European Symposium on Research in Computer Security, Vienna, Austria, September 21--25, 2015, Proceedings, Part I, volume 9326 of Lecture Notes in Computer Science, pages 243--265. Springer, 2015.

Digital Library

[8]

J. Bootle and J. Groth. Efficient batch zero-knowledge arguments for low degree polynomials. In M. Abdalla and R. Dahab, editors, Public-Key Cryptography - PKC 2018 - 21st IACR International Conference on Practice and Theory of Public-Key Cryptography, Rio de Janeiro, Brazil, March 25--29, 2018, Proceedings, Part II, volume 10770 of Lecture Notes in Computer Science, pages 561--588. Springer, 2018.

[9]

J. Camenisch, R. Chaabouni, and A. Shelat. Efficient protocols for set membership and range proofs. In J. Pieprzyk, editor, Advances in Cryptology - ASIACRYPT 2008, 14th International Conference on the Theory and Application of Cryptology and Information Security, Melbourne, Australia, December 7--11, 2008. Proceedings, volume 5350 of Lecture Notes in Computer Science, pages 234--252. Springer, 2008.

Digital Library

[10]

J. Camenisch and A. Lysyanskaya. Dynamic accumulators and application to efficient revocation of anonymous credentials. In M. Yung, editor, Advances in Cryptology - CRYPTO 2002, 22nd Annual International Cryptology Conference, Santa Barbara, California, USA, August 18--22, 2002, Proceedings, volume 2442 of Lecture Notes in Computer Science, pages 61--76. Springer, 2002.

[11]

M. Campanelli, D. Fiore, S. Han, J. Kim, D. Kolonelos, and H. Oh. Succinct zeroknowledge batch proofs for set accumulators. IACR Cryptol. ePrint Arch., page 1672, 2021.

[12]

A. Chiesa, Y. Hu, M. Maller, P. Mishra, P. Vesely, and N. Ward. Marlin: Preprocessing zksnarks with universal and updatable srs. In A. Canteaut and Y. Ishai, editors, Advances in Cryptology - EUROCRYPT 2020 - 39th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Virtual Conference, May 1--15, 2020, Proceedings, Part I, volume 12105 of Lecture Notes in Computer Science, pages 738--768. Springer, 2020.

Digital Library

[13]

D. Feist and D. Khovratovich. Fast amortized kate proofs.

[14]

G. Fuchsbauer, E. Kiltz, and J. Loss. The algebraic group model and its applications. In H. Shacham and A. Boldyreva, editors, CRYPTO 2018, Santa Barbara, CA, USA, August 19--23, 2018, Proceedings, Part II, volume 10992 of LNCS, pages 33--62. Springer, 2018.

[15]

A. Gabizon and Z. J. Williamson. Plonk: Permutations over lagrange-bases for oecumenical noninteractive arguments of knowledge. IACR Cryptol. ePrint Arch., page 953, 2019.

[16]

A. Gabizon and Z. J. Williamson. plookup: A simplified polynomial protocol for lookup tables. IACR Cryptol. ePrint Arch., page 315, 2020.

[17]

E. Ghadafi and J. Groth. Towards a classification of non-interactive computational assumptions in cyclic groups. IACR Cryptol. ePrint Arch., page 343, 2017.

[18]

L. Grassi, D. Khovratovich, A. Roy, C. Rechberger, and M. Schofnegger. Poseidon: A new hash function for zero-knowledge proof systems. Usenix Security 2021, 2021.

[19]

J. Groth. On the size of pairing-based non-interactive arguments. In EUROCRYPT, volume 9666 of Lecture Notes in Computer Science, pages 305--326. Springer, 2016.

[20]

J. Groth and M. Kohlweiss. One-out-of-many proofs: Or how to leak a secret and spend a coin. In E. Oswald and M. Fischlin, editors, Advances in Cryptology - EUROCRYPT 2015 - 34th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Sofia, Bulgaria, April 26--30, 2015, Proceedings, Part II, volume 9057 of Lecture Notes in Computer Science, pages 253--280. Springer, 2015.

[21]

A. Kate, G. M. Zaverucha, and I. Goldberg. Constant-size commitments to polynomials and their applications. In ASIACRYPT, volume 6477 of Lecture Notes in Computer Science, pages 177--194. Springer, 2010.

[22]

M. Kohlweiss, M. Maller, J. Siim, and M. Volkhov. Snarky ceremonies. In ASIACRYPT (3), volume 13092 of Lecture Notes in Computer Science, pages 98--127. Springer, 2021.

Digital Library

[23]

U. M. Maurer. Unifying zero-knowledge proofs of knowledge. In AFRICACRYPT, volume 5580 of Lecture Notes in Computer Science, pages 272--286. Springer, 2009.

Digital Library

[24]

I. Miers, C. Garman, M. Green, and A. D. Rubin. Zerocoin: Anonymous distributed e-cash from bitcoin. In 2013 IEEE Symposium on Security and Privacy, SP 2013, Berkeley, CA, USA, May 19--22, 2013, pages 397--411. IEEE Computer Society, 2013.

Digital Library

[25]

C. Papamanthou, E. Shi, and R. Tamassia. Signatures of correct computation. In TCC, volume 7785 of Lecture Notes in Computer Science, pages 222--242. Springer, 2013.

Digital Library

[26]

L. Pearson, J. Fitzgerald, H. Masip, M. Bellés-Muñoz, and J. L. Muñoz-Tapia. Plonkup: Reconciling plonk with plookup. IACR Cryptol. ePrint Arch., page 86, 2022.

[27]

A. Tomescu, I. Abraham, V. Buterin, J. Drake, D. Feist, and D. Khovratovich. Aggregatable subvector commitments for stateless cryptocurrencies. In C. Galdi and V. Kolesnikov, editors, Security and Cryptography for Networks - 12th International Conference, SCN 2020, Amalfi, Italy, September 14--16, 2020, Proceedings, volume 12238 of Lecture Notes in Computer Science, pages 45--64. Springer, 2020.

Digital Library

[28]

Tornado cash privacy solution version 1.4, 2021. https://tornado.cash/Tornado. cash_whitepaper_v1.4.pdf.

[29]

ZCash protocol specification, 2022, 1st February. https://github.com/zcash/zips/ blob/master/protocol/protocol.pdf.

[30]

Zksync rollup protocol, 2021. https://github.com/matter-labs/zksync/blob/ master/docs/protocol.md.

Cited By

Campanelli MFiore DGennaro R(2025)Natively Compatible Super-Efficient Lookup Arguments and How to Apply ThemJournal of Cryptology10.1007/s00145-024-09535-038:1Online publication date: 9-Jan-2025
https://doi.org/10.1007/s00145-024-09535-0
Rosenberg MMopuri THafezi HMiers IMishra PLuo BLiao XXu JKirda ELie D(2024)Hekaton: Horizontally-Scalable zkSNARKs Via Proof AggregationProceedings of the 2024 on ACM SIGSAC Conference on Computer and Communications Security10.1145/3658644.3690282(929-940)Online publication date: 2-Dec-2024
https://dl.acm.org/doi/10.1145/3658644.3690282
Ganesh CNair VSharma ALuo BLiao XXu JKirda ELie D(2024)Dual Polynomial Commitment Schemes and Applications to Commit-and-Prove SNARKsProceedings of the 2024 on ACM SIGSAC Conference on Computer and Communications Security10.1145/3658644.3690219(884-898)Online publication date: 2-Dec-2024
https://dl.acm.org/doi/10.1145/3658644.3690219
Show More Cited By

Index Terms

Caulk: Lookup Arguments in Sublinear Time
1. Security and privacy
  1. Cryptography
    1. Public key (asymmetric) techniques

Recommendations

RSA-based Convertible Nominative Signature Scheme
CSSS '12: Proceedings of the 2012 International Conference on Computer Science and Service System

Nominative signature is an useful cryptographic primitive to limit the publicly verifiable property of ordinary digital signature. In a nominative signature scheme, a nominator and a nominee jointly generate a signature in such a way that only the ...
Nonmalleable Cryptography

The notion of nonmalleable cryptography, an extension of semantically secure cryptography, is defined. Informally, in the context of encryption the additional requirement is that given the ciphertext it is impossible to generate a different ciphertext ...
Certificateless undeniable signature scheme

In this paper, we present the first certificateless undeniable signature scheme. The scheme does not suffer from the key escrow problem, which is inherent in identity based cryptosystems. Also it can avoid the onerous management of certificates. ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

CCS '22: Proceedings of the 2022 ACM SIGSAC Conference on Computer and Communications Security

November 2022

3598 pages

ISBN:9781450394505

DOI:10.1145/3548606

General Chairs:
Heng Yin
University of California, Riverside
,
Angelos Stavrou
Virginia Tech
,
Program Chairs:
Cas Cremers
CISPA Helmholtz Center for Information Security
,
Elaine Shi
Carnegie Mellon University

Copyright © 2022 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Sponsors

SIGSAC: ACM Special Interest Group on Security, Audit, and Control

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 07 November 2022

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Conference

CCS '22

Sponsor:

SIGSAC

CCS '22: 2022 ACM SIGSAC Conference on Computer and Communications Security

November 7 - 11, 2022

CA, Los Angeles, USA

Acceptance Rates

Overall Acceptance Rate 1,261 of 6,999 submissions, 18%

Upcoming Conference

CCS '25

Sponsor:
sigsac

ACM SIGSAC Conference on Computer and Communications Security

October 13 - 17, 2025

Taipei , Taiwan

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

20
Total Citations
View Citations
353
Total Downloads

Downloads (Last 12 months)138
Downloads (Last 6 weeks)6

Reflects downloads up to 13 Feb 2025

Other Metrics

View Author Metrics

Citations

Cited By

Campanelli MFiore DGennaro R(2025)Natively Compatible Super-Efficient Lookup Arguments and How to Apply ThemJournal of Cryptology10.1007/s00145-024-09535-038:1Online publication date: 9-Jan-2025
https://doi.org/10.1007/s00145-024-09535-0
Rosenberg MMopuri THafezi HMiers IMishra PLuo BLiao XXu JKirda ELie D(2024)Hekaton: Horizontally-Scalable zkSNARKs Via Proof AggregationProceedings of the 2024 on ACM SIGSAC Conference on Computer and Communications Security10.1145/3658644.3690282(929-940)Online publication date: 2-Dec-2024
https://dl.acm.org/doi/10.1145/3658644.3690282
Ganesh CNair VSharma ALuo BLiao XXu JKirda ELie D(2024)Dual Polynomial Commitment Schemes and Applications to Commit-and-Prove SNARKsProceedings of the 2024 on ACM SIGSAC Conference on Computer and Communications Security10.1145/3658644.3690219(884-898)Online publication date: 2-Dec-2024
https://dl.acm.org/doi/10.1145/3658644.3690219
Sun HLi JZhang HLuo BLiao XXu JKirda ELie D(2024)zkLLM: Zero Knowledge Proofs for Large Language ModelsProceedings of the 2024 on ACM SIGSAC Conference on Computer and Communications Security10.1145/3658644.3670334(4405-4419)Online publication date: 2-Dec-2024
https://dl.acm.org/doi/10.1145/3658644.3670334
Zhai MLiu YWu QQin BZheng HDai XDing ZSusilo W(2024)Accountable Secret Committee Election and Anonymous Sharding Blockchain ConsensusIEEE Transactions on Information Forensics and Security10.1109/TIFS.2024.345960819(9158-9172)Online publication date: 2024
https://doi.org/10.1109/TIFS.2024.3459608
Zhai MWu QLiu YQin BDai XGao QSusilo W(2024)Secret Multiple Leaders & Committee Election With Application to Sharding BlockchainIEEE Transactions on Information Forensics and Security10.1109/TIFS.2024.339058419(5060-5074)Online publication date: 2024
https://doi.org/10.1109/TIFS.2024.3390584
Liu TXie TZhang JSong DZhang Y(2024)Pianist: Scalable zkRollups via Fully Distributed Zero-Knowledge Proofs2024 IEEE Symposium on Security and Privacy (SP)10.1109/SP54263.2024.00035(1777-1793)Online publication date: 19-May-2024
https://doi.org/10.1109/SP54263.2024.00035
Kudzin AToyoda KKawazoe MTakayama SIshigame A(2024)Scaling Ethereum 2.0’s Cross-Shard Transactions With Efficient Verification and Aggregation of KZG CommitmentsIEEE Internet of Things Journal10.1109/JIOT.2024.341993211:19(31822-31835)Online publication date: 1-Oct-2024
https://doi.org/10.1109/JIOT.2024.3419932
Luthra ACavanaugh JOlcese HRaymond MEustache RHirsch RFu X(2024)Mitigating Ponzi schemes by zero-knowledge auditingInformation Security Journal: A Global Perspective10.1080/19393555.2024.2404216(1-24)Online publication date: 15-Dec-2024
https://doi.org/10.1080/19393555.2024.2404216
Bünz BChen J(2024)Proofs for Deep Thought: Accumulation for Large Memories and Deterministic ComputationsAdvances in Cryptology – ASIACRYPT 202410.1007/978-981-96-0935-2_9(269-301)Online publication date: 10-Dec-2024
https://dl.acm.org/doi/10.1007/978-981-96-0935-2_9
Show More Cited By

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Figures

Tables

Media

View Table of Conten