Multi-Key / Spooky Fully Homomorphic Encryption
361 views · Published 14 April 2016 · 56:56 · Indexed 16 November 2026
Channel: Institut Henri Poincaré · 2016 · Science & Technology
By Daniel Wichs (Northeastern) Abstract: A garbling scheme is used to garble a circuit C and an input x in a way that reveals the output C(x) but hides everything else. In many settings, the circuit can be garbled off-line without strict constraints on efficiency, but the input must be garbled very efficiently on-line, in time which is much smaller than the circuit size |C|. Yao's garbling scheme only achieves this under one-way functions in the selective security setting. It has remained as an open problem to achieve the stronger notion of adaptive security where the adversary can choose the input x adaptively after seeing the garbled circuit. In this work, we modify Yao's scheme in a way that maintains all of its desirable features, while allowing us to prove adaptive security in various parameter regimes under one-way functions. As our main instantiation, we get a scheme where the size of the garbled input is only proportional to the width of the circuit, which is related to the space complexity of the computation, but independent of the circuit's depth. More broadly, we develop a connection between adaptive security in our framework and a certain type of pebble complexity} As our main tool, of independent interest, we develop a new notion of somewhere equivocal encryption, which allows us to efficiently equivocate on a small subset of the message bits.
More from this channel
-
29:47
10 ans du Groupe Calcul : Histoire du Calcul - Introduction
-
52:14
Gauss, Jacobi, Seidel, Richardson, Krylov: the Invention of Iterative Methods
-
55:33
Les "invariants arithmétiques" de H. Poincaré
-
1:08:53
Henri Poincaré, a founding father of the modern theory of PDEs
-
57:13
Sympletic topology from Poincaré to Gromov
-
57:35
Structural Realism, Then and Now
-
46:26
Poincaré inequalities in probability and geometric analysis
-
1:02:05
On the contributions of Henri Poincaré to modern geophysics...