Oblivious Lookup Tables
This addresses secure computation challenges in cryptography, offering a novel primitive for privacy-preserving operations, though it appears incremental as it builds on existing group-homomorphic encryption.
The paper tackles the problem of evaluating encrypted functions on encrypted data without decryption, introducing the concept of 'oblivious lookup tables' and proving their existence using group-homomorphic encryption. It presents a concrete construction with security analysis and connections to other cryptographic primitives.
We consider the following question: given a group-homomorphic public-key encryption $E$, a ciphertext $c=E(x,pk)$ hiding a value $x$ using a key $pk$, and a "suitable" description of a function $f$, can we evaluate $E(f(x), pk)$ without decrypting $c$? We call this an "oblivious lookup table" and show the existence of such a primitive. To this end, we describe a concrete construction, discuss its security and relations to other cryptographic primitives, and point out directions of future investigations towards generalizations.