Constructing Digital Signatures from a One Way Function

At a coffee house in Berkeley around 1975, Whitfield Diffie described a problem to me that he had been trying to solve: constructing a digital signature for a document. I immediately proposed a solution. Though not very practical–it required perhaps 64 bits of published key to sign a single bit–it was the first digital signature algorithm. Diffie and Hellman mention it in their classic paper: Whitfield Diffie and Martin E. Hellman. New Directions in Cryptography. IEEE Transactions on Information Theory IT-22, 6 (1976), 644-654. (I think it’s at the bottom right of page 650.) In 1978, Michael Rabin published a paper titled Digitalized Signatures containing a more practical scheme for generating digital…