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

In Tatsuaki Okamoto, editor, Advances in Cryptology – ASIACRYPT 2000, volume 1976 of Lecture Notes in Computer Science, pages 116–129, Kyoto, Japan, December 3–7, 2000. Springer-Verlag, Berlin, Germany.

[BB04] Dan Boneh and Xavier Boyen. Eﬃcient selective-id secure identity based encryption without random oracles. In Christian Cachin and Jan Camenisch, editors, Advances in Cryptology – EUROCRYPT 2004, volume 3027 of Lecture Notes in Computer Science, pages 223–238, Interlaken, Switzerland, May 2–6, 2004. Springer-Verlag, Berlin, Germany.

[BF03] Dan Boneh and Matthew K. Franklin. Identity based encryption from the Weil pairing. SIAM Journal on Computing, 32(3):586–615, 2003.

[BGB05] D. Boneh, E.-J. Goh, and X. Boyen. Hierarchical identity based encryption with constant size ciphertext. In Ronald Cramer, editor, Advances in Cryptology – EUROCRYPT 2005, Lecture Notes in Computer Science, page ???? Springer-Verlag, Berlin, Germany, May 22–26, 2005.

[BGG94] Mihir Bellare, Oded Goldreich, and Shaﬁ Goldwasser. Incremental cryptography the case of hashing and signing. In Yvo Desmedt, editor, Advances in Cryptology – CRYPTO’94, pages 57–66. Springer-Verlag, Berlin, Germany, August 21–25, 1994.

[BGG95] Mihir Bellare, Oded Goldreich, and Shaﬁ Goldwasser. Incremental cryptography and application to virus protection. In 27th Annual ACM Symposium on Theory of Computing, pages 57–66, Las Vegas, Nevada, USA, May 29 – June 1, 1995. ACM Press.

[BGLS03] Dan Boneh, Craig Gentry, Ben Lynn, and Hovav Shacham. Aggregate and veriﬁably encrypted signatures from bilinear maps. In Eli Biham, editor, Advances in Cryptology – EUROCRYPT 2003, volume 2656 of Lecture Notes in Computer Science, pages 416–432, Warsaw, Poland, May 4–8, 2003. Springer-Verlag, Berlin, Germany.

[BM96] Daniel Bleichenbacher and Ueli M. Maurer. Optimal tree-based one-time digital signature schemes. In STACS ’96: Proceedings of the 13th Annual Symposium on Theoretical Aspects of Computer Science, pages 363–374. Springer-Verlag, 1996.

[BM99] Mihir Bellare and Sara Miner. A forward-secure digital signature scheme. In Michael J. Wiener, editor, Advances in Cryptology – CRYPTO’99, volume 1666 of Lecture Notes in Computer Science, pages 431–448, Santa Barbara, CA, USA, August 15–19, 1999. Springer-Verlag, Berlin, Germany.

[CHK03] Ran Canetti, Shai Halevi, and Jonathan Katz. A forward-secure public-key encryption scheme. In Eli Biham, editor, Advances in Cryptology – EUROCRYPT 2003, volume 2656 of Lecture Notes in Computer Science, pages 255–271, Warsaw, Poland, May 4–8, 2003. Springer-Verlag, Berlin, Germany.

[CHYC04] S. S. M. Chow, L. C. K. Hui, S. M. Yiu, and K. P. Chow. Secure hierarchical identity based signature and its application. In Proceedings of ICICS 2004, pages 480–494, 2004.

[FCC+ 03] Yun Fu, Jeﬀrey Chase, Brent Chun, Stephen Schwab, and Amin Vahdat. SHARP: an architecture for secure resource peering. In Proceedings of the 19th ACM Symposium on Operating System Principles (SOSP), Bolton Landing, NY, October 2003.

[Gol01] Oded Goldreich. Foundations of Cryptography: Basic Tools, volume 1. Cambridge University Press, Cambridge, UK, 2001.

[Gol04] Oded Goldreich. Foundations of Cryptography: Basic Applications, volume 2. Cambridge University Press, Cambridge, UK, 2004.

[GS02] C. Gentry and A. Silverberg. Hierarchical id-based cryptography. In Yuliang Zheng, editor, Advances in Cryptology – ASIACRYPT 2002, volume 2501 of Lecture Notes in Computer Science, pages 548–566, Queenstown, New Zealand, December 1–5,

2002. Springer-Verlag, Berlin, Germany.

[HM02] A. Hevia and D. Micciancio. The provable security of graph-based one-time signatures and extensions to algebraic signature schemes. In Yuliang Zheng, editor, Advances in Cryptology – ASIACRYPT 2002, volume 2501 of Lecture Notes in Computer Science, pages 379 – 396, Queenstown, New Zealand, December 1–5, 2002.

Springer-Verlag, Berlin, Germany.

[HPS04] Yih-Chun Hu, Adrian Perrig, and Marvin Sirbu. SPV: secure path vector routing for securing BGP. In Proceedings of the ACM SIGCOMM Conference, pages 179–192, 2004.

[JMSW02] Robert Johnson, David Molnar, Dawn Xiaodong Song, and David Wagner. Homomorphic signature schemes. In Bart Preneel, editor, Topics in Cryptology – CTRSA 2002, volume 2271 of Lecture Notes in Computer Science, pages 244–262, San Jose, CA, USA, February 18–22, 2002. Springer-Verlag, Berlin, Germany.

[KLS00] Stephen Kent, Charles Lynn, and Karen Seo. Secure border gateway protocol (SBGP). IEEE Journal on Selected Areas in Communications, 18(4):582–592, 2000.

[LMRS04] Anna Lysyanskaya, Silvio Micali, Leonid Reyzin, and Hovav Shacham. Sequential aggregate signatures from trapdoor permutations. In Christian Cachin and Jan Camenisch, editors, Advances in Cryptology – EUROCRYPT 2004, volume 3027 of Lecture Notes in Computer Science, pages 74–90, Interlaken, Switzerland, May 2–6,

2004. Springer-Verlag, Berlin, Germany.

[Mer88] Ralph C. Merkle. A digital signature based on a conventional encryption function.

In Carl Pomerance, editor, Advances in Cryptology – CRYPTO’87, volume 293 of Lecture Notes in Computer Science, pages 369–378, Santa Barbara, CA, USA, August 16–20, 1988. Springer-Verlag, Berlin, Germany.

[MOR01] Silvio Micali, Kazuo Ohta, and Leonid Reyzin. Accountable-subgroup multisignatures. In ACM CCS 01: 8th Conference on Computer and Communications Security, pages 245–254, Philadelphia, PA, USA, November 5–8, 2001. ACM Press.

[MR02] Silvio Micali and Ronald L. Rivest. Transitive signature schemes. In Bart Preneel, editor, Topics in Cryptology – CT-RSA 2002, volume 2271 of Lecture Notes in Computer Science, pages 236–243, San Jose, CA, USA, February 18–22, 2002.

Springer-Verlag, Berlin, Germany.

[Rom90] John Rompel. One-way functions are necessary and suﬃcient for secure signatures.

In 22nd Annual ACM Symposium on Theory of Computing, pages 387–394, Baltimore, Maryland, USA, May 14–16, 1990. ACM Press.

[RR02] Leonid Reyzin and Natan Reyzin. Better than biba: Short one-time signatures with fast signing and verifying. In Proceedings of 7th Australasian Conference ACSIP, 2002.

[Sha85] Adi Shamir. Identity-based cryptosystems and signature schemes. In G. R. Blakley and David Chaum, editors, Advances in Cryptology – CRYPTO’84, volume 196 of Lecture Notes in Computer Science, pages 47–53, Santa Barbara, CA, USA, August 19–23, 1985. Springer-Verlag, Berlin, Germany.

[SRS+ 04] Lakshminarayanan Subramanian, Volker Roth, Ion Stoica, Scott Shenker, and Randy Katz. Listen and whisper: Security mechanisms for bgp. In Proceedings of USENIX/ACM NSDI, 2004.

[WKvO05] Tao Wan, Evangelos Kranakis, and P.C. van Oorschot. Pretty secure BGP (psBGP).

In Proceedings of ISOC NDSS, 2005.

A Public Key Signature Schemes

**A public key signature scheme SG N = (SGN.G, SGN.S, SGN.V) is a collection of three algorithms:**

a key generation algorithm SGN.G, a signing algorithm SGN.S, and a veriﬁcation algorithm SGN.V. These algorithms must be polynomial time in the security parameter and should have

**the following input/output speciﬁcation:**

• SGN.G takes as input the security parameter 1k and outputs a secret key/public key pair (sk, pk ). The public key also includes some system parameters like the description of the message space SGN.MSpace.

• SGN.S takes as input a message M ∈ SGN.MSpace and produces a string sig which is called a signature of a message M.

• SGN.V takes as input a public key pk, a message M and a signature sig and returns either true or false.

The veriﬁcation algorithm must accept all signatures produced by the signing algorithm, namely the following should hold for every (sk, pk ) produced by SGN.G(k ), every message M ∈ SGN.MSpace

**and every choice of random coins:**

Next we deﬁne unforgeability under chosen message attacks (sig-uf-cma) for a signature scheme.

Deﬁnition A.1 [SIG-UF-CMA] Let SG N be a signature scheme, let k be a security parameter,

**and let A be an adversary. We consider the following experiment:**

Signature scheme SG N is said to be unforgeable under chosen message attacks (sig-uf-cma) if the above advantage is negligible function in k for all polynomial-time adversaries A.

B Proof of Theorem 3.1 We show that for any adversary A against AOS1, there exists an adversary B against SG N running in about the same time as A such that Advaos-uf-cma (k ) ≤ s · Advsig-uf-cma (k ).

AOS1,A SG N,B The reduction factor s is the upper bound on the number of messages M for which Sig[M ] is deﬁned by the Extract(·) oracle in the experiment Expforge-cma (k ). This bound should be AOS1,A known by B before she runs the simulation of A and the bound should hold for any choice of the public key, for any random coins of A and for any oracle responses. The number s could be also upper bounded by qe · d, where qe is the maximal number of AOSSign(·) queries made by A and d is the maximal length of the queries.

Now we proceed to the construction of adversary B who attacks the unforgeability of the public key signature scheme SG N. In the sig-uf-cma experiment the challenger runs a key generation algorithm SGN.G(1k ) to get a pair of keys (sk, pk ) and gives pk as input to B as well as an access to the SGN.Ssk (·) oracle.

During its execution B will construct a set T that at each moment of time will contain all the messages M for which Sig[M ] is already deﬁned by Extract(·). This set plays the same role as in the original aos-uf-cma experiment. The only diﬀerence is that now, for each message M [1..n] ∈ T, we will keep not only a signature Sig[M [1..n]] but also a pair of elements (sk M [1..n], pk M [1..n] ). The latter will correspond to the secret key/public key pair for SG N generated by Extract(·) oracle when computing the signature for M [1..n]. The pseudocode

**for the adversary B is given below:**

At a high level, the adversary B works as follows. Before running A, it randomly selects an $ integer guess ← [1..s] which corresponds to an index of some message that will be queried to the Extract(·) oracle. Note that all messages are selected by A, so B does not know in advance the actual message M + [1..n+ ]. (It is deﬁned only at the time when guess-th new message is queried to Extract(·).) Next, B runs A and simulates the AOSSign(·) oracle. B follows the protocol of the original oracle to compute signatures of all the messages that do not contain the guessed one as a preﬁx. For the guessed message M + [1..n+ ], the adversary B sets pk M + [1..n+ ] to be equal to the input public key pk and sk M + [1..n+ ] ← false. Therefore, if A queries the guessed message to the AOSSign oracle, B declares Failure since she does not know the secret key sk which corresponds to pk. However, B still can correctly answer all the AOSSign queries that contain M + [1..n+ ] as a preﬁx by using the SGN.Ssk (·) oracle that is given by the Expsig-uf-cma experiment. Also, since Extract(·) is recursive, any message is added to T only after all its preﬁxes are already in T.

Let A terminate and output a forgery of a message M ∗ [1..n]. B assumes that the forgery is valid and that her guessed message M + [1..n+ ] is equal to the preﬁx M ∗ [1..n∗ ] of the forged message. M ∗ [1..n∗ ] is the longest preﬁx of M ∗ [1..n] such that all the public keys pk ∗,... pk ∗ + 1 n from the signature Sig∗ match the stored public keys pk M ∗ [1],... pk M ∗ [1..n+ ]. In this case, B can easily make a forgery for SG N : if n+ n∗ then sign+ +1 is a forgery for SG N, otherwise (if ∗ + = n∗ ) the secret key sk ∗ should match the unknown secret key sk.

n n Next we bound the advantage of B. There are several events in the experiment we must consider.

FAIL : B does output Failure.

Without loss of generality, we can assume that if B does not fail then A always outputs a forgery Sig∗ for some message M ∗ [1..n] and that no preﬁx of M ∗ [1..n] was queried to AOSSign(·) (if this does not hold, A automatically loses). The second event is deﬁned as

that is, AOS.Vfy(AOS.pk, Sig∗, M ∗ [1..n]) = 1. This event is deﬁned only if B does not fail.

Finally, we consider random variables M + [1..n+ ] and M ∗ [1..n∗ ]. The former random variable, M + [1..n+ ], corresponds to a message, whose signature was deﬁned at the time when B sets guess = ctr. If no such query was made, we set M + [1..n+ ] ← ⊥. The latter random variable, M ∗ [1..n∗ ], corresponds to the “good” preﬁx of the forgery M ∗ [1..n] returned by A. It is deﬁned only if B does not fail. We deﬁne GUESS to be the event that B guesses the message A outputs

**a forgery on:**

GUESS : M + [1..n+ ] = M ∗ [1..n∗ ].

We observe that if B does not fail, A wins and the guess is correct; B then outputs a valid forgery of the signature scheme SG N. Therefore

The analysis is based on the following two claims. The ﬁrst claim establishes that if B guessed the right value for M + [1..n+ ] and B does not output failure then the simulation of A is perfect and we have

It is left to show (3): that if B does not return Failure then the input of A is identically distributed to the original aos-uf-cma experiment.

First, from the construction of B we see that the claim is true for messages that do not contain the guessed message M + [1..n+ ] as a preﬁx. In this case, the Extract oracle uses the AOS.Append algorithm of AOS1 to append the signatures and therefore all signatures are distributed identically to the ones constructed by the Extract oracle in the original aos-uf-cma experiment.

In the case when A queries M [1..n] = M + [1..n+ ] to the AOSSign(·) oracle, the AOSSign(·) oracle calls Extract(M + [1..n+ ]) to get Sig[M + [1..n+ ]]. The signature Sig[M + [1..n+ ]] returned by the Extract oracle to has a form {pk 1, sig 1,..., pk n+, sig n+, sk n+ }, where sk n+ = false and B declares Failure on such a query.