@InProceedings{MR02b, author = { Silvio Micali and Ronald L. Rivest }, title = { Transitive signature schemes }, pages = { 236--243 }, doi = { 10.1007/3-540-45760-7_16 }, booktitle = { Topics in Cryptology - CT-RSA 2002: Cryptographer's Track at the RSA Conference 2002 }, publisher = { Springer }, isbn = { 978-3-540-43224-1 }, date = { 2002-02 }, OPTyear = { 2002 }, OPTmonth = { February 18--22, }, editor = { Bart Preneel }, series = { Lecture Notes in Computer Science }, volume = { 2271 }, eventtitle = { CT-RSA'02 }, eventdate = { 2002-02-18/2002-02-22 }, venue = { San Jose, California }, htmlnote = { A related talk Riv00 was given in 2000. }, OPTannote = {}, keywords = { public-key cryptography, digital signatures, graphs, transitive closure }, abstract = { We introduce and provide the first example of a transitive digital signature scheme. Informally, this is a way to digitally sign vertices and edges of a dynamically growing, transitively closed, graph $G$ so as to guarantee the following properties: Given the signatures of edges $(u, v)$ and $(v,w)$, anyone can easily derive the digital signature of the edge $(u,w)$. \par It is computationaly hard for any adversary to forge the digital signature of any new vertex or other edge of $G$, even if he can request the legitimate signer to digitally sign any number of $G$'s vertices and edges of his choice in an adaptive fashion (i.e., even if he can choose which vertices and edges the legitimate signer should sign next after he sees the legitimate signatures of the ones requested so far). }, }