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

Statement: AI-written, not yet formalized. Proof: open – no attempt yet.

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 · Download LaTeX source

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.

Open, and the paper’s own tool cannot settle it.

What is known, both ends. From the trade-off \(\binom{\alpha + d}{d+1} \ge n\) (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 known construction — from indistinguishability obfuscation, from CDH or LWE, and the verifiable variant — achieves \(O(\log n)\).

Why the existing argument stops. The attack converts sparsity of the update graph into a security break by finding a skipping sequence: the paper shows every forward DAG with \(\binom{k+d}{d+1}\) vertices and out-degree at most \(d\) contains one of size \(k\). Appendix C proves that bound tight. So no sharpening of the skipping-sequence count can reach \(\log n\); the improvement has to come from a different combinatorial object, or from an attack that does not go through graph sparsity at all.

And a reason to suspect the conjecture is false. Replacing the binary merging structure behind the known constructions with a \(b\)-ary one, \(b = \mathrm{poly}(\log n)\), would plausibly keep the public parameters at \(\mathrm{poly}(\kappa, \log n)\) — the roots of \((b-1)\log_b n\) trees — while only \(\log_b n = O(\log n / \log\log n)\) merges affect any given party. That would meet the paper’s bound exactly and refute this statement. The observation is the drafter’s rather than the paper’s, and it has not been checked whether the delayed-encryption layer of the known constructions survives the change.

This is 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 has no more to give. The candidate refutation above is the reason to read the statement as a genuine question rather than a formality — if the \(b\)-ary construction works, the answer is \(\Theta(\log n / \log\log n)\) and the existing bound was already tight.

Either resolution says something about the primitive rather than about the proof. A proof of \(\Omega(\log n)\) would mean Merkle-style constructions are optimal; a refutation would mean the accumulator shape everyone has used is the wrong one.

The companion statement c/0026 asks the orthogonal question — whether the lower bound survives at all once update times may depend on the registered keys.

Prove \(\Omega(\log n)\), or construct a compact RBE with \(o(\log n)\) updates and fixed update times.
Check the \(b\)-ary candidate: does a \(\mathrm{poly}(\log n)\)-ary merging structure keep the parameters compact and the delayed-encryption layer intact?
Find a combinatorial object beyond skipping sequences, given that the skipping-sequence bound is tight.
Settle the same question for the amortized rather than worst-case number of updates.
Formalize the statement in Lean. Forward DAGs, out-degree over the first \(n\) nodes, and fixed-update-graph completeness need writing first.

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.