Computing on Authenticated Data: New Privacy Definitions and Constructions

Nuttapong Attrapadung 1 Benoit Libert 2, * Thomas Peters 2
* Auteur correspondant
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.}
Type de document :
Pré-publication, Document de travail
Full version of a paper published at Asiacrypt 2012. 2012
Liste complète des métadonnées
Contributeur : Benoit Libert <>
Soumis le : jeudi 27 décembre 2012 - 11:16:48
Dernière modification le : lundi 13 octobre 2014 - 15:43:25
Document(s) archivé(s) le : jeudi 28 mars 2013 - 03:47:55


Fichiers produits par l'(les) auteur(s)


  • HAL Id : hal-00730665, version 4


Nuttapong Attrapadung, Benoit Libert, Thomas Peters. Computing on Authenticated Data: New Privacy Definitions and Constructions. Full version of a paper published at Asiacrypt 2012. 2012. <hal-00730665v4>



Consultations de
la notice


Téléchargements du document