Improved Garbled Circuit: Free XOR Gates and Applications

DOI10.1007/978-3-540-70583-3_40zbMath1155.94374OpenAlexW1826277484MaRDI QIDQ3519525

Thomas Schneider, Vladimir Kolesnikov

Publication date: 19 August 2008

Published in: Automata, Languages and Programming (Search for Journal in Brave)

Full work available at URL: https://encrypto.de/papers/KS08XOR.pdf

Mathematics Subject Classification ID

Related Items (72)

Three halves make a whole? Beating the half-gates lower bound for garbled circuits ⋮ Threshold Schnorr with stateless deterministic signing from standard assumptions ⋮ On various nonlinearity measures for Boolean functions ⋮ Pushing the limits of Valiant's universal circuits: simpler, tighter and more compact ⋮ Exploring crypto dark matter: new simple PRF candidates and their applications ⋮ Practical attacks against the walnut digital signature scheme ⋮ An efficient structural attack on NIST submission DAGS ⋮ Logic minimization techniques with applications to cryptology ⋮ Garbling XOR gates ``for free in the standard model ⋮ Full-threshold actively-secure multiparty arithmetic circuit garbling ⋮ Optimizing registration based encryption ⋮ A simple post-quantum non-interactive zero-knowledge proof from garbled circuits ⋮ Adaptive security of practical garbling schemes ⋮ Differential uniformity and linearity of S-boxes by multiplicative complexity ⋮ \textsc{EpiGRAM}: practical garbled RAM ⋮ Garbled circuits with sublinear evaluator ⋮ Distributed (correlation) samplers: how to remove a trusted dealer in one round ⋮ More efficient oblivious transfer extensions ⋮ Upper bounds on the multiplicative complexity of symmetric Boolean functions ⋮ Fast garbling of circuits under standard assumptions ⋮ Secure two-party computation via cut-and-choose oblivious transfer ⋮ New ways to garble arithmetic circuits ⋮ Actively secure half-gates with minimum overhead under duplex networks ⋮ Efficient and scalable universal circuits ⋮ How to Circumvent the Two-Ciphertext Lower Bound for Linear Garbling Schemes ⋮ High-throughput secure three-party computation with an honest majority ⋮ NanoGRAM: garbled RAM with \(\widetilde{O}(\log N)\) overhead ⋮ Garbling, stacked and staggered. Faster \(k\)-out-of-\(n\) garbled function evaluation ⋮ On compiling Boolean circuits optimized for secure multi-party computation ⋮ Faster Privacy-Preserving Location Proximity Schemes ⋮ Private evaluation of a decision tree based on secret sharing ⋮ Manticore: a framework for efficient multiparty computation supporting real number and Boolean arithmetic ⋮ Breaking and fixing garbled circuits when a gate has duplicate input wires ⋮ Half-tree: halving the cost of tree expansion in COT and DPF ⋮ Exact Synthesis of ESOP Forms ⋮ Tri-state circuits. A circuit model that captures RAM ⋮ Multiplicative complexity of vector valued Boolean functions ⋮ New cryptanalysis of LowMC with algebraic techniques ⋮ On multiparty garbling of arithmetic circuits ⋮ Free IF: how to omit inactive branches and implement \(\mathcal{S}\)-universal garbled circuit (almost) for free ⋮ Concretely efficient large-scale MPC with active security (or tinykeys for tinyot) ⋮ A single shuffle is enough for secure card-based computation of any Boolean circuit ⋮ Secure two-party computation in a quantum world ⋮ Secure Multi-party Computation: Information Flow of Outputs and Game Theory ⋮ The multiplicative complexity of 6-variable Boolean functions ⋮ TinyKeys: a new approach to efficient multi-party computation ⋮ Actively secure garbled circuits with constant communication overhead in the plain model ⋮ Public-Seed Pseudorandom Permutations ⋮ Block cipher invariants as eigenvectors of correlation matrices ⋮ On the exact round complexity of secure three-party computation ⋮ Boolean functions with multiplicative complexity 3 and 4 ⋮ Dispelling myths on superposition attacks: formal security model and attack analyses ⋮ High-performance multi-party computation for binary circuits based on oblivious transfer ⋮ Low cost constant round MPC combining BMR and oblivious transfer ⋮ Stacked garbling for disjunctive zero-knowledge proofs ⋮ \textsf{LogStack}: stacked garbling with \(O(b \log b)\) computation ⋮ Large scale, actively secure computation from LPN and free-XOR garbled circuits ⋮ Threshold garbled circuits and ad hoc secure computation ⋮ Network Oblivious Transfer ⋮ Linicrypt: A Model for Practical Cryptography ⋮ Efficient Zero-Knowledge Proof of Algebraic and Non-Algebraic Statements with Applications to Privacy Preserving Credentials ⋮ Encryption Switching Protocols ⋮ SecGDB: Graph Encryption for Exact Shortest Distance Queries with Efficient Updates ⋮ On the decision tree complexity of threshold functions ⋮ Efficient constant-round MPC with identifiable abort and public verifiability ⋮ Stacked garbling. Garbled circuit proportional to longest execution path ⋮ Better concrete security for half-gates garbling (in the multi-instance setting) ⋮ Garbled Circuits as Randomized Encodings of Functions: a Primer ⋮ Faster Secure Two-Party Computation in the Single-Execution Setting ⋮ Non-interactive Secure 2PC in the Offline/Online and Batch Settings ⋮ Hashing Garbled Circuits for Free ⋮ The price of active security in cryptographic protocols

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• A proof of security of Yao's protocol for two-party computation
• Conditional Encrypted Mapping and Comparing Encrypted Numbers
• A Practical Universal Circuit Construction and Secure Evaluation of Private Functions
• Universal circuits (Preliminary Report)
• Advances in Cryptology - CRYPTO 2003
• An Efficient Protocol for Secure Two-Party Computation in the Presence of Malicious Adversaries
• Gate Evaluation Secret Sharing and Secure One-Round Two-Party Computation
• A Permutation Network

This page was built for publication: Improved Garbled Circuit: Free XOR Gates and Applications