Search

US-12627465-B2 - Attribute based encryption with bounded collusion resistance

US12627465B2US 12627465 B2US12627465 B2US 12627465B2US-12627465-B2

Abstract

An attribute based encryption system includes a key generator configured to generate a cyclic group (G) having a prime order q; generate an attribute key matrix (M); generate a master public key (MPK) based, at least in part, on the group (G) and (M); generate a master secret key (MSK) based on a first vector s and a second vector t that represent an encryption policy; generate a user secret key based, at least in part, on the MSK and on a set of one or more user attributes; and send the user secret key to a user device, wherein a ciphertext message can be successfully decrypted if a vector y associated with attributes of the user associated with the user secret key is orthogonal to each row of a set of rows of M selected according to a set of authorization attributes used to encrypt the ciphertext message.

Inventors

  • Karim Eldefrawy
  • Nicholas James Genise

Assignees

  • SRI INTERNATIONAL

Dates

Publication Date
20260512
Application Date
20220302

Claims (20)

  1. 1 . A method comprising: generating, by one or more processors, a cyclic group G having a prime order q; selecting, by the one or more processors, a first generator g and a second generator h from the cyclic group G; generating, by the one or more processors, an attribute key matrix M, wherein each row of M corresponds to a candidate attribute of a plurality of candidate attributes; generating a first vector s and a second vector t, each of s and t having a length l corresponding to a number of candidate attributes; generating a vector H having the length l, wherein each i th component of H comprises a value determined by: g s i ⁢ h t i generating, by the one or more processors, a master public key (MPK) based, at least in part, on the cyclic group G, q, g, h, H and M; generating a master secret key (MSK) based on the first vector s and the second vector t; generating, by the one or more processors, a user secret key, the user secret key based, at least in part, on the MSK and on a vector x representing one or more user attributes; and sending, by the one or more processors, the user secret key to a user device.
  2. 2 . The method of claim 1 , further comprising sampling a random prime q according to: p = 2 * q + 1 , wherein generating the cyclic group G comprises generating a subgroup of squares in the set of integers modulo p.
  3. 3 . The method of claim 2 , wherein generating the attribute key matrix M comprises concatenating a first identity matrix with a vector v, wherein each element of v is non-zero and selected from the set of integers modulo p.
  4. 4 . The method of claim 3 , further comprising generating a check matrix d comprising a concatenation of a negative of a transpose of the vector v with a second identity matrix; wherein a row of M corresponding to a candidate attribute comprises a decryption key based on the pair (M, d).
  5. 5 . The method of claim 4 , wherein generating the user secret key comprises: generating a random vector r from the set of integers modulo p; generating a vector y according to the formula: y i =r(−v i ·x i ) for i=1 to l−1, and y l =r 1 , where x i is a vector of attributes associated with the user; determining a first user secret key component sk s according to the inner product of y and s; determining a second user secret key component sk t according to the inner product of y and t; and generating the user secret key as a concatenation of y, sk s and sk t .
  6. 6 . The method of claim 1 , wherein generating the cyclic group G comprises generating a prime order group using an elliptic curve.
  7. 7 . The method of claim 1 , further comprising: receiving a plaintext message μ and a vector f of authorization attributes selected from the plurality of candidate attributes; selecting a subset of the rows of M corresponding to the vector f of authorization attributes; and encrypting the plaintext message μ in accordance with the MPK and the selected subset of rows of M to create a ciphertext message.
  8. 8 . The method of claim 7 , further comprising: selecting a random non-zero exponent r from a group of integers modulo q; determining a first component C of the ciphertext message according to C:=g r ; determining a second component D of the ciphertext message according to D:=h r ; determining a third component c of the ciphertext message, c having i subcomponents c i , wherein i represents a number of attributes n in the vector f of authorization attributes, and wherein each c i is determined according to the formula c i := μg s i ⁢ H i r for i=1 . . . n; and concatenating C, D and c to create the ciphertext message.
  9. 9 . The method of claim 7 , wherein the vector f comprise identifies a hierarchical rank corresponding to an integer n, and wherein selecting the subset of the rows of M comprises selecting the first n−1 rows of M.
  10. 10 . The method of claim 1 , further comprising: receiving a ciphertext message having components c, C and D, and a user secret key having components y, sk s , and sk t ; determining a first value ζ according to the formula ( ζ = ∏ c i y i ) C sk s ⁢ D sk t ; determining a second value z according to the formula z=(Σy i ) −1 (mod q); and determining output plaintext μ′ according to the formula μ′=ζ z ∈G.
  11. 11 . The method of claim 10 , wherein plaintext μ associated with the ciphertext message and μ′ match if y is orthogonal to each row of a set of rows of M selected according to a set of authorization attributes.
  12. 12 . An attribute based encryption system comprising: one or more processors; and a key generator executable by the one or more processors and configured to: generate a cyclic group G having a prime order q, select a first generator g and a second generator h from the cyclic group G, generate an attribute key matrix M, wherein each row of M corresponds to a candidate attribute of a plurality of candidate attributes, generate a first vector s and a second vector t, each of s and t having a length l corresponding to a number of candidate attributes, generate a vector H having the length l, wherein each i th component of H comprises a value determined by: g s i ⁢ h t i , generate a master public key (MPK) based, at least in part, on the cyclic group G, q, g, h, H and M, generate a master secret key (MSK) based on the first vector s and the second vector t, generate a user secret key, the user secret key based, at least in part, on the MSK and on a vector x representing one or more user attributes, and send the user secret key to a user device.
  13. 13 . The attribute based encryption system of claim 12 , wherein the key generator is further configured to sample a random prime q according to: p = 2 * q + 1 , wherein to generate the cyclic group G, the key generator is configured to generate a subgroup of squares in the set of integers modulo p, and wherein to generate the attribute key matrix M, the key generator is configured to concatenate a first identity matrix with a vector v, wherein each element of v is non-zero and selected from the set of integers modulo p.
  14. 14 . The attribute based encryption system of claim 13 , wherein the key generator is further configured to generate a check matrix d comprising a concatenation of a negative of a transpose of the vector v with a second identity matrix; wherein a row of M corresponding to a candidate attribute comprises a decryption key based on the pair (M, d).
  15. 15 . The attribute based encryption system of claim 13 , wherein the key generator is further configured to: generate a random vector r from the set of integers modulo p; generate a vector y according to the formula: y i =r(−v i ·x i ) for i=1 to l−1, and y l =r 1 , where x i is a vector of attributes associated with the user; determine a first user secret key component sk s according to the inner product of y and s; determine a second user secret key component sk t according to the inner product of y and t; and generate the user secret key as a concatenation of y, sk s and sk t .
  16. 16 . The attribute based encryption system of claim 12 , further comprising an encryption service executable by the one or more processors, the encryption service configured to: receive a plaintext message μ and a vector f of authorization attributes selected from the plurality of candidate attributes; select a subset of the rows of M corresponding to the vector f of authorization attributes; and encrypt the plaintext message μ in accordance with the MPK and the selected subset of rows of M to create a ciphertext message.
  17. 17 . The attribute based encryption system of claim 16 , wherein the encryption service is further configured to: select a random non-zero exponent r from a group of integers modulo q; determine a first component C of the ciphertext message according to C:=g r ; determine a second component D of the ciphertext message according to D:=h r ; determine a third component c of the ciphertext message, c having i subcomponents c i , wherein i represents a number of attributes n in the vector f of authorization attributes, and wherein each c i is determined according to the formula c i := μg s i ⁢ H i r for i=1 . . . n; and concatenate C, D and c to create the ciphertext message.
  18. 18 . The attribute based encryption system of claim 12 , further comprising a decryption service executable by the one or more processors, the decryption service configured to: receive a ciphertext message having components c, C and D, and a user secret key having components y, sk s , and sk t ; determine a first value ζ according to the formula ζ = ( ζ = ∏ c i y i ) C sk s ⁢ D sk t ; determine a second value z according to the formula z=(Σy i ) −1 (mod q); and determine output plaintext μ′ according to the formula μ′=ζ z ∈G.
  19. 19 . The attribute based encryption system of 18 , wherein the plaintext μ associated with the ciphertext message and the plaintext μ′ match if y is orthogonal to each row of a set of rows of M selected according to a set of authorization attributes.
  20. 20 . A method comprising: generating, by one or more processors, a cyclic group G having a prime order q; generating, by the one or more processors, an attribute key matrix M, wherein each row of M corresponds to a candidate attribute of a plurality of candidate attributes; generating, by the one or more processors, a master public key (MPK) based, at least in part, on the cyclic group G and M; generating a master secret key (MSK) based on a first vector s and a second vector t, where s and t each represent an encryption policy; generating, by the one or more processors, a user secret key, the user secret key based, at least in part, on the MSK and on a set of one or more user attributes; and sending, by the one or more processors, the user secret key to a user device, wherein a first plaintext μ associated with a ciphertext message and second plaintext μ′ associated with a decryption of the ciphertext message match if a vector y associated with attributes of the user associated with the user secret key is orthogonal to each row of a set of rows of M selected according to a set of authorization attributes used to encrypt the first plaintext μ.

Description

CROSS REFERENCE This application is a National Stage Entry of International Application No. PCT/US2022/018531, filed Mar. 2, 2022, which claims the priority benefit of U.S. Provisional Patent Application No. 63/155,642, filed on Mar. 2, 2021, each of which is hereby incorporated by reference. GOVERNMENT RIGHTS This invention was made with Government support under contract no. N66001-15-C-4071 awarded by Space and Naval Warfare (SPAWAR) Systems Center Pacific. The Government has certain rights in the invention. TECHNICAL FIELD This disclosure is related to encryption, and more specifically to attribute based encryption in computing systems. BACKGROUND Private data sharing remains a critical challenge for individuals, enterprises, and national/international organizations. While sharing data is essential, sharing sensitive data with the wrong partner can have devastating consequences or even be prohibited by law. Attribute Based Encryption (ABE) is quickly becoming a desirable form of encryption for sharing sensitive data inside and between enterprises and other entities. This can be especially true when such data is stored by third parties in cloud platforms. ABE enables a fine-grained sharing of sensitive information. In some examples of ABE, organizations can set up attributes corresponding to natural sharing settings, e.g., corresponding to divisions, teams, and roles, and then issue keys to users depending on where in the organization they fit and/or their role. SUMMARY Standard public key encryption when used in organizational and inter-organizational settings is limiting and inadequate because it only enables selective sharing at a coarse-grained level. For example, anyone in possession of the private key corresponding to a specific public key under which a digital object is encrypted can decrypt the digital object. In addition, such organizational and inter-organizational settings are often dynamic because the set of users in such systems, and their identities, may be unknown, which renders issuing keys to specific identities impractical and cumbersome. Attribute based encryption has been developed to provide a more fine-grained level of encryption in which the encryption of data is based on a combination of required attributes that a user must possess in order to decrypt data. However, in some existing system, attribute based encryption can be defeated when users collude with one another to combine their attributes in order to decrypt data. For example, assume that user A has a user key that allows decryption of data encrypted for attributes I, J and K. Further assume that user B has a user key that allows decryption of data encrypted for attributes K, L, M and N. In the case of data encrypted for attributes I, J, M and N, neither user A nor user B have the complete set of attributes needed to decrypt the data. However, user A and user B may collude and combine their attributes, thereby enabling user A and user B to decrypt the data by combining their attributes. Some existing systems have implemented encryption schemes that attempt to make the encryption more resistant to collusion. However, such systems typically experience quadratic growth in the resources required to provide more collusion resistance. In general, the disclosure describes techniques for performing attribute based encryption with bounded collusion resistance using an ElGamal style encryption scheme that further includes an “AND” gate. Details on the ElGamal encryption scheme may be found in ElGamal (1985). “A Public-Key Cryptosystem and a Signature Scheme Based on Discrete Logarithms”. IEEE Transactions on Information Theory. 31 (4): 469-472, which is incorporated by reference herein in its entirety. The AND gate can be implemented using a key matrix in which each row in the matrix corresponds to a decryption key for a particular attribute. A request to encrypt data may include a specification of the attributes that will be required to decrypt the data. The encryption scheme according to the techniques disclosed herein can thus encrypt data according to a modified disjunctive normal form (DNF) formula by encrypting the data under each “AND” clause represented by the selected row in the key matrix. The encryption scheme selects rows from the key matrix based on the specified attributes. In order to decrypt data encrypted using the scheme, the user must have all of the attributes used to encrypt the data. The techniques described herein can be incorporated into a practical application such as an encryption/decryption system having one or more technical advantages over existing systems. For example, as discussed above, existing systems that attempt to provide collusion resistance typically experience quadratic grown in the resources used and the size of the ciphertext that corresponds to the degree to which collusion resistance is provided. In contrast, the techniques disclosed herein may provide an encryption system in which the growt