@InProceedings{GMR84b,
  replaced-by =  { GMR88 },                  
  author = 	 { Shafi Goldwasser and Silvio Micali and Ronald L. Rivest },
  title = 	 { A ``Paradoxical'' Solution to the Signature Problem },
  titleaddon =   { (Extended abstract) },
  pages = 	 { 441--448 },
  doi =          { 10.1109/SFCS.1984.715946 },                  
  booktitle =    { Proceedings Twenty-Fifth IEEE Annual Symposium on Foundations of Computer Science },
  issn =         { 0272-5428 },
  publisher =    { IEEE Computer Society },
  date =         { 1984-10 },                  
  OPTyear = 	 { 1984 },
  OPTmonth = 	 { October 24--26, },
  eventdate =    { 1984-10-24/1984-10-26 },
  eventtitle =   { FOCS '84 },                  
  venue =        { Singer Island, Florida },                  
  OPTorganization = { IEEE },
  keywords =     { cryptography, digital signatures, factoring, chosen message attacks,
                   authentication, claw-free paris of functions, randomization },                  
  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 a specific instance of our general scheme, we prove that
        \begin{enumerate}
          \item forging signatures is provably equivalent to factoring, while
          \item adaptive chosen message attacks are of no help to an ``enemy'' who
                wishes to forge a signature.  
        \end{enumerate}
        Such a 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.                          
                 },
}