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 .