7
$\begingroup$

I am reading the Real-World Cryptography book and in the chapter on signatures it says:

The best way to understand how signatures work in cryptography is to understand where they come from. For this reason, let’s take a moment to briefly introduce ZKPs and then I’ll get back to signatures.

I find this hard to believe. Did digital signatures actually come from Zero Knowledge Proofs? I thought ZKP were a more recent advancement in Cryptography while digital signatures are older. If that is the case how could signatures could have originated from ZKPs?

$\endgroup$
2
  • $\begingroup$ A bit of history is here. Rabin Signature is the first true signature! $\endgroup$
    – kelalaka
    Jun 6, 2022 at 21:13
  • 1
    $\begingroup$ Nitpick: In the excerpt you quoted, the author technically doesn't claim that DSs come from ZKPs. $\endgroup$ Jun 7, 2022 at 15:35

1 Answer 1

9
$\begingroup$

Did digital signatures actually come from Zero Knowledge Proofs?

You are correct; the original proposals for digital signatures were not based on zero knowledge proofs.

The idea of digital signatures were first presented in New Directions in Cryptography, which proposed using a trapdoor permutation to generate signatures (however, they did not give an example of such a permutation).

The first actual signature algorithm proposed was RSA; that is in fact based on a trapdoor permutation (and not a zero knowledge proof).

Now, a number of signature algorithms are, indeed, based on a noninteractive zero knowledge proof, however that's not how it got started (nor is it universal among signature algorithms, even skipping the example of RSA).

$\endgroup$
11
  • 3
    $\begingroup$ I wonder about “The first actual signature algorithm proposed was RSA”. Michael O. Rabin proposed “Digitalized Signatures” or is it “Digital Signatures Using Conventional Encryption Algorithms” (not based on integer factorization) in a 3 day workshop held Oct. 1977. Proceedings are “Foundations of Secure Computation”, by Richard A. DeMillo, David P. Dobkin, Anita K. Jones, Richard J. Lipton, Academic Press 1978, ISBN 0-12-210350-5/978-0-12-210350-6. The paper is on pages 155-168. Unfortunately the only version I found floating around stops at p.153. I ordered a paper copy, will arrive in July. $\endgroup$
    – fgrieu
    Jun 6, 2022 at 15:40
  • 3
    $\begingroup$ @fgrieu: that's news to me - I'm wondering if it was some sort of hash-based signature scheme (typically viewed as being invented by Lamport and made more practical by Merkle). Or, it is something else that has since been broken (and hence forgotten) $\endgroup$
    – poncho
    Jun 6, 2022 at 16:25
  • 3
    $\begingroup$ I wonder in the same direction. The mysterious paper I refer to is cited by Michael O. Rabin as "Digitalized signature" in his MIT-LCS-TR-212, and in the T.O.C. of Foundations of Secure Computation (January 1978). But there are many other references as “Digital Signatures Using Conventional Encryption Algorithms” October 1977, including on page 153 of “Foundations of Secure Computation”. Anyway, you are right: RSA would still be first, since that's April 1977. Pretty close call. $\endgroup$
    – fgrieu
    Jun 6, 2022 at 17:17
  • 1
    $\begingroup$ @DavidSchwartz: volunteering to decrypt chosen ciphertexts is scarcely zero knowledge. More fundamentally, just because something can be used to implement a zero knowledge proof does not mean that something else that thing is used for (signatures in this case) is based on zero knowledge. $\endgroup$
    – poncho
    Jun 7, 2022 at 1:49
  • 1
    $\begingroup$ @poncho : received and scanned Michael O. Rabin's Oct. 1977 Digitalized Signatures. I'm still scratching my head about if it's a signature. $\endgroup$
    – fgrieu
    Jun 29, 2022 at 17:17

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.