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 (ϵ,T) to those of the reduction’s (ϵproof,Tproof) using this technique: One originates to Waters (Eurocrypt 2005) who introduced the famous artificial abort step to prove his IBE, achieving (ϵproof,Tproof)=(O(ϵ/Q),T+O(Q2/ϵ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 (ϵproof,Tproof)=(O(ϵ2/Q),T+O(Q)). Importantly, the current reductions all loose quadratically in ϵ. 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 (ϵproof,Tproof)=(O(ϵ3/2/Q),T+O(Q)), breaking the quadratic dependence on ϵ. 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 (ϵproof,Tproof)=(O(ϵ/Q),T+O(Q)). This is a much better reduction than the previously known (O(ϵ3/Q2),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.
