Attribute-based encryption

From CryptoWiki
Jump to: navigation, search

Attribute-based encryption is a kind of algorithm of public key cryptography in which the private key is used to decrypt data is dependent on certain user attributes such as position, place of residence, type of account.

The idea of encryption attribute was first published Amit Sahai and Brent Waters in the «Fuzzy Identity-Based Encryption ", and later it was developed in article Vipul Goyal, Omkant Pandey, Amit Sahai and Brent Waters«Attribute-Based Encryption for Fine-Grained Access Control of Encrypted Data».


Statement of problem

Attribute encryption allows the sender to encrypt the message without obtaining the public key certificate. Ability to encrypt data with a public key without certificates in some cases is a solution of the problem. For example, the user A can send an encrypted message to the recipient B without PKI or when the recipient is not connected at the time of transmission. Personality is viewed as a set of descriptive attributes using attribute-based encryption. A user with a secret key ω can decrypt data encrypted with the public key ω', if and only if ωand ω' differ slightly. The threshold of insignificance of differences is set by some metric d. Assuming the sender wants to encrypt the document for all users who have a specific set of attributes. For example, the head of the bus fleet wants to convey information in an encrypted form to drivers. In this case, the data is encrypted with the attribute of the form: {"bus fleet", "Head", "driver"}. Anyone with these attributes, can decrypt this data. The advantage of this algorithm is that the encrypted file can be transmitted over an open communication channel or stored on a unprotected server. Theoretically the attribute can be any information. It is important that the attribute was inseparable from the subject or the object to which it is assigned or belong to. With regard to the subjects inalienability of attributes achieved either physically or through the use of technical, organizational and other security measures. With respect to information resources it is achieved by cryptographic methods.

Consider a simple example. The bus fleet has attributes: {"Head","accountant","engineer","driver","Bus(allowed access to the bus) "," bus fleet (allowed access to the territory of the bus fleet) "}. If the user A is a bus driver, he has the attributes {"bus fleet" ∧ "Bus" ∧ "Driver"}. If head encrypt the file with attributes {"bus fleet" ∧ ("Accountant" ∨ "engineer")}, the driver will not be able to decrypt the data. If the attributes are {"bus fleet" ∧ ("Accountant" ∨ "engineer" ∨ "driver")}, the driver will be able to decrypt the data.

The general scheme of the attribute-based encryption

This encryption algorithm took in part 3 side. The owner of the data, the user receives the data and the third party, the so-called trusted center. The role of the trusted center is to generate keys for encryption and decryption of data owners and recipient. Public and master keys are generated by a complete set of pre-defined attributes. If it add a user with new attribute to the system, the attribute is added to the set, and the open and master keys are generated anew. The owner of the data encrypts them with the public key and some attributes. The user receives the data can decrypt it using its own private key. This key provides the user a trusted center. Then it checks the correspondence between the attributes of the user's private key and attributes of the encrypted data. If the number of matched attributes exceeds a predetermined threshold d, the user can decrypt the data using the private key. Otherwise, data can not be decrypted.


Attributes of the encrypted data are {"bus fleet", "Head", "driver"}, d = 2. To the user has the ability to decrypt the data and access them a set of attributes of the user's private key must have at least two of the three attributes of data encryption.

Description of structures Access

Let {P1, P2,..., Dn} are a set of attributes. Set A ⊆ 2{P1, P2,..., Pn}is called monotone if: ∀ B,C : B ∈ A, B ⊆ C → C ∈ A. Structure access (monotone structure access) is a set (a monotone set) A non-empty subsets {P1, P2,..., Pn},ie, A ⊆ 2{P 1, P2,..., Pn}\{∅}. Users with a set of attributes that are included in the A is authorized sets, users are allowed access to the data. Sets do not belong to the A are unauthorized sets of attributes. It is important to note that the use of encryption schemes based on the attributes in its original form is limited monotone access structure. In 2007, it was proposed a generalization of the scheme in the event of non-monotonic structures, however, it is ineffective.

Description of the algorithm

Let G1,G2 are bilinear group of order p (p - prime), g is generator group G1:

e:G1xG2→G2 is bilinear mapping;

d is threshold value.

The general scheme consists of four stages, for each of them has its own algorithm.

Generating the public key and master key

Trusted center selects randomly t1,...,tn, y from finite field Zq and calculates the public key PK=(T1=gt1,...,Tn=gtn,Y=e(g,g)y), where g is a bilinear group generator G1 of order p (p - prime). In this step, the master key is also generated MK=(t1,...,tn,y).

Generate private keys

A set of user attributes is supplied to the input of the private key generation algorithm, and the output of the algorithm turns user's private key. The trusted center generates a private key for each user U. AU is a set of user attributes. Randomly polynomial q of degree d-1 is selected such that is q(0)=y. Private key is D={Di=g(q(i))/(ti)}∀i∈AU.


The input to the encryption algorithm is fed the message which it is necessary to encrypt, a set of attributes, the owner of which will be able to decrypt the data, and randomly selected number, and the output of the algorithm obtained encrypted data. Owner data encrypt a message M∈ G2 using a set of attributes ACT and a random number s ∈ Zq : CT=(ACT, E=MYs=e(g,g)ys,{Ei=gtis}∀i∈AU).


A set of user attributes AU and the encrypted data are supplied to the input of the decryption algorithm, and the output of the algorithm is obtained decrypted message. If |AU∩ACT|≥d, then of i∈AU∩ACT selected d attributes to compute values e(Ei,Di)=e(g,g)q(i)s,Ys=e(g,g)q(0)s=e(g,g)ys. Original message is M=E/Ys. Private keys are generated in the scheme for the principle of secret sharing. The new private key can not be obtained by the combination of several private keys that prevents the possibility of attack as a result of collusion users.

Types of encryption based on attributes

Key-policy attribute-based encryption

In 2006, in the Attribute-Based Encryption for Fine-Grained Acces Control of Encrypted Data ,authors are Vipul Goyal, Omkant Pandey, Amit Sahai и Brent Waters, the key-policy attribute-based encryption scheme of the attributes has been proposed. It says that encrypted data is described by a set of attributes, and access rule contained in the user's private key. If a set of attributes of data matches the structure of access to the user's private key, the data can be decrypted. For example, data encrypted with attributes {"Bus fleet" ∧ "Driver"}, a user's private key corresponds to the structure of access {"Bus fleet" ∧ ("Head" ∨ "Driver")}. Attributes of encrypted data correspond to the structure of the access user's private key, so the user can decrypt the data. The encryption algorithm is different from the original version of the ABE generating the private key and accordingly decrypt: the user's private key is generated by according to the structure of the necessary access. By separating secret for the vertices from the root to the top of each end x selected polynomial qx such that qx(0)=qparent(x)(index(x)), where parent(x) is node relative to the parent x, and index(x) is number tops x among the peaks belonging to the same parent. In this way, qr(0) corresponds to master key y, which is distributed on the leaves of the tree, the corresponding components of the private key.

Ciphertext-policy Attribute-based Encryption (CP-ABE)

In 2007 J. Bethencourt, A. Sahai, and B. Waters in work Ciphertext-policy attribute-based encryption, in Proceedings of IEEE Symposium on Security and Privacy proposed encryption scheme based on ciphertext-policy attribute-based encryption . Policy to access data not contained in user's private key, and the encrypted data itself (ciphertext). Private key corresponds to a set of attributes. If the attributes contained in the user's private key corresponding to the structure of the ciphertext access, the user can decrypt the data. For example, if the structure of access contained in the data looks like: {"Bus fleet" ∧ ("Head" ∨ "Driver")}, and a set of attributes in the user's private key is {"Bus fleet" ∧ "Head"}, the user can access the data. The main purpose of this algorithm is to achieve such a situation that few people, being in collusion, can decrypt the data only when at least one of them could do on their own. Let us consider the structure of access. Let {P1,P2...Pn} are attributes parties. A ⊆ 2{P1,P2...Pn} is monotone if ∀ B,C: if B ∈ A and B ⊆ C then C ∈ A. The structure of access is a set of A non-empty subsets of {P1,P2...Pn} i.e A ⊆ 2{P1,P2...Pn}\{∅}. Set of A is an authorized set. The algorithm consists of four steps: preliminary steps, encryption, decryption and key generation. Preliminary action is to describe the security settings and access attributes. The output is a public key and a master key. Encryption. The encryption algorithm accepts as input the public key, data to be encrypted, and access structure. The data will be encrypted so that only the user who has the necessary set of attributes, which in turn satisfy the structure of access can decrypt the data. We assume that the encrypted text implicitly contains A. Key generation. Key generation algorithm accept as input a universal key and a set of attributes. The output is a secret key. Decryption. Decryption algorithm accepts as input the public key cipher text and a secret key. If a set of attributes contained in secret key satisfies structure of access, the data will be decrypted. The main feature of the scheme is to facilitate key management and cryptographic access.

The complexity of the encryption CP-ABE linearly increases from the access policy parameters, but does not depend on the security policy tree. One can safely generate a large part of the complex encryption on the side, keeping a small amount of secret information processed locally. Decryption algorithm is computationally big, because the compound of the bilinear operation on encrypted text and private key is a complex computing process. PP-CP-ABE solves the problem by calculating a reliable private key and operations connection on the side of decryption service provider (DSP). Outsourcing does not give the content of these ciphertext DSP because the final stage of decoding performed descriptor. First it comes the configuration of the system and key. Trusted authority (TA) at the first install PP-CP-ABE system selects a bilinear operator e:G0 * G0 → G1 prime order δp generator g. TA also selects two random parameters α, β ∈ Zp. Open parameters are published in the form: PK={G0,g,h=gβ, f=g1/β, e(g,g)α}. The main key is MK=(β, gα), known only to TA. The user must register with the TA, as the user is authenticated, and create a personal private key. An attribute can be any descriptive string that identifies and classifies user. The algorithm of key generation: First, it chooses a random r ∈ Zp, then chooses arbitrary rj ∈ Zp for each parameter j ∈ S, where S is a set of attributes. Further, the private key is generatedSK={D=g(α +r)/(β); ∀ j ∈ S : Dj=gr × H(j)rj; D'j=grj}. Forward SK is sent to the owner of the data through a closed channel. For the third-party calculation of encryption and data privacy, owner of the data must selest the access policy treeT=TESP^TDO, where ^ is a logic element connecting TESP and TDO. TESP is policy data access to be executed by the encryption service provider and TDO policy-driven access to data. TDO has one parameter that can define a polynomial of degree 1 qR(x), and sets s=qR(0), s1=qR, s2=qR. Then the owner of the data sends the ESP {s1,TESP}. ESP runs the encryption algorithm: 1)∀ x ∈ TESP randomly selected polynomial qx with a degree of dx=kx-l, where kx is threshold secret sharing: for the root node TESP, i.e RESP, select dRESP is the degree of the polynomial qRESP(0)=s1; ∀ x ∈ TESP/RESP sets dx is the degree of the polynomial qx(0)=qparent(x)(index(x)). 2) It formed a temporary ciphertext CTESP={∀ y ∈ YESP:Cy=gqy(0),C'y=H(att(y))qy(0)}, where YESP is a set of finite nodes TESP. At the same time, the owner of data performs the following operations: 1) encrypts (s2,TDO) and receives CTDO={∀ y ∈ Y2:Cy=gqy(0),C'y=H(att(y))qy(0)}; 2) computes Ć=Me(g,g)αs and C=hs where M is a message. 3) sends CTDO,Ć,C in ESP. After receiving a message from the sender of data, ESP generates ciphertext CT={T=TESP^TDO; Ć=Me(g,g)αs; C=hs; ∀ y ∈ YESP ∪ YDO : Cy=gqy(0); C'y=H(att(y))qy(0)}. At the final stage ESP sends Encryption data to the data storage service provider. The sender of data checks whether the attributes owned by the recipient access rule T. If so, and sender sends SK and the ciphertext. After receiving the decryption occurs as follows: ∀ y ∈ Y=YESP ∪ YDO. It performs recursive function of decryption unit. R is rootT. The decryption unit (CT',SḰ, y). e(Di,Cy)/e(D'i,C'y)= e(gr × H(i)ri,gqy(0))/e(gr, H(i)qy(0))=e(g,g)ry(0)=Fy. Recursion is handled as follows:: ∀ y child element x calls the decryption function and stores the file as Fy.

Encryption with non-monotone access structure

Initially, restrictions imposed on access structures in encryption schemes based on the attributes, namely implied monotony of these structures. Tree appropriate structure might contain logic elements "And", "Or", but not "not", which imposes certain restrictions on the possible access rules. For example, if the head of the bus fleet wants to share some data with the drivers, but the drivers are not dismissed, the access structure should look like: {"Bus fleet" ∧ "Driver" ∧ "NOT_Dismissed driver"}. A method of partitioning algorithm to the case of non-monotone access structure was proposed in 2007 in the work of Ostrovsky and others. They proposed to add the negation in space of the attributes along with each item. Thus, the total number of possible attributes is doubled as compared with the classical scheme. As for the rest principle of the algorithm remains the same. This scheme has significant shortcomings. If the access structure is supposed explicitly to specify the negation of all the attributes, which is not expected to open access to the data, the resulting ciphertext may be contained in a large number of negations attributes that have no practical value to decrypt the data. It leads to a strong increase in the size of the ciphertext. Further, after encryption of data in the system may be new attributes, and encryption will have to produce again.

Practical application attribute encryption

Using attribute encryption can implement attribute access control model. Attribute encryption scheme is a mechanism that links the access policy rules either the access control objects (e.g. files) or cryptographic keys via which access is made. When it is necessary to provide access to information for many users, the usual encryption schemes are ineffective, since there is the need for data re-encrypted by public key of each user separately. Therefore attributive encryption scheme in which the policy is bound to the key, is to add a set of attributes to encrypted data and give a pair (Key, Policy) for each user. Key works only when the attributes in the ciphertext certify policy. Policy formed as conditions connected via logic operations "And" and "Or".

Attribute model of access control. The main difference of this model is that each situation is evaluated in terms of attributes. Politics, in fact, is a set of conditions in which the various attributes must satisfy the requirements imposed on them. Obviously there are several categories of attributes:

  • Resource Attributes
    • Type;
    • Creator;
    • Name;
    • ...
  • The attributes of the subject
    • Name;
    • Department;
    • Position;
    • ...
  • Attributes actions
    • Name;
    • ...
  • Attributes environment
    • IP-address;
    • Time;
    • Device;
    • ...

To perform the authorization values of all attributes are taken at the time of inspection rights and are compared with the expected values. The fulfillment of all conditions provides access to a resource. In this model, there is no limit to the complexity of the policy. To attribute access control model there is a standard XACML.



Go to References.

Return to the table of contents.

Zhuravlev K.A., 2015