Evaluating Branching Programs on Encrypted Data

By Yuval Ishai, Anat Paskin-Cherniavsky. 2007

240 citations recorded by the source corpus.

Subfields: Artificial Intelligence, Computational Theory and Mathematics

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Computational Theory and Mathematics

Citations in the corpus

A Review of Homomorphic Encryption Libraries for Secure Computation (2018, background): “Some examples of Somewhat Homomorphic Encryption schemes are [4,5,6,7,8].”
A Survey on Homomorphic Encryption Schemes (2017, methodology): “ic properties of well-known PHE schemes are brieﬂy summarized in Table I. 3.2. Somewhat Homomorphic Encryption Schemes There are useful SWHE examples [Yao 1982; Sander et al. 1999; Boneh et al. 2005; Ishai and Paskin 2007] in the literature before 2009. After the ﬁrst plausible FHE published in 2009”
Fully Homomorphic Encryption over the Integers (2010, background): “A distribution D is ²-uniform if its statistical distance from the uniform distribution is at most ², where the statistical difference between two distributions D1, D2 over a finite domain X is 12 ∑ x∈X |D1(x)−D2(x)|.”
Fully homomorphic encryption using ideal lattices (2009, background): “Ishai and Paskin [ 26 ] do this for branching programs, which covers NC1 circuits (by Barrington [6]), and ciphertexts in their scheme are much shorter – proportional to the length of the branching program rather than its size, though the computation is proportional to the size.”
Compressible FHE with Applications to PIR (2019, background): “But Damg˚ard-Jurik is only additively homomorphic, so their solution becomes much more complicated, relying on the Ishai-Paskin homomorphic construction for branching-programs [IP07] (which internally uses Damg˚ard-Jurik).”
First CPIR Protocol with Data-Dependent Computation (2009, methodology): “In particular, [14] assumed that a strong oblivious transfer protocol is used in every node.”
Delegating computation: interactive proofs for muggles (2008, background): “We note that such a PIR scheme exists for any κ ≥ log |DB| (where |DB| is the database size) under the N -th Residuosity Assumption [48, 40], and under the Φ-Hiding Assumption [20].”
A Simpler Rate-Optimal CPIR Protocol (2017, methodology): “[10], following earlier protocols [11,16,12,8,13], homomorphically executes a branching program, by using a (w, 1)-CPIR at every internal node of the branching program.”
Optimal Rate Private Information Retrieval from Homomorphic Encryption (2015, methodology): “In [20, 25, 26], one recursively applies a basic (w, 1)CPIR, for a small w, that is based on the cryptosystem of [11].”
Efficient Fully Homomorphic Encryption from (Standard) LWE (2011, background): “The problem was suggested by Rivest, Adleman and Dertouzos [34] back in 1978, yet the first plausible candidate came thirty years later with Gentry’s breakthrough work in 2009 [13], [14] (although, there has been partial progress in the meanwhile [21], [31], [6], [22]).”
Lattice-based FHE as secure as PKE (2014, methodology): “In a high level, our technique here is reminiscent of Ishai and Paskin’s method of evaluating branching programs on encrypted data [13].”
Homomorphic Encryption (2017, methodology): “In 2007, Ishai and Paskin described a compact scheme that can evaluate branching programs [62], with security under the N -th residuosity assumption [78].”