Invariant Signatures and Non-Interactive Zero-Knowledge Proofs are Equivalent (Extended Abstract)
Shafi Goldwasser, Rafail Ostrovsky · 1992
The standard definition of digital signatures allows a document to have many valid signatures. In this paper, we consider a subclass of digital signatures, called invariant signatures, in which all legal signatures of a document must be identical according to some polynomialtime computable function (of a signature) which is hard to predict given an unsigned document. We formalize this notion and show its equivalence to non-interactive zero-knowledge proofs. Appeared in Springer-Verlag Lecture Notes in Computer Sciene, proceedings of CRYPTO-92, August 1992, Santa-Barbara, California. y MIT. This research was supported in part by NSF-FAW CCR-9023313, NSF-PYI CCR-865727, Darpa N0014-89-J-1988, BSF 89-00312. z International Computer Science Institute at Berkeley and University of California at Berkeley. Supported by NSF Postdoctoral Fellowship. Parts of this work were done at MIT, Bellcore and IBM T.J. Watson Research Center. 1 Introduction Currently, due to the lack of proven non...