Quantum Cryptography

Statements tagged with the quantum 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)
– 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)
– Erasing real-or-random vs Boneh–Zhandry
Open: whether erasing real-or-random security implies Boneh-Zhandry security. The reverse non-implication is proved only in the quantum random oracle model, and this direction is one of six non-implications the source paper conjectures and does not prove. 5 open 		standardseparationresearch-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)
– One erasing challenge vs many embedding learns
Open: whether a single erasing two-ciphertext challenge query, with classical learning queries, implies security against polynomially many embedding-model superposition learning queries. One of six non-implications the source paper conjectures, and on its own account the one that would close the most remaining cells. 5 open 		standardseparationresearch-opennew-idea (ai)
– Standard real-or-random vs embedding two-ciphertext
Open: whether one standard-oracle real-or-random challenge query implies one embedding-model two-ciphertext challenge query, with classical learning queries on both sides. Both notions are singleton classes in the source’s classification, and this is one of six non-implications it conjectures. 5 open 		standardseparationresearch-opennew-idea (ai)
– Threshold one-shot decryption without extractability
Open: whether threshold one-shot decryption (for every corruption threshold f < 1/2) follows from one-shot signatures and an ordinary, non-extractable witness encryption scheme. The one known construction needs the witness-encryption extractor to run its security reduction, and the source paper leaves open whether extractability can be weakened or dropped altogether. 5 open 		standardassumptionresearch-opennew-idea (ai)IOG
– 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)
– 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)
– 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)
No matching items