Welcome to the resource topic for
**2024/1481**

**Title:**

Tighter Adaptive IBEs and VRFs: Revisiting Waters’ Artificial Abort

**Authors:**
Goichiro Hanaoka, Shuichi Katsumata, Kei Kimura, Kaoru Takemure, Shota Yamada

**Abstract:**

One of the most popular techniques to prove adaptive security of identity-based encryptions (IBE) and verifiable random functions (VRF) is the partitioning technique. Currently, there are only two methods to relate the adversary’s advantage and runtime (\epsilon, {\sf T}) to those of the reduction’s (\epsilon_{\sf proof}, {\sf T}_{\sf proof}) using this technique: One originates to Waters (Eurocrypt 2005) who introduced the famous artificial abort step to prove his IBE, achieving (\epsilon_{\sf proof}, {\sf T}_{\sf proof}) = (O(\epsilon/Q), {\sf T} + O(Q^2/\epsilon^2)), where Q is the number of key queries. Bellare and Ristenpart (Eurocrypt 2009) provide an alternative analysis for the same scheme removing the artificial abort step, resulting in (\epsilon_{\sf proof}, {\sf T}_{\sf proof}) = (O(\epsilon^2/Q), {\sf T} + O(Q)). Importantly, the current reductions all loose quadratically in \epsilon.

In this paper, we revisit this two decade old problem and analyze proofs based on the partitioning technique through a new lens. For instance, the Waters IBE can now be proven secure with (\epsilon_{\sf proof}, {\sf T}_{\sf proof}) = (O(\epsilon^{3/2}/Q), {\sf T} + O(Q)), breaking the quadratic dependence on \epsilon. At the core of our improvement is a finer estimation of the failing probability of the reduction in Waters’ original proof relying on artificial abort. We use Bonferroni’s inequality, a tunable inequality obtained by cutting off higher order terms from the equality derived by the inclusion-exclusion principle.

Our analysis not only improves the reduction of known constructions but also opens the door for new constructions. While a similar improvement to Waters IBE is possible for the lattice-based IBE by Agrawal, Boneh, and Boyen (Eurocrypt 2010), we can slightly tweak the so-called partitioning function in their construction, achieving (\epsilon_{\sf proof}, {\sf T}_{\sf proof}) = (O(\epsilon/Q), {\sf T} + O(Q)). This is a much better reduction than the previously known (O(\epsilon^3/Q^2), {\sf T} + O(Q)). We also propose the first VRF with proof and verification key sizes sublinear in the security parameter under the standard d-LIN assumption, while simultaneously improving the reduction cost compared to all prior constructions.

**ePrint:**
https://eprint.iacr.org/2024/1481

See all topics related to this paper.

Feel free to post resources that are related to this paper below.

**Example resources include:**
implementations, explanation materials, talks, slides, links to previous discussions on other websites.

For more information, see the rules for Resource Topics .