Implementing blind signature on ed25519

Blind-signatures are cryptographic schemes allowing to perform signature on encrypted message that is also valid on decrypted message. This powerful scheme enables many anonimization systems to exists. The process of blind-signature can be visualized as follows:

1. Alice prepares a letter
2. Place it into an envelope along with carbon paper.
3. Bob signs the envelope.
4. Alice takes a signed letter from the envelope.

In result, Bob learns nothing about content of the letter, while Alice ends up with letter signed by Bob.

Although this schema is widely known for RSA signatures, it is hard to find for other signature algorithms like EdDSA, in this post we will look how to implement blind signature on ed25519 schema.

Elliptic Curve Cryptography (ECC) is defined over finite prime field, so we are using modular arithmetic, meaning that every time we perform addition or multilipaction we also need to perform $\pmod{p}$ for both x and y coordinate. For Curve25519, $p = 2^{255} - 19$.

We use uppercase letters for points on curve, and lowercase for scalars.

G is publiictly known point on the curve called “generator” or “base point”.

In ECC, private key is defined as scalar number, whereas public key is point on the curve. We can derive public key $P$ from private key $s$ by multiplying generator point $G$ by $s$, i.e., $P=G * s$.

Multipling point $G$ by scalar $n$ is the same as adding point $G$ to itself $n$ times.

For example, assume Alice to be a voter, and Bob to be authorization person who sign ballot-papers validating them. Since Alice don’t want to dislose her vote option to Bob, they proceed with blind signature.

Let:

• P be a Bob public key,
• H be a hash function SHA-512,
• || be a concatendation operator,
• M be the message we want to sign blindly.

The process of signing blindly is interactive and consist of four steps, starting from Bob:

1. Bob generate random number (nonce) $k$ in range $(1, q-1)$, compute $$r=k * G (mod\ p)$$ and sends $r$ to Alice.

2. Alice picks two random numbers $a$ and $b$ in the range $(1, q-1)$, use them to compute challenge number $e$, \begin{aligned} R’ &= r * (G^a) * (P^b) \pmod{p} \\ e’ &= H(R’|| P || M) \\ e &= e\prime + b \pmod{q} \end{aligned} and sends $e$ to Bob

3. Bob perform sign $$s = e \ast x + k \pmod{q}$$ and sends $s$ to Alice

4. Alice computes $$s’ = s + a \pmod{q}$$

The pair $$(R’, s’)$$ is a valid signature on transaction $M$.