Oblivious lookup-tables

Abstract

Evaluating arbitrary functions on encrypted data is one of the
holy grails of cryptography, with Fully Homomorphic Encryption (FHE) being
probably the most prominent and powerful example. FHE, in its current state
is, however, not ecient enough for practical applications. On the other hand,
simple homomorphic and somewhat homomorphic approaches are not powerful
enough, to support arbitrary computations.
We propose a new approach towards a practicable system for evaluating func-
tions on encrypted data. Our approach allows to chain an arbitrary number of
computations, which makes it more powerful than existing ecient schemes. To
gain an eciency advantage over FHE we do not encrypt or in any way hide the
function, that is evaluated on the encrypted data. It is, however, sucient that
the function description is known only to the evaluator. This situation arises in
practice for Software as a Service (SaaS)-scenarios, where an evaluator provides
a function only known to him and the user wants to protect his data. Another
application might be the analysis of sensitive data, such as medical records.
In this paper we restrict ourselves to functions with only one input parameter,
which allow arbitrary transformations on encrypted data.