Idealized Models

Statements tagged with the idealized-models 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
– Constant-round Luby–Rackoff, quantum
Open for every round count: whether some constant number of Luby-Rackoff rounds with random round functions is indistinguishable from a random invertible permutation against quantum queries in both directions. Four rounds are refuted by a known quantum attack, and the source reports that the published proof of the weaker forward-only four-round claim is flawed. 6 open 		otherequivalenceresearch-opennew-idea (ai)
– 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)
– Fully quantum time-lock puzzles
Open in the fully quantum case. Settled by the source paper when the generator is classical and the solver quantum, and when the generator is quantum and the solver classical under perfect completeness; a classical-query attack on the remaining cell would prove a simulation conjecture. 5 open 		qromimpossibilityresearch-opennew-idea (ai)
– CAQB key agreement, imperfect completeness
Open. Settled for perfect completeness by the source paper’s Theorem 3.1; the argument’s final step uses perfect completeness in a way that no known weakening survives, and the paper’s Simulation-Conjecture barrier does not cover this party structure. 5 open 		qromimpossibilityresearch-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)
– 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)
– 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)
– No round-optimal pairing-free blind signature
Open for a polynomial query budget. The impossibility is proved when User_2 and Verify together make O(log lambda) random-oracle queries, including when oracle outputs contain group elements; the superpolynomial message space hypothesis is retained. 5 open 		ggmimpossibilityresearch-openadaptation (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)
– 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)
– Three moves from DL, ROM only
Open: three moves, black-box in the group, ROM only, from DL alone. Three moves is achieved from DDH in the ROM and from DL in AGM+ROM; four moves is achieved from DL in the ROM. 5 open 		romassumptionresearch-opennew-idea (ai)
No matching items