Paper 2016/766
Functional Commitment Schemes: From Polynomial Commitments to PairingBased Accumulators from Simple Assumptions
Benoît Libert, Somindu C. Ramanna, and Moti Yung
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 noninteractive functional commitment allows committing to a message in such a way that the committer has the flexibility of only revealing a function $F(M)$ of the committed message during the opening phase. We provide constructions for the functionality of linear functions, where messages consist of vectors of $n$ elements over some domain $\mathcal{D}$ (e.g., $\vec{m} = (m_1,\ldots,m_n) \in \mathcal{D}^n$) and commitments can later be opened to a specific linear function $\sum_{i=1}^n m_i x_i = y \in \mathcal{R}$ of the vector coordinates. An opening for a function $F: \mathcal{D}^n \rightarrow \mathcal{R}$ thus generates a witness for the fact that $F(\vec{m})$ indeed evaluates to $y$. One security requirement is called \emph{function binding} and requires that it be infeasible open a commitment to two different evaluations $y,y'$ for the same function $F$. We propose a construction of functional commitment (FC) 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 \emph{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 constantsize subgroup decisional assumptions. We show that FCs 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 pairingbased polynomial commitments and accumulators for large universes, known to achieve security under simple assumptions. We also substantially extend our pairingbased accumulator to handle subset queries which requires a nontrivial extension of the Déjà Q framework.
Metadata
 Available format(s)
 Category
 Cryptographic protocols
 Publication info
 Published elsewhere. MAJOR revision.ICALP 2016
 Keywords
 Commitment schemesfunctional commitmentsaccumulatorspairingbasedsimple assumptions
 Contact author(s)
 somindu ramanna @ enslyon fr
 History
 20160810: received
 Short URL
 https://ia.cr/2016/766
 License

CC BY
BibTeX
@misc{cryptoeprint:2016/766, author = {Benoît Libert and Somindu C. Ramanna and Moti Yung}, title = {Functional Commitment Schemes: From Polynomial Commitments to PairingBased Accumulators from Simple Assumptions}, howpublished = {Cryptology ePrint Archive, Paper 2016/766}, year = {2016}, note = {\url{https://eprint.iacr.org/2016/766}}, url = {https://eprint.iacr.org/2016/766} }