// Schnorr Signature Scheme #Computer-Science #Bitcoin
A Simple Scheme
With the lower level abstract algebra under the belt from a little bit of elliptic curve cryptography it is now possible to sink a bit further into an implementation of the signature pattern we see in applications of cryptography. The particular scheme we are looking at is the Schnorr Signature Scheme.
The first goal of a signature (will get into the second later) is for Alice to prove to Bob that she is the holder of a private key without given up the private key. One way Alice could prove she owns her super secret 256-bit private key is by just showing it to Bob, but now Bob can go and pretend to be Alice. Defeats the whole point of this thing being secret.
Before diving in, here is a quick recap of the abstract algebra layer we have to work with: the elliptic curve points which make up a group. Since it is just a group, not a field, there is a single binary operator across the set of points. We refer to it as “addition” where a point can be added to a point to produce a third point. More common in cryptography, a point can be added to itself a bunch of times. We call this “scalar multiplication” since we are scaling up a point by some number. For example, P + P + P + P is just 4P, scaling the point P four times. This is the most common operation in cryptography since it is how we introduce the discrete log problem, by just scaling a common “generator” point. And this addition binary operator is the only tool we have to work with to try and reach our goal of proof without sharing. But it has a few characteristics which should get the spidy senses tingling that there is a way to pull this off.
A public key is a point on the elliptic curve. Since public keys are always based off of the generator point G, adding two public keys is just adding the scalars of the generator point. So if one public key is kG and the other is pG, adding them together is just adding G to itself k + p times.
sG = kG + pG
sG = (k + p)G
G is the public generator point and s, k, and p are private scalars.
There are some interesting relations between the scaled-up (or lifted), public, version of the calculation and the scalar-based, private, version. If given a scalar s, it is easy to find the public key sG, but if given sG we can’t find s due to the discrete log problem. But we can do addition operations on either level to get s or sG…so seems like there should be a way to do some private addition which can be verified with public addition. The fancy-pants term for this is homomorphism, which means “same structure”. We are doing operations on either level and the “structure” remains the same in both.
s = k + p
The scalar-based, private, calculation of the above public key addition where it is scaled-up by G.
Ok, let’s lay out the scenario. Alice has a private key p which corresponds to the public key pG. She has given Bob the public key pG, but Bob doesn’t trust that Alice hasn’t just copy/pasta’d this from the interwebs somewhere, he wants proof that Alice has the private key.
In the box below, we have the public equation on top and the private equation below. Bear with me for this super simple example of s = p, this is just establishing the mental model of these two equations. So Bob knows pG, the public key, and can also be told s to verify that s is the key for sG. This is proof that Alice knows p, since p is required to know s, but it also obviously doesn’t achieve our goal since s == p and Alice just gave away her private key to Bob. But is there a tweak we can add to this model to hide that?
sG = pG
^ ^
| |
EC POINTS | |
-----------+----+---
SCALARS | |
| |
s = p
What if Bob is told s with pG? Still pretty useless since Alice just gave away p.
Well, the only other tool we have is adding G’s so let’s throw it in there and see what happens. n is a private scalar that only Alice knows, often called a nonce (number once). Again, Bob gets the top public equation and just the left-hand side, s, of the bottom private equation.
sG = (p + n)G
^ ^
| |
EC POINTS | |
-----------+----+---------
SCALARS | |
| |
s = p + n
Add G to itself n more times.
This appears better since Alice doesn’t immediately tell Bob the secret key p. However, does she tell Bob anything? If she gives him just s and sG and says, “Hey, by the way this proves I have p” he will just ask “How?”. If she then tells him “It is because I added the random number n to my key!”, Bob can then go verify that sG = (p+n)G, but the first step would be to calculate p = s - n, giving away p again. Back to the drawing board.
sG = pG + nG
^ ^ ^
| | |
EC POINTS | | |
-----------+----+----+---
SCALARS | | |
| | |
s = p + n
Add G n more times to itself, but also give Bob nG along with s.
Ok, this is looking interesting. So Bob already knows pG, the public key Alice is trying to prove she owns. Alice can calculate s because she knows p and n. She can safely give s to Bob because he can’t calculate n from nG due to the discrete log problem. Bob can verify sG = pG + nG and that s is the private key for sG. All the while p remains hidden!
But…does this prove ownership of p?
Let’s say Mallory, not the owner of p, is trying to trick Bob into thinking she knows p. She could choose any random number for s, derive sG from it, and then calculate nG = sG - pG since pG is public information. So n is doing a good job of protecting p from being shared for Alice, but Bob has no reason to trust the output. The issue is that nG can be manipulated by an attacker. They can lie! And it would be impossible to detect the lie since the discrete log problem is masking the source.
So what if after Alice proposes a nG, Bob gets to add some spice to the equations so that nG can’t be calculated from a randomly chosen s, since it’s already “locked in” (Bob knows it already). Bob can add a challenge scalar to the equation.
sG = cG + pG + nG
^ ^ ^ ^
| | | |
EC POINTS | | | |
-----------+----+----+----+---
SCALARS | | | |
| | | |
s = c + p + n
Add a challenge scalar c to try and throw a wrench in Mallory’s plans to manipulate nG.
The challenge scalar c is part of the private equation since it is a scalar. Having Bob add something to the public equation wouldn’t be too useful since no one would know the key. Since Bob only gave Mallory c after he gets nG, Mallory can no longer easily calculate nG = sG - pG - cG because she would have to have known c beforehand! Right? Hm…
If we take another look at how Mallory tricked Bob last time, nG = sG - pG, we can plug this into the public equation which might help reveal her more general strategy: sG = pG + (sG - pG). It is obvious arithmetic, but the pG’s are cancelling each other out which means that their p counterparts don’t play a role in the private equation. This is fantastic for Mallory since she doesn’t know p.
Back to our new challenge scalar, Mallory can take a similar strategy and make nG = nG - pG. Wait, what. That doesn’t check out at all. So naming the public variable nG was a bad call because it makes an assumption that Alice/Mallory is going to play nice and provide a scaled up n as nG. Maybe R is better notation, since it is nG in the happy path, but a bad actor doesn’t need to follow that and can propose any number. And the point here is that if Malloy proposes R = nG - pG the pG’s get cancelled out: sG = cG + pG + (nG - pG). The private equation then boils down to s = c + n and bad actor Mallory can pretend to know p in a way that is impossible for Bob to detect! Funny story, I didn’t comprehend this scenario until sipa walked me through it.
sG = cG + nG
^ ^ ^
| | |
EC POINTS | | |
-----------+----+----+---
SCALARS | | |
| | |
s = c + n
Mallory’s ideal scenario where Bob is none the wiser since impossible for him to know the pG’s are gone.
So the challenge scalar needs to be applied in a fashion which doesn’t let Mallory cancel out the pG. What if c is applied to the public key itself like in the naive second attempt above? Scaling a scaled point is just more scalar multiplication: c*(pG) == (c*p)G. And if c is applied to pG there is no way for Mallory to modify her R candidate to cancel out all pG’s in the equation since she won’t know c ahead of time. Okay, so there is technically one way, she could take a wild guess at c, say 42, and propose R = nG - 42*pG. And then hope it hits…extremely low odds if c is a 256-bit scalar.
sG = c*pG + R
^ ^ ^
| | |
EC POINTS | | |
-----------+----+------+---
SCALARS | | |
| | |
s = c*p + n
Move the challenge scalar c to scale the public key pG so that p cannot be manipulated out of the equation by Mallory.
This is pretty great, but can be improved! Right now it involves interaction between Alice and Bob. Bob needs to have Alice commit to an R candidate before he chooses a random c so that he can trust R. Plus imagine if Carol comes along and also wants Alice to prove to her that she owns p. None of the work done with Bob can be shared since Carol has no reason to trust Bob! A new interaction dance is required.
Luckily, Fiat and Shamir had an idea for this, something like a mathematical knot.
Recall that hashing something gives random data. If Alice commits to an R and then hashes it, could that hash be the challenge scalar c? This is theoretically just as random a value as Bob choosing a number out of a hat. To recap, the challenge scalar c is there so that attacker Mallory can’t propose an R candidate to cancel out the pGs. So if pG goes from c*pG to hash(R)*pG, Mallory would need to propose an R = nG - hash(R)*pG in order to trick Bob. For a Bob-generated c scalar, Mallory only has one shot to guess it. She has all the time in the world to think of hash generated c!…But is that enough time? Given that a hash is a one-way function, Mallory isn’t able to choose a hash(R) and calculate an R based on it. That is equivalent to not knowing R and guessing its hash, it would take forever. So Mallory gets in a bit of a catch 22 with the hash function and the discrete log problem when she tries to manipulate R. The hash is a commitment to R, it implies order of knowledge, you can’t know the hash without first knowing R. Hm, very similar to Mallory having to choose an R before Bob would tell her c. If Mallory attempts to manipulate things by choosing an R, getting its hash(R), she could calculate the necessary nG for her attack. But now she needs to find n in order to calculate her s. Ouch, the discrete log problem! Mallory is left in a pretty tough spot where she can either (1) guess a hash to manipulate R, (2) break the discrete log problem to manipulate R, or (3) just guess p straight up. Each of these options require many, many lifetimes of guesses to pull off, so it is not looking good for Malory. Great for Bob though!
So with a hash, the protocol is now non-interactive and can be re-used by any parties. Alice commits to an R and proves she knows p by sharing R and s. Bob or Carol (or anyone) can use R and s to verify Alice knows p. Alice can prove she knows p without revealing p! Goal achieved.
sG = hash(R)*pG + R
^ ^ ^
| | |
EC POINTS | | |
-----------+----+------------+---
SCALARS | | |
| | |
s = hash(R)*p + n
Base the challenge scalar c on R so that the protocol becomes non-interactive.
So finally, the promised second feature of signatures: provide the ability for Alice to put a digital signature on some arbitrary message. “I Alice, knower of p, declare…m”. This message, m, is public information which Alice just needs to be able to opt-in, or commit, to proof that she knows m. Our non-interactive protocol already has a commitment from Alice for R in the hash(R)! And we can just add more to that hash commitment. Alice either knows m before creating the hash, or she randomly guessed the hash (a.k.a. lifetimes of guesses) to then create the correct s. So the knower of p opts-in to also showing their knowledge of m, a digital signature.
sG = hash(R||m)*pG + R
^ ^ ^
| | |
EC POINTS | | |
-----------+----+---------------+---
SCALARS | | |
| | |
s = hash(R||m)*p + n
Concatenate an arbitrary message m to the hash commitment.
To wrap it up, the (R, s) bits of information are often passed around as the digital signature on an implicit message and public key. Beautiful!
