Identity Based Signature

Adi Shamir (Identity-based cryptosystems and signature schemes. In Proceedings of CRYPTO 84 on Advances in cryptology, pages 47–53.) described how one can use his/her identity to sign a message.


Setup

Let:

m - Message
i - Identity
n - Composite of two large primes
f - One way function

g^e = i (mod n)

Note: Think of this as RSA decryption of an encryption of i which is g.

Where e is a large prime that is relatively prime to Φ(n)

g - private
e - public

Signature

t = r^e (mod n) , r - random

s = g∙r^f(t,m) (mod n)

<s,t> is the signature value sent to the receiver of message m.

Verification

Test:

s^e == i∙t^f(t,m) (mod n)

This works because

s^e == g^e∙r^e∙f(t,m) (mod n)

Since t = r^e and g^e = i :

=> s^e == i∙t^f(t,m) (mod n)