Document Open Access Logo

Functional Commitment Schemes: From Polynomial Commitments to Pairing-Based Accumulators from Simple Assumptions

Authors Benoît Libert, Somindu C. Ramanna, Moti Yung

PDF
Thumbnail PDF

File

LIPIcs.ICALP.2016.30.pdf
  • Filesize: 0.51 MB
  • 14 pages

Document Identifiers

Author Details

Benoît Libert
Somindu C. Ramanna
Moti Yung

Cite As Get BibTex

Benoît Libert, Somindu C. Ramanna, and Moti Yung. Functional Commitment Schemes: From Polynomial Commitments to Pairing-Based Accumulators from Simple Assumptions. In 43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 55, pp. 30:1-30:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016) https://doi.org/10.4230/LIPIcs.ICALP.2016.30

Abstract

We formalize a cryptographic primitive called functional commitment (FC) which can be viewed as a generalization of vector commitments (VCs), polynomial commitments and many other special kinds of commitment schemes. A non-interactive functional commitment allows committing to a message in such a way that the committer has the flexibility of only revealing a function of the committed message during the opening phase. We provide constructions for the functionality of linear functions, where messages consist of vectors over some domain and commitments can later be opened to a specific linear function of the vector coordinates. An opening for a function thus generates a witness for the fact that the function indeed evaluates to a given value for the committed message. One security requirement is called function binding and requires that no adversary be able to open a commitment to two different evaluations for the same function.

We propose a construction of functional commitment for linear functions based on constantsize assumptions in composite order groups endowed with a bilinear map. The construction has commitments and openings of constant size (i.e., independent of n or function description) and is perfectly hiding - the underlying message is information theoretically hidden. Our security proofs build on the Déjà Q framework of Chase and Meiklejohn (Eurocrypt 2014) and its extension by Wee (TCC 2016) to encryption primitives, thus relying on constant-size subgroup decisional assumptions. We show that FC for linear functions are sufficiently powerful to solve four open problems. They, first, imply polynomial commitments, and, then, give cryptographic accumulators (i.e., an algebraic hash function which makes it possible to efficiently prove that some input belongs to a hashed set). In particular, specializing our FC construction leads to the first pairing-based polynomial commitments and accumulators for large universes known to achieve security under simple assumptions. We also substantially extend our pairing-based accumulator to handle subset queries which requires a non-trivial extension of the Déjà Q framework.

Subject Classification

Keywords
  • Cryptography
  • commitment schemes
  • functional commitments
  • accumulators
  • provable security
  • pairing-based
  • simple assumptions.

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

References

  1. Niko Baric and Birgit Pfitzmann. Collision-Free Accumulators and Fail-Stop Signature Schemes Without Trees. In EUROCRYPT'97, volume 1233 of LNCS, pages 480-494. Springer, 1997. Google Scholar
  2. Josh Cohen Benaloh and Michael de Mare. One-Way Accumulators: A Decentralized Alternative to Digital Sinatures (Extended Abstract). In EUROCRYPT'93, volume 765 of LNCS, pages 274-285. Springer, 1993. Google Scholar
  3. Manuel Blum, Paul Feldman, and Silvio Micali. Non-Interactive Zero-Knowledge and Its Applications (Extended Abstract). In STOC 1988, pages 103-112. ACM, 1988. Google Scholar
  4. Dan Boneh and Henry Corrigan-Gibbs. Bivariate Polynomials Modulo Composites and Their Applications. In ASIACRYPT 2014, volume 8873 of LNCS, pages 42-62. Springer, 2014. Google Scholar
  5. Dan Boneh, Craig Gentry, and Brent Waters. Collusion Resistant Broadcast Encryption with Short Ciphertexts and Private Keys. In CRYPTO 2005, volume 3621 of LNCS, pages 258-275. Springer, 2005. Google Scholar
  6. Dan Boneh, Amit Sahai, and Brent Waters. Functional Encryption: Definitions and Challenges. In TCC 2011, volume 6597 of LNCS, pages 253-273. Springer, 2011. Google Scholar
  7. Jan Camenisch, Maria Dubovitskaya, Kristiyan Haralambiev, and Markulf Kohlweiss. Composable and Modular Anonymous Credentials: Definitions and Practical Constructions. In ASIACRYPT 2015, volume 9453 of LNCS, pages 262-288. Springer, 2015. Google Scholar
  8. Jan Camenisch, Markulf Kohlweiss, and Claudio Soriente. An Accumulator Based on Bilinear Maps and Efficient Revocation for Anonymous Credentials. In PKC 2009, volume 5443 of LNCS, pages 481-500. Springer, 2009. Google Scholar
  9. Jan Camenisch and Anna Lysyanskaya. Dynamic Accumulators and Application to Efficient Revocation of Anonymous Credentials. In CRYPTO 2002, volume 2442 of LNCS, pages 61-76. Springer, 2002. Google Scholar
  10. Dario Catalano and Dario Fiore. Vector Commitments and Their Applications. In PKC 2013, volume 7778 of LNCS, pages 55-72. Springer, 2013. Google Scholar
  11. Dario Catalano, Dario Fiore, and Mariagrazia Messina. Zero-Knowledge Sets with Short Proofs. In EUROCRYPT 2008, volume 4965 of LNCS, pages 433-450. Springer, 2008. Google Scholar
  12. Melissa Chase, Alexander Healy, Anna Lysyanskaya, Tal Malkin, and Leonid Reyzin. Mercurial Commitments with Applications to Zero-Knowledge Sets. In EUROCRYPT 2005, Proceedings, volume 3494 of LNCS, pages 422-439. Springer, 2005. Google Scholar
  13. Melissa Chase and Sarah Meiklejohn. Déjà Q: Using Dual Systems to Revisit q-Type Assumptions. In EUROCRYPT 2014, volume 8441 of LNCS, pages 622-639. Springer, 2014. Google Scholar
  14. Benny Chor, Shafi Goldwasser, Silvio Micali, and Baruch Awerbuch. Verifiable Secret Sharing and Achieving Simultaneity in the Presence of Faults (Extended Abstract). In FOCS 1985, pages 383-395. IEEE Computer Society, 1985. Google Scholar
  15. David Derler, Christian Hanser, and Daniel Slamanig. Revisiting Cryptographic Accumulators, Additional Properties and Relations to Other Primitives. In CT-RSA 2015, volume 9048 of LNCS, pages 127-144. Springer, 2015. Google Scholar
  16. Cynthia Dwork, Moni Naor, Omer Reingold, and Larry J. Stockmeyer. Magic Functions. J. ACM, 50(6):852-921, 2003. Google Scholar
  17. Sergey Gorbunov, Vinod Vaikuntanathan, and Daniel Wichs. Leveled Fully Homomorphic Signatures from Standard Lattices. In STOC 2015, pages 469-477. ACM, 2015. Google Scholar
  18. Malika Izabachène, Benoît Libert, and Damien Vergnaud. Block-Wise P-Signatures and Non-interactive Anonymous Credentials with Efficient Attributes. In IMACC 2011, volume 7089 of LNCS, pages 431-450. Springer, 2011. Google Scholar
  19. Aniket Kate, Gregory M. Zaverucha, and Ian Goldberg. Constant-Size Commitments to Polynomials and Their Applications. In ASIACRYPT 2010, volume 6477 of LNCS, pages 177-194. Springer, 2010. Google Scholar
  20. Allison B. Lewko and Brent Waters. New Techniques for Dual System Encryption and Fully Secure HIBE with Short Ciphertexts. In TCC 2010, Proceedings, volume 5978 of LNCS, pages 455-479. Springer, 2010. Google Scholar
  21. Jiangtao Li, Ninghui Li, and Rui Xue. Universal Accumulators with Efficient Nonmembership Proofs. In ACNS 2007, volume 4521 of LNCS, pages 253-269. Springer, 2007. Google Scholar
  22. Benoît Libert and Moti Yung. Concise Mercurial Vector Commitments and Independent Zero-Knowledge Sets with Short Proofs. In TCC 2010, Proceedings, volume 5978 of LNCS, pages 499-517. Springer, 2010. Google Scholar
  23. Helger Lipmaa. Secure Accumulators from Euclidean Rings without Trusted Setup. In ACNS 2012, volume 7341 of LNCS, pages 224-240. Springer, 2012. Google Scholar
  24. Silvio Micali, Michael O. Rabin, and Joe Kilian. Zero-Knowledge Sets. In FOCS 2003, pages 80-91. IEEE Computer Society, 2003. Google Scholar
  25. Silvio Micali, Michael O. Rabin, and Salil P. Vadhan. Verifiable Random Functions. In FOCS'99, pages 120-130. IEEE Computer Society, 1999. Google Scholar
  26. Lan Nguyen. Accumulators from Bilinear Pairings and Applications. In CT-RSA 2005, volume 3376 of LNCS, pages 275-292. Springer, 2005. Google Scholar
  27. Rafail Ostrovsky, Charles Rackoff, and Adam D. Smith. Efficient Consistency Proofs for Generalized Queries on a Committed Database. In ICALP 2004, volume 3142 of LNCS, pages 1041-1053. Springer, 2004. Google Scholar
  28. Charalampos Papamanthou, Elaine Shi, Roberto Tamassia, and Ke Yi. Streaming Authenticated Data Structures. In EUROCRYPT 2013, volume 7881 of LNCS, pages 353-370. Springer, 2013. Google Scholar
  29. Charalampos Papamanthou, Roberto Tamassia, and Nikos Triandopoulos. Optimal Verification of Operations on Dynamic Sets. In CRYPTO 2011, volume 6841 of LNCS, pages 91-110. Springer, 2011. Google Scholar
  30. Torben P. Pedersen. Non-Interactive and Information-Theoretic Secure Verifiable Secret Sharing. In CRYPTO'91, volume 576 of LNCS, pages 129-140. Springer, 1991. Google Scholar
  31. Amit Sahai and Brent Waters. Fuzzy Identity-Based Encryption. In EUROCRYPT 2005, Proceedings, volume 3494 of LNCS, pages 457-473. Springer, 2005. Google Scholar
  32. Hoeteck Wee. Déjà Q: Encore! Un Petit IBE. In TCC 2016-A, volume 9563 of LNCS, pages 237-258. Springer, 2016. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact