Blind Signatures and Secret Splitting

Blind Signatures

(taken from Applied Cryptography , by Bruce Schneier, p. 550)

The notion of blind signatures was invented by David Chaum, who also invented their first implementation. It uses the RSA algorithm.

Bob has a public key e, a private key d, and a public modulus, n. Alice wants Bob to sign message m blindly.

1.

Alice chooses a random value, k, between 1 and n. Then she blinds m by computing

$$t = mk^{e} \bmod{n}$$

2.

Bob signs t

$$t^{d} = (mk^{e})^{d} \bmod{n}$$

3.

Alice unblinds t^d by computing

$$s = t^{d}/k \bmod{n}$$

4.

And the result is

$$s=m^{d} \bmod{n}$$

This can easily be shown

$$t^{d}\equiv (mk^{e})^{d} \equiv m^{d}k \pmod{n},$$

so

$$t^{d}/k = m^{d}k/k \equiv m^{d} \pmod{n}.$$

Secret Splitting

Here is one way to split a secret message B into two ``pieces'' so that you need both ``pieces'' to reconstruct any part of the message.

1.

Generate a random number a, and consider the line

y=a x + B.

Keep a secret.

2.

Pick (distinct) random numbers x₁ and x₂. Let

y₁=a x₁ + B,

y₂=a x₂ + B.

3.

Give Alice (x₁, y₁) and give Bob (x₂, y₂).

4.

Discard a.

Alice and Bob can now find B by finding the unique line which goes through the two points (x₁, y₁) and (x₂, y₂). However, Alice cannot do anything without Bob because there are infinitely many lines going through (x₁, y₁). Likewise Bob cannot do anything without Alice.

We could choose a third point on the line and give it to Carol. Then any two people could reconstruct the message, but no single person could. Using a polynomial of degree m-1 we can divide any message into n pieces so that any m of them can reconstruct the message, but no one with less than m pieces can do anything.

About this document ...

Blind Signatures and Secret Splitting

This document was generated using the LaTeX2HTML translator Version 97.1 (release) (July 13th, 1997)

Copyright © 1993, 1994, 1995, 1996, 1997, Nikos Drakos, Computer Based Learning Unit, University of Leeds.

The command line arguments were:
latex2html -link 0 -split +0 blind_split.tex.

The translation was initiated by Joshua Holden on 10/19/2000