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 , \textsf{T})\) to those of the reduction’s ( \(\epsilon _\textsf{proof}, \textsf{T}_\textsf{proof}\) ) using this technique: One originates to Waters (Eurocrypt 2005) who introduced the famous artificial abort step to prove his IBE, achieving \((\epsilon _\textsf{proof}, \textsf{T}_\textsf{proof}) = (O(\epsilon /Q), \textsf{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 _\textsf{proof}, \textsf{T}_\textsf{proof}) = (O(\epsilon ^2/Q), \textsf{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 _\textsf{proof}, \textsf{T}_\textsf{proof}) = (O(\epsilon ^{3/2}/Q), \textsf{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 _\textsf{proof}, \textsf{T}_\textsf{proof}) = (O(\epsilon /Q), \textsf{T} + O(Q))\) . This is a much better reduction than the previously known \( (O(\epsilon ^3/Q^2), \textsf{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.