Logarithmically Many Decryption Updates Are Necessary in Compact Registration-Based Encryption

•

Statement: AI-written, not yet formalized. Refutation: human draft, not yet independently reviewed, not yet formalized.

Registration Based Encryption

Every known registration-based encryption scheme spends \(\Theta(\log n)\) decryption updates per party, and the best lower bound is \(\Omega(\log n / \log\log n)\). One of the two is loose and nobody knows which. This statement picks the lower bound’s side: that \(\log n\) is the truth. Its interest is that the tool which proved the weaker bound is provably out of room — the source paper’s own appendix shows the counting argument is tight — so whichever way it goes, settling it needs something new.

View PDF · LaTeX source · Formal statement — not yet formalized

Let \(\Pi\) be an RBE scheme and let \(G\) be an infinite forward DAG such that \(\Pi\) is \(\rho\)-complete with fixed update graph \(G\) for some \(\rho \ge 0.99\), and \(0\)-corruption secure. Write \(\mathrm{outdeg}(G_n)\) for the worst-case number of updates an identity needs over the first \(n\) registrations, and \(\alpha(n)\) for the public-parameter size; suppose \(\alpha(n) \le p(\kappa, \log n)\) for some polynomial \(p\).

Conjecture. For every \(\kappa\) there are a constant \(c > 0\), depending on \(\Pi\), \(p\) and \(\kappa\), and infinitely many \(n\) such that \[\mathrm{outdeg}(G_n) \ \ge\ c \log n.\] Equivalently: \(\mathrm{outdeg}(G_n)\) is not \(o(\log n)\).

This is the source’s Corollary 4.2(3) with \(\log n / \log\log n\) replaced by \(\log n\) — same quantifier structure, same fixed \(\kappa\), same “infinitely many \(n\)”, same restriction of \(\mathrm{outdeg}\) to the first \(n\) nodes.

The direction is a choice. The paper poses this as “close the gap” and does not commit to a side. Picking the lower-bound direction is what makes it a definite claim to prove or refute; a reader may reasonably prefer the neutral phrasing.

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, Corollary 4.2(3) — the statement above with the weaker bound — the skipping-sequence lemma, and Appendix C proving it tight.
  • Garg, Hajiabadi, Mahmoody, and Rahimi. Registration-based encryption: removing private-key generator from IBE. TCC 2018, pp. 689–718. The \(O(\log n)\) upper bound, from obfuscation.
  • Garg, Hajiabadi, Mahmoody, Rahimi, and Sekar. Registration-based encryption from standard assumptions. PKC 2019, pp. 63–93. The same upper bound from CDH or LWE.
  • Goyal and Vusirikala. Verifiable registration-based encryption. CRYPTO 2020, Part I, LNCS 12170, pp. 621–651. The verifiable variant.

View PDF — no proof written yet · LaTeX source — no proof written yet · Formal proof — not yet formalized

Refuted. Mahmoody and Qi, Online Mergers and Applications to Registration-Based Encryption and Accumulators (ITC 2023), construct a compact RBE scheme with \(d(n) = O(\log n / \log\log n)\) decryption updates — strictly below the \(\Omega(\log n)\) this statement conjectured, and matching the known lower bound exactly.

What was known before, both ends. From the trade-off \(\binom{\alpha+d}{d+1} \ge n\) (source Theorem 1.1), with \(\alpha \le \mathrm{poly}(\kappa,\log n)\), one gets \(d \ge \Omega(\log n/\log\log n)\) (Corollary 4.2). Every construction known at the time — from indistinguishability obfuscation, from CDH or LWE, and the verifiable variant — achieved only \(O(\log n)\).

The construction, and how it relates to this page’s own speculation. This page had already conjectured, before finding this paper, that a \(b\)-ary merging structure with \(b = \mathrm{poly}(\log n)\) would plausibly close the gap — replacing the binary tree-merging behind the known constructions with higher-arity merges to cut the number of merges any one party is exposed to. Mahmoody–Qi’s actual fix is a genuine generalization of that idea: an online merger abstraction (their Construction 18/28) with a tunable merge arity \(d(n)\), where the public parameter length and update count trade off as \(\binom{|\mathrm{acc}_n| + d(n) + 1}{d(n)+1} > n\) in the general (additive-accumulator) framework their companion 2026 paper (see c/0026) later builds on. Setting \(d(n) = \log n/\log\log n\) gives update count \(\log n/\log\log n\) with public parameter \(\mathrm{poly}(\kappa,\log n)\) (their Remark 30), matching the lower bound and refuting this page’s conjectured \(\Omega(\log n)\). Quoting the paper directly: “resolving the open question of Mahmoody, Rahimi, Qi [TCC’22] who proved that Ω(log n / log log n) number of decryption updates are necessary.”

One thing not yet independently checked. The paper’s own security proof for the construction is sketched, not fully re-derived, deferring most of the argument to the original RBE security proof of Garg–Hajiabadi–Mahmoody–Rahimi (TCC 2018); see Open obligations.

This was the cleanest kind of open problem: a known upper bound, a known lower bound a \(\log\log\) factor apart, and a proof that the technique behind the lower bound had no more to give. It resolved in the direction this page thought more likely — the accumulator shape everyone had used (binary tree merging) was not the tight one; a higher-arity online merger is.

The companion statement c/0026 — whether the lower bound survives at all once update times may depend on the registered keys — is proved (not refuted) by a related, later paper from the same author (Wei Qi, 2026); see that page.