Secure Efficient History-Hiding Append-Only Signatures in the Standard Model

Benoît Libert 1 Marc Joye 2 Moti Yung 3, 4 Thomas Peters 5, 6, 7, 8
1 ARIC - Arithmetic and Computing
Inria Grenoble - Rhône-Alpes, LIP - Laboratoire de l'Informatique du Parallélisme
8 CASCADE - Construction and Analysis of Systems for Confidentiality and Authenticity of Data and Entities
DI-ENS - Département d'informatique de l'École normale supérieure, Inria Paris-Rocquencourt, CNRS - Centre National de la Recherche Scientifique : UMR 8548
Abstract : As formalized by Kiltz et al. (ICALP '05), append-only signatures (AOS) are digital signature schemes where anyone can publicly append extra message blocks to an already signed sequence of messages. This property is useful, e.g., in secure routing, in collecting response lists, reputation lists, or petitions. Bethencourt, Boneh and Waters (NDSS '07) suggested an interesting variant, called history-hiding append-only signatures (HH-AOS), which handles messages as sets rather than ordered tuples. This HH-AOS primitive is useful when the exact order of signing needs to be hidden. When free of subliminal channels (i.e., channels that can tag elements in an undetectable fashion), it also finds applications in the storage of ballots on an electronic voting terminals or in other archival applications (such as the record of petitions, where we want to hide the influence among messages). However, the only subliminal-free HH-AOS to date only provides heuristic arguments in terms of security: Only a proof in the idealized (non-realizable) random oracle model is given. This paper provides the first HH-AOS construction secure in the standard model. Like the system of Bethencourt et al., our HH-AOS features constant-size public keys, no matter how long messages to be signed are, which is atypical (we note that secure constructions often suffer from a space penalty when compared to their random-oracle-based counterpart). As a second result, we show that, even if we use it to sign ordered vectors as in an ordinary AOS (which is always possible with HH-AOS), our system provides considerable advantages over existing realizations. As a third result, we show that HH-AOS schemes provide improved identity-based ring signatures (i.e., in prime order groups and with a better efficiency than the state-of-the-art schemes).
Type de document :
Communication dans un congrès
Public Key Cryptography 2015 (PKC 2015), Mar 2015, Washington DC, United States. Springer, 9020, 2015, Public Key Cryptography 2015 (PKC 2015). 〈https://www.iacr.org/workshops/pkc2015/〉. 〈10.1007/978-3-662-46447-2_20〉
Liste complète des métadonnées

Littérature citée [48 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/hal-01225344
Contributeur : Benoit Libert <>
Soumis le : vendredi 6 novembre 2015 - 10:22:34
Dernière modification le : vendredi 25 mai 2018 - 12:02:05
Document(s) archivé(s) le : lundi 8 février 2016 - 12:46:12

Fichier

superset-sig-final.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

Collections

Citation

Benoît Libert, Marc Joye, Moti Yung, Thomas Peters. Secure Efficient History-Hiding Append-Only Signatures in the Standard Model. Public Key Cryptography 2015 (PKC 2015), Mar 2015, Washington DC, United States. Springer, 9020, 2015, Public Key Cryptography 2015 (PKC 2015). 〈https://www.iacr.org/workshops/pkc2015/〉. 〈10.1007/978-3-662-46447-2_20〉. 〈hal-01225344〉

Partager

Métriques

Consultations de la notice

513

Téléchargements de fichiers

107