Universal circuits (Preliminary Report)

DOI10.1145/800113.803649zbMath0365.94044OpenAlexW2002616520MaRDI QIDQ4140882

Leslie G. Valiant

Publication date: 1976

Published in: Proceedings of the eighth annual ACM symposium on Theory of computing - STOC '76 (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1145/800113.803649

zbMATH Keywords

complexityBoolean functionBoolean circuit

Mathematics Subject Classification ID

Related Items (31)

Pushing the limits of Valiant's universal circuits: simpler, tighter and more compact ⋮ Practical attacks against the walnut digital signature scheme ⋮ On the limits of gate elimination ⋮ One-Time Programs with Limited Memory ⋮ Improved zero-knowledge argument of encrypted extended permutation ⋮ Models of lower-bounds proofs ⋮ Lower bounds for synchronous circuits and planar circuits ⋮ Efficient Universal Quantum Circuits ⋮ Garbled circuits with sublinear evaluator ⋮ Making Private Function Evaluation Safer, Faster, and Simpler ⋮ Speed-stacking: fast sublinear zero-knowledge proofs for disjunctions ⋮ Efficient and scalable universal circuits ⋮ How to Circumvent the Two-Ciphertext Lower Bound for Linear Garbling Schemes ⋮ Succinct attribute-based signatures for bounded-size circuits by combining algebraic and arithmetic proofs ⋮ Time-release cryptography from minimal circuit assumptions ⋮ \texttt{MOTIF}: (almost) free branching in GMW. Via vector-scalar multiplication ⋮ Improved Garbled Circuit: Free XOR Gates and Applications ⋮ Maliciously circuit-private multi-key FHE and MPC based on LWE ⋮ Free IF: how to omit inactive branches and implement \(\mathcal{S}\)-universal garbled circuit (almost) for free ⋮ Dual System Framework in Multilinear Settings and Applications to Fully Secure (Compact) ABE for Unbounded-Size Circuits ⋮ Circuit-Private Multi-key FHE ⋮ A Practical Universal Circuit Construction and Secure Evaluation of Private Functions ⋮ Obfustopia built on secret-key functional encryption ⋮ \textsf{LogStack}: stacked garbling with \(O(b \log b)\) computation ⋮ Masked triples. Amortizing multiplication triples across conditionals ⋮ Breaking the Circuit Size Barrier for Secure Computation Under DDH ⋮ Stacked garbling. Garbled circuit proportional to longest execution path ⋮ Parallel solutions to geometric problems in the scan model of computation ⋮ Hashing Garbled Circuits for Free ⋮ Blind polynomial evaluation and data trading ⋮ Zero-knowledge proofs for committed symmetric Boolean functions

This page was built for publication: Universal circuits (Preliminary Report)