Identity-based encryption schemes

From CryptoWiki
Jump to: navigation, search

Once in 1984, Shamir proposed the idea about the prospect of the creation of public-key cryptosystems based on the identification data (IBE) [Shamir_85], for nearly 20 years was not offered a single algorithm that meets all performance and safety requirements, allowing to implement this idea into practice. Some solutions require that the condition of the impossibility of collusion scheme participants, the other - a large processing time at the request of the user's private key generation center of the private key (Private Key Generator, PKG). Things changed with the appearance of the article Bonn-Franklin [Boneh_Franklin_01] in the year 2001, which was proposed encryption scheme based on the identity using the Weil pairing. However, from the practical point of view, the use of mating presents some difficulties due to the high complexity of its calculation.


Mathematical apparatus

Pairing [Kogos_14] is called nondegenerate linear mapping e: G × G → H, where G - the additive group of order N, H - multiplicative group of order N. Bilinearity by definition means that the following identities [Bolotov_06]: e(P1 + P2,Q) = e(P1,Q) e(P2,Q), e(P,Q1 + Q2) = e(P,Q1)e(P, Q2), and nondegenerate means that e (P, P) ≠ 1. If for calculating pairing polynomial algorithm is known, it can be used to create cryptosystems. Strength of cryptosystems based on intractable bilinear problems Diffie - Hellman [Bolotov_06].

The Weil and Tate pairings

Among the infinite number of pairings two class of pairings are used often in elliptic curve cryptography - the Weil pairing and the Tate pairing [Kogos_14]. Let E (Fqk) is an elliptic curve over the field Fq k, where k - characteristic of the field, qk - the order of the field, (0) - an infinite point. For any point P: P + (0) = (0) + P = P. If P = (x, y), the -P = (x, -y). The point P of the curve E (Fq k) is called the point of r-torsion if [r] P = (0). Let E [r] - the set of points r-torsion. The Weil pairing is a pairing er: E [r] × E [r] → Fqk, satisfying conditions of [Kogos_14]: 1) bilinearity er (P1 + P2, Q) = er (P1, Qer (P2, Q), er (P, Q1 + Q2) = er (P, Q1) er (P, Q2); 2) non-degeneracy for any finite point P ∈ E [r] there is a point Q ∈ E [r], such that er (P, Q) ≠ 1; 3) alternation er (P, P) = 1. The Tate Pairing is a pairing <x, x>: E (Fq) [r] × E [r] → Fqk, satisfying the same conditions 1-3 as the Weil pairing. Connection between the Weil and the Tate pairings is known [Gentry_03]:

Связь Вейля Тейта.png

According to this correlation considered that for the calculation of the Weil pairing is necessary to calculate two Tate pairings, because of the complexity of the division operation is much less than the computational complexity of pairing.

Miller's Weil pairing algorithm

The subsequent exposition is based on the concepts are defined in [Bolotov_06]. Divisor of curve E is a formal sum

Дивизор eng.png

Divisor of a nonzero rational function f is a formal sum

Дивизор функции eng.png

It is important for the following arguments is the statement that for any positive integer i and any point P there is a nonzero rational function fi such that its divisor is div (fi) = iP - [i] P - (i - 1) (0) [Boneh_Franklin_01].

Miller has suggested the idea for the calculation of the Tate pairing based on the theorem of principal divisors [Bolotov_06]. According to this algorithm, the calculations of addition and doubling the points of an elliptic curve, and the result is a divisor of a rational function. This function is the desired value of the Tate pairing.

Алгоритм Миллера eng.png

In Miller's algorithm [Kogos_14] m doublings a point of the elliptic curve and an average of m / 2 additions a point of the elliptic curve are calculated.

Identity Based Encryption

Identity Based Encryption (IBE) - asymmetric cryptosystem [Klochkov 08], in which the user's public key is calculated by a known manner based on the identity of the user. The identification information may be a user name, e-mail, mobile phone number, etc. The main advantage over classical asymmetric cryptosystems (public key, public key certificate, private key) is to simplify PKI (Public Key Infrastructure). In the initialization phase of scheme the services of the center key generation are required for the calculation of the private key of the user. At the user's request and the passage of a specific authentication procedure the center gives the private key. It is obvious that the center should enjoy absolute trust. As noted in the introduction, the idea of ​​cryptosystems based on the identification data belongs to Shamir. Boneh and Franklin [Boneh_Franklin_01] presented at the conference Crypto 2001 its encryption scheme based on the identification data, which is the first full-featured, efficient and provably resistant IBE and is based on the properties of bilinear pairings on elliptic curves . Cryptosystems based on bilinear pairings allow to solve basic problems of cryptography: encryption, public key generation, digital signature. Next consider encryption protocols.

IBE protocols [Kosolapov_07] are used to achieve privacy (confidentiality) in the exchange of information between the two callers. The problem of the distribution of public keys is eliminated, the public key of user B is obtained by a known manner on the identity of the user. For decryption of a message user B is passing the authentication procedure and receives from the PKG the private key.

The Boneh-Franklin IBE

Consider a basic encryption scheme based on the identity of the proposed Boneh and Franklin in 2001 [Boneh_Franklin_01]. This scheme is not resistant to the attack based on the selected ciphertext is the prototype of the complete circuit IBE, having this resistance.


In the basic scheme generator IG of random parameters BDHP is used, satisfying hypothesis BDHP. Let k - parameter of security is received by the protocol as an argument on the input.

Боне-Франклин eng.png

Thus, after decrypting the encrypted message obtain the original plaintext.

An IBE scheme based on the FullIdent Algorithm

On the basis of the basic IBE scheme the full scheme IBE [Fujisaki 99] was received. This scheme is resistant to attacks based on the selected ciphertext under the assumption that the BDHP generator parameters satisfies hypothesis BDHP.


Let n - is the length of the encrypted message.

Полная IBE 1 eng.png

Полная IBE 2 eng.png

Public Key Encryption with keyword Search implies IBE

This scheme was proposed by Boneh, Crescenzo, Ostrovsky and Persiano [Boneh_03] in 2003. Suppose User A wants to be able to read their e-mail, using a set of devices, such as laptop, computer, pager, telephone, and so on. d. [Kosolapov_07 ]. A mail server based on any key word in the letter, sent a letter to the appropriate device. Let B sends a letter with a mark "speed letter". Then after checking for the presence of the letters of the word, the server sends a message to a pager. Asymmetric encryption is used in this case is called Searchable Public Key Encryption (SPKE). In order for to send a message M with keywords W1, ..., Wn, B sends

Сообщение М eng.png

The truth of Public Key Encryption with keyword Search here is that, with given SPKE (Apub, W ') and certain loophole (issued to the server by user A) server can verify the equality W = W '. This scheme is protected from attacks based on the selected key words. Consider the example of a non-interactive SPKE scheme using bilinear pairings [Kosolapov_07].


Избирательное шифрование eng.png

Hierarchical Identity Based Encryption

The hierarchical encryption scheme based on the identity (HIBE) was proposed Gentry and Silverberg [Gentry_02], and allows the root PKG distribute the load, delegate to lower-level PKG the right of generate private keys and authentication.


Иерархическая схема шифрования eng.png

Comparison IBE and PKI systems

Make comparisons IBE systems and PKI, which are used in asymmetric cryptography.

Таблица сравнения eng.png

The most significant advantage of the IBE over the PKI is to simplify PKI. Instead of storing a huge database of public keys, the system can only store usernames and, if necessary, obtains public keys. There is no need to request certificate of the public key every time for an establishment of connection - sufficiently to use the identity of the partner to generate a public key. The main disadvantage of IBE is a large computational complexity of pairings on which the personal cryptography is based. Worldwide the question of a method's development of pairing optimization calculation is being investigated. In addition, the disadvantage of IBE is the PKG center's knowledge of the user's private key, which can be a serious problem. PKG must have absolute trust and/or IBE must be applied to a small network that has a trusted subject. Another difficulty in the use of IBE systems - the obligatory presence of a secure communication channel to transmit the PKG user's private key.



Go to Reference.


Belozubova A., 2015