Targeted malleability: homomorphic encryption for restricted computations
Authors: D. Boneh, G. Segev, and B. Waters
Abstract:
We put forward the notion of targeted malleability: given a
homomorphic encryption scheme, in various scenarios we would like to
restrict the homomorphic computations one can perform on encrypted
data. We introduce a precise framework, generalizing the foundational
notion of non-malleability introduced by Dolev, Dwork, and Naor
(SICOMP ’00), ensuring that the malleability of a scheme is targeted
only at a specific set of “allowable” functions.
In this setting we are mainly interested in the efficiency of such schemes as a function of the number of repeated homomorphic operations. Whereas constructing a scheme whose ciphertext grows linearly with the number of such operations is straightforward, obtaining more realistic (or merely non-trivial) length guarantees is significantly more challenging.
We present two constructions that transform any homomorphic encryption scheme into one that offers targeted malleability. Our constructions are rather general, and rely on non-interactive zero-knowledge proofs, and succinct non-interactive arguments. The two constructions offer somewhat different efficiency guarantees, each of which may be preferable depending on the underlying building blocks. In particular, in our first construction the length of the ciphertext does not grow as long as the number of repeated homomorphic operations is limited.
Reference:
In proceedings of Innovations in Theoretical Computer Science (ITCS), ACM, 2012, pp.350-366.
[BIBTEX]
Full paper: pdf