@InProceedings{GMR84a,
  replaced-by =  { GMR88 },                  
  author = 	 { Shafi Goldwasser and Silvio Micali and Ronald L. Rivest },
  title = 	 { A `Paradoxical' solution to the signature problem (brief abstract) },
  pages = 	 { 467 },
  OPTurl =       { http://dx.doi.org/10.1007/3-540-39568-7_37 },
  doi =          { 10.1007/3-540-39568-7_37 },
  booktitle =    { Advances in Cryptology -- Proceedings of CRYPTO 1984 },
  date =         { 1985 },                  
  editor = 	 { George Blakley and David Chaum },
  publisher =    { Springer },
  isbn =         { 978-3-540-15658-1 },
  series = 	 { Lecture Notes in Computer Science },
  volume =       { 196 },
  organization = { IACR },
  OPTyear = 	 { 1985 },
  OPTmonth = 	 { August },
  eventdate =    { 1984-08-19/1984-08-22 },                  
  eventtitle =   { CRYPTO '84 },
  venue =        { Santa Barbara, California },                  
  abstract =     { 
                  We present a general signature scheme which uses
                  any pair of trap-door permutations $(f_0, f_1)$ for
                  which it is infeasible to find any $x, y$ with $f_0(x) =
                  f_1(y)$. The scheme possesses the novel property of
                  being robust against an adaptive chosen message
                  attack: no adversary who first asks for and then
                  receives signatures for messages of his choice (which
                  may depend on previous signatures seen) can later
                  forge the signature of even a single additional
                  message.  
                  \par                  
                  For specific instance of our general
                  scheme, we prove that (1) forging signatures is
                  provably equivalent to factoring (i.e., factoring is
                  polynomial-time reducible to forging signatures, and
                  vice versa) while (2) forging an additional
                  signature, after an adaptive chosen message attack
                  is still equivalent to factoring.  Such scheme is
                  ``paradoxical'' since the above two properties were
                  believed (and even ``proven'' in the folklore) to be
                  contradictory.  
                  \par
                  The new scheme is potentially
                  practical: signing and verifying signatures are
                  reasonably fast, and signatures are not too long.  
                 },
}