Attribute based encryption using lattices

• US 9,281,944 B2
• Filed: 01/10/2014
• Issued: 03/08/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
• Primary Examiner(s): HOLDER, BRADLEY W
• Application Number:
  US14/152,312
• Publication Number:
  US 20140129845A1
• Time in Patent Office: 788 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 system for performing attribute based encryption of information, comprising:

setup logic 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 T as a master secret key;

key generator logic 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;

encryption logic 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; and

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

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

3. The system of claim 2 wherein the encryption logic 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 random vector s with lattice B for the given attribute.

4. The system of claim 3 wherein the encryption logic computes a ciphertext for message m as an inner product of random vector s and y for the given attribute.

5. The system of claim 4 wherein the encryption logic outputs the value c and the ciphertext as the encrypted form of message m.

6. The system of claim 5 and further comprising:

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

7. A method for performing attribute based encryption of information, the method comprising:

receiving a set of allowed attributes to which the information can be encrypted;

for each attribute in the set of allowed attributes, generating a lattice B and a trap door lattice T as well as a random vector y, outputting the lattice B and vector y as a master public key, and maintaining the trap door lattice T as a master secret key;

receiving 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 and the vector y being shared with the user;

generating, by a computer processor, 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 vector y, given lattice B, the user secret key being output for encrypting messages; and

receiving a 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.

8. The method of claim 7, comprising generating vector e such that eB=y, where eB is a multiplication of a vector with a lattice.

9. The method of claim 8 and further comprising selecting a random vector s and computing a value c for each given attribute in the predefined subset of attributes, the value c including a multiplication of random vector s with lattice B for the given attribute.

10. The method of claim 9 and further comprising computing a ciphertext for message m as an inner product of random vector s and y for the given attribute.

11. The method of claim 10 further comprising outputing the value c and the ciphertext as the encrypted form of message m.

12. The method of claim 11 and further comprising:

receiving the decrypted form of the message m and decrypting the encrypted form of the message m using the user secret key.