Computing on Authenticated Data

Authors: J.H. Ahn, D. Boneh, J. Camenisch, S. Hohenberger, A. Shelat, and B. Waters

In tandem with recent progress on computing on encrypted data via fully homomorphic encryption, we present a framework for computing on authenticated data via the notion of slightly homomorphic signatures, or P-homomorphic signatures. With such signatures, it is possible for a third party to derive a signature on the object m' from a signature of m as long as P(m,m')=1 for some predicate P which captures the ``authenticatable relationship" between m' and m. Moreover, a derived signature on m' reveals no extra information about the parent m. We carefully formulate the definition of this new primitive, and then provide generic constructions for all univariate and closed predicates, and specific efficient constructions for a broad class of natural predicates such as quoting, weighted sums, averages, and Fourier transforms.

In proceedings of TCC'12, LNCS 7194, pp. 1-20, 2012   [BIBTEX]

Full paper: pdf