ATTRIBUTE BASED ENCRYPTION USING LATTICES

• US 20160156465A1
• Filed: 02/02/2016
• Published: 06/02/2016
• Est. Priority Date: 12/17/2010
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Inventors: Vaikuntanathan, Vinod, Voulgaris, Panagiotis
• Granted Patent: US 9,503,264 B2
• Time in Patent Office: Days
• US Class Current: 1/1
• CPC Class Codes: G06F 21/72 in cryptographic circuits
• CPC Class Codes: H04L 9/0825 using asymmetric-key encryption or public key infrastructure [PKI], e.g. key signature or public key certificates
• CPC Class Codes: H04L 9/0861 Generation of secret information including derivation or calculation of cryptographic keys or passwords
• CPC Class Codes: H04L 9/088 Usage controlling of secret information, e.g. techniques for restricting cryptographic keys to pre-authorized uses, different access levels, validity of crypto-period, different key- or password length, or different strong and weak cryptographic algorithms network architectures or network communication protocols for using time-dependent keys in a packet data network H04L63/068
• CPC Class Codes: H04L 9/0894 Escrow, recovery or storing of secret information, e.g. secret key escrow or cryptographic key storage
• CPC Class Codes: H04L 9/3093 involving Lattices or polynomial equations, e.g. NTRU scheme

Abstract

A master public key is generated as a first set of lattices based on a set of attributes, along with a random vector. A master secret key is generated as a set of trap door lattices corresponding to the first set of lattices. A user secret key is generated for a user'"'"'s particular set of attributes using the master secret key. The user secret key is a set of values in a vector that are chosen to satisfy a reconstruction function for reconstructing the random vector using the first set of lattices. Information is encrypted to a given set of attributes using the user secret key, the given set of attributes and the user secret key. The information is decrypted by a second user having the given set of attributes using the second user'"'"'s secret key.

Claims

1. A computing system for performing attribute based decryption, comprising:

decryption logic that receives a user secret key, a ciphertext, and a value c and decrypts the ciphertext to obtain a message m, the value c being a multiplication of a first random vector s chosen during encryption for each attribute in a subset of attributes to which the message m is encrypted and a lattice B generated for each of the subset of attributes to which the message m is encrypted, and the ciphertext being an inner product of the first random vector s and a second random vector y plus the message m, the second random vector y and the lattice B being generated as a master public key for each of the attributes in the subset of attributes, the user secret key including a set of values for a vector e that satisfies a reconstruction function for reconstructing the second random vector y, given the lattice B;

a computer processor being a functional part of the computing system and activated by the decryption logic to facilitate decrypting the ciphertext to obtain the message m.

2. The computing system of claim 1, wherein the decryption logic multiplies the value c by the vector e to obtain a value for a vector product sy and subtracts vector product sy from the ciphertext to obtain the message m, wherein the vector product sy represents a product of the first random vector s and the second random vector y.

3. The computing system of claim 1 and further comprising:

key generator logic that generates the user secret key based on a set of attributes that define the user and are provided in an access structure that identifies a type of information the user can decrypt, the master public key and a master secret key that comprises a set of trap door lattices generated for each of the attributes in the set of attributes provided in the access structure.

4. The computing system of claim 3 wherein the key generator further secret shares the second random vector y with the user.

5. The computing system of claim 3, wherein the user secret key is generated by generating values for the vector e that satisfy a reconstruction function eB=y for a given attribute, where the reconstruction function eB is a multiplication of vector e with lattice B.

6. The computing system of claim 3, wherein, prior to generating the user secret key, a set of allowed attributes U are received, and, for each attribute in the set of allowed attributes U, a setup operation is run to generate the master public key and the master secret key.

7. The computing system of claim 1 and further comprising:

encryption logic that receives the message m to be encrypted and generates an encrypted form of the message m to a predefined subset of attributes using the master public key.

8. The computing system of claim 7 wherein the encryption logic selects the random vector s and computes the value c for each given attribute in the predefined subset of attributes, the value c including a multiplication of the first random vector s with the lattice B for the given attribute.

9. The computing system of claim 8 wherein the encryption logic computes the ciphertext for message m as an inner product of the first random vector s and the second random vector y for the given attribute.

10. The computing system of claim 9 wherein the encryption logic outputs the value c and the ciphertext as the encrypted form of the message m.

11. A computer-implemented method for performing attribute based decryption of information, the method comprising:

receiving a user secret key, a ciphertext, and a value c, wherein the value c comprises a multiplication of a first random vector s chosen during encryption for each attribute in a subset of attributes to which a message m is encrypted and a lattice B generated for each of the subset of attributes to which the message m is encrypted, and the ciphertext being an inner product of the first random vector s and a second random vector y plus the message m, and wherein the second random vector y and the lattice B are generated as a master public key for each of the attributes in the subset of attributes, the user secret key including a set of values for a vector e that satisfies a reconstruction function for reconstructing the second random vector y, given the lattice B; and

decrypting the ciphertext to obtain the message m using a computer processor.

12. The computer-implemented method of claim 11, and further comprising:

multiplying the value c by the vector e to obtain a value for a vector product sy; and

subtracting the vector product sy from the ciphertext to obtain the message m, wherein the vector product sy represents a product of the first random vector s and the second random vector y.

13. The computer-implemented method of claim 11, and further comprising:

generating the user secret key based on a set of attributes that define the user and are provided in an access structure that identifies a type of information the user can decrypt, the master public key, and a master secret key that comprises a set of trap door lattices generated for each of the attributes in the set of attributes provided in the access structure.

14. The computer-implemented method of claim 13, and further comprising:

secret sharing the second random vector y with the user.

15. The computer-implemented method of claim 13, wherein generating the user secret key comprises:

generating values for the vector e that satisfy the reconstruction function eB=y for a given attribute, where eB is a multiplication of vector e with lattice B.

16. The computer-implemented method of claim 13, and further comprising:

prior to generating the user secret key,

receiving a set of allowed attributes U; and

for each attribute in the set of allowed attributes U, running a setup operation to generate the master public key and the master secret key.

17. The computer-implemented method of claim 11 and further comprising:

receiving the message m to be encrypted; and

generating an encrypted form of the message m to a predefined subset of attributes using the master public key.

18. The computer-implemented method of claim 17, and further comprising:

selecting the random vector s; and

computing the value c for each given attribute in the predefined subset of attributes, the value c including a multiplication of the first random vector s with the lattice B for the given attribute.

19. The computer-implemented method of claim 18, and further comprising:

computing the ciphertext for the message m as an inner product of the first random vector s and the second random vector y for the given attribute.

20. The computer-implemented method of claim 19, and further comprising:

outputting the value c and the ciphertext as the encrypted form of the message m.