# «Eike Kiltz∗ Anton Mityagin† Saurabh Panjwani‡ Barath Raghavan§ April 30, 2005 Abstract We present a new primitive—Append-only Signatures ...»

2 Append-only Signatures Informally, append-only signatures (AOS) are signatures that enable the public extension of existing signatures. That is, any party given an AOS signature Sig on a message (M1,..., Mn ) can compute an AOS signature on any message (M1,..., Mn, Mn+1 ). (As in the introduction, one could represent the message (M1,..., Mn ) as the string M1 ||... ||Mn which better captures the idea of appending. However, since we want to diﬀerentiate between a message of the form “A” “B” and that of the form “AB” (“A”,“B” and “AB” being three diﬀerent message symbols), we prefer to think of messages as n-tuples). Besides the append operation, AOS is the same as ordinary signatures. That is, given only an AOS signature on the message (M1,..., Mn ) it should be infeasible to forge an AOS signature on any message not having (M1,..., Mn ) as a preﬁx. In terms of conventional signatures, AOS may seem strange, as it allows the “forgery” of signatures on messages not previously obtained. In particular, given a signature on the empty message ε, a signature on any message (M1,..., Mn ) can be computed. In the context of AOS, we view this as a feature, and, as we will show, this is useful in several applications.

We now formally deﬁne AOS and the corresponding notion of security. Let AOS.MSpace be any set of symbols (for example, {0, 1} or {0, 1}∗ ). For an integer n ≥ 0, a message of length n is an n tuple of symbols written as M [1..n] = (M1, M2,..., Mn ) with Mi ∈ AOS.MSpace.

The special case of n = 0 is the empty message, denoted as ε, also written as M [1..0]. We use the symbol ⊑ to denote the preﬁx relation over the messages: for a given message M [1..n] = (M1, M2,..., Mn ), any message from the set {M [1..i], 0 ≤ i ≤ n} is a preﬁx. Note that ε is a preﬁx of any other message.

An append-only signature (AOS) scheme with respect to the message space AOS.MSpace is a collection of three algorithms: a setup algorithm (AOS.Setup), an append algorithm (AOS.Append),

**and a verify algorithm (AOS.Vfy), deﬁned as follows:**

• AOS.Setup (the key generation algorithm) takes the security parameter as input and outputs a pair of keys: the public key AOS.pk and the secret key Sig[ε], which is the signature on the empty message ε.

• AOS.Append (the append algorithm) takes the public key AOS.pk, a signature on a message M [1..n − 1] = (M1,... Mn−1 ), of length n − 1, and a symbol Mn ∈ AOS.MSpace and produces a signature on the message M [1..n] = (M1,..., Mn ).

• AOS.Vfy (the veriﬁcation algorithm) takes the public key AOS.pk, a message M [1..n], and a signature sig, and returns either true or false.

All algorithms can be randomized and all of them must be polynomial-time in the security parameter. Additionally, the scheme should have the property that for any pair (AOS.pk, Sig[ε]) generated by AOS.Setup(1k ) and any message M [1..n] = (M1, M2,..., Mn ) (where n is polynomially bounded in the security parameter), the signature on M [1..n] given by sig = AOS.Append(AOS.pk, M [1..n − 1], AOS.Append(AOS.pk, M [1..n − 2],...

..., AOS.Append(AOS.pk, Sig[ε], M1 ), · · ·, Mn−1 ), Mn ) (1) should be accepted by a veriﬁcation algorithm. That is, AOS.Vfy(AOS.pk, M [1..n], sig) must return true.

The way an AOS signature is deﬁned in Eq. (1) implies that the only way of appending a sequence of symbols to a given AOS signature is to append the symbols one-by-one.

This means that the distribution of an AOS signature created by appending a symbol Mn to a message (M1, · · ·, Mn−1 ) is the same as the distribution of the signature on the message (M1, · · ·, Mn−1, Mn ) when generated from scratch (using the secret key Sig[ε]). This fact ensures history independence of AOS: that is, no party, given an AOS signature, can tell whether the signature was created by the owner of the secret key or whether it passed through multiple parties that appended symbols at every step1. History independence is a useful property to have The above deﬁnition precludes trivial schemes of the following form: Let SG N = (SGN.G, SGN.S, SGN.V) be any standard digital signature scheme. Construct an append-only signature scheme using SG N in which the signature of any message M [1..n] = (M1, · · ·, Mn ) is (SGN.S(M [1..n]), n) and the program AOS.Append takes a in most applications (as already highlighted in previous work on algebraic signatures [JMSW02] and incremental signatures [BGG95]).

Note that in our deﬁnition of security, adversary A is given access to the oracle AOSSign(·), not to the oracle Extract(·). (The latter is used internally by AOSSign(·) to create intermediate signatures.) The history independence property of AOS ensures that the adversary can get no advantage when given the power to decide “how” the signature on any message is to be created by AOSSign(·) (for example, whether it asks for a message (M1, M2 ) to be signed from scratch or by ﬁrst signing M1 and then appending M2, it would get the same reply in return).

3 Eﬃcient AOS Constructions

3.1 Certiﬁcate-Based Append-Only Signatures We present an eﬃcient construction of a provably-secure AOS scheme based on a public-key signature scheme. Let SG N = (SGN.G, SGN.S, SGN.V) be a signature scheme with a space of public keys SGN.PKSpace and message space SGN.MSpace = AOS.MSpace × SGN.PKSpace. (A formal deﬁnition of a public-key signature scheme including a security deﬁnition is given in Appendix A.) That is, messages to be signed by SG N are tuples of the form (M, pk), where M ∈ AOS.MSpace and pk ∈ SGN.PKSpace. Intuitively, an AOS signature Sig of a message

**M [1..n] consists of the following elements:**

{pk1, sig 1,..., pkn, sig n, skn }, message M [1..n], its signature (σ, n) and a new symbol M [n + 1] and simply outputs (σ, n). Veriﬁcation of a signature (σ, n) on message M [1..N ] (N ≥ n) is carried out by testing if σ is the signature, according to SG N, on M [1..n]. Although this scheme allows appending to already signed messages in an arbitrary manner, one can easily distinguish between signatures created by such append operations and those created from scratch.

where for 1 ≤ i ≤ n, (pk i, sk i ) are random public/secret key pairs of the public-key signature scheme SG N and sig i is a signature on the tuple (Mi, pk i ) under the secret key ski−1. Note that the secret key sk i used to sign sig i is entangled with sig i+1 by signing its corresponding public key pk i, thereby certifying its validity. For this reason, this construction is sometimes referred to as a certiﬁcate chain. The signature sig 0 needs to be signed with the secret key sk 0, which we deﬁne to be the master secret key.

More formally, we construct the AOS scheme AOS1 with the message space AOS.MSpace

**as speciﬁed below:**

• AOS.Setup(1k ) (the setup algorithm):

Run SGN.G(1k ) to generate a pair (sk0, pk0 ). Set AOS.pk ← pk0 and Sig[ε] ← {sk0 }.

Return (AOS.pk, Sig[ε]).

• AOS.Append(AOS.pk, Sig[M [1..n]], Mn+1 ) (the append algorithm):

Parse Sig as {pk1, sig 1,..., pkn, sig n, skn }. If n = 0, then Sig[ε] consists of a single secret key sk0. Run SGN.G(1k ) to generate a pair (skn+1, pkn+1 ). Compute sig n+1 ← SGN.Sskn (Mn+1, pkn+1 ). Return {pk1, sig 1,..., pkn, sig n, pkn+1, sig n+1, skn+1 }.

• AOS.Vfy(AOS.pk, M [1..n], Sig) (the veriﬁcation algorithm):

Parse Sig as {pk1, sig 1,..., pkn, sig n, skn }. If n = 0, then Sig = {sk0 }. Set pk0 to be the master public key AOS.pk. For i = 1..n−1 verify that SGN.V(pki−1, sig i, (Mi, pki )) = true.

If any of the veriﬁcations fail, return false. If all the veriﬁcations succeed, verify that (skn, pkn ) is a valid secret key/public key pair: pick any message M ∈ SGN.MSpace and $ compute sig ← SGN.S(skn, M ). Return true if SGN.V(pkn, sig, M ) = true and false otherwise.

The length of a signature of AOS1 grows linearly with the number of symbols in a message.

The eﬃciency of AOS1 is summarized in Table 1. We prove aos-uf-cma security of AOS1 provided that the original public-key signature scheme SG N is sig-uf-cma secure (as deﬁned in Appendix A).

** Theorem 3.1 The AOS scheme AOS1 is aos-uf-cma secure assuming that the public-key signature scheme SG N is sig-uf-cma secure.**

The full proof of Theorem 3.1 is in Appendix B. Here we sketch the main ideas of why this construction works. Intuitively, in order to break the aos-uf-cma security of AOS1, an adversary has two choices between which we must distinguish. First, she could try to forge a signature on a preﬁx of a message she already knows the signature of. Since a valid AOS1 signature of this preﬁx (say, of length n′ ) has to contain the secret key sk n′ in cleartext, this would imply a full break of the security of the signature scheme. Second, the adversary could try to forge an AOS signature on a message that is diﬀerent from all those with known signatures. To do so, the adversary could use existing public/secret key pairs, meaning she has to produce (for some i) a new signature on a tuple (Mi, pk i ) under an unknown secret key and a diﬀerent message Mi.

Otherwise, the adversary breaks the certiﬁcate chain. That is, at some position i, the adversary creates a fresh secret-public key pair (sk i, pk i ) and uses sk i to create sigi. However, sigi−1 is a signature on the public key pk i and the symbol Mi−1 under the secret key sk i−1. In order to use a new secret key sk i to create sigi, the adversary has to forge a signature under the unknown secret key sk i−1. This clearly contradicts the uf-cma security of the signature scheme.

Metric Certiﬁcate-based AOS n SG N signatures, n SG N public keys, 1 SG N secret key Signature length 1 × SGN.G(·) Setup time 1 × SGN.G(·), 1 × SGN.S(·) Append time (n + 1) × SGN.V(·), 1 × SGN.S(·) Verify time Table 1: Eﬃciency of certiﬁcate-based AOS. Data is given for messages of length n.

3.2 Shorter Signatures via Aggregation An aggregate signature scheme, A SG N = (ASGN.G, ASGN.S, ASGN.AGG, ASGN.V), allows the aggregation of n signatures on n distinct messages from n distinct users into a single signature.

Its veriﬁcation algorithm, ASGN.V(n, ·), takes an aggregated signature, n messages, and n public keys and veriﬁes that the n users signed the n messages. A sequential signature aggregation algorithm assumes to receive the signatures sequentially: given an aggregated signature of n − 1 messages and a signature on an nth message, it outputs an aggregated signature for all n messages.

When using the certiﬁcate-based construction of AOS from Section 3.1, we can use sequential signature aggregation to shrink the size of the signature (without signiﬁcantly decreasing security or eﬃciency). To be more precise, the length of an AOS signature of a message of length n can be condensed to one signature of A SG N, n public keys of A SG N, and one secret key of A SG N.

We summarize the eﬃciency of this approach in Table 2. We note that there are two known signature aggregation techniques. The ﬁrst scheme, given in [BGLS03], is based on bilinear maps. The second scheme (only supporting sequential aggregation) is from [MOR01] and can be based on homomorphic trapdoor permutations (such as RSA). We note that both aggregation schemes are in the random oracle model.

Table 2: Eﬃciency of AOS with signature aggregation. Data is given for messages of length n.

3.3 Compact Signatures via the Boneh-Goh-Boyen HIBE

Table 3: Eﬃciency of AOS2. d represents the maximum message length. e(·, ·) is a pairing operation on elements of the group G1 as used by the HIBE scheme.

0, 1 0, 1 0, 0 1, 1 1, 0 [0, 1] [0, 0] [0,[1, 1] 0] [1, 0] [0] [1] [1]

Figure 1: Structure of the hash-tree construction for d = 2. The diagram on the left depicts the hash tree. The diagram on the right highlights the node u = 0, 1 (shown in black) and the set of its complements, Comp(u) (shown in gray).

3.4 AOS via Hash Trees If the number of symbols in the alphabet AOS.MSpace is small, AOS can be eﬃciently implemented using hash trees [Mer88]. This approach suﬀers from dramatic complexity blowup as the size of the message space increases, but uses only secret-key primitives and provides good security guarantees. We believe that this construction is useful in computationally constrained applications.

Next we construct an AOS scheme AOS3 with ﬁxed message space AOS.MSpace = {0, 1};

the messages of AOS3 are limited to length at most d. The construction uses a pseudorandom generator and a collision-resistant hash function (for a formal deﬁnition of the two primitives we refer the reader to the textbook of Goldreich [Gol01]). Let G : {0, 1}k → {0, 1}2k be a pseudorandom generator. Denote Gi : {0, 1}k → {0, 1}k to be the i-th k -bit component of G for i ∈ {0, 1}. Let H : {0, 1}2k → {0, 1}k be a collision-resistant hash function.

Consider the left graph T depicted in Figure 1. T consists of the upper tree U T and lower tree LT. The top node ε is called the source and the bottom node ε is called the destination.

˜ Let v1,..., vj denote the node at level j below ε (in the upper tree) such that each vi ∈ {0, 1} is an index of a node taken at the i-th level on the path from ε to v1,..., vj. A mirror image of this node in the lower tree is denoted as [v1,..., vj ].

Let u = v1,..., vj be any node in the upper tree of the graph. We deﬁne the complement of u, denoted Comp(u), to be the minimal set of nodes in LT − {˜} such that every path from ε ε to ε passes through exactly one node from {u} ∪ Comp(u). An example of a complement ˜ set is given in Figure 1 (the right graph). Let ¬ denote the not operator. Then Comp(u) = {[v1,..., vi−1, ¬vi ] | i = 1,..., j}.