Characterization

Status	Statement	Tags
	dv-SNARG, One Group Element Numbered Conjecture 1.3 of the source. Its own theorems achieve one group element plus O(tau) bits, and (with a random oracle) one group element, one hash output and about 2 tau bits; the conjecture halves the additive term to tau + o(tau) and asks for no random oracle. 4 open	Generic Group Model Proof Size Lower Bounds Snarksggmcharacterization
	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)
	Efficient Parity-Tolerance Simulation Feasibility is settled: every circuit can be compiled into a t-parity-tolerant one. What is open is the simulator’s running time, which in the source’s construction is exponential in t; the source gives partial evidence, under LPN, that inefficient simulation may be inherent for a related relaxed notion. 4 open	Leakage Resilient Circuits Learning Parity With Noisecharacterization
	SZK Batch Verification Named by the source as the most pressing open question its work leaves. Its Theorem 1.1 gives the NISZK analogue: communication and CRS length poly(n, log k) for k up to 2⁽ⁿ0.01). A poly(n) dependence is unavoidable even at k = 1 under a sub-exponential hardness assumption, so log k is the aggressive part of the bound. The source also offers a weaker fallback target: any sub-linear dependence on k. 5 open	Batch Verification Direct Product Theorems Limited Independence Randomness Extractioncharacterization
	Sublinear-Time CGKA Refresh The source achieves worst-case sublinear communication with forward secrecy, but its refresh algorithms still run in time polynomial in the group size, and it leaves open, without committing to a specific target rate, whether sublinear-time refresh is achievable at all. 4 open	Broadcast Encryption Continuous Group Key Agreementcharacterization
	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)
	Seeded Extractors Are Multi-Instance Posed by the source with both answers live. It proves the property for two code-based extractors via a hinting property it isolates; concurrent independent work of Dinur, Stemmer, Woodruff and Zhou proves it for universal hash functions by a different argument. No extractor is known to fail it and no general proof is known. 4 open	Incompressible Encryption Randomness Extractioncharacterization
	Logarithmic independence implies PRP Open at independence order log n. The same implication is refuted at order 4 and at every constant order by an explicit construction; the logarithmic-order form is untouched, and no unconditional proof of it can be expected. 5 open	Limited Independence Pseudorandom Permutationscharacterization
	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)
	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)
	Salt Length vs. Call Count Fully open in both directions: no construction with \(O(\lambda)\)-length, message-independent salts and \(O(1)\) Merkle-Damgård calls is known, and no proof that none can exist, nor any trade-off between the two, has been given either. 4 open	Indifferentiability Random Oracle Modelromcharacterization
	Short-Salt MD Combiner Security Open in both directions: the source’s Theorem 3.1 proves security only when salts exceed the message by at least the security parameter, and reports neither an attack nor a security proof once the salts shrink to a constant number of blocks. 4 open	Indifferentiability Random Oracle Modelromcharacterizationadaptation (ai)
	SSS Implies Fiat-Shamir Friendly Conjecture 1.3 of the source. It is explicit that it does not prove it – ‘only conjecture it’ – and asks for the proof or refutation as an important open problem. It does prove that SSS implies straight-line soundness, hence post-quantum soundness, and that its own instantiation of Kilian’s protocol is SSS. 4 open	Commitment Schemes Fiat Shamir Snarkscharacterization
	Hold-Out Soundness, Dirty Coordinates The source’s distinguishing attack is unconditional and proved. Its decryption attack is heuristic, and this is the unproved step: completeness on clean coordinates is its Claim 6.2, while soundness on dirty ones is supported only by a heuristic dimension count and small-parameter experiments. 5 open	Code Based Cryptography Private Information Retrievalcharacterization
	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
	WP Threshold Share Size The 2-out-of-n case is settled: Beimel and Franklin give 1/n-weakly-private schemes with share size 2, against Theta(log n) for perfect privacy. The source states large thresholds are open and asks specifically about (n-1)-out-of-n at share size o(log n). 5 open	Threshold Secret Sharingcharacterizationadaptation (ai)
	AES t-Wise Independence, t > 2 Named by the source as the first of the two outstanding open problems that come of its work. It proves almost pairwise independence (t = 2) for multi-round AES with independent round keys, and an existential t-wise result for key-alternating ciphers with most permutations, but nothing for concrete AES beyond t = 2. Its Appendix B attacks 4-wise independence in the width-1 case with the same S-box. 4 open	Block Ciphers Limited Independence Pseudorandom Permutations T Wise Independencecharacterizationbarrier (ai)