Abstract. We present a public-key encryption scheme with the following properties. Given a branching program P and an encryption c of an input x, it is possible to efficiently compute a succinct ciphertext c from which P (x) can be efficiently decoded using the secret key. The size of c depends polynomially on the size of x and the length of P , but does not further depend on the size of P . As interesting special cases, one can efficiently evaluate finite automata, decision trees, and OBDDs on encrypted data, where the size of the resulting ciphertext c does not depend on the size of the object being evaluated. These are the first general representation models for which such a feasibility result is shown. Our main construction generalizes the approach of Kushilevitz and Ostrovsky (FOCS 1997) for constructing single-server Private Information Retrieval protocols. We also show how to strengthen the above so that c does not contain additional information about P (other than P (x) for some x) even if the public key and the ciphertext c are maliciously formed. This yields a two-message secure protocol for evaluating a length-bounded branching program P held by a server on an input x held by a client. A distinctive feature of this protocol is that it hides the size of the server's input P from the client. In particular, the client's work is independent of the size of P .
Of particular note, though, is a protocol due to Ishai and Paskin REF to evaluate a branching program (which can be used to encode a DFA) on encrypted data.
Evaluating branching programs on encrypted data
In TCC 2007
Computer Science