Zero-Knowledge for Homomorphic Key-Value Commitments with Applications to Privacy-Preserving Ledgers | SpringerLink
Skip to main content
Springer Nature Link
Log in

Zero-Knowledge for Homomorphic Key-Value Commitments with Applications to Privacy-Preserving Ledgers

  • Conference paper
  • First Online:
Security and Cryptography for Networks (SCN 2022)

Part of the book series: Lecture Notes in Computer Science ((LNCS,volume 13409))

Included in the following conference series:

  • 944 Accesses

Abstract

Commitments to key-value maps (or, authenticated dictionaries) are an important building block in cryptographic applications, including cryptocurrencies and distributed file systems.

In this work we study short commitments to key-value maps with two additional properties: double-hiding (both keys and values should be hidden) and homomorphism (we should be able to combine two commitments to obtain one that is the “sum” of their key-value openings). Furthermore, we require these commitments to be short and to support efficient transparent zero-knowledge arguments (i.e., without a trusted setup).

As our main contribution, we show how to construct commitments with the properties above as well as efficient zero-knowledge arguments over them. We additionally discuss a range of practical optimizations that can be carried out depending on the application domain. Finally, we formally describe a specific application of commitments to key-value maps to scalable anonymous ledgers. We show how to extend QuisQuis (Fauzi et al. ASIACRYPT 2019). This results in an efficient, confidential multi-type system with a state whose size is independent of the number of transactions.

This is a preview of subscription content, log in via an institution to check access.

Access this chapter

Log in via an institution

Subscribe and save

Springer+ Basic
¥17,985 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Chapter
JPY 3498
Price includes VAT (Japan)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
eBook
JPY 12583
Price includes VAT (Japan)
  • Available as EPUB and PDF
  • Read on any device
  • Instant download
  • Own it forever
Softcover Book
JPY 15729
Price includes VAT (Japan)
  • Compact, lightweight edition
  • Dispatched in 3 to 5 business days
  • Free shipping worldwide - see info

Tax calculation will be finalised at checkout

Purchases are for personal use only

Institutional subscriptions

Similar content being viewed by others

Notes

  1. 1.

    This is a way to describe our setting asymptotically. We stress, however, that is not necessary: an interesting setting for our constructions is just one where the universe of keys is concretely large.

  2. 2.

    In a transparent argument system the setup does not need to be produced by a trusted party. This property is interesting in the case of non-interactive argument systems, which are the focus of this work.

  3. 3.

    This is true for the aforementioned approach with sigma-protocols as well as for other straightforward applications of NIZKs.

  4. 4.

    I.e., a commitment which can be opened using a secret key in place of the randomness.

  5. 5.

    Here we consider the case where leaking the density of the key-value map is not a problem. We will also adapt our construction where this leakage does not occur if an upper bound on this density is known.

  6. 6.

    An accumulator is a cryptographic data structure that allows to commit to a set in a binding manner and to prove membership of an element efficiently. NB: we can compute accumulators deterministically from a set, i.e., without a trusted authority.

  7. 7.

    We refer the reader to [35] for a survey of this rapidly growing field.

  8. 8.

    Plausible deniability: no one can tell if a user meant to be involved in a transaction.

  9. 9.

    We will use this when defining the homomorphic property of commitments.

  10. 10.

    If malleability is a concern, Bulletproofs are proven to be non-malleable in the AGM [24].

  11. 11.

    For some applications this can be huge—for comparison, the ZCash circuit [26] has approximately 100k constraints.

  12. 12.

    This is a lower bound but we expect it be a reasonable estimate (up to approximately a factor 2) of hashing-to-group techniques close to those in Sect. 1.1 in [15].

  13. 13.

    Since there is no public circuit implementation for Ristretto operations for this, we use arkworks [1] BL12-381 implementation for this estimate. We expect this to be an upper bound on Ristretto points given their smaller field size—\(\frac{255}{381}\)x smaller, more precisely. We measure this number using the implementation in [1].

  14. 14.

    We use a different implementation [3] on BL12-381 points as the implementation in [2] is not compatible with BL12-381.

References

  1. Ark-works. http://arkworks.rs

  2. Dalek bulletproofs implementation. https://github.com/zkcrypto/bulletproofs.git

  3. Zengo-x bulletproofs implementation. https://github.com/ZenGo-X/bulletproofs

  4. Agarwal, A., Kamara, S.: Encrypted key-value stores. In: Bhargavan, K., Oswald, E., Prabhakaran, M. (eds.) INDOCRYPT 2020. LNCS, vol. 12578, pp. 62–85. Springer, Cham (2020). https://doi.org/10.1007/978-3-030-65277-7_4

    Chapter  Google Scholar 

  5. Agrawal, S., Raghuraman, S.: KVaC: key-value commitments for blockchains and beyond. In: Moriai, S., Wang, H. (eds.) ASIACRYPT 2020, Part III. LNCS, vol. 12493, pp. 839–869. Springer, Cham (2020). https://doi.org/10.1007/978-3-030-64840-4_28

    Chapter  Google Scholar 

  6. Albrecht, M.R., et al.: Feistel structures for MPC, and more. In: Sako, K., Schneider, S., Ryan, P.Y.A. (eds.) ESORICS 2019, Part II. LNCS, vol. 11736, pp. 151–171. Springer, Cham (2019). https://doi.org/10.1007/978-3-030-29962-0_8

    Chapter  Google Scholar 

  7. Albrecht, M., Grassi, L., Rechberger, C., Roy, A., Tiessen, T.: MiMC: efficient encryption and cryptographic hashing with minimal multiplicative complexity. In: Cheon, J.H., Takagi, T. (eds.) ASIACRYPT 2016, Part I. LNCS, vol. 10031, pp. 191–219. Springer, Heidelberg (2016). https://doi.org/10.1007/978-3-662-53887-6_7

    Chapter  Google Scholar 

  8. Aly, A., Ashur, T., Ben-Sasson, E., Dhooghe, S., Szepieniec, A.: Design of symmetric-key primitives for advanced cryptographic protocols. Cryptology ePrint Archive, Report 2019/426 (2019). https://eprint.iacr.org/2019/426

  9. Attema, T., Cramer, R.: Compressed \(\Sigma \)-protocol theory and practical application to plug  & play secure algorithmics. In: Micciancio, D., Ristenpart, T. (eds.) CRYPTO 2020, Part III. LNCS, vol. 12172, pp. 513–543. Springer, Cham (2020). https://doi.org/10.1007/978-3-030-56877-1_18

    Chapter  Google Scholar 

  10. Attema, T., Cramer, R., Rambaud, M.: Compressed sigma-protocols for bilinear circuits and applications to logarithmic-sized transparent threshold signature schemes. Cryptology ePrint Archive, Report 2020/1447 (2020). https://eprint.iacr.org/2020/1447

  11. Ben-Sasson, E., et al.: Zerocash: decentralized anonymous payments from bitcoin. In: 2014 IEEE Symposium on Security and Privacy, pp. 459–474. IEEE Computer Society Press, May 2014. https://doi.org/10.1109/SP.2014.36

  12. Benarroch, D., Campanelli, M., Fiore, D., Kolonelos, D.: Zero-knowledge proofs for set membership: efficient, succinct, modular. Cryptology ePrint Archive, Report 2019/1255 (2019). https://eprint.iacr.org/2019/1255

  13. Boneh, D., Bünz, B., Fisch, B.: Batching techniques for accumulators with applications to IOPs and stateless blockchains. In: Boldyreva, A., Micciancio, D. (eds.) CRYPTO 2019, Part I. LNCS, vol. 11692, pp. 561–586. Springer, Cham (2019). https://doi.org/10.1007/978-3-030-26948-7_20

    Chapter  Google Scholar 

  14. Bootle, J., Groth, J.: Efficient batch zero-knowledge arguments for low degree polynomials. In: Abdalla, M., Dahab, R. (eds.) PKC 2018, Part II. LNCS, vol. 10770, pp. 561–588. Springer, Cham (2018). https://doi.org/10.1007/978-3-319-76581-5_19

    Chapter  Google Scholar 

  15. Brier, E., Coron, J.-S., Icart, T., Madore, D., Randriam, H., Tibouchi, M.: Efficient indifferentiable hashing into ordinary elliptic curves. In: Rabin, T. (ed.) CRYPTO 2010. LNCS, vol. 6223, pp. 237–254. Springer, Heidelberg (2010). https://doi.org/10.1007/978-3-642-14623-7_13

    Chapter  Google Scholar 

  16. Bünz, B., Bootle, J., Boneh, D., Poelstra, A., Wuille, P., Maxwell, G.: Bulletproofs: short proofs for confidential transactions and more. In: 2018 IEEE Symposium on Security and Privacy, pp. 315–334. IEEE Computer Society Press, May 2018. https://doi.org/10.1109/SP.2018.00020

  17. Campanelli, M., Engelmann, F., Orlandi, C.: Zero-knowledge for homomorphic key-value commitments with applications to privacy-preserving ledgers. Cryptology ePrint Archive, Report 2021/1678 (2021). https://eprint.iacr.org/2021/1678

  18. Campanelli, M., Fiore, D., Greco, N., Kolonelos, D., Nizzardo, L.: Incrementally aggregatable vector commitments and applications to verifiable decentralized storage. In: Moriai, S., Wang, H. (eds.) ASIACRYPT 2020, Part II. LNCS, vol. 12492, pp. 3–35. Springer, Cham (2020). https://doi.org/10.1007/978-3-030-64834-3_1

    Chapter  Google Scholar 

  19. Campanelli, M., Hall-Andersen, M.: Veksel: simple, efficient, anonymous payments with large anonymity sets from well-studied assumptions. IACR Cryptology ePrint Archive 2021/327 (2021)

    Google Scholar 

  20. Catalano, D., Fiore, D.: Vector commitments and their applications. In: Kurosawa, K., Hanaoka, G. (eds.) PKC 2013. LNCS, vol. 7778, pp. 55–72. Springer, Heidelberg (2013). https://doi.org/10.1007/978-3-642-36362-7_5

    Chapter  Google Scholar 

  21. Engelmann, F., Müller, L., Peter, A., Kargl, F., Bösch, C.: SwapCT: Swap confidential transactions for privacy-preserving multi-token exchanges. PoPETs 2021(4), 270–290 (2021). https://doi.org/10.2478/popets-2021-0070

    Article  Google Scholar 

  22. Farashahi, R.R., Fouque, P.A., Shparlinski, I., Tibouchi, M., Voloch, J.: Indifferentiable deterministic hashing to elliptic and hyperelliptic curves. Math. Comput. 82(281), 491–512 (2013)

    Article  MathSciNet  Google Scholar 

  23. Fauzi, P., Meiklejohn, S., Mercer, R., Orlandi, C.: Quisquis: a new design for anonymous cryptocurrencies. In: Galbraith, S.D., Moriai, S. (eds.) ASIACRYPT 2019, Part I. LNCS, vol. 11921, pp. 649–678. Springer, Cham (2019). https://doi.org/10.1007/978-3-030-34578-5_23

    Chapter  Google Scholar 

  24. Ganesh, C., Orlandi, C., Pancholi, M., Takahashi, A., Tschudi, D.: Fiat-Shamir bulletproofs are non-malleable (in the algebraic group model). In: Dunkelman, O., Dziembowski, S. (eds.) EUROCRYPT 2022, Part II. LNCS, vol. 13276, pp. 397–426. Springer, Heidelberg (2022). https://doi.org/10.1007/978-3-031-07085-3_14

    Chapter  Google Scholar 

  25. Grassi, L., Khovratovich, D., Rechberger, C., Roy, A., Schofnegger, M.: Poseidon: a new hash function for zero-knowledge proof systems. In: 30th USENIX Security Symposium (2021)

    Google Scholar 

  26. Hopwood, D., Bowe, S., Hornby, T., Wilcox, N.: Zcash protocol specification, version 2021.1.15 (2021)

    Google Scholar 

  27. Kate, A., Zaverucha, G.M., Goldberg, I.: Constant-size commitments to polynomials and their applications. In: Abe, M. (ed.) ASIACRYPT 2010. LNCS, vol. 6477, pp. 177–194. Springer, Heidelberg (2010). https://doi.org/10.1007/978-3-642-17373-8_11

    Chapter  Google Scholar 

  28. Lai, R.W.F., Malavolta, G., Ronge, V.: Succinct arguments for bilinear group arithmetic: practical structure-preserving cryptography. In: Cavallaro, L., Kinder, J., Wang, X., Katz, J. (eds.) ACM CCS 2019, pp. 2057–2074. ACM Press, November 2019. https://doi.org/10.1145/3319535.3354262

  29. Lai, R.W.F., Ronge, V., Ruffing, T., Schröder, D., Thyagarajan, S.A.K., Wang, J.: Omniring: scaling private payments without trusted setup. In: Cavallaro, L., Kinder, J., Wang, X., Katz, J. (eds.) ACM CCS 2019, pp. 31–48. ACM Press, November 2019. https://doi.org/10.1145/3319535.3345655

  30. Libert, B., Yung, M.: Concise mercurial vector commitments and independent zero-knowledge sets with short proofs. In: Micciancio, D. (ed.) TCC 2010. LNCS, vol. 5978, pp. 499–517. Springer, Heidelberg (2010). https://doi.org/10.1007/978-3-642-11799-2_30

    Chapter  Google Scholar 

  31. Noether, S., Mackenzie, A., et al.: Ring confidential transactions. Ledger 1, 1–18 (2016)

    Article  Google Scholar 

  32. Poelstra, A., Back, A., Friedenbach, M., Maxwell, G., Wuille, P.: Confidential assets. In: Zohar, A., et al. (eds.) FC 2018. LNCS, vol. 10958, pp. 43–63. Springer, Heidelberg (2019). https://doi.org/10.1007/978-3-662-58820-8_4

    Chapter  Google Scholar 

  33. Setty, S., Angel, S., Gupta, T., Lee, J.: Proving the correct execution of concurrent services in zero-knowledge. In: 13th USENIX Symposium on Operating Systems Design and Implementation, OSDI 2018, pp. 339–356 (2018)

    Google Scholar 

  34. Tibouchi, M., Kim, T.: Improved elliptic curve hashing and point representation. Des. Codes Cryptogr. 82(1), 161–177 (2017)

    Article  MathSciNet  Google Scholar 

  35. Tomescu, A., Xia, Y., Newman, Z.: Authenticated dictionaries with cross-incremental proof (dis)aggregation. Cryptology ePrint Archive, Report 2020/1239 (2020). https://eprint.iacr.org/2020/1239

  36. Valiant, P.: Incrementally verifiable computation or proofs of knowledge imply time/space efficiency. In: Canetti, R. (ed.) TCC 2008. LNCS, vol. 4948, pp. 1–18. Springer, Heidelberg (2008). https://doi.org/10.1007/978-3-540-78524-8_1

    Chapter  MATH  Google Scholar 

  37. Yi, Z., Ye, H., Dai, P., Tongcheng, S., Gelfer, V.: Confidential assets on MimbleWimble. Cryptology ePrint Archive, Report 2019/1435 (2019). https://eprint.iacr.org/2019/1435

Download references

Acknowledgements

Research supported by: the Concordium Blockhain Research Center, Aarhus University, Denmark; the Carlsberg Foundation under the Semper Ardens Research Project CF18-112 (BCM); the European Research Council (ERC) under the European Unions’s Horizon 2020 research and innovation programme under grant agreement No 803096 (SPEC). This work was partly produced while Matteo Campanelli and Felix Engelmann were affiliated with Aarhus University.

Author information

Authors and Affiliations

  1. Protocol Labs, San Francisco, USA

    Matteo Campanelli

  2. IT University of Copenhagen, Copenhagen, Denmark

    Felix Engelmann

  3. Aarhus University, Aarhus, Denmark

    Claudio Orlandi

Authors
  1. Matteo Campanelli
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Felix Engelmann
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Claudio Orlandi
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Felix Engelmann .

Editor information

Editors and Affiliations

  1. Università degli Studi di Salerno, Fisciano, Italy

    Clemente Galdi

  2. University of California at Irvine, Irvine, CA, USA

    Stanislaw Jarecki

Rights and permissions

Reprints and permissions

Copyright information

© 2022 The Author(s), under exclusive license to Springer Nature Switzerland AG

About this paper

Check for updates. Verify currency and authenticity via CrossMark

Cite this paper

Campanelli, M., Engelmann, F., Orlandi, C. (2022). Zero-Knowledge for Homomorphic Key-Value Commitments with Applications to Privacy-Preserving Ledgers. In: Galdi, C., Jarecki, S. (eds) Security and Cryptography for Networks. SCN 2022. Lecture Notes in Computer Science, vol 13409. Springer, Cham. https://doi.org/10.1007/978-3-031-14791-3_33

Download citation

  • DOI: https://doi.org/10.1007/978-3-031-14791-3_33

  • Published:

  • Publisher Name: Springer, Cham

  • Print ISBN: 978-3-031-14790-6

  • Online ISBN: 978-3-031-14791-3

  • eBook Packages: Computer ScienceComputer Science (R0)

Publish with us

Policies and ethics

Search

Navigation