Fast attribute-based encryption with improved security

1 . A method for implementing key-policy attribute-based encryption, the method comprising:

(a) receiving, by one or more hardware processors, a plaintext message to be encrypted, a master public key, and a set of attributes;

(b) generating, by the one or more hardware processors, a random integer s within a range defined by a prime integer p, wherein the prime integer p is established by a pairing-friendly elliptic curve comprising a first source group 1 , a second source group 2 , and a target group T ;

(c) computing, by the one or more hardware processors, a set of attribute encodings by:

(i) hashing each attribute in the set of attributes to an element of the first source group 1 , and

(ii) multiplying each hashed attribute by the random integer s;

(d) deriving, by the one or more hardware processors, a blinding factor by multiplying a target group element from the master public key by the random integer s;

(e) generating, by the one or more hardware processors, a masked message by combining the plaintext message with the blinding factor;

(f) constructing, by the one or more hardware processors, a ciphertext comprising:

(i) the masked message,

(ii) the set of attributes,

(iii) the set of attribute encodings, and

(iv) an encoding of the random integer s in the second source group 2 ; and

(g) outputting, by the one or more hardware processors, the ciphertext for storage in a non-transitory computer-readable medium or for transmission over a communications interface to a receiving device;

wherein the pairing-friendly elliptic curve is asymmetric, such that no efficiently computable homomorphism exists from the second source group 2 to the first source group 1 ; and

wherein the outputted ciphertext is decryptable by the receiving device, the receiving device having a secret key associated with a key-policy, only when the set of attributes satisfies the key-policy associated with the secret key.

2 . The method of claim 1 , further comprising executing a key generation routine, the key generation routine comprising:

(a) receiving a master secret key and the master public key from a setup routine, and a key-policy;

(b) computing shares of the master secret key with respect to the key-policy using a linear secret-sharing scheme, wherein each share is associated with an attribute in the key-policy;

(c) sampling n multiuse random integers between 1 and the prime integer p, where n multiuse is a maximum number of times any attribute appears in the key-policy;

(d) masking each share in the first source group using a secure hash of the attribute and the random integers between 1 and the prime integer p, such that no random integer is used twice for the same attribute by maintaining a counter for each attribute;

(e) computing a secret key as a concatenation of the masked shares and an encoding of the random integers between 1 and the prime integer p in the second source group and the key-policy; and

(f) outputting the secret key.

3 . The method of claim 2 , wherein to select a random oracle hash function (ROH), the processor picks a random 256-bit key, which is input as a prefix to a SHA-256 hash function.

4 . The method of claim 1 , wherein group operations in the second source group 2 require at least twice as much computational time as group operations in the first source group 1 .

5 . The method of claim 1 , further comprising executing a setup routine, the setup routine comprising:

(a) selecting a random number generator from a library of random number generators, if none have been selected by a user;

(b) picking a master secret key msk as a random integer between 1 and the prime integer p;

(c) picking a secure random oracle hash function (ROH);

(d) computing the master public key based on the pairing-friendly curve, the hash function, and an encoding of msk as a target group element; and

(e) establishing a keystore in a device memory, the keystore comprising storage for the master secret key and the master public key.

6 . The method of claim 1 , further comprising:

(a) receiving a ciphertext, wherein the ciphertext comprises a masked message, a set of attributes, a set of attribute encodings, and an encoding of s in the second source group;

(b) receiving a secret key, wherein the secret key comprises masked shares and an encoding of random integers between 1 and the prime integer p in the second source group and a key-policy;

(c) computing a pairing of the set of attribute encodings in the ciphertext with the encoding of random integers in the secret key;

(d) computing a pairing of masked shares in the secret key with the encoding of s in the ciphertext;

(e) combining an output of the pairing computations to compute a blinding factor using a linear secret-sharing scheme;

(f) combining the blinding factor with the ciphertext to recover the message; and

(g) outputting the recovered message.

7 . A system for implementing key-policy attribute-based encryption, the system comprising:

(a) one or more hardware processors; and

(b) a memory storing instructions that, when executed by the one or more hardware processors, cause the system to perform operations comprising:

(i) receiving a plaintext message to be encrypted, a master public key, and a set of attributes;

(ii) generating a random integer s within a range defined by a prime integer p, wherein the prime integer p is established by a pairing-friendly elliptic curve comprising a first source group 1 , a second source group 2 , and a target group T ;

(iii) computing a set of attribute encodings by:

(a) hashing each attribute in the set of attributes to an element of the first source group 1 , and

(b) multiplying each hashed attribute by the random integer s;

(iv) deriving a blinding factor by multiplying a target group element from the master public key by the random integer s;

(v) generating a masked message by combining the plaintext message with the blinding factor;

(vi) constructing a ciphertext comprising:

(a) the masked message,

(b) the set of attributes,

(c) the set of attribute encodings, and

(d) an encoding of the random integer s in the second source group 2 ; and

(vii) outputting the ciphertext for storage in a non-transitory computer-readable medium or for transmission over a communications interface to a receiving device;

wherein the pairing-friendly elliptic curve is asymmetric, such that no efficiently computable homomorphism exists from the second source group 2 to the first source group 1 ; and

wherein the outputted ciphertext is decryptable by the receiving device, the receiving device having a secret key associated with a key-policy, only when the set of attributes satisfies the key-policy associated with the secret key.

8 . The system of claim 7 , wherein the operations further comprise executing a key generation routine, the key generation routine comprising:

(a) receiving a master secret key and the master public key from a setup routine, and a key-policy;

(b) computing shares of the master secret key with respect to the key-policy using a linear secret-sharing scheme, wherein each share is associated with an attribute in the key-policy;

(c) sampling n multiuse random integers between 1 and the prime integer p, where n multiuse is a maximum number of times any attribute appears in the key-policy;

(d) masking each share in the first source group using a secure hash of the attribute and the random integers between 1 and the prime integer p, such that no random integer is used twice for the same attribute by maintaining a counter for each attribute;

(e) computing a secret key as a concatenation of the masked shares and an encoding of the random integers between 1 and the prime integer p in the second source group and the key-policy; and

(f) outputting the secret key.

9 . The system of claim 8 , wherein to select a random oracle hash function (ROH), the processor picks a random 256-bit key, which is input as a prefix to a SHA-256 hash function.

10 . The system of claim 7 , wherein group operations in the second source group 2 require at least twice as much computational time as group operations in the first source group 1 .

11 . The system of claim 7 , wherein the operations further comprise executing a setup routine, the setup routine comprising:

(a) selecting a random number generator from a library of random number generators, if none have been selected by a user;

(b) picking a master secret key msk as a random integer between 1 and the prime integer p;

(c) picking a secure random oracle hash function (ROH);

(d) computing the master public key based on the pairing-friendly curve, the hash function, and an encoding of msk as a target group element; and

(e) establishing a keystore in a device memory, the keystore comprising storage for the master secret key and the master public key.

12 . The system of claim 7 , wherein the operations further comprise:

(a) receiving a ciphertext, wherein the ciphertext comprises a masked message, a set of attributes, a set of attribute encodings, and an encoding of s in the second source group;

(b) receiving a secret key, wherein the secret key comprises masked shares and an encoding of random integers between 1 and the prime integer p in the second source group and a key-policy;

(c) computing a pairing of the set of attribute encodings in the ciphertext with the encoding of random integers in the secret key;

(d) computing a pairing of masked shares in the secret key with the encoding of s in the ciphertext;

(e) combining an output of the pairing computations to compute a blinding factor using a linear secret-sharing scheme;

(f) combining the blinding factor with the ciphertext to recover the message; and

(g) outputting the recovered message.

13 . A non-transitory computer-readable storage medium storing instructions that, when executed by one or more hardware processors, cause the one or more hardware processors to perform operations for implementing key-policy attribute-based encryption, the operations comprising:

(a) receiving a plaintext message to be encrypted, a master public key, and a set of attributes;

(b) generating a random integer s within a range defined by a prime integer p, wherein the prime integer p is established by a pairing-friendly elliptic curve comprising a first source group 1 , a second source group 2 , and a target group T ;

(c) computing a set of attribute encodings by:

(i) hashing each attribute in the set of attributes to an element of the first source group 1 , and

(ii) multiplying each hashed attribute by the random integer s;

(d) deriving a blinding factor by multiplying a target group element from the master public key by the random integer s;

(e) generating a masked message by combining the plaintext message with the blinding factor;

(f) constructing a ciphertext comprising:

(i) the masked message,

(ii) the set of attributes,

(iii) the set of attribute encodings, and

(iv) an encoding of the random integer s in the second source group 2 ; and

(g) outputting the ciphertext for storage in the non-transitory computer-readable storage medium or for transmission over a communications interface to a receiving device;

wherein the pairing-friendly elliptic curve is asymmetric, such that no efficiently computable homomorphism exists from the second source group 2 to the first source group 1 ; and

wherein the outputted ciphertext is decryptable by the receiving device, the receiving device having a secret key associated with a key-policy, only when the set of attributes satisfies the key-policy associated with the secret key.

14 . The non-transitory computer-readable storage medium of claim 13 , wherein the operations further comprise executing a key generation routine, the key generation routine comprising:

(a) receiving a master secret key and the master public key from a setup routine, and a key-policy;

(b) computing shares of the master secret key with respect to the key-policy using a linear secret-sharing scheme, wherein each share is associated with an attribute in the key-policy;

(c) sampling n multiuse random integers between 1 and the prime integer p, where n multiuse is a maximum number of times any attribute appears in the key-policy;

(d) masking each share in the first source group using a secure hash of the attribute and the random integers between 1 and the prime integer p, such that no random integer is used twice for the same attribute by maintaining a counter for each attribute;

(e) computing a secret key as a concatenation of the masked shares and an encoding of the random integers between 1 and the prime integer p in the second source group and the key-policy; and

(f) outputting the secret key.

15 . The non-transitory computer-readable storage medium of claim 14 , wherein to select a random oracle hash function (ROH), the processor picks a random 256-bit key, which is input as a prefix to a SHA-256 hash function.

16 . The non-transitory computer-readable storage medium of claim 13 , wherein group operations in the second source group 2 require at least twice as much computational time as group operations in the first source group 1 .

17 . The non-transitory computer-readable storage medium of claim 13 , wherein the operations further comprise executing a setup routine, the setup routine comprising:

(a) selecting a random number generator from a library of random number generators, if none have been selected by a user;

(b) picking a master secret key msk as a random integer between 1 and the prime integer p;

(c) picking a secure random oracle hash function (ROH);

(d) computing the master public key based on the pairing-friendly curve, the hash function, and an encoding of msk as a target group element; and

(e) establishing a keystore in a device memory, the keystore comprising storage for the master secret key and the master public key.

18 . The non-transitory computer-readable storage medium of claim 13 , wherein the operations further comprise:

(a) receiving a ciphertext, wherein the ciphertext comprises a masked message, a set of attributes, a set of attribute encodings, and an encoding of s in the second source group;

(b) receiving a secret key, wherein the secret key comprises masked shares and an encoding of random integers between 1 and the prime integer p in the second source group and a key-policy;

(c) computing a pairing of the set of attribute encodings in the ciphertext with the encoding of random integers in the secret key;

(d) computing a pairing of masked shares in the secret key with the encoding of s in the ciphertext;

(e) combining an output of the pairing computations to compute a blinding factor using a linear secret-sharing scheme;

(f) combining the blinding factor with the ciphertext to recover the message; and

(g) outputting the recovered message.

19 . The method of claim 1 , wherein the pairing-friendly curve is selected from a group consisting of Barreto-Naehrig curves, Barreto-Lynn-Scott curves, and Kachisa-Schaefer-Scott curves.

20 . The method of claim 1 , wherein the linear secret-sharing scheme is based on Shamir's secret sharing or a monotone span program.