Update Lower Bounds for Registration-Based Encryption with Key-Dependent Update Times
Statement: AI-written, not yet formalized. Proof: human draft, not yet independently reviewed, not yet formalized.
Registration-based encryption keeps a compact public parameter and charges parties for updates: as others register, a party occasionally needs a fresh opening before it can decrypt again. The source paper proves that \(\Omega(\log n / \log\log n)\) updates are necessary — but only when the schedule of updates is fixed in advance. The standard completeness notion is on demand: decryption returns “fetch an update” when it needs one, so when updates happen can depend on the sampled public keys. Whether the lower bound survives that is the conjecture.
View PDF · LaTeX source · Formal statement — not yet formalized
Let \(\Pi = (\mathsf{Gen}, \mathsf{Reg}, \mathsf{Enc}, \mathsf{Upd}, \mathsf{Dec})\) be an RBE scheme that is \(\rho\)-complete with on-demand updates, and write \(n\) for the number of registrations, \(d(n)\) for the number of updates any one identity needs over the first \(n\), and \(\alpha(n)\) for the size of the public parameter.
Conjecture. For every \(n\), every \(\ell\) with \[n \ \ge\ \binom{\ell + d(n)}{\,d(n)+1\,},\] and every \(\delta = 1/\mathrm{poly}(\kappa)\), there is a \(\mathrm{poly}(\kappa)\)-time adversary that registers at most \(n\) identities and wins the \(0\)-corruption security game with probability at least \[\rho \ -\ \sqrt{\frac{\alpha(n)\ln 2}{2\ell}}\ -\ \delta.\]
In particular, for each fixed \(\kappa\): if \(\Pi\) is \(\rho\)-complete with \(\rho \ge 0.99\), is \(0\)-corruption secure, and has \(\alpha(n) \le \mathrm{poly}(\kappa, \log n)\), then \(d(n)\) is not \(o(\log n / \log\log n)\) — there are a constant \(c > 0\) and infinitely many \(n\) with \(d(n) \ge c \log n / \log\log n\).
One threshold to check. The corollary is transcribed with \(\rho \ge 0.99\) where the source’s proof writes \(\rho > 0.99\). The arithmetic goes through at \(0.99\) either way, but a reader reconciling the two documents should know the inequality was not strict in the original.
Sources
- Mahmoody, Qi, and Rahimi. Lower Bounds for the Number of Decryption Updates in Registration-Based Encryption. Cryptology ePrint Archive, Report 2022/1285; TCC 2022, pp. 559–587. Theorem 1.1 (the \(\binom{\alpha+d}{d+1} \ge n\) trade-off), Theorem 4.1 and Corollary 4.2, Theorem 4.12, and Section 4.4’s statement of what the extension does not cover.
- Garg, Hajiabadi, Mahmoody, and Rahimi. Registration-based encryption: removing private-key generator from IBE. TCC 2018, pp. 689–718. Where the primitive is introduced.
- Garg, Hajiabadi, Mahmoody, Rahimi, and Sekar. Registration-based encryption from standard assumptions. PKC 2019, pp. 63–93. The construction from CDH or LWE.
- Goyal and Vusirikala. Verifiable registration-based encryption. CRYPTO 2020, Part I, LNCS 12170, pp. 621–651. The verifiable variant, also spending \(\Theta(\log n)\) updates.
View PDF — no proof written yet · LaTeX source — no proof written yet · Formal proof — not yet formalized
Resolved. Wei Qi, Tight Lower Bound on Witness Update Frequency in Additive Positive Accumulators (IACR Communications in Cryptology, 2026) — a co-author of the source paper — closes exactly the gap this page identified.
What was proved before. Theorem 4.1 of the source gave the bound when the update schedule is a fixed function of the registration times. Theorem 4.12 extended it to schedules that are any fixed function of the sequence of registered identity names and of the CRS — but explicitly not of the keys.
What the new paper does. It generalizes the lower-bound framework to additive positive accumulators in general, and — critically — removes the fixed-update-time assumption entirely, via a new combinatorial structure the paper calls a falling-step sequence: a strengthening of the source’s skipping sequence, built to survive the resampling a value-dependent schedule forces on the counting argument (a skipping sequence found in one execution’s update graph is not guaranteed to still be one once the graph itself depends on the sampled values; a falling-step sequence’s defining property is stable under that resampling). Quoting the paper directly: “Crucially, our lower bound shows that allowing update times to depend on the registered values does not reduce the number of updates required for soundness.” — precisely the key-dependent, on-demand case this page’s conjecture was about, stated as an explicit resolution: “thereby resolving the open problem left in [MQR22] [the source paper].”
The gap between the settled and open cases used to be narrow on paper and wide in practice — every deployed-style RBE hands out updates on demand, which is exactly the case the source paper’s own techniques didn’t reach. That gap is now closed: the lower bound was never an artifact of the proof being convenient rather than general: it holds for the schedules an implementation actually uses too.
The companion statement c/0027 — whether the bound is tight even in the originally settled case — is refuted by a related paper from the same author; see that page.