Sakai–Kasahara scheme

(Redirected from SK-KEM)

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

edit

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

Preliminaries

edit

The scheme uses two multiplicative groups   and  . It is assumed:

  • The Diffie-Hellman problem is hard in  . Meaning that given two members of the group   and  , it is hard to find   such that  .
  • The Diffie-Hellman problem is hard in  . Meaning that given two members of the group   and  , it is hard to find   such that  .
  • There is a bilinear map, a Tate-Lichtenbaum pairing,   from E to G. This means that for   a member of  :
 

Frequently,   is a supersingular elliptic curve, such as   (over a finite field of prime order  ). A generator   of prime order   is chosen in  . The group   is the image due to the pairing of the group generated by   (in the extension field of degree 2 of the finite field of order p).

Two hash functions are also required,   and  .   outputs a positive integer,  , such that  .   outputs   bits, where   is the length of the message  .

Key generation

edit

The PKG has a master secret   where  , and a public key   which is a point on  . The PKG generates the private key,  , for the user with identity   as follows:

 

Encryption

edit

To encrypt a non-repeating message  , the sender requires receiver's identity,   and the public PGK value  . The sender performs the following operation.

  1. Create:  
  2. The sender generates   using  
  3. Generate the point   in  :
     
  4. Create the masked message:
     
  5. The encrypted output is:  

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

edit

To decrypt a message encrypted to  , the receiver requires the private key,   from the PKG and the public value  . The decryption procedure is as follows:

  1. Compute  
  2. Receive the encrypted message:  .
  3. Compute:
     
  4. Extract the message:
     
  5. To verify the message, compute  , and only accept the message if:
     

Demonstration of algorithmic correctness

edit

The following equations demonstrate the correctness of the algorithm:

 

By the bilinear property of the map:

 

As a result:

 

Standardisation

edit

There are four 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.
  • 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.[5]

Security

edit

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.[6][7][8] 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,[9] and that the KMS should be protected by an air-gap.[10]

Cryptographic libraries and implementations

edit

The scheme is part of the MIRACL cryptographic library.

See also

edit

References

edit
  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, M. (February 2012). Sakai-Kasahara Key Encryption (SAKKE). IETF. doi:10.17487/RFC6508. RFC 6508.
  4. ^ Barbosa, M.; et al. (January 2006). "SK-KEM: An Identity-Based KEM [IEEE P1363.3 submission]".
  5. ^ "Common Technology Standards". Secure Chorus. 2019. Archived from the original on 2020-02-04. Retrieved 4 February 2020.
  6. ^ Murdoch, Steven J. (March 2016). "Insecure by Design: Protocols for Encrypted Phone Calls". Computer. 49 (3). IEEE: 25–33. doi:10.1109/MC.2016.70. S2CID 10072519.
  7. ^ Murgia, Madhumita (22 January 2016). "GCHQ-developed software for secure phone calls open to 'eavesdropping'". The Telegraph. Archived from the original on 2019-07-09. Retrieved 2020-02-04.
  8. ^ Baraniuk, Chris (23 January 2016). "GCHQ-developed phone security 'open to surveillance'". BBC News. Retrieved 2020-02-04.
  9. ^ Levy, Ian (26 January 2016). "The development of MIKEY-SAKKE". GCHQ. Retrieved 2020-02-04.
  10. ^ "MIKEY-SAKKE frequently asked questions". GCHQ. 7 August 2016. Retrieved 2020-02-04.