Foundations of Cryptography

Statements tagged with the foundations area. This is a generated view, not a home directory – a statement can belong to several areas at once. See all statements for the full index, or the schema for what each column means.

Status Statement Tags
– Best-first search trees
Open, with no bound of any kind proved for the best-first algorithm on any class of query distributions. Exact optimality is already refuted by the paper’s own exhaustive search, so only the approximation ratio remains, and a workload on which greedy is off by an unbounded factor would settle it. 5 open 		standardtight-boundresearch-opennew-idea (ai)
– Dream DPT for a moderately hard function
Open: whether there exists a function family, and a standard fine-grained hardness hypothesis (the paper suggests NSETH as an example), for which solving t independent instances requires resources within a subexponentially small factor of solving them one at a time, with no loss in the exponent. The source reduces its permissionless consensus protocol to exactly this statement and leaves it unconstructed. 5 open 		standardassumptionresearch-opennew-idea (ai)IOG
– Four-party NIKE, quadratic, Maurer’s model
Open. Achieved in Shoup’s generic group model by the source paper (Construction 9, Theorem 10); in Maurer’s model the paper’s own O(n^2) attack sets a ceiling that a construction would meet exactly, and nothing is known about reaching it. 5 open 		ggmseparationresearch-opennew-idea (ai)
– 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)
– Partial-PKI consensus up to one-half resilience
Open: whether consensus is achievable at every resilience gamma < 1/2 in the paper’s permissionless common-random-string setting, by some protocol using any means of bootstrapping party identities. The source proves resilience up to 1/4(1-3*epsilon) via a specific protocol and proves 1/4 is tight only for the restricted class of protocols that sign everything they send and verify everything they receive; the gap to the classical 1/2 ceiling is open for arbitrary protocols. 5 open 		standardtight-boundresearch-opennew-idea (ai)IOG
– Split-source decomposition
Open for a query budget of two or more: whether a random oracle decomposes into bit-fixing mixtures when the advice is produced by two sources that never communicate. Proved and tight at q = 0, and proved at q = 1 under an extra hypothesis. 4 open 		romtight-boundresearch-opennew-idea (ai)
– CRS-free everlasting commitment from malicious PUFs
Open: whether everlasting UC commitment is achievable in the fully malicious token model with no trusted setup. The source achieves it with a common reference string (its Theorem 31) and explicitly leaves removing the CRS as a question, noting that the usual equivocation techniques do not transfer to the everlasting setting. 6 open 		otherassumptionresearch-opennew-idea (ai)
– Double-sided zero search
Open: whether finding x with H(x||0^n) = y||0^n is hard for a quantum adversary with polynomially many queries to a random permutation H and its inverse. The source proves it only under its own compressed-permutation-oracle soundness conjecture, as a usage example. 6 open 		otherlower-boundresearch-opennew-idea (ai)
– Level-optimal beyond disjunctions
Open beyond disjunctive queries, and the authors state it as a conjecture without naming the broader class – identifying one is part of the problem. Proved for every distribution supported on disjunctions, where the log n factor is also shown necessary. Wide open for conjunctive queries, where the paper’s proof technique demonstrably fails. 5 open 		standardtight-boundresearch-opennew-idea (ai)
– Logarithmic independence implies PRP
Open at independence order log n. The same implication is refuted at order 4 and at every constant order by an explicit construction; the logarithmic-order form is untouched, and no unconditional proof of it can be expected. 5 open 		standardcharacterizationresearch-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)
– No key agreement from GC-OWF
Open for round complexity growing with the security parameter. Proved in full for two messages, which is public-key encryption; the constant-round extension is sketched in the paper’s appendix without a theorem, its security half deferred to the PKE proof. 5 open 		otherseparationresearch-openadaptation (ai)
– OWFs are black-box useless for key agreement
Open in the general case, which the paper names as the central open problem left by its work. Settled for three restricted protocol classes: constant-query perfect, constant-round constant-query imperfect, and Merkle-type. 6 open 		otherimpossibilityresearch-opennew-idea (ai)
– OWFs are black-box helpful for CRHFs
Open in both directions. Two relaxations — distributional and class-reduction helpfulness — are proved conditional on the Simon-oracle amplification conjecture; neither yields the universal auxiliary primitive the full statement needs. 5 open 		otherseparationresearch-opennew-idea (ai)
– OWF minimality, non-black-box reductions
Open when the classical security implication is not witnessed by a black-box reduction between the two games. Settled affirmatively whenever it is, for uniform and non-uniform quantum adversaries alike, with the implementation reduction left arbitrary. 5 open 		standardequivalenceresearch-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)
– PKE from constant-noise planted k-XOR
Open: whether public-key encryption can be based on the hardness of planted k-XOR with a linear number of equations and a constant noise rate, as a single assumption. The survey poses it as one of two closing open questions and does not return to it; every combinatorial scheme it surveys needs sub-constant noise. 		standardseparationresearch-openbarrier (ai)
– Ring-LWE error parity
Open: whether recovering the Ring-LWE error modulo two is as hard as recovering the error itself. The easy direction is trivial; the source states it has no formal reduction for this one and relies on two heuristics instead, one of which changes the error distribution. 6 open 		standardequivalenceresearch-opennew-idea (ai)
– Computationally unique VDFs in the ROM
Open under computational uniqueness, which is the notion the definition of a VDF actually requires. Settled for perfect uniqueness with perfect completeness, and settled in the tight regime even with no uniqueness assumption at all. 5 open 		romimpossibilityresearch-opennew-idea (ai)
– Certifying no small non-expanding set
Open: whether the non-existence of a small non-expanding set in a random unbalanced bipartite graph admits a nondeterministic certificate that is sound and complete on average, at the parameters the ABW cryptosystem uses. The survey poses it as one of two closing open questions, takes no position, and does not return to it. 		standardseparationresearch-opennew-idea (ai)
– Compressed permutation oracle soundness
Open: whether the compressed permutation oracle is indistinguishable from a random permutation with inverse access, against polynomially many quantum queries. The source defines the oracle and proves only a conditional converse; the statement itself is settled nowhere. 5 open 		otherequivalenceresearch-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)
– Polynomial Compatibility Conjecture
Open in the inverse-polynomial regime. Proved for exponentially small influences by the paper that introduced it, and false for influences at or above 1/(2d); everything between is what the quantum separations depend on. 5 open 		qromassumptionresearch-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)
No matching items