caa a22 4500 606148906 CHVBK 20210128100531.0 cr unu---uuuuu 210128e20150401xx s 000 0 eng 10.1007/s00145-014-9182-0 doi (NATIONALLICENCE)springer-10.1007/s00145-014-9182-0 Computing on Authenticated Data [Elektronische Daten] [Jae Ahn, Dan Boneh, Jan Camenisch, Susan Hohenberger, Abhi Shelat, Brent 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$$ P -homomorphic signatures. With such signatures, it is possible for a third party to derive a signature on the object $$m'$$ m ′ from a signature of $$m$$ m as long as $$P(m,m')=1$$ P ( m , m ′ ) = 1 for some predicate $$P$$ P which captures the "authenticatable relationship" between $$m'$$ m ′ and $$m$$ m . Moreover, a derived signature on $$m'$$ m ′ reveals no extra information about the parent $$m$$ m . Our definition is carefully formulated to provide one unified framework for a variety of distinct concepts in this area, including arithmetic, homomorphic, quotable, redactable, transitive signatures, and more. It includes being unable to distinguish a derived signature from a fresh one even when given the original signature. The inability to link derived signatures to their original sources prevents some practical privacy and linking attacks, which is a challenge not satisfied by most prior works. Under this strong definition, we then provide generic constructions for all univariate and closed predicates, and specific efficient constructions for a broad class of natural predicates such as quoting, subsets, weighted sums, averages, and Fourier transforms. To our knowledge, these are the first efficient constructions for these predicates (excluding subsets) that provably satisfy this strong security notion. International Association for Cryptologic Research, 2014 Authentication nationallicence Homomorphic signatures nationallicence Quotable signatures nationallicence Ahn Jae Johns Hopkins University, Baltimore, MD, USA aut Boneh Dan Stanford University, Stanford, CA, USA aut Camenisch Jan IBM Research - Zurich, Ruschlikon, Switzerland aut Hohenberger Susan Johns Hopkins University, Baltimore, MD, USA aut Shelat Abhi University of Virginia, Charlottesville, VA, USA aut Waters Brent University of Texas at Austin, Austin, TX, USA aut Journal of Cryptology Springer US; http://www.springer-ny.com 28/2(2015-04-01), 351-395 0933-2790 28:2<351 2015 28 145 https://doi.org/10.1007/s00145-014-9182-0 text/html Onlinezugriff via DOI BK010053 XK010053 XK010000 Metadata rights reserved Springer special CC-BY-NC licence nationallicence 1 research-article jats NATIONALLICENCE NATIONALLICENCE NL-springer NATIONALLICENCE 856 40 https://doi.org/10.1007/s00145-014-9182-0 text/html Onlinezugriff via DOI NATIONALLICENCE 700 1- Ahn Jae Johns Hopkins University, Baltimore, MD, USA aut NATIONALLICENCE 700 1- Boneh Dan Stanford University, Stanford, CA, USA aut NATIONALLICENCE 700 1- Camenisch Jan IBM Research - Zurich, Ruschlikon, Switzerland aut NATIONALLICENCE 700 1- Hohenberger Susan Johns Hopkins University, Baltimore, MD, USA aut NATIONALLICENCE 700 1- Shelat Abhi University of Virginia, Charlottesville, VA, USA aut NATIONALLICENCE 700 1- Waters Brent University of Texas at Austin, Austin, TX, USA aut NATIONALLICENCE 773 0- Journal of Cryptology Springer US; http://www.springer-ny.com 28/2(2015-04-01), 351-395 0933-2790 28:2<351 2015 28 145