Skip to Main content Skip to Navigation
Preprints, Working Papers, ...

Computing on Authenticated Data: New Privacy Definitions and Constructions

Nuttapong Attrapadung 1 Benoit Libert 2, * Thomas Peters 2 
* 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.}
Document type :
Preprints, Working Papers, ...
Complete list of metadata

Cited literature [41 references]  Display  Hide  Download
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


Files produced by the author(s)


  • HAL Id : hal-00730665, version 4


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



Record views


Files downloads