# «Append-Only Signatures Eike Kiltz∗ Anton Mityagin† Saurabh Panjwani‡ Barath Raghavan§ May 6, 2005 Abstract We present a new ...»

In AOS3, we associate every node of the graph T with a secret key. Keys are assigned in a top-down manner, starting with a random key for the root ε of U T. Furthermore, for nodes in U T everybody can compute key( v1,..., vj, 0 ) and key( v1,..., vj, 1 ) from key( v1,..., vj, 0 ) (using the pseudo random generators G0 (·), G1 (·)) and for nodes in LT everybody can compute key([v1,..., vj ]) from key([v1,..., vj, 0]) and key([v1,..., vj, 1]) (using the hash function H(·, ·)).

The nodes between LT and U T are “connected” through the pseudorandom generator G 0 (·).

The secret key is key(ε), the public key is key(˜). The AOS of a node v1,..., vn (representing ε n, n ≤ d) is given by the set of keys {key(x) | x ∈ the message M [1..n] = (M1,..., Mn ) ∈ {0, 1} { v1,..., vn }∪Comp( v1,..., vn )}. Veriﬁcation of a given AOS is done by computing top-down the corresponding keys in LT and checking if the last key matches the public key key(˜). The ε

**algorithms constituting AOS3 are deﬁned as follows:**

We give the eﬃciency of this scheme in Table 4. We prove aos-uf-cma security of the AOS3

**scheme assuming the security of the underlying functions G(·) and H(·, ·):**

** Theorem 3.2 If G(·) is a secure pseudorandom generator, G0 (·), G1 (·), are secure one-way functions and H(·, ·), G0 (·), and G1 (·) are all collision-resistant hash functions, then AOS3 is aos-uf-cma secure.**

Table 4: Eﬃciency of the hash-tree based scheme AOS3. d represents the maximum message length, n represents the length of a given message, and k is the security parameter.

3.5 AOS via One-time Signatures We observe that we can combine the ideas of certiﬁcate-based AOS (Section 3.1) and hash-tree AOS (Section 3.4) to gain a more eﬃcient append-only signature scheme when the message space is small. Assume the message space AOS.MSpace consists of m elements. Then we can use our certiﬁcate-based construction AOS1 instantiated with a m-time signature scheme. mtime signatures can be eﬃciently constructed using hash-trees (see [BM96], [HM02], [Mer88], and [RR02] for the deﬁnition and eﬃcient constructions of m-time signatures). In addition, the security proof of AOS1 guarantees unforgeability if SGN is at least an |AOS.MSpace|-time signature scheme. Note that in contrast to AOS3, the length of the AOS messages in this construction is unbounded2.

4 Relations between HIBS and AOS In this section, we show that the concepts of AOS and Hierarchical Identity-based Signatures (HIBS) are in fact equivalent. Before we present the poly-time reductions between the AOS and HIBS, we ﬁrst review related concepts and relationships.

In Identity-based Signature (IBS) schemes, the identity of a sender (for example, an email address) is used as a public key for veriﬁcation of the signature. This approach assumes the existence of a trusted party (the certiﬁcate authority), which assigns secret keys to all users.

The certiﬁcate authority has a pair of keys: a master public key and a master secret key; the master secret key is used to delegate keys to the users and the master public key is used for signature veriﬁcation. Anyone can verify signatures on messages signed by any user, knowing only the master public key and the identity of that user.

Hierarchical Identity-based Signature (HIBS) schemes are a natural generalization of IBS to the setting with a hierarchical organization of users. Assume that the users are structured in a tree with a root being the certiﬁcate authority. Descendants of a user are the usernames that contain this user’s name as a preﬁx; the canonical example involves domain names. In HIBS, each individual user can play the role of a certiﬁcate authority and can delegate secret keys to his descendants. As in IBS, a secret key allows a user to sign arbitrary messages such that anyone is able to verify the signature knowing only the identity of the sender and the master public key (announced by the certiﬁcate authority, who can be viewed as the root user). A formal description of HIBS follows.

Hierarchical Identity-based Encryption (HIBE) assumes the same hierarchy of users as HIBS and provides encryption/decryption mechanisms rather than signatures. In HIBE, anyone can Similar ideas were used by Abdalla and Reyzin [AR00] who who suggested how to improve the eﬃciency of binary certiﬁcation method for constructing forward-secure signatures (see also Bellare and Miner [BM99]).

encrypt data to any user in the hierarchy knowing only the user’s identity and the master public key; the ciphertext can only be decrypted using the user’s secret key.

As noted by Naor (see Section 6 of [BF03]), any IBE scheme can readily be converted into a public key signature scheme (by interpreting user identities of IBE as messages for a regular signature scheme and deﬁning the signature of a message to be the secret key associated with the corresponding identity). Similarly, any HIBE scheme can be transformed into a HIBS scheme.

This was sketched by Gentry and Silverberg [GS02], giving the construction for a HIBS scheme.

We note that the converse (transforming HIBS into HIBE) is not known to be possible. Related to these are Forward-secure Signature (FSS) schemes, which modify a secret key over time (while the public key remains the same) such that exposure of the secret key at a certain time period does not allow forgery of signatures from previous time periods. (See [BM99] for an exact deﬁnition of FSS.) In [CHK03] it is proved that HIBE implies Forward-secure Encryption (FSE) (which is deﬁned as FSS with signing replaced by encryption). Using the same construction it is easy to show that HIBS implies FSS (as explicitly noted in [CHYC04]). More precisely, a HIBS scheme of depth d can be used to construct a forward-secure scheme providing security for 2d time steps (using a tree-based construction). The converse (transforming FSS into HIBS) is not known to be possible. Thus, relating HIBE, HIBS, AOS, and FSS, we obtain the following

**hierarchy:**

HIBE ⇒ HIBS ⇔ AOS ⇒ FSS In particular, given a secure HIBE scheme, we can construct a secure AOS scheme and given a secure AOS scheme, it is easy to obtain a secure FSS scheme.

4.1 Deﬁnition of HIBS We recall the syntax of Hierarchical Identity-based Signature (HIBS) schemes and the appropriate notions of unforgeability. Let HIBS.IDSpace be any set of identities (typically {0, 1} ∗ ). For an integer n ≥ 0, a username at the level n in the tree (called hierarchical identity of depth n) is an (ordered) n-tuple of identities written as I[1..n] = (I1, I2,..., In ) with each Ii ∈ HIBS.IDSpace.

The special case of n = 0 is the root identity, denoted as I[1..0] or ε. Further on, we will

**refer to strings from HIBS.IDSpace as identities and to n-tuples of them as hierarchical identities. We use the symbol to denote the preﬁx relation over the set of hierarchical identities:**

for a given hierarchical identity I[1..n] = (I1, I2,..., In ), any hierarchical identity from the set {I[1..i], 0 ≤ i ≤ n} is its preﬁx. Note that the root identity ε is a preﬁx of any other hierarchical identity.

A HIBS scheme HIBS with respect to the message space HIBS.MSpace and the identity space HIBS.IDSpace is made up of four algorithms: a setup algorithm HIBS.Setup, a key delegation algorithm HIBS.KeyDel, a signature algorithm HIBS.Sign, and a veriﬁcation algorithm HIBS.Vfy.

• HIBS.Setup (the setup algorithm) takes as input a security parameter and generates the master public key HIBS.pk of the scheme and the secret key of the root identity HIBS.SK[ε] (the master secret key).

• HIBS.KeyDel (the key delegation algorithm) takes as input a hierarchical identity I[1..n] = (I1,..., In ), its associated secret key HIBS.SK[I[1..n]], and an identity In+1 ∈ HIBS.IDSpace of its child. It returns a secret key HIBS.SK[I[1..n+1]] associated with the new hierarchical identity I[1..n + 1] = (I1,..., In, In+1 ).

• HIBS.Sign (the signing algorithm) takes a hierarchical identity I[1..n], the associated secret key HIBS.SK[I[1..n]], and a message M ∈ HIBS.MSpace. It computes a signature on this message M with respect to this identity.

• HIBS.Vfy (the veriﬁcation algorithm) takes the master public key HIBS.pk, a hierarchical identity I[1..n], a message M, and a signature sig. It outputs true or false depending on whether sig is a valid signature of M signed by hierarchical identity I[1..n].

All these algorithms can be randomized. All of them must be polynomial-time in the security parameter. Moreover, it is required that for all pairs (HIBS.pk, HIBS.SK[ε]) of master public and secret keys output by HIBS.Setup, and for all messages M ∈ HIBS.MSpace, hierarchical identities I[1..n] and associated secret keys HIBS.SK[I[1..n]] (recursively generated from the secret key HIBS.SK[ε] using the HIBS.KeyDel algorithm),

** HIBS.Vfy(HIBS.pk, I[1..n], HIBS.Sign(HIBS.SK[I[1..n]], I[1..n]), M ), M ) = true.**

Unforgeability of the HIBS scheme HIBS under chosen-plaintext attacks is formally deﬁned as

**follows:**

Deﬁnition 4.1 [HIBS-UF-CMA] Let HIBS = (HIBS.Setup, HIBS.KeyDel, HIBS.Sign, HIBS.Vfy) be a hierarchical identity-based signature scheme, let k be the security parameter, and let A be

**an adversary. We consider the experiment:**

Oracle Extract(I[1..i]) // deﬁned recursively if i = 0 return HIBS.SK[ε] else if HIBS.SK[I[1..i]] = deﬁned then return HIBS.SK[I[1..i]] else HIBS.SK[I[1..i]] ← HIBS.KeyDel(HIBS.pk, I[1..i − 1], Extract(I[1..i − 1]), I i ) return HIBS.SK[I[1..i]] The hibs-uf-cma-advantage of an adversary A in breaking the security of the scheme HIBS is deﬁned as hibs-uf-cma hibs-uf-cma (k ) = Pr[ ExpHIBS,A (k ) = 1 ], AdvHIBS,A and HIBS is said to be existentially unforgeable under chosen message attacks (hibs-uf-cmasecure) if the above advantage is a negligible function in k for all polynomial-time adversaries A. Note that the adversary is given access to the two oracles Corrupt(·) and Sign(·, ·), not to the oracle Extract(·). The latter one is only used internally by the experiment.

4.2 Constructing AOS from HIBS The idea of the reduction is as follows. We set AOS.MSpace = HIBS.IDSpace and associate an AOS message (M1,..., Mn ) of length n with the hierarchical identity I[1..n] = (M1,..., Mn ) of depth n. We then deﬁne the signature of this message as the secret key HIBS.SK[I[1..n]] of the hierarchical identity I[1..n].

Given the above analogy between signatures of messages and secret keys of hierarchical identities, we construct an AOS scheme given a HIBS scheme as follows. Appending to a given signature in AOS is done using key delegation in HIBS. The veriﬁcation of an AOS signature HIBS.SK[I[1..n]] is done by signing a random message M ∈ HIBS.MSpace under the secret key HIBS.SK[I[1..n]] and verifying that the resulting signature is valid.

Construction 4.2 Given a HIBS scheme HIBS = (HIBS.Setup, HIBS.KeyDel, HIBS.Sign, HIBS.Vfy),

**we construct an AOS scheme AOS = (AOS.Setup, AOS.Append, AOS.Vfy) as follows:**

• AOS.Setup: Run the HIBS.Setup algorithm to generate a pair (HIBS.pk, HIBS.SK[ε]) and output (HIBS.pk, HIBS.SK[ε]) as the key pair for AOS. HIBS.SK[ε] is the signature of an empty message ε.

• AOS.Append: Given the public key AOS.pk, signature Sig[M [1..n]] of the message M [1..n], and the message Mn to append, the AOS signature on Sig[M [1..n + 1]] is returned as Sig[M [1..n + 1]] ← HIBS.KeyDel(HIBS.pk, Sig[M [1..n]], Mn+1 ).

• AOS.Vfy: Given a public key AOS.pk, a message M [1..n], and a signature Sig[I[1..n]], the veriﬁcation algorithm ﬁrst signs a random message M ∈ HIBS.MSpace under hierarchical

**identity M [1..n] using Sig[I[1..n]] as a secret key of M [1..n] in HIBS :**

sig ← HIBS.Sign(I[1..n], Sig[I[1..n]], M ).

Then it outputs the result of the HIBS veriﬁcation HIBS.Vfy(HIBS.pk, I[1..n], M, sig).

** Theorem 4.3 If the HIBS scheme HIBS = (HIBS.**

Setup, HIBS.KeyDel, HIBS.Sign, HIBS.Vfy) is hibs-uf-cma secure, then the AOS scheme from Construction 4.2 is aos-uf-cma secure.

We omit the proof of Theorem 4.3.

4.3 Constructing HIBS from AOS A naive approach to building a HIBS scheme HIBS from an AOS scheme AOS is to ﬁrst append all the identities and then to append a message to be signed. That is, both the identity space HIBS.IDSpace and the message space HIBS.MSpace of HIBS are subsets of the message space AOS.MSpace of the AOS scheme. The secret key of a hierarchical identity I[1..n] in this HIBS scheme is exactly the AOS signature of I[1..n] viewed as the AOS message. Delegation in HIBS is equivalent to appending in AOS. Signing a message M with respect to a hierarchical identity I[1..n] is deﬁned by appending M to the AOS signature of I[1..n].

This naive construction is secure only if HIBS.IDSpace and HIBS.MSpace are disjoint subsets of AOS.MSpace. If there is some identity J which itself is a valid message, the security of the HIBS scheme can be broken even if its corresponding AOS is secure. An adversary could query the HIBS signing oracle with a message J and some hierarchical identity I[1..n]. The resulting signature equals the secret key for the hierarchical identity (I1,..., In, J), which violates the security of the HIBS scheme.

Our idea to overcome this problem is to insert a unique identiﬁer between identities and messages. Let AOS = (AOS.Setup, AOS.Append, AOS.Vfy) be a secure AOS scheme with message space AOS.MSpace. Let HIBS.IDSpace and HIBS.MSpace be arbitrary subsets of AOS.MSpace such that there is some symbol ∆ from the AOS message space which is not a valid identity for the HIBS scheme (∆ can still be in the HIBS message space). Then we can construct a secure HIBS scheme HIBS = (HIBS.Setup, HIBS.KeyDel, HIBS.Sign, HIBS.Vfy) with identity

**space HIBS.IDSpace and message space HIBS.MSpace as follows:**

**Construction 4.4 HIBS = (HIBS.Setup, HIBS.KeyDel, HIBS.Sign, HIBS.Vfy):**