Garbled Circuits

Yao’s garbling technique for two-party computation, and constructions or separations built from it.

Status	Statement	Tags
	AVPs Are Lengthy Posed as Hypothesis 1.2 and offered both as a working hypothesis and as an ambitious target. Theorem 1.3 proves it implies super-polynomial lower bounds on sd-PIR, general secret sharing and fully-decomposable randomized encodings – for none of which a super-linear lower bound is currently known. The source adapts counting-based arguments to the model but does not reach the best-known bound for any primitive. 4 open	Garbled Circuits Private Information Retrieval Proof Size Lower Bounds Randomized Encodingslower-boundbarrier (ai)
	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)
	No key agreement from GC-OWF Open for round complexity growing with the security parameter. Proved in full for two messages, which is public-key encryption; the constant-round extension is sketched in the paper’s appendix without a theorem, its security half deferred to the PKE proof. 5 open	Black Box Separations Garbled Circuits Key Agreementotherseparationadaptation (ai)