Time Space Tradeoffs
Tradeoffs between offline precomputation and online query time for a cryptanalytic search task.
| Status | Problem | Tags |
|---|---|---|
|
Balanced Root-n Preprocessing PIR The client-space-times-bandwidth product is settled up to \(n^{o(1)}\) by the source’s own matching bounds. What is open is whether client space, bandwidth and per-query server computation can all sit at \(\tilde{O}(n^{1/2})\) simultaneously; the best known point has client space and server computation \(\tilde{O}(n^{2/3})\). 4 open |
Private Information RetrievalTime Space Tradeoffstight-bound | |
|
Two-block sponge attack, quadratic advice Open: whether the multi-instance two-block sponge attack of advantage \((S^2T^4/C^2)^S\) lifts to an auxiliary-input attack of advantage \(S^2T^4/C^2\), matching the best proved security bound. Settled in the multi-instance model; no partial result in the auxiliary-input model. 7 open |
Collision FindingCollision Resistant HashingTime Space Tradeoffspromlower-boundadaptation (ai) | |
|
Quantum two-block MD collisions Open, in both directions and with no partial result: whether the best known quantum preprocessing attack, of advantage \(ST^2/N+T^3/N\), is optimal for two-block Merkle-Damgård collisions. The source reports that no matching quantum bounds are known at any block length. 7 open |
Collision FindingCollision Resistant HashingQuantum Query ComplexityQuantum Random Oracle ModelTime Space Tradeoffsqromtight-bound | |
|
CSAT with Small Space and Preprocessing Conjecture 1.2 of the source, a parameterized family rather than a single claim. Corollary 1.3 turns each parameter setting into a limitation on succinct IOPs. The source attaches decreasing confidence as the class \(T\) grows, calling the largest setting only (arguably) unlikely to be false rather than confidently believed. 4 open |
Interactive Oracle ProofsProof Size Lower BoundsSpace Bounded ComputationTime Space Tradeoffslower-boundbarrier (ai) | |
|
r-round DLOG tradeoff Open for every intermediate \(r\): the \(r=1\) endpoint is the source’s own theorem and \(r=T\) is Corrigan-Gibbs–Kogan, with nothing proved in between. The source conjectures the interpolating formula and says a matching attack exists at every \(r\), so the missing half is the lower bound. 6 open |
AdaptivityDiscrete LogarithmGeneric Group ModelTime Space Tradeoffsggmtight-bound | |
|
3-way collision, oblivious sequential curve Open: closing the factor-\(\sqrt{S}\) gap between the proved oblivious lower bound and a matching table-and-hunt algorithm for finding a 3-way collision with an oblivious sequential branching program. 2 open |
Collision FindingRandom Oracle ModelTime Space Tradeoffsromtight-boundadaptation (ai) | |
|
Non-adaptive DDH bound Open, and asserted rather than asked: the source proves \(1/2+\tilde{O}(T^2/N+\sqrt{ST/N})\), states twice that it conjectures this is not tight for DDH, and names \(1/2+\tilde{O}(T^2/N+ST/N)\) as the right answer. The same theorem’s square-DDH bound is sharp, with a matching attack, which is what makes the DDH case a question rather than a suspicion. 6 open |
AdaptivityDiscrete LogarithmGeneric Group ModelTime Space Tradeoffsggmtight-boundadaptation (ai) | |
|
STB conjecture (Merkle-Damgård) Open for non-constant \(B\) in the regime \(ST^2>2^n\), where the best published security bound and the best published attack are a factor of up to \(S\) apart; settled at \(B=1\), \(B=2\), every constant \(B\), \(B\approx T\), and every \(2<B<T\) with \(ST^2\le 2^n\). 6 open |
Collision FindingCollision Resistant HashingRandom Oracle ModelTime Space Tradeoffsromtight-boundbarrier (ai) | |
|
STB conjecture (sponge) Open for every \(B\ge 2\) except \(B\approx T\): at \(B=2\) in the regime \(ST^3>C\), and at \(B\ge 3\) with a gap of about \(T/B\). The source asks for a proof or a refutation and takes no position. 7 open |
Collision FindingCollision Resistant HashingTime Space Tradeoffspromtight-boundbarrier (ai) | |
|
Tight \(k\)-collision time-space tradeoff The exact tight time-space tradeoff for \(k\ge 3\) collisions under preprocessing is open; only the \(k=2\) case has a matching upper and lower bound. 2 open |
Collision FindingRandom Oracle ModelTime Space Tradeoffsromtight-bound |
No matching items