2. Review of Shamir's identity-based signature scheme
2.1. PKG keys
The PKG chooses its public and private key pairs as follows:
1. Runs the probabilistic polynomial algorithm to generate two random large primes, p and q.
2. Chooses a random public key e such that gcd(e,(n)) = 1 and computes the private key d = e?1 mod(n).
2.2. Signer secret key generation
In this algorithm, the signer gets a copy of his secret key from the PKG through a two-step process:
1. A signer submits his identity i to the PKG.
2. The PKG, with its private key d and the corresponding public key e, signs i by generating a secret key g, such that g = id mod n, where g is the secret key of the signer.
2.3. Message signing
To sign a message m, the signer with the secret key g and the corresponding public key e of the PKG signs a message m by generating a signature pair σ = (t, s) as follows:
1. Selects a random number r and computes
2. For the same random number r, computes
σ = (t, s) is the complete signature of the message m.
2.4. Message verification
The identity-based signature σ = (t, s) of a signer with identity i is valid if and only if the following equality holds
|