Identity-based Cryptography

Public key infrastructure (PKI) requires key distribution and has been long criticised for its usability issues [13,14,15]. In an experiment [15] conducted for analysing the usability of Mailvelop, a modern PGP tool rated 4.4 out of 5 stars on Chrome web store, 9 out of 10 pairs of participants failed to complete the assigned task of exchanging encrypted emails, i.e. 90% failure rate. Only one pair of participants successfully completed the task and that is only because one participant from this pair had prior knowledge in public key cryptography. The most common mistake that repeatedly occurred in all of these studies [13,14,15] was to encrypt a message with the sender’s public key. It is difficult for a novice user to develop the understanding that he needs other users’ public keys.

In 1984, Shamir proposed the idea of identity-based cryptography (IBC) where a user’s public key can be his meaningful identities like names and email addresses [1]. This identity-based setting gets rid of the public key management and, therefore, simplifies the PKI requirements. Shamir described the first RSA-based identity-based signature (IBS) scheme in [1]. A straightforward but paradoxical way [2,3] of constructing IBS from a standard signature scheme is to include a signer’s public key and all the corresponding certificates in the signatures he generated. Obviously this general approach is at the cost of increasing the size of a signature. For example, a standard SSL certificate is 2~4 KB and the typical depth of the chains of certificates is around 3~4. This means about ~10KB overhead for including certificates into a signature while the signature itself could just be around 200 bytes. Therefore the straightforward construction is only considered as a benchmark for measuring the efficiency of the direct IBS constructions [3]. Indeed, many direct IBS instantiations [5,6] can save on signature size, achieving constant size signature which only has 2~3 group elements.

Constructing an identity-based encryption (IBE) turns out to be much harder than IBS. The first practical IBE scheme was given by Boneh and Franklin [7] in 2001 using bilinear pairing on elliptic curves. The Boneh-Franklin scheme employs a Private Key Generator (PKG) to compute each user’s private key using the PKG’s master secret key and the user’s identity. As illustrated below, Alice’s identity string is represented by her email address. The PKG derives a private key for Alice using the PKG’s master secret key and Alice’s email address. Bob can encrypt a message using Alice’s email address, and Alice can decrypt and obtain the message using her private key. Additional information, such as a timestamp, can also be included in Alice’s identity string in case Alice’s private key needs to be revoked.

So far, most of the IBC instantiations rely on the trusted PKGs to compute and issue user private keys. This is an inherent “key escrow” issue. IBC is mostly suitable to be deployed in an enterprise environment due to its light-weight key management, built-in key recovery and accountability. It is not recommended to use IBC for services or applications that target individual users. The UK government is promoting the MIKEY-SAKKE protocol [16] that implements an identity-based protocol proposed by SAKAI and KASAHARA in 2003. The protocol seems to have been deployed in UK emergency services from 2018 [17,18].

Since 2001, various extensions of normal IBE/IBS have been proposed:

• Identity-based signcrypt schemes. This type of scheme (e.g., [8,9]) combines signature and encryption in a secure way, providing efficient joint authentication and encryption. Bob encrypts a message with Alice’s identity and signs the message using his private key. Alice can then perform the decryption using her private key and verify the signature using Bob’s identity. This approach is much more efficient than the blackbox combination of IBS and IBE.
• Identity-based broadcasting encryption (IBBE). IBBE is a natural generalisation of IBE which enables a user to encrypt messages for any group of users. The trivial approach of encrypting a message once for each user in the group would result in a ciphertext of size linear in the size of the group. The IBBE scheme proposed in [10] achieves constant size ciphertexts and private keys. Only the public parameters is of size linear in the maximal number of receivers.
• Hierarchical identity-based encryption/signature (HIBE/HIBS). Hierarchical identity-based crypto enables PKGs to distribute the workload of private key generations to lower level PKGs, so that user authentication and key delivery can happen locally. The hierarchical scheme presented in [6] achieves constant size ciphertext consisting of just three group elements, as well as constant size signature with only two group elements. We shall further discuss the hierarchical identity-based cryptography below.
• Revocable IBE. A simple way to revoke a user’s private key in IBE is to add a timestamp to the user’s identity and periodically renew his private keys [7]. This introduces extra overhead on the PKGs to generate and deliver new user private keys. Revocable IBE [12] provides a scalable revocation method. Each user has a secret key, a key update and a decryption key. For each time period, the PKG broadcasts a key update and only a non-revoked user is able to compute a decryption key for this time period using the user’s secret key and the key update. The computation of the key update is only logarithmic in the total number of users.
• Lattice based IBE. The first lattice based IBE is given by [19] which proposes a sampling algorithm to generate short lattice vectors using a short trap-door basis. The implementations of this scheme on NTRU lattices are practical [20,21]: the encryption/decryption are extremely fast. The sampling algorithm of [19] is later used to construct lattice based HIBE [22,23].

To read more, on our Horizons blog.

Hierarchical identity-based cryptography

Having a single PKG issue private keys for all the users could be burdensome, especially for large organisations that may spread all over the world. This is because the private key generation is computationally expensive, and the authentication of the users and the delivery of the keys require secure channels between the PKG and the corresponding users. Hierarchical identity-based crypto (HIBC) is a generalisation of IBC that reflects an organisational hierarchy and eases the hierarchical administrative issues in large international companies or government. HIBC enables a root PKG to delegate the key generation and delivery to lower-level PKGs:

Level-i PKGs generate private keys for level-i+1 PKGs and the PKGs of the lowest level creates and distributes private keys for users. A level-i entity is identified by an identity-tuple (ID1,ID2,…,IDi) whose children on level- i+1 is identified by the tuple (ID1,ID2,…,IDi,ID(i+1)). Suppose a user Alice works at Thales e-Security in Cambridge. Thales can serve as a root PKG and generate low-level private keys for Thales e-Security. Thales computes a private key for the Cambridge office and then the Cambridge office can issue a private key for Alice. Alice’s identity, for example, can be of the form “Thales e-Security/Cambridge/Alice”. To encrypt a message for Alice, Bob only needs to obtain the public parameters associated with the root PKG and Alice’s identity. The low-level PKGs do not have any other parameters. Alice and Bob can exchange their identities through a similar way that their email addresses, phone numbers, etc., are exchanged.

A hierarchical identity-based encryption (HIBE) scheme can be converted into a hierarchical identity-based signature (HIBS) scheme as mentioned in [2]: a signer extracts a “private key” associated with the identity-tuple (ID1,ID2,…,IDl,M) as a signature where (ID1,ID2,…,IDl) is the signer’s identity-tuple and M is the message to be signed. The verifier can check the validity of the signature by first encrypting a random message M’ with the “public key” (ID1,ID2,…,IDl,M) and then decrypting it using the signature, i.e., the “private key”.

Summary

In identity based cryptography, a user’s “public key” can be an intelligible public string, e.g., name and email address, rather than the large random-looking string used in traditional PKI. The validation of such intelligible “public key” becomes implicit which effectively gets rid of the unusable public key management. Unlike PKI where a user is able to select his own private key, a user’s private key in IBC is typically derived from the user’s identity string and the PKG’s master secret key. This renders IBC to be a security solution mostly for enterprise applications, especially when firms and governments use services and applications provided by other third parties for staff communication, data storage and computing resources. Companies and governments can host their own PKGs to issue private keys for their departments and employees to secure their work-related communications and intellectual properties.

For more information, please visit our Horizons research website. Horizons explores and prototypes new data security technologies and techniques, particularly in distributed cloud environments. Findings are shared publicly, whenever possible, to further the advancement of the information security community.

References

1. A. Shamir. Identity-based cryptosystems and signature schemes, in Advances in Cryptology — Crypto ’84, Lecture Notes in Computer Science 196 (1984), Springer, 47–53.
2. Craig Gentry and Alice Silverberg. Hierarchical ID-based cryptography. In Advances in Cryptology – ASIACRYPT 2002, pages 548–566. Springer Verlag, 2002
3. Eike Kiltz, Gregory Neven: Identity-Based Signatures. Identity-Based Cryptography 2009: 31-44
4. Dan Boneh, Ben Lynn, and Hovav Shacham. Short signatures from the Weil pairing. In Colin Boyd, editor, Advances in Cryptology – ASIACRYPT 2001, pages 514–532.
5. Jae Cha Choon and Jung Hee Cheon. An Identity-Based Signature from Gap Diffie-Hellman Groups. PKC 2003, pp 18-30.
6. Dan Boneh, Xavier Boyen, and Eu-Jin Goh. Hierarchical Identity Based Encryption with Constant Size Ciphertext. EUROCRYPT 2005
7. D. Boneh and M. Franklin, Identity Based Encryption from the Weil Pairing, Proc. of Crypto ’01, pp. 213-229, 2001.
8. X. Boyen. Multipurpose Identity-Based Signcryption: A Swiss Army Knife for Identity-Based Cryptography. CRYPTO 2003.
9. John Malone-Lee. Identity-Based Signcryption. Cryptology ePrint Archive, Report 2002/098.
10. Cécile Delerablée. Identity-Based Broadcast Encryption with Constant Size Ciphertexts and Private Keys. ASIACRYPT 2007.
11. A. Sahai and B. Waters. Fuzzy Identity-Based Encryption. In EUROCRYPT, 2005.
12. Boldyreva A, Goyal V, Kumar V. Identity-based encryption with efficient revocation. ACM CCS, 2008.
13. A. Whitten, J.D. Tygar. Why Johnny can’t encrypt. USENIX Security Symposium, 1999.
14. Sheng, S., Broderick, L., Koranda, C., and Hyland, J. Why Johnny Still Can’t Encrypt: Evaluating the Usability of Email Encryption Software. USENIX SOUPS (poster) 2006.
15. Ruoti, S., Andersen, J., Zappala, D., and Seamons, K. Why Johnny Still, Still Can’t Encrypt: Evaluating the Usability of a Modern PGP Client. 2015 (study included in CHI2016)
16. https://www.ncsc.gov.uk/whitepaper/using-mikey-sakke–building-secure-multimedia-services
17. https://www.securechorus.org/documents/Emergency-Services-White-Paper.pdf
18. Peter Campbell and Michael Groves. Practical post-quantum hierarchical identity-based encryption. https://www.qub.ac.uk/sites/CSIT/FileStore/Filetoupload,785752,en.pdf
19. Craig Gentry, Chris Peikert, and Vinod Vaikuntanathan. Trapdoors for hard lattices and new cryptographic constructions. STOC ’08
20. Ducas, L., Lyubashevsky, V., Prest, T.: Efficient identity-based encryption over NTRU lattices, ASIACRYPT 2014
21. Sarah McCarthy and Neil Smyth and Elizabeth O’Sullivan. A Practical Implementation of Identity-Based Encryption over NTRU Lattices. IMACC 2017
22. Shweta Agrawal, Dan Boneh, and Xavier Boyen. Efficient lattice (H)IBE in the standard model. In Proc. of Eurocrypt’10, 2010.
23. Shweta Agrawal, Dan Boneh, and Xavier Boyen. Lattice basis delegation in fixed dimension and shorter-ciphertext hierarchical IBE. In CRYPTO, 2010