1
Foundation of Attribute-Based Encryption
1.1 Introduction
What is encryption? Encryption is a key concept in cryptography. To explain the meaning of encryption, let us consider the following scenario without being blown away by the whims of mathematics.
Imagine your friend Bob is organizing a back-alley chess game. Bob does not want anyone to come into his shady gambling den without authorization, so he issues you a pass with the phrase "Knock and wait." When you knock on the right sleazy door, the bouncer asks for the pass in a genre-savvy baritone. You can get in if you say the right phrase. Otherwise, your entry will be denied, and you will stay outside in the metaphorical rain.
To stretch the analogy, Bob can alter the pass each time he hosts a chess game. Knowing the passphrase for the day, you can share it with one of your acquaintances or some of your friends in the criminal investigation bureau. In cryptography, the pass is referred to as a secret key. When plaintext is combined with a secret key, cryptography offers a black box that converts plaintext to ciphertext. The ciphertext is unreadable junk to those without the right secret key. On the other hand, those with a valid secret key can recover the plaintext from a given ciphertext back. The process involved in transforming plaintext into ciphertext is referred to as encryption. Succinctly put, encryption is the cryptographic mechanism of converting information into a secret code that conceals the true meaning of the transformed information (ciphertext). When an unauthorized party intercepts ciphertext, the intruder must determine which algorithm and keys were used to encrypt the message. The computation complexity required in decoding a ciphertext without a valid secret key is what makes encryption a crucial security tool.
Encryption has been a longstanding technique to secure sensitive data. Historically, it was used by governments and militaries. Encryption is used in modern times to secure data stored on computers and storage devices and data in transit across networks. Prior to the advent of public key cryptography, it was widely assumed that for two users to transmit data securely, they would need to establish a mutually held secret key. While this may be acceptable for certain small or close-knit groups, it is infeasible for larger networks, such as the Internet of today, which has billions of users. Diffie and Hellman [1] proposed a novel concept in public key cryptography over thirty years ago, where two parties can securely communicate without sharing a prior mutual secret, dramatically upsetting common knowledge held at the time. Public key encryption is a crucial tool today. It is widely used in developing tools ranging from secure web communication (e.g. secure shell [SSH], secure sockets layer [SSL]) to disk encryption and a secure software patch distribution. Before the introduction of functional encryption, there were widely held views that:
- Encryption is a method of sending a message or data to a single entity with a secret key.
- Access to encrypted data is all or nothing - one can either decrypt and read the entire plaintext or learn nothing about the plaintext other than its length.
These views determined the method used for computation of ciphertext and secret key before they were modified by functional encryption. Functional encryption enables a data encryptor to encrypt data with a boolean function, such that only a decryptor with the correct private key can recover the plaintext if the boolean function returns true. Before delving into the details of functional encryption and how it is a superior encryption technique, we will explore the earlier encryption techniques.
1.1.1 Symmetric Encryption
Howbeit, data can be encrypted with symmetric key encryption mechanisms. The symmetric key encryption algorithm uses only one secret key, referred to as a session key, to encipher and decipher information [2]. As seen in Figure 1.1, one secret key is required to cipher and decipher information in symmetric encryption. A key can be a number, a word, or a random sequence of letters. The key is used to scramble the plaintext of a message into unreadable content (ciphertext) and recover the content. Therefore, the session key must be shared in advance between the sender and recipient prior to its usage in the encryption method. Symmetric encryption includes advanced encryption standard (AES), RC4, data encryption standard (DES), RC5, and RC6. Encryption schemes like AES-128, 192, and 256 are the most extensively used symmetric algorithms.
The inherent problem with the symmetric encryption is that a session key must be exchanged between the data owner and data users in advance before a symmetric key encryption algorithm can be used [3]. However, it is impossible to know every potential data user in advance to share data with them in multi-user data sharing systems. Even if the data owner does, it has to encrypt the data repeatedly with each session key shared with the multiple data users in the system. There are as many as key pairs to be managed in an extensive network. Consequently, key management will undoubtedly involve high storage overhead.
1.1.2 Asymmetric Key Encryption
Symmetric encryption has existed for a very long time, whereas asymmetric encryption is very recent. For data encryption and decryption, asymmetric encryption requires two keys, namely public and private keys. The public keys are used for data encryption, whereas the private keys are required for data decryption. Asymmetric encryption enables parties to preserve sensitive information in an encrypted format on a public network, such as the Internet, without exchanging a session key in advance. Asymmetric encryption ensures that only the authorized recipient with the proper private key can decipher the encrypted messages. The use of two related keys in asymmetric encryption increases security, as anyone with the secret key can decipher the message. Anyone can send a message to any user using their public key, which is accessible to the public.
Figure 1.1 Symmetric encryption.
Figure 1.2 Asymmetric encryption.
As illustrated in Figure 1.2, the public key and private key are utilized to encrypt and decrypt a message, respectively. There is no need to protect the public keys because they are accessible to the whole public. However, the private key must be kept secret such that only the end user knows it; otherwise, any entity with knowledge of the private key can decrypt any communication encrypted with the corresponding public key. Using an asymmetric key for communication is substantially more secure than a symmetric key. Well-known asymmetric key encryption methods include EIGamal and Rivest-Shamir-Adleman (RSA).
To prevent man-in-the-middle attacks, asymmetric encryption relies on the public key infrastructure to associate a user's public key with a certificate. This certificate is "signed" by the Certificate Authority (CA), the digital equivalent of a notary. It is evident that the CA plays a significant role in the public key infrastructure (PKI) model since this approach is founded on the premise that the CA is true, trustworthy, and legitimate. Therefore, a hacker who takes control of a CA can use it to generate fake certificates and impersonate any public key.
Over the years, there have been repeated breaches of CA firms, including DigiNotar, GlobalSign, Comodo, and Digicert Malaysia. These attacks were a direct result of the commoditization of certificates, in which smaller, less qualified businesses have gained a larger proportion of the market for certificate authorities.
Asymmetric key encryption schemes also have some drawbacks similar to symmetric key encryption schemes. For example, the data owner must obtain each data user's public key, encrypt the data multiple times, and store multiple copies of the data in the cloud.
1.1.3 Identity-Based Encryption
Imagine a corporate email system in which the employees send encrypted communications. Alice discovers Bob's public key, writes a message, encrypts it in an email, and sends the email to Bob. However, Bob wrote his private key in his notebook, which he left at an airport. Or maybe Bob's private key was stored on his phone, and one of his children dropped it in the drain. Now that Bob has a new phone, he tries to read all of Alice's emails and discovers that he cannot. Without a private key, there are no emails that can be read. However, as is synonymous with key and door systems, when the lone key to a lock is lost, the entire lock must be replaced. Digital cryptosystems are no different; public and private keys are generated as a pair, and it is impossible to generate one from the other, just as it is impossible to construct a key from a lock. Bob must therefore generate a new pair of public and private keys, upload the new public key to the corporate directory, and inform everyone that the previous public key is no longer valid. As shown in Figure 1.3, if Alice does not detect this change, she will continue to send Bob encrypted emails using his previous public key, and Bob will continue to be unable to read them. It turns out that this is a widespread issue in cryptography systems - individuals are lousy at managing keys. In 1984, a cryptographer named Adi Shamir [4] came up with a brilliant concept: what if the firm itself managed the keys? He believed that the entire concept...
