Multi-Party Computation

Status	Statement	Tags
	Perfectly Correct Statistical ARE Statistical security with statistical correctness is settled by the source for every finite function. Perfect correctness is known in the computational setting and, in the statistical setting, only in a relaxed Las Vegas form where the evaluator may declare failure. 4 open	Additive Randomized Encodings Shuffle Modelcharacterizationadaptation (ai)
	Subexponential-query PCF from sparse LPN Open in both directions, and the source paper poses it as a question rather than conjecturing an answer; the affirmative direction is this page’s reading. The one follow-up construction from sparse LPN inherits the same superpolynomial ceiling and says so. 6 open	Learning Parity With Noise Pseudorandom Correlation Functions Random Oracle Modelromassumption
	Sources vs Randomness Blowup Conjecture 13 of the source. Its companion question – how many parties must be able to toss coins – is settled exactly by the same paper: t sources for deterministic functionalities, t+1 for randomized ones, even though the adversary may corrupt all of them. What the count costs is not settled. Both halves of the Theta are open. 5 open	Random Sources Randomness Complexitytight-bound
	Standard-model weak PCF from sparse LPN Open, posed by the source as its second open question with an obstruction it names explicitly; the affirmative direction is this page’s reading. An independent follow-up construction reports the same random oracle as inherent to the same recursion. 6 open	Learning Parity With Noise Pseudorandom Correlation Functions Random Oracle Modelassumption
	Optimal 2D LPHS Open, and asserted rather than asked: the source prints the algorithm, conjectures the error rate, reports experiments consistent with it, states it could not analyse it, and leaves settling it to future work. The matching lower bound is the source’s own theorem, so a proof would close the two-dimensional case exactly. 7 open	Distributed Discrete Logarithm Generic Group Model Locality Preserving Hashingtight-boundadaptation (ai)
	Constant-Overhead AMD Circuits Polylogarithmic overhead in \|C\| and lambda is achieved by Genkin, Ishai and Weiss; constant overhead is open. The source’s Theorem 43 shows that achieving it would – together with the source’s own constant-overhead OT protocol – settle the main open question on constant-overhead secure computation for general Boolean circuits. 4 open	Fault Tolerant Circuits Oblivious Transfercharacterization
	Degree-2 Statistical RE Question 1.6 of the harvested paper, attributed there to Ishai-Kushilevitz and Applebaum-Ishai-Kushilevitz and described as open for almost 20 years. Degree-3 statistical encodings exist for every finite function; negative results are known for perfectly private degree 2. The harvested paper adds a new consequence, its Proposition 1.7. 4 open	Arithmetic Cryptography Non Interactive Secure Computation Randomized Encodingscharacterizationbarrier (ai)
	Distance from Lines Modulo a Prime Numbered Conjecture 5.37 of the source, described there as a natural but apparently new number-theoretic conjecture whose study may be of independent interest. Nothing is proved about it; the source notes a deterministic variant might be easier to prove and is still useful. 5 open	Oblivious Linear Evaluation Oblivious Transferlower-bound
	NISC Overhead from a PRG The source poses this question and then answers the variant in which the pseudorandom generator is replaced by a random oracle, which leaves the question as posed unresolved. Each of the four relaxations – polylogarithmic overhead, correlated-abort security, extra rounds, or programmable OLE correlations – is already known. 4 open	Garbled Circuits Non Interactive Secure Computationcharacterizationadaptation (ai)
	EA-Code Distance over Rings Theorem 3.10 of the source proves the distance bound over F_2 only. Over a ring of size q its proof technique forces the rate to satisfy R much less than 1/ln q, which the source states it believes is an artefact of the argument, supported by small-parameter weight-distribution experiments over F_17 and Z_16. 5 open	Code Based Cryptography Dual Distance Learning Parity With Noise Pseudorandom Correlation Functionslower-boundadaptation (ai)
	Quasi-Abelian GV, Growing Group Named as a conjecture by the source, which says the development is out of reach of the article. It is what makes the choice of group free in the QA-SD line: resistance to every linear test, for any abelian G, reduces to it. Partially advanced in 2026 by concrete non-asymptotic bounds for particular groups, which restate the general question as open. 5 open	Code Based Cryptography Dual Distance Pseudorandom Correlation Functions Syndrome Decodinglower-boundadaptation (ai)
	Statistical Robust ARE The source asks whether all functions admit a statistically secure ARE, robust or non-robust, and strongly conjectures the answer is negative. The non-robust half was refuted: Bitansky, Erabelli, Garg and Ishai construct statistical AREs for all finite functions. The robust half is open, and is re-posed by that later work. 4 open	Additive Randomized Encodings Randomized Encodingscharacterization
	Binary dual-distance bound is the worst case Open, and asserted rather than asked – the source writes that it expects the inequality, gives an intuition covering one of the two competing effects, records that all prior work assumes it, and proves nothing. A probe at small parameters is consistent with it; the parameters the source’s own construction uses are out of computational reach, which is why the source does not check it either. 7 open	Average Case Hardness Dual Distance Learning Parity With Noiselower-boundadaptation (ai)
	Randomness Complexity of XOR The source proves an Omega(t^2) lower bound, matching Kushilevitz and Mansour’s non-explicit O(t^2 log(n/t)) upper bound up to a logarithmic factor, and up to a constant factor when t = Omega(n). It also gives an explicit protocol at O(t^2 log^2 n). It states it leaves the remaining polylogarithmic gaps open. 4 open	Limited Independence Randomness Complexitytight-bound