Privacy-Enhancing Technologies

Status	Statement	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 O~(n^{1/2}) simultaneously; the best known point has client space and server computation 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 <= t <= 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