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

We are left to show what happens when the AOSSign query M [1..n] contains M + [1..n+ ] as a preﬁx and n+ n. We know that signatures of all the preﬁxes of length smaller that n+ are correctly distributed. The recursive Extract oracle constructs Sig[M [1..n+ ]] and appends it using the SGN.Ssk (·) oracle. The signature Sig[M [1..n+ ]] has the form {pk 1, sig 1,..., pk n+, sig n+, sk n+ }, where pk n+ = pk and sk n+ = false. The input public key pk was generated by SGN.G(1k ) and thus pk n+ is correctly distributed. To append Sig[M [1..n+ ]] with Mn+ +1, Extract(·) computes (sk n+ +1, pk n+ +1 ) ← SGN.G(1k ), queries sig sk (Mn+ +1, pk n+ +1 ) and sets Sig[M [1..n+ + 1]] ← {pk 1, sig 1,..., pk n+ +1, sig n+ +1, sk n+ +1 }. This signature is correctly distributed and all the following signatures are constructed by appending this one using AOS.Append.

Proof of of Claim B.2: Let A terminate and output a forgery for M ∗ [1..n]. Without loss of generality we can assume that no preﬁx of M ∗ [1..n] is contained in MSGSet. Thus the target message M ∗ [1..n∗ ] must be diﬀerent from all the AOSSign queries made by A. The previous claim established that A’s AOSSign queries are totally independent from the choice of M + [1..n+ ].

The index of the guessed message was uniformly chosen from [1..s]. If there exists an AOSSign query equal to M + [1..n+ ], then B declares Failure; otherwise A outputs message M ∗ [1..n∗ ] which must be diﬀerent from all the AOSSign queries. Therefore the probability that B does not fail and that M ∗ [1..n∗ ] = M + [1..n+ ] is exactly 1/s.

Here Advxxx (k ) denotes the advantage of a (polynomially bounded) adversary B attacking the S,B xxx security of the primitive S, where xxx can be cr (collision resistance), 1-way (one-wayness), or prg (pseudorandomness). For a formal deﬁnition we refer the reader to the textbooks of Goldreich [Gol01, Gol04]).

We denote the original aos-uf-cma experiment played by A as Exp. Consider an arbitrary adversary A that is run in Exp. At the key-generation stage the challenger picks a random secret key key(ε), computes the values of key(·) on all the nodes in the graph T, and gives a public key key(˜) to A. The adversary outputs a forgery (M ∗ [1..t], Sig∗ ) and with probabilε ity Advaos-uf-cma (k ), A’s forgery is valid. Let u∗ = M1,..., Mt∗ and parse Sig∗ as the set ∗ AOS3,A {key∗ (x) | x ∈ {u∗ } ∪ Comp(u∗ )}. Let Desc(u∗ ) be the set {u∗ } ∪ Comp(u∗ ) including all their (lower) descendants in the graph T. Then the signature on u∗ deﬁnes key∗ (·) on the set Desc(u∗ ).

We deﬁne the event

i.e. key∗ (˜) = key(˜). We deﬁne KEYS as the event that key∗ (x) = key(x) on all x ∈ Desc(u∗ ) ε ε in experiment Exp. Then we have

Intuitively, we are going to show that in the ﬁrst case there is an eﬃcient attack on the pseudorandomness of G or the one-wayness of G0 or G1 and in the second case one can break collision-resistance of H, G0 or G1.

We will bound p1 and p2 in turn. First we bound p2. Note that ¬E means that there exists some x ∈ Desc(u∗ ) such that key∗ (x) = key(x). Hence FORGE ∧ ¬KEYS means that among the possible descendants x ∈ Desc(u∗ ) satisfying key∗ (x) = key(x), there must exist some x together with one of its children y, such that key∗ (x) = key(x) but key∗ (y) = key(y) (since we require key∗ (˜) = key(˜)).

ε ε Consider the following adversary B (attacking the collision resistance of G0, G1 or H) that runs the aos-uf-cma experiment for A. B picks a random secret key key(ε), recursively computes key(x) for all nodes x in the graph T, and returns the public key key(˜) to A. The input of ε A is distributed identically to the experiment Expaos-uf-cma (k ). Thus with probability p2, A AOS3,A outputs a valid forgery {key∗ (x) | x ∈ {u∗ } ∪ Comp(u∗ )} for some node u∗ ∈ U T such that there exists a node x ∈ T (x is some descendant x of {u∗ } ∪ Comp(u∗ )) and its child y such that key∗ (x) = key(x) but key∗ (y) = key(y). Such an x can be identiﬁed by B in the same time as verifying a signature. If x ∈ U T then {key∗ (x), key(x)} is a collision either for G0 or G1 (Gi (key∗ (x)) = Gi (key(x)) for some i ∈ {0, 1}). Otherwise let x′ be another parent of y, then H(key∗ (x), key∗ (x′ )) = H(key(x), key(x′ )) and {(key∗ (x), key∗ (x′ )), (key(x), key(x′ ))} is a collision for H(·, ·). Therefore p2 ≤ Advcr (k ) + Advcr0,B (k ) + Advcr1,B (k ).

H,B G G We now proceed to bound p1. First consider a single adversary C0 participating in the oneway experiments for both G0 and G1 simultaneously. The adversary C0 will run A and in the case A successfully forges AOS3, she will win in either one of the experiments (that is, ﬁnding a preimage for G0 or G1 of a given input value C). Second, consider an adversary C1 participating in the same oneway experiment and that only slightly diﬀers from the description of adversary C0. The adversary C1 will be used to bound probability p1.

Finally, using a hybrid argument, we will connect the two adversaries by showing that the views of adversary A when run by C0 and C1 in the execution of the experiment are computational indistinguishable assuming G is a pseudorandom generator.

**We describe the two adversaries C0 and C1 as follows:**

**Adversary Ci (1k, c):**

$ key(ε) ← {0, 1}k and deﬁne key(·) recursively on all the descendants.

+$ + Pick a random node u+ = M1,..., Mn ← U T \ {ε} ∪ {d-th level of LT }.

+ ) ← c else do nothing if i = 0 then redeﬁne key(u

**Run A(1k, key(˜)) and answer all the Sign(M [1..t]) queries made by A as follows:**

ε if (M [1..t] = M + [1..t]) and (t n) then return abort.

else set u = M1,..., Mt ; return Sig = {key(x) | x ∈ {u} ∪ Comp(u)}.

Eventually A terminates and outputs a forgery Sig∗ for some message M ∗ [1..t].

Denote M1,..., Mt∗ as u∗ ; parse Sig∗ as {key∗ (x) | x ∈ u∗ ∪ Comp(u∗ )}.

∗ if M ∗ [1..t] = M + [1..n − 1] then return key∗ (u∗ ) else return abort.

For i ∈ {0, 1} denote by Expi the simultaneous oneway experiment when run under adversary Ci. We deﬁne the two events ABORTCi :Adversary Ci aborts in experiment Expi KEYSCi :key∗ (x) = key(x) for all x ∈ Desc(u∗ ) in experiment Expi Furthermore, we deﬁne the two probabilities

in experiment Expi. Intuitively, in the remainder of the proof we will show that the value q0 is related to the onewayness of G0 and G1, that q1 can be lower bounded using p1, and that |q0 − q1 | is small.

Consider the experiment Exp0. Assuming C0 does not abort, u+ is a child of u∗ and hence we have GMn (key∗ (u∗ )) = key(u+ ) = c if the event KEYSC0 happens. Hence adversary C0 outputs +

in experiment Exp0. We will now lower bound probability q1 in experiment Exp1.

Claim C.1 q1 ≥ p1 /(3 · 2d ).

We rewrite q1 as q1 = Pr [ KEYSC1 | ¬ABORTC1 ] · Pr[ ¬ABORTC1 ].

The event ¬ABORTC1 in Exp1 happens if and only if the right value for u+ was guessed by C1, i.e. if u+ is a child of u∗. Hence, assuming C1 does not abort, the view of A in experiment Exp1 is identically distributed to the view of A the experiment Exp. Hence with probability at least p1, A outputs a valid forgery (u∗, Sig∗ ) such that key∗ (x) = key(x) on all descendants

**x ∈ Desc(u∗ ) in Exp1 :**

Since the choice of u+ in the experiment Exp1 is totally independent from the inputs of A (and u+ is chosen randomly from the set of 3 · 2d − 2 nodes), we have

This completes the proof of the claim.

For i ∈ {0, 1} deﬁne Viewi to be the view of adversary A in experiment Expi. The following lemma establishes that the views of A in the experiments Exp0 and Exp1 are computationally indistinguishable.

Lemma C.2 A cannot distinguish between the two distributions View0 and View1 better than with probability 2d · Advprg (k ) for some adversary D running in about the same time as A.

G,D We will prove the lemma later. As an implication of Lemma C.2 we get that |q0 − q1 | ≤ 2d · Advprg (k ). Thus G,D

In Exp1, key(ε) is chosen at random and the keys on the rest of R is generated by iterating G(·).

On the other hand, in Exp0 the values of key(·) on R are deﬁned in the same way except for + + key( M1,..., Mn ), which is replaced by the challenge string for the onewayness experiment.

Our goal is to show that from adversary A’s view, these two experiments are computational indistinguishable.

We deﬁne a sequence of n hybrid adversaries C1 [1],..., C1 [n] as follows: Let C1 [1] = C1 and the i-th adversary C1 [i] behaves like C1 except that it assigns random keys key(·) on the nodes + + + + + { M1,..., Mj, M1,..., Mj−1, ¬Mj | j = 1,..., i} and uses G(·) to compute key(·) on the rest of the nodes. The only diﬀerence between adversaries C1 [i] and C1 [i + 1] is that in the ﬁrst case key( M1,..., Mi+ ), key( M1,..., ¬Mi+ ) are pseudorandom and in the second case they + +

View0 ≈ View′ ≡ View′ [1] ≈... ≈ View′ [n] ≡ View1 [n] ≈... ≈ View1 [1] ≡ View1, where ≈ means that the distributions of the two random variables are computational indistinguishable and ≡ means they are identical. A cannot distinguish between any consecutive pair of the views any better than with probability Advprg (k ), therefore total probability that A will G,D distinguish between View0 and View1 is no more than 2n · Advprg (k ) ≤ 2d · Advprg (k ).

G,D G,D D AOS with short key size In this section we review the hybrid HIBE scheme from Boneh, Goh and Boyen (see Section 4 of [BGB05]) (B G B − H IBE ) achieving short private keys. By the results from Section 4 we know that a HIBE scheme implies an AOS scheme. Motivated by this reduction, we present a concrete AOS scheme (called AOS2 ) based on BG B − H IBE. In presenting the concrete scheme, we are able to make some (straightforward) eﬃciency improvements over the generic reduction by making the AOS veriﬁcation algorithm deterministic (instead of probabilistic).

The main intention of this section is to demonstrate that AOS (and hence also HIBS) can be carried out with secret key size of order “square root of the length of the signed message”.

We brieﬂy review the necessary facts about bilinear maps and bilinear groups. Let G1 and G2 be groups with the following properties.

• G1 is an additive groups of prime order q.

We have stipulated that our groups should have a bilinear map e : G1 × G1 → G2. This should satisfy the conditions below.

Bilinear: For all U, V ∈ G1, a, b ∈ Z, e(aU, bV ) = e(U, V )ab Non-degenerate: e(P, P ) = 1G2

We denote the induced index mapping as π : {1,..., d} → {1,..., l} × {1,..., l} with π(n) = (n1, n2 ). Here n1 is called the row index and n2 the column index.

We may now describe AOS2 = (AOS.Setup, AOS.Append, AOS.Vfy) giving its constituting algorithms.

• AOS.Setup(1k ): Pick two random generators P, Q ∈ G1 and a random element α ∈ Zq.

Next, pick random elements G1,..., Gl and H1,..., Hl ∈ G1. The public key consists of

In this case we have π(n) = (n1, 1) and to generate a signature for the message M [1..n] chose a random r ∈ Zq and compute Sig[M [1..n]] as

The length of the signature of AOS2 grows linearly with the square root of the length of the message. Security is proved with respect to the l + 1-Bilinear Diﬃe-Hellman Exponent (BDHE) assumption. (See [BGB05] for an exact deﬁnition.) Theorem D.1 Suppose the computational l + 1-BHDE assumptions holds in the group G1.

Then the AOS2 scheme is selective message aos-uf-cma secure.

Here selective message aos-uf-cma security is deﬁned similar to Deﬁnition 2.1. The diﬀerence is that in the security experiment, the adversary has to commit to the message she is going to forge the signature for before the public/secret keys are issued and the public key is given to her. In the random oracle model, the scheme can be modiﬁed to get a full unforgeable AOS scheme. However, the security reduction is not tight and only allows for signatures on messages of constant length. Again, we refer the reader to [BGB05] for more details.

The proof of the theorem follows that of the BG B − H IBE scheme from [BGB05] and is omitted here. We note that since we are dealing with signatures instead of encryption, we can prove security of our scheme with respect to a computational assumption (rather than a decisional assumption as the original BG B − H IBE scheme).