Signatures

$$ \gdef\delim#1#2#3{\mathopen{}\mathclose{\left#1 #2 \right#3}} \gdef\p#1{\delim({#1})} \gdef\G{\mathrm{G}} \gdef\H{\mathtt{H}} \gdef\HP{\mathtt{H}_{\mathrm{P}}} $$

Take $\G$ a generator of a group in which discrete logarithm is hard. Capital letters denote group elements, lower case are field elements in the groups multiplicative order, and bold are vectors of either. Take $\H, \HP$ hash functions mapping their inputs to a field element and a group element respectively.

The verification steps can all be checked using basic algebra. This is a useful exercise for the reader.

Warning. These formulas are just to clarify the basic schemes and omit many security critical checks.


Schnorr Signatures

Bob wants to authenticate a message $m$ to Alice. Bob generates a random number 'private key' $b$ and computes 'public key' $B = b ⋅\G$. Bob securely shares $B$ with Alice. Bob computes

$$ \begin{aligned} R &= \H(b, m) ⋅ \G & e &= \H(R, m) & s &= \H(b, m) - e ⋅ b \end{aligned} $$

Bob sends the message $m$ and signature $(e, s)$ to Alice. Alice verifies by recovering $R$ and checking $\H(R, m) = e$ using

$$ \begin{aligned} R &= s ⋅ \G + e ⋅ B & \end{aligned} $$

Note: sometimes $\H(R, B, m)$ is used instead of $\H(R, m)$.

As a variant, the signature is $(R, s)$ which is verified by recovering $B$ using

$$ B = \frac{R - s ⋅ G}{\H(R, m)} $$

ElGamal / DSA Signatures

Bob wants to authenticate a message $m$ to Alice. Bob generates a random number 'private key' $b$ and computes 'public key' $B = b ⋅\G$. Bob securely shares $B$ with Alice. Bob computes

$$ \begin{aligned} R &= \H(b, m) ⋅ \G & s &= \frac{\H(m) + \H(R) ⋅ b}{\H(b, m)} \end{aligned} $$

Bob sends the message $m$ and signature $(R, s)$ to Alice. Alice verifies by checking

$$ \H(m) ⋅ \G + \H(R) ⋅ B - s ⋅ R = 0 $$

Alternatively, Alice verifies by recovering $B$ using

$$ B = \frac{s ⋅ R - \H(m) ⋅ \G}{\H(R)} $$

It is common to take $\H(R)$ to be the $x$-coordinate of $R$. This is not a good hash since $\H(-R) = \H(R)$. In this case $(-R, -s)$ would also a valid signature.

If instead of $\H(b,m)$ an arbitrary non-trivial value $k$ is used this also results in a valid signature. However, if the same $k$ is used to sign multiple messages $m_1$, $m_2$ with signatures $(R_1, s_1), (R_2, s_2)$ then $R_1 = R_2$ and we can recover $k$ and $b$ by

$$ \begin{aligned} k &= \frac{\H(m_1) - \H(m_2)}{s_1 - s_2} & b &= \frac{k ⋅ s_1 - \H(m_1)}{\H(R)} \end{aligned} $$

As a variant, the signature can be $(\H(R), s)$ which is then verified using

$$ \H\p{\frac{\H(m)}{s} ⋅ \G + \frac{\H(R)}{s} ⋅ B} = \H(R) $$

Again, if $\H(R)$ is simply the $x$-coordinate, $\H(-R) = \H(R)$ and $(\H(R), -s)$ is also a valid signature.


Blind Signatures

Alice and Bob want Bob to sign $m$ without revealing $m$ to Bob. For example, Bob is notary that verifies Alice's passport to authenticates Alice's messages. Alice does not want Bob to know their content. Bob has a key pair $b, B$. Bob generates a random number $k$, computes $R' = k ⋅ \G$ and sends $R'$ to Alice. Alice generates random numbers $u, v$ and computes

$$ \begin{aligned} R &= u ⋅ R' + v ⋅\G & m' &= \frac{\H(R, m)}{u} \end{aligned} $$

Alice sends $m'$ to Bob. Bob computes $s' = k - m' ⋅ b$ and sends $s'$ to Alice. Alice computes $s = u ⋅ s' + v$ The signature is $(R, s)$. Verification is as in Schnorr by recovering Bob's key:

$$ B = \frac{R - s ⋅ \G}{\H(R, m)} $$

Ring Signatures

There are many Bob's all with key pairs $b_i, B_i$. Alice has public keys $\vec B = B_1, \dots B_n$. Bob number $s$ wants to send a message to Alice without revealing $s$. Bob generates random numbers $k$ and $\vec r$ except $r_s$. Bob computes the recursion (with indices wrapping around) and completes $\vec r$

$$ \begin{aligned} c_s &= \H(\vec B, m, k ⋅ \G) & c_i &= \H(\vec B, m, r_i ⋅ \G + c_{i - 1} ⋅ B_i) & r_s &= k - c_{s - 1} ⋅ b_s \end{aligned} $$

Bob sends $m$ and the signature $(c_1, \vec r)$ to Alice. Alice verifies by reconstruct $\vec c$ using $c_1$ and the above recursion step. If this circles around and produces $c_1$ again then the signature is correct.

Linkable Ring Signatures

Same as ring signatures, but Alice can also determine if two messages came from the same Bob. Bob number $s$ now computes

$$ \begin{aligned} K &= b_s ⋅ \HP(B_s) \\ c_s &= \H(\vec B, m, k ⋅ \G, k ⋅ \HP(B_s)) \\ c_i &= \H(\vec B, m, r_i ⋅ \G + c_{i - 1} ⋅ B_i, r_i ⋅ \HP(B_i) + c_{i - 1} ⋅ K) \\ r_s &= k - c_{s - 1} ⋅ b_s \end{aligned} $$

Bob sends $m$ and the signature $(K, c_1, \vec r)$ to Alice. Alice verifies by reconstruct $\vec c$ using $c_1$ and the above recursion step. If this circles around and produces $c_1$ again then the signature is correct. Two signatures are by the same Bob iff the $K$ values are the same.


Stealth Addresses

Alice wants to mention Bob without identifying him. Bob creates two keypairs $(a, A)$ and $(b, B)$ and sends $(A, B)$ ('stealth address') to Alice. To mention Bob, Alice picks a random number $r$ and computes

$$ \begin{aligned} R &= r ⋅ \G & P &= \H(r ⋅ A) ⋅ \G + B \end{aligned} $$

Alice mentions $(P, R)$. Bob looks through all mentions and for each checks

$$ P = \H(a ⋅ R) ⋅ \G + B $$

If this holds, then it was Bob who was mentioned and he can compute $p$ such that $P = p ⋅ \G$.

$$ p = \H(a ⋅ R) + b $$

Bob proceeds with a signature algorithm using $(p, P)$ as the keypair to sign messages as the person mentioned without revealing his identity.

Note that $(a, B)$ ('scanning key') is sufficient to recognize mentions of Bob, but $(a, b)$ ('signing key') is required to sign.

Hierarchical Deterministic Wallets

Bob has private key $b$ and public key $B = b ⋅ \G$. Bob wants to derive more key pairs. Both in a way that Alice can follow using the public key and not.

Bob creates a random 'chain code' $c$ and shares it with Alice. Bob's 'extended private key' is $(b, c)$ and Alice has the 'extended public key' $(B, c)$.

To create the $i$-th new key pair such that Alice can follow, compute

$$ \begin{aligned} b' &= b + \H(c, B, i, 0) & c' &= \H(c, B, i, 1) \end{aligned} $$

The new extended private key is $(b', c')$ and Alice can derive the $i$-th new extended public key

$$ \begin{aligned} B' &= B + \H(c, B, i, 0) ⋅ \G & c' &= \H(c, B, i, 1) \end{aligned} $$

To derive the $i$-th key pair that Alice can not follow, compute

$$ \begin{aligned} b' &= b + \H(c, b, i, 0) & c' &= \H(c, b, i, 1) \end{aligned} $$

References

Remco Bloemen
Math & Engineering
https://2π.com