The Sakai–Kasahara scheme allows the encryption of a message \mathbb{M} to an receiver with a specific identity, \textstyle I_U. Only the entity with the private key, \textstyle K_U, associated to the identity, \textstyle I_U, will be capable of decrypting the message. As part of the scheme, both the sender and receiver must trust a Private Key Generator (PKG), also known as a
Key Management Server (KMS). The purpose of the PKG is to create the receiver's private key, \textstyle K_U, associated to the receiver's identity, \textstyle I_U. The PKG must securely deliver the identity-specific private key to the receiver, and PKG-specific public parameter, \textstyle Z, to all parties. These distribution processes are not considered as part of the definition of this cryptographic scheme.
Preliminaries The scheme uses two multiplicative groups \textstyle E and \textstyle G. It is assumed: • The
Diffie-Hellman problem is hard in \textstyle E. Meaning that given two members of the group \textstyle P and \textstyle Q, it is hard to find \textstyle x such that \textstyle [x].P = Q. • The
Diffie-Hellman problem is hard in \textstyle G. Meaning that given two members of the
group g and t, it is hard to find \textstyle x such that \textstyle g^x = t. • There is a
bilinear map, a Tate-Lichtenbaum
pairing, \textstyle e(,) from E to G. This means that for \textstyle P a member of \textstyle E: ::::\textstyle e(P,[x].P) = e([x].P,P) = e(P,P)^x Frequently, \textstyle E is a supersingular
elliptic curve, such as \textstyle E: y^2 = x^3 - 3x (over a finite field of prime order \textstyle p). A generator \textstyle P of prime order \textstyle q is chosen in \textstyle E. The group \textstyle G is the image due to the pairing of the group generated by \textstyle P (in the extension field of degree 2 of the finite field of order p). Two
hash functions are also required, \textstyle H_1 and \textstyle H_2. \textstyle H_1 outputs a positive integer, \textstyle x, such that \textstyle 1. \textstyle H_2 outputs \textstyle n bits, where \textstyle n is the length of the message \mathbb{M}.
Key generation The PKG has a master secret \textstyle z where 1, and a public key \textstyle Z=[z].P which is a point on \textstyle E. The PKG generates the private key, \textstyle K_U, for the user with identity \textstyle ID_U as follows: ::::\textstyle K_U = [\frac{1}{z + H_1(ID_U)}].P
Encryption To encrypt a non-repeating message \mathbb{M}, the sender requires receiver's identity, \textstyle ID_U and the public PGK value \textstyle Z. The sender performs the following operation. • Create: \textstyle id = H_1(ID_U) • The sender generates \textstyle r using \textstyle r = H_1(\mathbb{M} || id) • Generate the point \textstyle R in \textstyle E: • ::::\textstyle R = [r].([id].P + Z) • Create the masked message: • ::::\textstyle S = \mathbb{M} \oplus H_2(g^r) • The encrypted output is: \textstyle (R,S) Note that messages may not repeat, as a repeated message to the same identity results in a repeated ciphertext. There is an extension to the protocol should messages potentially repeat.
Decryption To decrypt a message encrypted to \textstyle ID_U, the receiver requires the private key, \textstyle K_U from the PKG and the public value \textstyle Z. The decryption procedure is as follows: • Compute \textstyle id = H_1(ID_U) • Receive the encrypted message: \textstyle (R,S). • Compute: • ::::\textstyle w = e(R,K_U) • Extract the message: • ::::\textstyle \mathbb{M} = S \oplus H_2(w) • To verify the message, compute \textstyle r = H_1(\mathbb{M}||id), and only accept the message if: • ::::\textstyle [r].([id].P + Z) \equiv R
Demonstration of algorithmic correctness The following equations demonstrate the correctness of the algorithm: :\textstyle w = e(R,K_U) = e([r].([id].P + Z),K_U) = e([r].([id].P + [z].P),K_U) = e([r(id+z)].P,K_U) By the bilinear property of the map: :\textstyle w = e([r(id+z)].P,K_U)= e([r(id+z)].P,[\frac{1}{(id+z)}].P) = e(P,P)^{\frac{r(id+z)}{(id+z)}} = g^r As a result: :\textstyle S \oplus H_2(w) = (\mathbb{M} \oplus H_2(g^r)) \oplus H_2(w) = \mathbb{M} ==Standardisation==