A Tale of Two Patents: Kravitz v Schnorr
A Tale of Two Patents: Kravitz v Schnorr
I know of the importance of protecting IP, and we have patented our research work for each of our spin-outs. But I find our existing patent infrastructure is archaic. Often, too, a patent can suppress the adoption of amazing methods. This happened with Claus Schnorr, and where the development of his method was suppressed, but where a method defined by David W. Kravitz advanced to become a global standard for digital signatures.
Schnorr
In Feb 1989, Claus Schnorr submitted a patent which was assigned to no one. It has 11 claims and allowed digital signatures to be merged for multiple signers [here]:
This method has the great advantage that we can have multiple signers to a message or a transaction and end up with a single signature for all the signers. It is now being used in Bitcoin transactions so that we have an efficient signature for a transaction that involves multiple entities.
With the Schnorr signature, we create a signature (R,s) for a hash of the message (m). Initially, Peggy (the prover) has a private key x, and her public key will then be:
and where G is the base point on the curve. She then generates random nonce (r_t) for the signing of a message and defines a commitment to this value:
Next, with a message (m), she computes a challenge (e) with a hash function of:
Next, Peggy computes:
Peggy then sends e,s to Victor (the verifier). Victor then determines if:
These should equal each other. This works because:
The Schnorr method — using elliptic curve methods — is implemented here:
https://asecuritysite.com/signatures/goschnorr
DSA
The DSA patent (No 5,231,668) was created by David W. Kravitz (an ex-NSA employee) and assigned to the USA in a royalty-free way:
David spent 11 years at the NSA and is currently a Senior Director of Research at Spring Labs [here]:
DSA was first outlined by NIST in 1991, within the Digital Signature Standard (DSS). This was then standardized within FIPS (Federal Information Processing Standard) 186 in 1994, and by FIPS 186–4 in 2013. Within FIPS 186–5, though, it is defined that DSA should not be used for the generation of signatures but can be used for signature verification. Most methods now use either RSA or ECDSA signing.
The ECDSA method is basically an extension of DSA, but implemented with elliptic curve (EC) methods. Overall, ECSDA is much more efficient in its computation and in its key sizes.
As with most public key signing methods, in DSA, we take a hash of a message — H(M) — and then apply a private key to create a signature (r,s). This is done by creating a random value (k) to produce the signature. The signature is then verified using the associated public key. This then verifies the creator of the signature and that the message has not been changed.
Initially, Bob creates two prime numbers (p and q) and generates a generator value of g. Next, he generates his secret key (x) and then computes his public key:
To create a signature for a message (M), he creates a random value (k) and then computes two values for the signature:
When Alice receives this signature, she takes Bob’s public key (p,q,g,Y) and the message and computes:
She then checks that v is equal to r . If so, the signature checks out. This works because:
DSA method using discrete logarithms is implemented here:
https://asecuritysite.com/powershell/dsa
Claus disputes the patent
There has been a long-running debate about whether DSA is based on the Schnorr patent. It seems that NIST just changed DSA enough to allow it to become a royalty-free patent. Schnorr actually sold his patent rights to Siemens and RSADSI, and who did not take forward patent breaches between DSA and the Schnorr signature method. The Schnorr patent has now timed-out, and is now being implemented within ZKPs (Zero Knowledge Proofs) and in distributed and scalable signatures.
If NIST hadn’t been able to supply DSA in a patent-free form, it is unlikely that ECDSA would have ever been adopted. The patent-free usage of ECDSA probably allowed Satoshi Nakamoto to adopt ECDSA, and the rest is history.