MT25 Strachey Lecture - Professor Rafail Ostrovsky: Advances in Garbled Circuits Nearly 40 years ago, Andy Yao proposed the construction of “Garbled Circuits,” which had an enormous impact on the field of secure computation -- both in theory and in practice. In Garbled Circuits, two parties agree on a Boolean circuit that they want to evaluate, where both parties have partial, disjoint inputs to the circuit, and neither party is willing to disclose to the other party anything but the output. In this talk, I will survey the state of the art for garbling schemes, including computing with Garbled Random Access Memory, the so-called GRAM constructions that were invented by Lu and Ostrovsky in 2013, as well as more recent progress, including the GRAM paper by Heath, Kolesnikov and Ostrovsky, which received the best paper award in Eurocrypt 2022. I will also discuss Garbled Circuits in the malicious setting, where parties try to deviate arbitrarily from the prescribed protocol execution to gain additional information, and will review some of the latest advances in this area. The talk will be self-contained and accessible to the general audience.
All content for Strachey Lectures is the property of Oxford University and is served directly from their servers
with no modification, redirects, or rehosting. The podcast is not affiliated with or endorsed by Podjoint in any way.
MT25 Strachey Lecture - Professor Rafail Ostrovsky: Advances in Garbled Circuits Nearly 40 years ago, Andy Yao proposed the construction of “Garbled Circuits,” which had an enormous impact on the field of secure computation -- both in theory and in practice. In Garbled Circuits, two parties agree on a Boolean circuit that they want to evaluate, where both parties have partial, disjoint inputs to the circuit, and neither party is willing to disclose to the other party anything but the output. In this talk, I will survey the state of the art for garbling schemes, including computing with Garbled Random Access Memory, the so-called GRAM constructions that were invented by Lu and Ostrovsky in 2013, as well as more recent progress, including the GRAM paper by Heath, Kolesnikov and Ostrovsky, which received the best paper award in Eurocrypt 2022. I will also discuss Garbled Circuits in the malicious setting, where parties try to deviate arbitrarily from the prescribed protocol execution to gain additional information, and will review some of the latest advances in this area. The talk will be self-contained and accessible to the general audience.
Dr Scott Aaronson (MIT, UT Austin) gives the 2016 Strachey lecture. In the near future, it will likely become possible to perform special-purpose quantum computations that, while not immediately useful for anything, are plausibly hard to simulate using a classical computer. These "quantum supremacy experiments" would be a scientific milestone---decisively answering quantum computing skeptics, while casting doubt on one of the foundational tenets of computer science, the Extended Church-Turing Thesis. At the same time, these experiments also raise fascinating questions for computational complexity theorists: for example, on what grounds should we believe that a given quantum system really is hard to simulate classically?
Does classical simulation become easier as a quantum system becomes noisier? and how do we verify the results of such an experiment? In this lecture, I'll discuss recent results and open problems about these questions, using three proposed "quantum supremacy experiments" as examples: BosonSampling, IQP / commuting Hamiltonians, and random quantum circuits.
Based partly on joint work with Alex Arkhipov and with Lijie Chen.
The Strachey Lectures are generously supported by OxFORD Asset Management.
Creative Commons Attribution-Non-Commercial-Share Alike 2.0 UK: England & Wales; http://creativecommons.org/licenses/by-nc-sa/2.0/uk/
Strachey Lectures
MT25 Strachey Lecture - Professor Rafail Ostrovsky: Advances in Garbled Circuits Nearly 40 years ago, Andy Yao proposed the construction of “Garbled Circuits,” which had an enormous impact on the field of secure computation -- both in theory and in practice. In Garbled Circuits, two parties agree on a Boolean circuit that they want to evaluate, where both parties have partial, disjoint inputs to the circuit, and neither party is willing to disclose to the other party anything but the output. In this talk, I will survey the state of the art for garbling schemes, including computing with Garbled Random Access Memory, the so-called GRAM constructions that were invented by Lu and Ostrovsky in 2013, as well as more recent progress, including the GRAM paper by Heath, Kolesnikov and Ostrovsky, which received the best paper award in Eurocrypt 2022. I will also discuss Garbled Circuits in the malicious setting, where parties try to deviate arbitrarily from the prescribed protocol execution to gain additional information, and will review some of the latest advances in this area. The talk will be self-contained and accessible to the general audience.
