Implementing blind signature on ed25519

Blind signature is a cryptographic scheme, which allows for a signature creation on an encrypted message that is also valid on the decrypted message. This powerful scheme enables many anonymous schemes to exist. The process of a blind signature can be visualized as follows:

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

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

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

Before we jump to equations, let’s recall some facts about elliptic-curve cryptography:

• Elliptic Curve Cryptography (ECC) is defined over a finite prime field, meaning that we are using modular arithmetic, so every time we perform addition or multiplication we also need to perform $\pmod{q}$ for both $x$ and $y$ coordinates. Particularly, for Curve25519, the $q = 2^{255} - 19$ (hence the name $\mathrm{Curve}_{\tiny{2}}255 {\tiny -} 19$).

• For scalar-only operations, we also use modular arithmetic but over a different prime number (group order) $L = 2^{252}+27742317777372353535851937790883648493$.

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

• $G$ is a publicly known point on a curve called generator or base point.

• In ECC, a private key is defined as a scalar number, whereas a public key is a point on the curve.

• In ECC, we use allow for two operators, addition ($+$) and multiplication ($\times$).

• Adding two points $P$ and $Q$ results in a new point that lies on the intersection of the curve and a straight line drawn from two points $P$ and $Q$.

• Multipling point $P$ by a scalar $n$ is the same as adding point $P$ to itself $n$ times.

• Public key $P$ (point on a curve) can be derived from private key $s$ (scalar) by multiplying generator point $G$ by $s$, that is, $P=s \times G$.

• Confused? Read Elliptic Curve Cryptography Explained.

Let’s assume a voting process where Alice is a voter and Bob is an authorization unit who signs ballot papers making them valid votes. Since Alice doesn’t want to disclose her vote option to Bob, they proceed with the blind signature protocol.

Let:

• P be Bob’s public key,
• H be a secure hash function (like SHA-512),
• || be a concatenation operator,
• M be a message we want to sign blindly.

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

1. Bob generates random number (nonce) $k$ in range $(1, L-1)$, computes point $$R=k \times G$$ and sends $R$ to Alice.

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

3. Bob calculates a signature $$s = e \times x + k \pmod{L}$$ and sends $s$ to Alice.

4. Alice calculate $$s’ = s + a \pmod{L}$$

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

In the first step, point $R$ is Bob’s public commitment to his secret $k$. In other words, value $R$ guarantees that Bob has not changed the nonce $k$ between steps 1 and 3 without revealing $k$ to Alice.

The number $k$ must be used only once (nonce—number once)—it must not be re-used between signatures.

However, there is no loss of signature blindness even if the value $k$ gets revealed—malicious Bob can not influence Alice’s anonymity.

You can find the experimental implementation in TypeScript here.

Read the discussion on stackoverflow.