How many decryption updates does registration-based encryption need?

Resolved both ways: the bound survives key-dependent schedules, and Θ(log n / log log n) — not Θ(log n) — is the truth

Motivation

Registration-based encryption removes the private-key generator that identity-based encryption depends on. Parties register their own public keys with a transparent accumulator, and a compact public parameter — \(\mathrm{poly}(\kappa, \log n)\) bits, not \(\Theta(n)\) — is all a sender needs to encrypt to an identity. The price is updates: as later parties register, the accumulator changes, and a registered party occasionally needs a fresh opening before it can decrypt again. How often is the question this hub tracks, and it is the one quantity that decides whether the primitive is practical.

Every known construction spends \(\Theta(\log n)\) updates per party. The source paper proves a lower bound of \(\Omega(\log n / \log\log n)\), from a clean combinatorial trade-off: if the public parameter is \(\alpha\) bits and each party needs at most \(d\) updates, then \(\binom{\alpha + d}{d+1} \ge n\). Two things are then open, and they are the two statements here — whether the bound survives when when to update may depend on the registered keys, and whether the true answer is \(\log n / \log\log n\) or \(\log n\).

Provenance and history

One source paper: Mahmoody, Qi and Rahimi, Lower Bounds for the Number of Decryption Updates in Registration-Based Encryption, ePrint 2022/1285; TCC 2022, pp. 559–587. Bibliographic details verified against ePrint and Crossref on 18 August 2026; the harvester’s record carried no venue for it.

Both statements were drafted by scripts/harvest_conjectures.py from that PDF and are AI-written and unreviewed, as the status badges say. One repair was applied before publication: the first draft asserted a specific accumulator shape — a Merkle forest merged like a binary counter — for the known constructions, where the paper describes a Merkle-tree root; the claim is now attributed to the construction papers rather than to this one.

Both open questions closed within a year, by the same two authors. Mahmoody and Qi, Online Mergers and Applications to Registration-Based Encryption and Accumulators (ITC 2023) refute c/0027 with a higher-arity “online merger” construction achieving \(O(\log n/\log\log n)\) updates — matching, not beating, the lower bound, so that endpoint of the gap was the tight one all along. Wei Qi’s later Tight Lower Bound on Witness Update Frequency in Additive Positive Accumulators (IACR Communications in Cryptology, 2026) proves c/0026, generalizing the lower-bound framework to schedules that depend on the sampled keys themselves via a new combinatorial object (a falling-step sequence). Between them, both cells this hub was tracking are now settled.

Parameter lattice

Two axes: what the update schedule may depend on, and how tight the bound is.

update schedule may depend on lower bound status
registration times only \(\Omega(\log n/\log\log n)\) settled — Theorem 4.1
registered identity names and the CRS \(\Omega(\log n/\log\log n)\) settled — Theorem 4.12
the sampled public keys (on-demand updates) \(\Omega(\log n/\log\log n)\) resolved — c/0026, Qi 2026
regime known lower bound known upper bound status
fixed update times, \(\mathrm{poly}(\kappa,\log n)\) parameters \(\Omega(\log n/\log\log n)\) \(O(\log n/\log\log n)\) resolved (refuted) — c/0027, Mahmoody–Qi 2023
constant \(d\) \(\alpha \ge \Omega(n^{1/(d+1)})\) — settled, from the same trade-off

The second table’s gap is now closed at the lower endpoint: Mahmoody–Qi’s online-merger construction (ITC 2023) achieves \(O(\log n/\log\log n)\) updates, matching rather than beating the bound, so \(\Theta(\log n/\log\log n)\) was the truth and c/0027’s \(\Omega(\log n)\) conjecture is refuted. The first table’s gap closes in the other direction: Wei Qi’s 2026 paper proves the same \(\Omega(\log n/\log\log n)\) bound survives even when the schedule depends on the sampled keys, so c/0026 is proved as conjectured.

Statements in this hub