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)
– 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)
– 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)
– 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)
– 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)
– 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)
– 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)
No matching items