Skip to Main content Skip to Navigation
Conference papers

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).
Document type :
Conference papers
Complete list of metadatas

Cited literature [48 references]  Display  Hide  Download
Contributor : Benoit Libert <>
Submitted on : Friday, November 6, 2015 - 10:22:34 AM
Last modification on : Tuesday, September 22, 2020 - 3:52:46 AM
Long-term archiving on: : Monday, February 8, 2016 - 12:46:12 PM


Files produced by the author(s)




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. ⟨10.1007/978-3-662-46447-2_20⟩. ⟨hal-01225344⟩



Record views


Files downloads