ATTRIBUTE BASED ENCRYPTION USING LATTICES

• US 20120155635A1
• Filed: 12/17/2010
• Published: 06/21/2012
• Est. Priority Date: 12/17/2010
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Vaikuntanathan, Vinod, Voulgaris, Panagiotis
• Granted Patent: US 8,634,563 B2
• Time in Patent Office: Days
• US Class Current: 380/44
• 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 computer implemented method of transmitting data using a computer with a processor, comprising:

receiving, with the processor, a set of attributes S in an access structure A, a master public key that includes a lattice B generated for the set of attributes S and a vector y generated for the set of attributes S, as well as a master secret key that includes a trapdoor lattice T generated for the set of attributes, wherein the access structure identifies a type of information that can be decrypted by an entity having the set of attributes S in the access structure A;

generating, with the processor, a user secret key for the set of attributes S in the access structure A, the user secret key comprising a vector e that satisfies a reconstruction function for B, given y; and

outputting, with the processor, the user secret key for use in decrypting a message m encrypted, using the master public key, to the set of attributes S in the access structure A.

2. The computer implemented method of claim 1 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.

3. The computer implemented method of claim 2 wherein outputting the user secret key comprises:

secret sharing vector y with the reconstruction function.

4. The computer implemented method of claim 3 and further comprising:

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

5. The computer implemented method of claim 3 and further comprising:

receiving the message m, a subset of the attributes S to which m is to be encrypted, and the master public key;

selecting a random vector s; and

encrypting the message m to the subset of attributes S using the master public key and the vector s.

6. The computer implemented method of claim 5 wherein encrypting the message m, comprises:

for each of the attributes in the subset of attributes S, generating a corresponding value c as a multiplication of the vector s and lattice B, and generating a ciphertext that is an inner product of the vector s and the vector y plus the message m; and

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

7. The computer implemented method of claim 6 and further comprising:

decrypting the encrypted form of the message m using the user secret key, the value c and the ciphertext.

8. A system for performing attribute based encryption of information, comprising:

a setup component that receives a set of allowed attributes to which the information can be encrypted and, for each attribute in the set of allowed attributes, generates a lattice B and a trap door lattice T as well as a random vector y, and outputs the lattice B and vector y as a master public key and maintains the trap door lattice as a master secret key;

a key generator component that receives a set of user attributes that corresponds to a user, in an access structure, the access structure identifying a type of information the user can decrypt, the key generator secret sharing the vector y with the user and generating a user secret key for the access structure and the set of user attributes, based on the master public key and the master secret key, the user secret key including a set of values in a vector e that satisfies a reconstruction function for reconstructing y, given lattice B, the user secret key being output for encrypting messages; and

a computer processor, being a functional part of the system, and activated by the setup component and the key generator component to facilitate outputting the master public key and the user secret key.

9. The system of claim 8 wherein the key generator generates vector e such that eB=y, where eB is a multiplication of a vector with a lattice.

10. The system of claim 9 and further comprising:

an encryption component that receives a 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.

11. The system of claim 10 wherein the encryption component selects a random vector s and computes a value c for each given attribute in the predefined subset of attributes, the value c including a multiplication of s with B for the given attribute.

12. The system of claim 11 wherein the encryption component computes a ciphertext for m as an inner product of s and y for the given attribute.

13. The system of claim 12 wherein the encryption component outputs the value c and the ciphertext as the encrypted form of m.

14. The system of claim 13 and further comprising:

a decryption component that receives the decrypted form of the message m and decrypts the encrypted form of the message m using the user secret key.

15. A system for performing attribute based decryption, comprising:

a decryption component that receives a user secret key, a ciphertext and a value c and performs decryption on 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 m is encrypted and a lattice B generated for each of the subset of attributes to which 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 y, given B;

a computer processor being a functional part of the system and activated by the decryption component to facilitate decryption to obtain the message m.

16. The system of claim 15 wherein the decryption component multiplies c by e to obtain a value for sy and subtracts sy from the ciphertext to obtain the message m.

17. The system of claim 15 and further comprising:

a key generator component that generates the user secret key based on a set of attributes defining the user and 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.

18. The system of claim 17 wherein the key generator further secret shares the second random vector y with the user.