Bob … is this YOUR signature? Yes. I can prove it, here …

Bob … is this YOUR signature? Yes. I can prove it, here …

How many times have you watched a movie, and there’s a court scene and where the person is ask, “Is this your signature?”. It’s a standard thing in trust, and where we must make sure that someone has signed something. In the world of digital trust, we normally use the private key to sign for something, and then the public key to prove it. But let’s say that that’s not enough for Alice, and she wants Bob to give her proof that it is his signature. For this, we look for an undeniable proof of a signature.

With an undeniable signatures, Alice requires an interaction with Bob to prove Bob’s signature. In this case we will implement the Chaum-van Antwepen undeniable signature scheme [here][1]:

For this, Bob interacts with Alice to prove that he was the one who signed a message

Key generation

Bob generates two prime numbers (p and q) and where:

p=2q+1

Next Bob selects a random value β and then selects:

Next Bob selects a random value of a from 0 to q−1 , and computes:

Bob’s public key is (p,α,y) and his private key is a .

Signature generation

Bob now computes a signature value (s) for a message (m) with:

The value of s is now the signature for message (m).

Checking signature

Now Alice must verify the signature, and for Bob to interact for there to be undeniable proof of the signature. First Alice generates two random values:

Alice then computes:

and sends this value to Bob. Bob computes:

and where aa^{−1} =1 (mod q). Bob sends this value to Alice. Alice then computes:

If w is equal to w′, the signature is accepted, and Bob provides undeniable proof that he did sign the message. This works because:

Here is the implementation:

and the code:

Conclusions

David Chuam is one of my great heros in privacy:

References

[1] Chaum, D., & Van Antwerpen, H. (1989, August). Undeniable signatures. In Conference on the Theory and Application of Cryptology (pp. 212–216). Springer, New York, NY.