Sakai–Kasahara scheme

The Sakai–Kasahara scheme allows the encryption of a message $\backslash mathbb\{M\}$ to an receiver with a specific identity, $\backslash textstyle\; I\_U$. Only the entity with the private key, $\backslash textstyle\; K\_U$, associated to the identity, $\backslash 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, $\backslash textstyle\; K\_U$, associated to the receiver's identity, $\backslash textstyle\; I\_U$. The PKG must securely deliver the identity-specific private key to the receiver, and PKG-specific public parameter, $\backslash textstyle\; Z$, to all parties. These distribution processes are not considered as part of the definition of this cryptographic scheme.

The scheme uses two multiplicative groups $\backslash textstyle\; E$ and $\backslash textstyle\; G$. It is assumed:

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

::::$\backslash textstyle\; e(P,[x].P)\; =\; e([x].P,P)\; =\; e(P,P)^x$

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

Two hash functions are also required, $\backslash textstyle\; H\_1$ and $\backslash textstyle\; H\_2$. $\backslash textstyle\; H\_1$ outputs a positive integer, $\backslash textstyle\; x$, such that

The PKG has a master secret $\backslash textstyle\; z$ where

::::$\backslash textstyle\; K\_U\; =\; [\backslash frac\{1\}\{z\; +\; H\_1(ID\_U)\}].P$

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

1. Create: $\backslash textstyle\; id\; =\; H\_1(ID\_U)$
2. The sender generates $\backslash textstyle\; r$ using $\backslash textstyle\; r\; =\; H\_1(\backslash mathbb\{M\}\; ||\; id)$
3. Generate the point $\backslash textstyle\; R$ in $\backslash textstyle\; E$:
4. ::::$\backslash textstyle\; R\; =\; [r].([id].P\; +\; Z)$
5. Create the masked message:
6. ::::$\backslash textstyle\; S\; =\; \backslash mathbb\{M\}\; \backslash oplus\; H\_2(g^r)$
7. The encrypted output is: $\backslash 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 $\backslash textstyle\; ID\_U$, the receiver requires the private key, $\backslash textstyle\; K\_U$ from the PKG and the public value $\backslash textstyle\; Z$. The decryption procedure is as follows:

1. Compute $\backslash textstyle\; id\; =\; H\_1(ID\_U)$
2. Receive the encrypted message: $\backslash textstyle\; (R,S)$.
3. Compute:
4. ::::$\backslash textstyle\; w\; =\; e(R,K\_U)$
5. Extract the message:
6. ::::$\backslash textstyle\; \backslash mathbb\{M\}\; =\; S\; \backslash oplus\; H\_2(w)$
7. To verify the message, compute $\backslash textstyle\; r\; =\; H\_1(\backslash mathbb\{M\}||id)$, and only accept the message if:
8. ::::$\backslash textstyle\; [r].([id].P\; +\; Z)\; \backslash equiv\; R$

The following equations demonstrate the correctness of the algorithm:

:$\backslash 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:

:$\backslash textstyle\; w\; =\; e([r(id+z)].P,K\_U)=\; e([r(id+z)].P,[\backslash frac\{1\}\{(id+z)\}].P)\; =\; e(P,P)^\{\backslash frac\{r(id+z)\}\{(id+z)\}\}\; =\; g^r$

As a result:

:$\backslash textstyle\; S\; \backslash oplus\; H\_2(w)\; =\; (\backslash mathbb\{M\}\; \backslash oplus\; H\_2(g^r))\; \backslash oplus\; H\_2(w)\; =\; \backslash mathbb\{M\}$

There are four standards relating to this protocol:

• Initial standardisation of scheme was begun by IEEE in 2006.{{cite web|last=Barbosa|first=M.|display-authors=etal|title=SK-KEM: An Identity-Based KEM [IEEE P1363.3 submission]|date=January 2006| url=https://www.researchgate.net/publication/253371235}}
• The scheme was standardised by the IETF in 2012 within RFC 6508.
• A key-exchange algorithm based on the scheme is the MIKEY-SAKKE protocol developed by the UK's national intelligence and security agency, GCHQ, and defined in RFC 6509.
• Sakai-Kasahara, as specified in MIKEY-SAKKE, is the core key-exchange algorithm of the Secure Chorus encrypted Voice over IP standard.{{cite web |url=https://www.securechorus.org/common-technology-standards/ |title=Common Technology Standards |author= |date=2019 |publisher=Secure Chorus |access-date=4 February 2020 |archive-url=https://web.archive.org/web/20200204180436/https://www.securechorus.org/common-technology-standards/ |archive-date=2020-02-04}}

In common with other identity-based encryption schemes, Sakai-Kasahara requires that the Key Management Server (KMS) stores a master secret from which all users' private keys can be generated. Steven Murdoch has criticised MIKEY-SAKKE for creating a security vulnerability through allowing the KMS to decrypt every users' communication.{{cite journal |last1=Murdoch |first1=Steven J. |author-link1=Steven Murdoch |date=March 2016 |title=Insecure by Design: Protocols for Encrypted Phone Calls |journal=Computer |publisher=IEEE |volume=49 |issue=3 |pages=25–33 |doi=10.1109/MC.2016.70 |s2cid=10072519 |url=https://discovery.ucl.ac.uk/id/eprint/1476827/ }}{{cite news |last=Murgia |first=Madhumita |date=22 January 2016 |title=GCHQ-developed software for secure phone calls open to 'eavesdropping' |url=https://www.telegraph.co.uk/technology/2016/01/26/gchq-developed-software-for-secure-phone-calls-open-to-eavesdrop/ |url-status=live |work=The Telegraph |archive-url=https://web.archive.org/web/20190709035853/https://www.telegraph.co.uk/technology/2016/01/26/gchq-developed-software-for-secure-phone-calls-open-to-eavesdrop/ |archive-date=2019-07-09 |access-date=2020-02-04}}{{cite news |last=Baraniuk |first=Chris |date=23 January 2016 |title=GCHQ-developed phone security 'open to surveillance' |url=https://www.bbc.com/news/technology-35372545 |work=BBC News |access-date=2020-02-04 }} Murdoch also noted that the lack of forward secrecy in MIKEY-SAKKE increases the harm that could result from the master secret being compromised. GCHQ, the creator of MIKEY-SAKKE, disputed this analysis, pointing out that the some organisations may consider such monitoring capabilities to be desirable for investigative or regulatory reasons,{{cite web |url=https://www.ncsc.gov.uk/information/the-development-of-mikey-sakke |title=The development of MIKEY-SAKKE |last=Levy |first=Ian |date=26 January 2016 |publisher=GCHQ |access-date=2020-02-04}} and that the KMS should be protected by an air-gap.{{cite web |url=https://www.ncsc.gov.uk/guidance/mikey-sakke-frequently-asked-questions |title=MIKEY-SAKKE frequently asked questions |author= |date=7 August 2016 |publisher=GCHQ |access-date=2020-02-04}}

The scheme is part of the MIRACL cryptographic library.

• ID-based encryption
• wolfSSL : A SSL/TLS library that has integration with MIKEY SAKKE

{{Reflist}}

{{DEFAULTSORT:Sakai Kasahara Scheme}}

Category:Public-key encryption schemes

Category:Pairing-based cryptography

Category:Identity-based cryptography

Category:Elliptic curve cryptography