Sakai–Kasahara scheme

The Sakai–Kasahara scheme, also known as the Sakai–Kasahara key encryption algorithm (SAKKE), is an identity-based encryption (IBE) system proposed by Ryuichi Sakai and Masao Kasahara in 2003.^[1] Alongside the Boneh–Franklin scheme, this is one of a small number of commercially implemented identity-based encryption schemes. It is an application of pairings over elliptic curves and finite fields. A security proof for the algorithm was produced in 2005 by Chen and Cheng.^[2] SAKKE is described in Internet Engineering Task Force (IETF) RFC 6508.^[3]

As a specific method for identity-based encryption, the primary use case is to allow anyone to encrypt a message to a user when the sender only knows the public identity (e.g. email address) of the user. In this way, this scheme removes the requirement for users to share public certificates for the purpose of encryption.

Description of Scheme

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$ and for $\textstyle g = e(P,P)$ a member of $\textstyle G$:

$\textstyle e(P,[x].P) = e([x].P,P) = e(P,P)^x = g^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<x<q$. $\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<z<q$, 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.

1. Create: $\textstyle id = H_1(ID_U)$
2. The sender generates $\textstyle r$ using $\textstyle r = H_1(\mathbb{M} || id)$
3. Generate the point $\textstyle R$ in $\textstyle E$:

   $\textstyle R = [r].([id].P + Z)$

4. Create the masked message:

   $\textstyle S = \mathbb{M} \oplus H_2(g^r)$

5. 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:

1. Compute $\textstyle id = H_1(ID_U)$
2. Receive the encrypted message: $\textstyle (R,S)$.
3. Compute:

   $\textstyle w = e(R,K_U)$

4. Extract the message:

   $\textstyle \mathbb{M} = S \oplus H_2(w)$

5. 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

There are two standards relating to this protocol:

• Initial standardisation of scheme was begun by IEEE in 2006.^[4]
• The scheme was standardised by the IETF in 2012 within RFC 6508. The scheme is used as part of the MIKEY-SAKKE protocol, defined in RFC 6509.

Cryptographic Libraries and Implementations

The scheme is part of the MIRACL cryptographic library.

See also

• ID-based encryption

References

1. Sakai, Ryuichi; Kasahara, Masao (2003). "ID Based cryptosystems with pairing on elliptic curve" (PDF). Cryptography ePrint Archive. 2003/054.
2. Chen, L.; Cheng, Z. "Security proof of Sakai-Kasahara's identity-based encryption scheme" (PDF). Cryptography ePrint Archive. 2005/226.
3. Groves, L. (February 2012). Sakai-Kasahara Key Encryption (SAKKE). IETF. RFC 6508. https://tools.ietf.org/html/rfc6508. 
4. Barbosa, M. (June 2006). "SK-KEM: An Identity-Based KEM" (PDF). IEEE. P1363.3.