Bit of cryptographic signatures

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 the signature pattern we see in applications of cryptography.

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. And just a heads-up, subtraction works the same.

```
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, *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.

```
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
^ ^
| |
| |
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. Again, Bob gets the top public equation and just the left-hand side, `s`

, of the bottom private equation.

```
sG = (p + n)G
^ ^
| |
| |
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
^ ^ ^
| | |
| | |
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 that `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 does know `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 it. The issue is that `nG`

can be manipulated by an attacker. They can lie! And it might be hard to see that they did 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
^ ^ ^ ^
| | | |
| | | |
s = c + p + n
```

*Add a challenge scalar c so that nG cannot be derived from a random s.*

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 great 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. Maybe `nG' = nG - pG`

is a bit 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 for `nG'`

. And the point here is that the `pG`

’s can get cancelled out (again): `sG = cG + pG + (nG - pG)`

. The private equation then boils down to `s = c + n`

and bad actor Mallory can pretend to know `p`

(again). Funny story, I didn’t realize this case until sipa told me.

So the challenge scalar needs to be applied in a way so that Mallory can’t cancel out the `pG`

. What if `c`

is applied to the public key itself like in the second attempt above? Scaling a scaled point is just scalar multiplication: `c*(pG) == (c*p)G`

. And if `c`

is applied to `pG`

there is *no way* for Mallory to modify her `nG'`

candidate to cancel out all `pG`

’s in the equation since she won’t know `c`

ahead of time.

```
sG = c*pG + nG'
^ ^ ^
| | |
| | |
s = c*p + n
```

*Move the challenge scalar c to the public key pG so that it cannot be removed from the equation by a bad actor.*

This is pretty great, but can be improved! Right now it involves *interaction* between Alice and Bob. Bob needs to have Alice commit to a `nG'`

candidate before he chooses a random `c`

so that he can trust her. Also, if Carol comes along and wants Alice to prove she owns `p`

, nothing done with Bob can be shared in this proof since Carol has no reason to trust Bob. *Fiat and Shamir* have something to say about this.

Recall that hashing something gives random data. If Alice commits to a `nG'`

and then hashes it, could that hash be the challenge scalar `c`

? This is theoretically just as random as Bob choosing a number out of a hat. Remember, `c`

is there so that attacker Mallory can’t propose a `nG'`

candidate to cancel out the public key `pG`

. If `pG`

goes from `c*pG`

to `hash(nG')*pG`

, Mallory doesn’t get to cancel out `pG`

for free, she would need to reverse a `hash(nG')`

. She has more time than if Bob interactively gives her a random `c`

and tells her he is only going to wait five minutes, but the maths are stacked against her, it would take a very, very, very long time to reverse a hash. And Bob can trust the hash since it is deterministic and easy to verify based on `nG'`

. Mallory is *committing* to that `nG'`

since the hash forces her to use it. So with the challenge hash, `p`

is still protected for Alice and Bob can trust `nG'`

, just like with a random `c`

from Bob. But now the protocol is *non-interactive* and can be re-used by any parties: Alice commits to a `nG'`

and proves she has `p`

by sharing `nG'`

and `s`

.

```
sG = hash(nG')*pG + nG'
^ ^ ^
| | |
| | |
s = hash(nG')*p + n
```

*Base the challenge scalar c on nG' so that the protocol becomes non-interactive.*

Alice can prove she owns `p`

without revealing `p`

! Goal achieved. Finally, the promised second feature of signatures: provide the ability for Alice to put a digital stamp on some arbitrary message. “I Alice, owner of `p`

, declare…`m`

”. This message, `m`

, is public information which Alice just needs to be able to commit to somehow. Our non-interactive public equation already has a commitment from Alice in it. The `hash(nG')`

“commits” Alice to `nG'`

. She either knew `nG'`

ahead of creating `s`

or she guessed the hash (impossible). We can just add more to that hash commitment.

```
sG = hash(nG'||m)*pG + nG'
^ ^ ^
| | |
| | |
s = hash(nG'||m)*p + n
```

*Concatenate an arbitrary message m to the hash commitment.*

Alice commits to `nG'`

in order to prove she has control of `p`

and also commits to `m`

. She either knew `m`

before-hand, or randomly guessed the hash (again, impossible). So the owner of `p`

has committed to `m`

, a signature on that message.