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

Benoît Libert 1, 2, * Somindu Ramanna 1, 2 Moti Yung 3, 4
* Auteur correspondant
2 ARIC - Arithmetic and Computing
Inria Grenoble - Rhône-Alpes, LIP - Laboratoire de l'Informatique du Parallélisme
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 F (M) of the committed message during the opening phase. We provide constructions for the functionality of linear functions, where messages consist of a vectors of n elements over some domain D (e.g., m = (m_1,. .. , m_n) ∈ D_n) and commitments can later be opened to a specific linear function of the vector coordinates. An opening for a function F : D_n → R thus generates a witness for the fact that F (m) indeed evaluates to y ∈ R. One security requirement is called function binding and requires that no adversary be able to open a commitment to two different evaluations y, y for the same function F. We propose a construction of functional commitment for linear functions based on constant-size 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 builds 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 the 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.
Type de document :
Communication dans un congrès
43rd International Colloquium on Automata, Languages and Programming (ICALP 2016), Jul 2016, Rome, Italy. 2016, 43rd International Colloquium on Automata, Languages and Programming (ICALP 2016) -- Track A (Algorithms, Complexity and Games). 〈http://www.easyconferences.eu/icalp2016/〉
Liste complète des métadonnées

Littérature citée [46 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/hal-01306152
Contributeur : Benoit Libert <>
Soumis le : mercredi 10 août 2016 - 10:01:45
Dernière modification le : vendredi 20 avril 2018 - 15:44:26

Fichier

poly-commit.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : hal-01306152, version 4

Collections

Citation

Benoît Libert, Somindu Ramanna, Moti Yung. Functional Commitment Schemes: From Polynomial Commitments to Pairing-Based Accumulators from Simple Assumptions. 43rd International Colloquium on Automata, Languages and Programming (ICALP 2016), Jul 2016, Rome, Italy. 2016, 43rd International Colloquium on Automata, Languages and Programming (ICALP 2016) -- Track A (Algorithms, Complexity and Games). 〈http://www.easyconferences.eu/icalp2016/〉. 〈hal-01306152v4〉

Partager

Métriques

Consultations de la notice

253

Téléchargements de fichiers

141