Form: lower bound

Statements with form: lower-bound. This page only exists because at least one statement currently uses this value – if you add a statement with a new form value not listed under Problems, copy this page as the starting point for its facet page (see CONTRIBUTING.md).

Status	Statement	Tags
	Quadratic attack on 3-NIKE, Shoup’s model Open in Shoup’s model. Settled by the source paper in Maurer’s model for every K at least 3, including imperfect correctness; its own three-party Shoup construction achieves only an n^1.5 gap, so the truth for three parties lies somewhere between n^1.5 and n^2. 5 open	ggmlower-boundresearch-opennew-idea (ai)
	Optimal martingale gap finders Open for small mu. Settled when mu is bounded away from zero, where the Cleve-Impagliazzo gap finder already gives the conjectured product; for general mu the known bound is a factor mu short and the paper states it does not know the answer. 5 open	standardlower-boundresearch-opennew-idea (ai)
	Generalized mirror theory The fully generalized Mirror Theory bound for arbitrary cycle-consistent multi-graphs up to the information-theoretic limit is open; current techniques only reach component size O(N^{1/4}). 2 open	standardlower-boundresearch-opennew-idea (ai)
	RBE needs Ω(log n) updates Open. The number of updates for fixed-update-time schemes with polylogarithmic public parameters is known to lie between Omega(log n / log log n) and O(log n); this statement picks the upper endpoint, and the paper’s own tool is proved tight, so it cannot decide the question. 5 open	standardlower-boundresearch-opennew-idea (ai)
	Simon-oracle amplification, strong version Open. The version without the collision finder is known only when the one-way function is itself a random oracle; with an arbitrary one-way function, with or without the collision finder, nothing is established. 5 open	otherlower-boundresearch-opennew-idea (ai)
	Censoring can only hurt Open. The censored side is proved at essentially optimal round count with matching lower bounds; what is missing is the transfer of any such bound to uncensored AES at the same round count. 5 open	standardlower-boundresearch-opennew-idea (ai)
	RBE update bound, key-dependent schedules Open exactly when the update schedule may depend on the sampled public keys, which is the standard on-demand completeness notion. Proved when the schedule is any fixed function of registration times (Theorem 4.1) or of the registered identity names and the CRS (Theorem 4.12). 5 open	standardlower-boundresearch-openadaptation (ai)