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.

This paper describes the first constructions of identity-based broadcast encryption (IBBE) using Type-3 pairings, which can be proved secure against adaptive-identity attacks based on the Symmetric eXternal Diffie-Hellman assumption (which is a static, if not a standard, assumption) achieving a security degradation which is not exponential in the size of the target identity set. The constructions are obtained by extending the currently known most efficient identity-based encryption scheme proposed by Jutla and Roy in 2013. The new constructions fill both a practical and a theoretical gap in the literature on efficient IBBE schemes.

Bellare and Kohno (2004) introduced the notion of balance to quantify the resistance of a hash function$h$to a generic collision attack. Motivated by their work, we consider the problem of quantifying the resistance of$h$to a generic multicollision attack. To this end, we introduce the notion of$r$-balance$\mu_{r}(h)$of$h$and obtain bounds on the success probability of finding an$r$-collision in terms of$\mu_{r}(h)$. These bounds show that for a hash function with$m$image points, if the number of trials$q$is$\Theta\left (rm^{\left ({{r-1}\over{r}}\right)\mu_{r}(h)}\right)$, then it is possible to find$r$-collisions with a significant probability of success. The behavior of random functions and the expected number of trials to obtain an$r$-collision is studied. These results extend and complete the earlier results obtained by Bellare and Kohno (2004) for collisions (i.e.,$r=2$). Going beyond their work, we provide a new design criteria to provide quantifiable resistance to generic multicollision attacks. Further, we make a detailed probabilistic investigation of the variation of$r$-balance over the set of all functions and obtain support for the view that most functions have$r$-balance close to one.