Securing Computation (Simons Institute, June 2015)
2015-06-08..2015-06-12
Berkeley, United States
who it's for
cryptography researchers, secure computation researchers, MPC implementers, applied crypto engineers, blockchain protocol developers, privacy engineers, theoretical computer scientists
topics
indistinguishability obfuscation for Turing machines; multilinear maps and CLT encodings; zeroizing attacks and defenses; garbled circuit optimizations and half-gates; fast garbling under PRF/AES assumptions; mixed-protocol ABY framework; two-round MPC via multi-key FHE; SNARKs and ZK proofs for contracts; oblivious RAM for MPC; information-theoretic MPC lower bounds; capacity inversion for noisy channels; sequential composition of rational proofs
| title | author | length |
|---|---|---|
| Obfuscation: Past, Present, and Possible Futures | Amit Sahai | 01h 06m |
Claims a concrete route to indistinguishability obfuscation by encoding matrix branching programs into candidate multilinear maps and proving security under a… | ||
| New Developments in Multilinear Maps: Zeroizing Attacks, Defenses, and Post-Zeroizing Obfuscation | Eric Miles | 01h 09m |
Shows how a family of CLT graded encodings yields a zeroizing attack that multiplies selected low‑level encodings into top‑level zeros, assembles an integer… | ||
| Indistinguishability Obfuscation for Turing Machines with Unbounded Memory | Brent Waters | 28m |
Presents a construction that extends indistinguishability obfuscation from circuits to Turing machines with large tape by building a message-hiding encoding… | ||
| Obfuscation with Constant Multiplicative Size Overhead | Prabhanjan Ananth | 33m |
Claims a construction of indistinguishability obfuscation for Turing machines whose obfuscated size is constant multiplicative overhead — essentially 2× size… | ||
| Cryptocurrencies and Smart Contracts | Elaine Shi | 30m |
Defines a formal F-blockchain model that trusts correctness but not privacy, then builds Hark, a compiler and protocol that turns ordinary smart contracts into… | ||
| Sequential Composition of Rational Proofs | Rosario Gennaro | 31m |
Defines sequential composability so honest computation remains the best long-term strategy, shows existing rational proofs fail for repeated volunteer tasks… | ||
| Rethinking Secure Computation - A Greedy Approach | Muthuramakrishnan Venkitasubramaniam | 30m |
Proposes that many graph and geometric problems (median, convex hull, MST, job scheduling, single‑source shortest paths approximations) are computable securely… | ||
| A Brief History of Practical Garbled Circuit Optimizations | Mike Rosulek | 01h 00m |
Thirty years of concrete optimizations cut garbled-circuit cost from four ciphertexts per gate to practical lows: row reduction drops four→three, free XOR… | ||
| Fast Garbling of Circuits Under Standard Assumptions | Yehuda Lindell | 35m |
Demonstrates that garbling can run fast under a plain PRF/AES assumption by translating per-wire keys to per-gate PRF labels, using AES-NI plus a hand-crafted… | ||
| A Framework for Efficient Mixed-Protocol Secure Two-Party Computation | Thomas Schneider | 21m |
A mixed-protocol system called ABY framework combines arithmetic sharing, GMW boolean sharing and Yao garbled circuits and converts between them using OT-based… | ||
| Lower Bounds for Information-Theoretic MPC | Ivan Damgård | 30m |
Unconditional MPC requires many messages: computing AND with n players and t corruptions needs omega(nt) messages, and for three players with one corruption… | ||
| Capacity Inversion and MPC over Elastic Noisy Channels | Hemanta Maji | 34m |
Shows how to get oblivious transfer from “elastic” noisy channels (receiver can reduce erasure/flip rate from alpha to beta) by decomposing repeated-channel… | ||
| Upending Stock Market Structure Using Secure Computation | Charanjit Jutla | 29m |
Proposes replacing the human specialist with secure multi-party computation to run a historical-style clearing-price auction so bids stay hidden; uses Gaussian… | ||
| Practical Private DB Querying | Vlad Kolesnikov | 31m |
Practical system for private queries on ~100M records uses an encrypted bloom-filter tree and deterministic tokens to get sublinear search with ~log-depth… | ||
| A Wishlist for Verifiable Computation: An Applied CS Perspective | Mike Walfish | 33m |
Surveys implemented verifiable computation systems (Pinocchio, Libsnark, Zatar, Buffet), identifies QAPs as the common costly core, and measures real limits… | ||
| SNARKs and their Practical Applications | Eran Tromer | 34m |
A working decentralized anonymous payment system called Zerocash uses zk-SNARKs to hide sender, recipient and amounts while preserving double-spend checks; it… | ||
| How to use Bitcoin to Enhance Secure Computation | Ranjit Kumaresan | 31m |
Uses Bitcoin claim-or-refund transaction primitives and timelocks to enforce a monetary penalty model that compensates honest parties when others abort… | ||
| Provably Secure Blockchain Protocols and Applications to Secure Computation | Aggelos Kiayias | 34m |
Defines a q‑bounded synchronous model and a bitcoin backbone abstraction and proves two concrete properties: common prefix (probability 1 − exp(−k) when… | ||
| The Simplest Oblivious Transfer Protocol | Claudio Orlandi | 17m |
Claim: a minimal UC‑secure oblivious transfer construction in the random oracle model built from a Diffie‑Hellman trick plus a tiny non‑committing, robust… | ||
| The Whole is Greater than the Sum of its Parts: Linear Garbling and Applications | Valerio Pastro | 25m |
Proposes a linear garbling framework that treats garbling as secret sharing (apply matrices to random vectors) and proves that two algebraic properties—linear… | ||
| Contention in Cryptography: Obfuscation, Leakage, UCE and the AI-DHI Assumptions | Stefano Tessaro | 31m |
Shows that auxiliary-input DDH (AI-DDH) cannot hold simultaneously with a modest form of virtual grey-box (VGB) obfuscation: construct an auxiliary-input… | ||
| How to Construct Indistinguishability Obfuscation from Compact Functional Encryption | Abhishek Jain | 31m |
Claims IO for P/poly from compact FE assuming a sub-exponentially secure public-key compact functional-encryption scheme (selective security, one key)… | ||
| Public-Coin Differing-Inputs Obfuscation and its Applications | Omkant Pandey | 29m |
Defines public-coin differing-input obfuscation that forbids secret auxiliary info and shows existing impossibility attacks no longer apply, then bootstraps… | ||
| Obfuscation of Probabilistic Circuits and Applications | Huijia Lin | 31m |
Defines and studies indistinguishability obfuscation for randomized programs (PIO/XPIO), shows correctness needs joint-output indistinguishability across… | ||
| Two Round MPC via Multi-Key FHE | Daniel Wichs | 28m |
Constructs two-round MPC from LWE by simplifying a GSW-style multi-key FHE so independent public keys encrypt into an expanded ciphertext space, then… | ||
| Efficient Multiparty Protocols via Log-Depth Threshold Formulae | Ron D. Rothblum | 26m |
Presents a reduction that builds n‑party MPC from small‑constant MPC by player emulation: n parties are mapped into a recursive tree where each virtual player… | ||
| Oblivious RAM for MPC | Stanislaw Jarecki | 35m |
Claims a practical speedup: secure computation of ORAM using Tree ORAM plus honest‑majority three‑party MPC (one corrupt) replaces costly 2PC garbled circuits… | ||
| Provably Secure Virus Detection: Using the Uncertainty to End Computer Malware | Vassilis Zikas | 38m |
Claim: compile a program by interleaving key shares with its memory and force the machine to reconstruct and erase those shares during a cryptographic… | ||
| On the Cryptographic Hardness of Finding a Nash Equilibrium | Omer Paneth | 23m |
Shows that, assuming indistinguishability obfuscation with subexponential security plus one-way functions, End-of-the-Line (hence PPAD and Nash equilibrium) is… | ||
| How Fair is your Protocol? A Utility-Based Approach to Protocol Optimality | Bjoern Tackmann | 33m |
Defines a utility-based fairness metric that assigns values gamma_{1,0}, gamma_{0,1}, gamma_{1,1}, etc., then models protocol design as a zero-sum meta-game… | ||
| Cryptographic Agents: Towards a Unified Theory of Computing on Encrypted Data | Manoj Prabhakaran | 35m |
Proposes a unifying framework where primitives are schemas of interactive program “agents,” security is indistinguishability-preserving security (tests that… | ||
| New Advances in Secure RAM Computation | Sanjam Garg | 28m |
Claims a black‑box garbled‑RAM construction that relies only on one‑way functions and avoids embedding PRF evaluations inside garbled CPU steps. Memory becomes… | ||
| nothing matches | ||