Privacy-Enhancing Technologies

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 Retrieval Time Space Tradeoffstight-bound
	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	Search Treestight-bound
	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	Search Treestight-bound
	SK-DEPIR from One-Way Functions Stated by the source as its own conjecture and proved for two-round passive-server schemes. Its main theorem – that any crypto oracle can be stripped out of a SK-DEPIR and replaced by a one-way function – is stated conditionally on this, so the conjecture is the single remaining hypothesis between that compiler and a clean statement that no idealized generic primitive helps. 4 open	Black Box Separations One Way Functions Private Information Retrievalimpossibility
	Arithmetic Two-Server PIR Optimality \(O(n^{1/3})\) is achieved by arithmetizing the classical two-server schemes. The source states that whether it can be improved – let alone brought to sub-polynomial – is unknown, and supplies a linear-algebraic characterization of exactly what an improvement would require. 5 open	Arithmetic Cryptography Private Information Retrievaltight-bound
	Perfect FASS at 3-out-of-5 Statistical and computational FASS are settled by the source and prior work. The perfect version is stated by the source to be open for every reconstruction threshold \(3\le t\le n-2\), and open even for the weaker multi-dealer notion, with 3-out-of-5 the smallest open case. Con has settled the perfect case for gap threshold structures. 5 open	Anonymity Threshold Secret Sharingcharacterizationadaptation (ai)
	Polylog Shuffle PIR, Negligible Error Settled in three neighbouring corners: \(O(n^\gamma)\) communication with inverse-polynomial error and polynomially many queries; polylogarithmic communication with \(n^{O(\log n)}\) queries; and negligible error with \(O(n/\log n)\) communication. The polylogarithmic-and-negligible corner with polynomially many queries is open, and is ruled out for inner-outer constructions with an additive inner layer by the source’s own Theorem 6.5. 5 open	Private Information Retrieval Shuffle Modelcharacterizationadaptation (ai)
	MDSD Linear-Test Bias The source proves a non-tight reduction from standard decisional syndrome decoding and separately conjectures that the DOOM algorithm is the best attack; the linear-test bias is the one quantity it states it cannot bound. 5 open	Learning Parity With Noise Shuffle Model Syndrome Decodinglower-bound