# Computing on Authenticated Data: New Privacy Definitions and Constructions

* Corresponding author
1 Research Team for Security Fundamentals
RCIS - Research Center for Information Security
2 Groupe Crypto
ICTEAM - Institute of Information and Communication Technologies, Electronics and Applied Mathematics
Abstract : Homomorphic signatures are primitives that allow for public computations on authenticated data. At TCC 2012, Ahn {\it et al.} defined a framework and security notions for such systems. For a predicate $P$, their notion of $P$-homomorphic signature makes it possible, given signatures on a message set $M$, to publicly derive a signature on any message $m'$ such that $P(M,m')=1$. Beyond unforgeability, Ahn {\it et al.} considered a strong notion of privacy -- called strong context hiding -- requiring that derived signatures be perfectly indistinguishable from signatures newly generated by the signer. In this paper, we first note that the definition of strong context hiding may not imply unlinkability properties that can be expected from homomorphic signatures in certain situations. We then suggest other definitions of privacy and discuss the relations among them. Our strongest definition, called {\it complete} context hiding security, is shown to imply previous ones. In the case of linearly homomorphic signatures, we only attain a slightly weaker level of privacy which is nevertheless stronger than in previous realizations in the standard model. For subset predicates, we prove that our strongest notion of privacy is satisfiable and describe a completely context hiding system with constant-size public keys. In the standard model, this construction is the first one that allows signing messages of arbitrary length. The scheme builds on techniques that are very different from those of Ahn {\it et al.}
Keywords :
Document type :
Preprints, Working Papers, ...

Cited literature [41 references]

https://hal.inria.fr/hal-00730665
Contributor : Benoit Libert Connect in order to contact the contributor
Submitted on : Thursday, December 27, 2012 - 11:16:48 AM
Last modification on : Friday, October 1, 2021 - 9:54:07 AM
Long-term archiving on: : Thursday, March 28, 2013 - 3:47:55 AM

### File

hsig-full-version-AC.pdf
Files produced by the author(s)

### Identifiers

• HAL Id : hal-00730665, version 4

### Citation

Nuttapong Attrapadung, Benoit Libert, Thomas Peters. Computing on Authenticated Data: New Privacy Definitions and Constructions. 2012. ⟨hal-00730665v4⟩

Record views