Garbled Circuits

Public presentation by Per Hallgren
on Tue. 18 April 2017 at 15:30-17:30 in room EDIT 3364
Garbled Circuits is a technique used to compute a function based on inputs from multiple parties without disclosing any data that correlated to the user's input, except for the output of the function. The technique has been around and under development for about 30 years, but has only recently seen enough performance improvements to be feasible for real applications. We detail the main ideas of the technique, and highlight two recent developments that lead to performance improvements. The first such improvement, TinyGarble, shows how to better utilize existing optimization tools used in computer architecture. The second improvement, called GraphSC, lends support to secure computation of graph algorithms.
View PDF

Introductory papers
  • Lindell & Pinkas: A Proof of Security of Yao's Protocol for Two-Party Computations (ECCC 2004) [pages 1-8, 10-15]
  • Advanced papers
  • Songhori et al.: TinyGarble: Highly Compressed and Scalable Sequential Garbled Circuits (S&P 2015)
  • Nayak et al.: GraphSC: Parallel Secure Computation Made Easy (S&P 2015)
  • Fork me on GitHub