Sakai–Kasahara scheme

The scheme uses two multiplicative groups ${\displaystyle \textstyle E}$ and ${\displaystyle \textstyle G}$. It is assumed:

• The Diffie-Hellman problem is hard in ${\displaystyle \textstyle E}$. Meaning that given two members of the group ${\displaystyle \textstyle P}$ and ${\displaystyle \textstyle Q}$, it is hard to find ${\displaystyle \textstyle x}$ such that ${\displaystyle \textstyle [x].P=Q}$.
• The Diffie-Hellman problem is hard in ${\displaystyle \textstyle G}$. Meaning that given two members of the group ${\displaystyle g}$ and ${\displaystyle t}$, it is hard to find ${\displaystyle \textstyle x}$ such that ${\displaystyle \textstyle g^{x}=t}$.
• There is a bilinear map, a Tate-Lichtenbaum pairing, ${\displaystyle \textstyle e(,)}$ from E to G. This means that for ${\displaystyle \textstyle P}$ a member of ${\displaystyle \textstyle E}$ and for ${\displaystyle \textstyle g=e(P,P)}$ a member of ${\displaystyle \textstyle G}$:

${\displaystyle \textstyle e(P,[x].P)=e([x].P,P)=e(P,P)^{x}=g^{x}}$

Frequently, ${\displaystyle \textstyle E}$ is a supersingular elliptic curve, such as ${\displaystyle \textstyle E:y^{2}=x^{3}-3x}$ (over a finite field of prime order ${\displaystyle \textstyle p}$). A generator ${\displaystyle \textstyle P}$ of prime order ${\displaystyle \textstyle q}$ is chosen in ${\displaystyle \textstyle E}$. The group ${\displaystyle \textstyle G}$ is the image due to the pairing of the group generated by ${\displaystyle \textstyle P}$ (in the extension field of degree 2 of the finite field of order p).

Two hash functions are also required, ${\displaystyle \textstyle H_{1}}$ and ${\displaystyle \textstyle H_{2}}$. ${\displaystyle \textstyle H_{1}}$ outputs a positive integer, ${\displaystyle \textstyle x}$, such that ${\displaystyle \textstyle 1<x<q}$. ${\displaystyle \textstyle H_{2}}$ outputs ${\displaystyle \textstyle n}$ bits, where ${\displaystyle \textstyle n}$ is the length of the message ${\displaystyle \mathbb {M} }$.

The PKG has a master secret ${\displaystyle \textstyle z}$ where ${\displaystyle 1<z<q}$, and a public key ${\displaystyle \textstyle Z=[z].P}$ which is a point on ${\displaystyle \textstyle E}$. The PKG generates the private key, ${\displaystyle \textstyle K_{U}}$, for the user with identity ${\displaystyle \textstyle ID_{U}}$ as follows:

${\displaystyle \textstyle K_{U}=[{\frac {1}{z+H_{1}(ID_{U})}}].P}$

To encrypt a non-repeating message ${\displaystyle \mathbb {M} }$, the sender requires receiver's identity, ${\displaystyle \textstyle ID_{U}}$ and the public PGK value ${\displaystyle \textstyle Z}$. The sender performs the following operation.

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

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

4. Create the masked message:

   ${\displaystyle \textstyle S=\mathbb {M} \oplus H_{2}(g^{r})}$

5. The encrypted output is: ${\displaystyle \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.

To decrypt a message encrypted to ${\displaystyle \textstyle ID_{U}}$, the receiver requires the private key, ${\displaystyle \textstyle K_{U}}$ from the PKG and the public value ${\displaystyle \textstyle Z}$. The decryption procedure is as follows:

1. Compute ${\displaystyle \textstyle id=H_{1}(ID_{U})}$
2. Receive the encrypted message: ${\displaystyle \textstyle (R,S)}$.
3. Compute:

   ${\displaystyle \textstyle w=e(R,K_{U})}$

4. Extract the message:

   ${\displaystyle \textstyle \mathbb {M} =S\oplus H_{2}(w)}$

5. To verify the message, compute ${\displaystyle \textstyle r=H_{1}(\mathbb {M} ||id)}$, and only accept the message if:

   ${\displaystyle \textstyle [r].([id].P+Z)\equiv R}$

The following equations demonstrate the correctness of the algorithm:

${\displaystyle \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:

${\displaystyle \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:

${\displaystyle \textstyle S\oplus H_{2}(w)=(\mathbb {M} \oplus H_{2}(g^{r}))\oplus H_{2}(w)=\mathbb {M} }$