ID-based encryption

ID-based encryption or identity-based encryption is an asymmetric cryptosystem in which the public key is calculated based on some unique information about the user's identity ( identification data ). Such information may be a username, email address, contact phone number or any other data.

In addition, other names of this cryptosystem are also used: IBE, encryption based on identification, personal encryption .

Content

History

In 1984, Adi Shamir put forward the idea of creating a cryptosystem with a public key obtained on the basis of identification data ^[1] . In his work, Adi Shamir did not give a complete description of the system, but developed a signature based on identification information and a public key infrastructure based on an email address.

The first practical implementations were presented in 2001 by Clifford Cox - ^2] , as well as Dan Boneh and Matthew K. Franklin - ^[3] .

IBE Job Description by Adi Shamir

Personal encryption allows any party to generate a public key from any user identification information, securely exchange messages, verify signatures without exchanging keys. The scheme requires a reliable center for generating private keys - a third trusted party called Private Key Generator (PKG), the purpose of which is to provide each new user with a personal smart card. The card consists of a microprocessor, I / O port, RAM, ROM with the user's private key, as well as programs for encrypting, decrypting, signing messages and verifying signatures. Previously released smart cards do not require updating when adding new users to the system. The scheme can be successfully used for a closed circle of users - an international company, a large bank, etc., since the headquarters of such an organization is able to organize and administer a trusted PKG for this group of users ^[1] .

In the authentication-based encryption scheme, a public key cryptosystem with some changes is taken as a basis. The difference between IBEs is that instead of generating a random pair of private and public keys and publishing the corresponding public key, the user selects his name, mail or other well-known identification data as a public key that can be uniquely associated with this user. The corresponding private key is calculated using PKG and issued to the user in the form of a smart card described above ^[1] .

The process of establishing a secure IBE communication channel can be described as follows:

User A signs a message using his private key on a personal smart card, encrypts the result using the recipient’s identity and sends a message to the recipient, user B. After receiving the message, user B decrypts it using the private key on his personal smart card, checks sender's signature using his identification data.

It is important to note that to ensure secure messaging, private keys should only be calculated by the PKG server.

The operation of the algorithm can be visualized in the form:

Figure 1. Personal encryption. Description of work

The overall reliability of this cryptosystem depends on:

Reliability of basic cryptographic functions
Reliability of storing information (keys) on a PKG server
Carefulness of checking future user information before issuing smart cards
Precautions to prevent loss, theft, duplication or unauthorized access to smart cards and their observance by users ^[1] .

Figure 2. Personal encryption. The difference between cryptosystems

The differences between the schemes with private, public key and personal encryption are clearly shown in Figure 2. In all schemes, the message $m$ ${\ displaystyle m}$ encrypted with a key $k e$ ${\ displaystyle ke}$ transmitted over an open channel as ciphertext $c$ ${\ displaystyle c}$ and decrypted with a key $k d$ ${\ displaystyle kd}$ . Key generation occurs using a random parameter $k$ ${\ displaystyle k}$ . In the private key scheme $ke=kd=k$ ${\ displaystyle ke = kd = k}$ public key encryption keys $k e$ ${\ displaystyle ke}$ and decryption $k d$ ${\ displaystyle kd}$ generated using a random parameter $k$ ${\ displaystyle k}$ through two different functions $ke=fe(k)$ ${\ displaystyle ke = fe (k)}$ and $kd=fd(k)$ ${\ displaystyle kd = fd (k)}$ . Another principle lies in the encryption scheme based on identification data: user identification information acts as an encryption key $ke=i$ ${\ displaystyle ke = i}$ , the decryption key is generated using some user ID $i$ ${\ displaystyle i}$ and random parameter $k$ ${\ displaystyle k}$ through function $kd=f(i,k)$ ${\ displaystyle kd = f (i, k)}$ ^[1] .

Figure 3. Personal encryption. Signature Differences

The signature scheme in a public-key cryptosystem is different from that for personal encryption. The difference between these signature schemes can be traced in Figure 3.

Implementation proposed by Adi Shamir

In 1984, Adi Shamir proposed a specific implementation only for the message signature scheme, suggested that there are implementations of the cryptosystem itself, and also urged the community to search and study them.

The signature scheme is based on the verification of the following conditions: $s^{e}=i*t^{f(t,m)}~(mod~n)$ ${\ displaystyle s ^ {e} = i * t ^ {f (t, m)} ~ (mod ~ n)}$ where $m$ ${\ displaystyle m}$ - message, $(s,t)$ ${\ displaystyle (s, t)}$ - signature $i$ ${\ displaystyle i}$ - user identity $n$ ${\ displaystyle n}$ - the product of two large prime numbers, $e$ ${\ displaystyle e}$ Is a large prime number that is mutually prime with $\varphi (n)$ ${\ displaystyle \ varphi (n)}$ ^[1] .

Options $n, e$ ${\ displaystyle n, e}$ and function $f$ ${\ displaystyle f}$ selected on the PKG side are equal for all users. Functional Description $f$ ${\ displaystyle f}$ stored by each user in an individual smart card. The values of these parameters may be public, but the decomposition $n$ ${\ displaystyle n}$ prime factors should only be stored on a PKG server. You can only distinguish one user from another based on their identifier $i$ ${\ displaystyle i}$ . Single private key $g$ ${\ displaystyle g}$ corresponding $i$ ${\ displaystyle i}$ , there is nothing like: $g^{e}=i~(mod~n)$ ${\ displaystyle g ^ {e} = i ~ (mod ~ n)}$ . This key can simply be calculated on the PKG server, but no one else can calculate $e$ ${\ displaystyle e}$ ^[1] .

Every message $m$ ${\ displaystyle m}$ has a large number of possible $(s,t)$ ${\ displaystyle (s, t)}$ signatures and, in this case, a random pairing algorithm $(s,t)$ ${\ displaystyle (s, t)}$ ineffective. Any attempt to fix a random value for one variable from a pair $(s,t)$ ${\ displaystyle (s, t)}$ and solve the expression $s^{e}=i*t^{f(t,m)}~(mod~n)$ ${\ displaystyle s ^ {e} = i * t ^ {f (t, m)} ~ (mod ~ n)}$ for another uncommitted variable will require factoring $n$ ${\ displaystyle n}$ , which is a difficult computational task at the moment. However, if the value $g$ ${\ displaystyle g}$ reliably known, and decomposition $n$ ${\ displaystyle n}$ not known, there is a simple way to generate any number of signatures for any message ^[1] .

To sign some message $m$ ${\ displaystyle m}$ , the user must select a random number $r$ ${\ displaystyle r}$ and calculate: $t=r^{e}~(mod~n)$ ${\ displaystyle t = r ^ {e} ~ (mod ~ n)}$ . The above condition $s^{e}=i*t^{f(t,m)}~(mod~n)$ ${\ displaystyle s ^ {e} = i * t ^ {f (t, m)} ~ (mod ~ n)}$ can be rewritten as: $s^{e}=g^{e}*r^{ef(t,m)}~(mod~n)$ ${\ displaystyle s ^ {e} = g ^ {e} * r ^ {ef (t, m)} ~ (mod ~ n)}$ . Because $e$ ${\ displaystyle e}$ is mutually simple with $\varphi (n)$ ${\ displaystyle \ varphi (n)}$ , then we can exclude the common factor from the exponent. Eventually: $s=g*r^{f(t,m)}~(mod~n)$ ${\ displaystyle s = g * r ^ {f (t, m)} ~ (mod ~ n)}$ can be calculated without calculation $e$ ${\ displaystyle e}$ ^[1] .

Existing IBE Cryptosystems

Currently, identity-based encryption schemes are based on bilinear pairings (Weil and Tate) and elliptic curves . Dan Boneh and developed the first of these schemes in 2001 - the ^[3] . It performs probabilistic encryption of a message of arbitrary length, similar to the El-Gamal scheme ^[3] .

A different approach to encryption was proposed by in 2001 - . This cryptosystem uses quadratic residues modulo a large number, encrypts messages one bit at a time, and increases the length of the ciphertext compared to the initial message ^[2] .

In practice, the following cryptosystems are used based on identification data:

(BF-IBE) ^[3]
(SK-IBE) ^[4]
Boneh-Boyen scheme (BB-IBE) ^[5]

Resistance Studies of Modern IBE Systems

In 2010, Xu An Wang and Xiaoyuan Yang conducted a study of the strength of two Hierarchical Identity-based Encryption schemes, which involve using multiple PKG servers of different "levels" to generate user keys. The researchers conducted an attack using a randomly selected private key of the first "level", obtaining the necessary private key for the target $I D$ ${\ displaystyle ID}$ user victim. The obtained private key will allow to decrypt any encrypted messages of the victim user ^[6] .

In 2014, Jyh-Haw Yeh researched the and concluded that the authors of this cryptosystem provide only an indication of the use of a cryptographic hash function , but do not offer any specific implementations of this hash function. Jyh-Haw Yeh in his work developed and proposed for use a cryptographic hash function that satisfies the following requirements ^[7] :

Simple “direct” calculation (unidirectional function)
Resistance to the search for the first prototype
Resistance to the search for the second prototype
Collision Resistance

In addition, when developing a cryptographic hash function, Jyh-Haw Yeh supplemented the list of requirements with the following ^[7] :

Resistance to the search for the ratio between the prototypes

In other words, this additional property requires the complexity of calculating the coefficient $c$ ${\ displaystyle c}$ for arbitrary prototypes $m_{1},m_{2}$ ${\ displaystyle m_ {1}, m_ {2}}$ in relation to $H(m_{1})=c*H(m_{2})$ ${\ displaystyle H (m_ {1}) = c * H (m_ {2})}$ or in $H(m_{2})=c*H(m_{1})$ ${\ displaystyle H (m_ {2}) = c * H (m_ {1})}$ where $H$ ${\ displaystyle H}$ - hash function. It is important to note that without the introduction of an additional property, the work of Jyh-Haw Yeh would be a study of the cryptographic strength of the Boneh-Franklin scheme ^[7] .

Benefits

One of the main advantages of identity-based encryption schemes is that in a system with a finite number of users and unchanged identifiers after generating keys in PKG, the main private key can be destroyed or PKG can stop working (it can reduce server support costs). This is possible because user keys are always valid after generation (the system does not have key cancellation methods). Systems that implement the key cancellation method lack this advantage ^[8] ^[9] .
Due to the fact that in the IBE system, public keys are generated by identifier, there is no need to create an infrastructure for distributing public keys. The authenticity of the public key is guaranteed as long as the sending of the user's private keys remains secure ^[8] ^[9] .
To receive an encrypted message from the recipient, preparation is not required ^[8] ^[9] .

Weaknesses

If the Private Key Generator is compromised, then all messages for all time protected by the private-public key pair will also be compromised. This makes Private Key Generator a valuable target for attackers. To reduce losses due to PKG hacking, a pair of master keys (main public and private keys) can be regenerated using a new pair of independent keys. However, in this case, it is necessary to implement a key management scheme, since each user must have the correct keys at the given time ^[8] ^[9] .
According to the basic principles of identifier-based encryption, Private Key Generator generates user private keys, so it can sign messages on behalf of any user, as well as decrypt messages without authorization. However, this drawback should not become a problem for organizations that host their own PKG, are ready to trust system administrators and do not require the ability to confirm user actions (non-repudiation). Traditional asymmetric encryption with public key infrastructure does not have this drawback ^[8] ^[9] .
To send a private key safely, a secure data channel between the Private Key Generator and the user is required. Users with PKG accounts must be able to authenticate with the system. This can be achieved, for example, using a login-password pair or a pair of public keys on smart cards ^[8] ^[9] .
The IBE system can be based on cryptographic methods that are not suitable for protection against attacks by quantum computers (Shor algorithm) ^[8] ^[9] .

Notes

↑ ¹ ² ³ ⁴ ⁵ ⁶ ⁷ ⁸ ⁹ Shamir A. Identity based cryptosystems and signature schemes // Advances in Cryptology. // Proceedings of CRYPTO 84. - 1985. - S. 47-53 .
↑ ¹ ² Clifford Cocks. An Identity Based Encryption Scheme Based on Quadratic Residues ( Neopr .) . Proceedings of the 8th IMA International Conference on Cryptography and Coding (2001).
↑ ¹ ² ³ ⁴ Dan Boneh, Matthew K. Franklin. Identity-Based Encryption from the Weil Pairing // Springer Berlin Heidelberg. - 2001.
↑ Sakai, Ryuichi; Kasahara, Masao. ID Based cryptosystems with pairing on elliptic curve // Cryptography ePrint Archive: journal. - 2003. - Vol. 2003/054 .
↑ Boneh, Dan; Boyen, X. Efficient selective-ID secure identity based encryption without random oracles // LNCS: journal. - Springer-Verlag, 2004 .-- Vol. Advances in Cryptography - EUROCRYPT 2004 . - P. 223-238 . - DOI : 10.1007 / 978-3-540-24676-3_14 .
↑ Jian WENG, Min-Rong CHEN, Kefei CHEN, Robert H. DENG. Cryptanalysis of a Hierarchical Identity-Based Encryption Scheme ( IE ) // IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences. - 2010-04-01. - Vol. E93.A , iss. 4 . - ISSN 1745-1337 0916-8508, 1745-1337 . - DOI : 10.1587 / transfun.E93.A.854 .
↑ ¹ ² ³ Jyh-Haw Yeh. Security Vulnerability in Identity-Based Public Key Cryptosystems from Pairings // International Journal of Information and Education Technology. - S. 466-470 . - DOI : 10.7763 / ijiet.2013.v3.319 .
↑ ¹ ² ³ ⁴ ⁵ ⁶ ⁷ Carl Youngblood. An Introduction to Identity-based Cryptography // CSEP 590TU.
↑ ¹ ² ³ ⁴ ⁵ ⁶ ⁷ Mao, Wenbo. Modern cryptography: theory and practice . - Upper Saddle River, NJ: Prentice Hall PTR, 2004 .-- xxxviii, 707 pages p. - ISBN 0130669431 .

[:2-1] ¹ ² ³ ⁴ ⁵ ⁶ ⁷ ⁸ ⁹ Shamir A. Identity based cryptosystems and signature schemes // Advances in Cryptology. // Proceedings of CRYPTO 84. - 1985. - S. 47-53 .

[:0-2] ¹ ² Clifford Cocks. An Identity Based Encryption Scheme Based on Quadratic Residues ( Neopr .) . Proceedings of the 8th IMA International Conference on Cryptography and Coding (2001).

[:1-3] ¹ ² ³ ⁴ Dan Boneh, Matthew K. Franklin. Identity-Based Encryption from the Weil Pairing // Springer Berlin Heidelberg. - 2001.

[4] Sakai, Ryuichi; Kasahara, Masao. ID Based cryptosystems with pairing on elliptic curve // Cryptography ePrint Archive: journal. - 2003. - Vol. 2003/054 .

[5] Boneh, Dan; Boyen, X. Efficient selective-ID secure identity based encryption without random oracles // LNCS: journal. - Springer-Verlag, 2004 .-- Vol. Advances in Cryptography - EUROCRYPT 2004 . - P. 223-238 . - DOI : 10.1007 / 978-3-540-24676-3_14 .

[6] Jian WENG, Min-Rong CHEN, Kefei CHEN, Robert H. DENG. Cryptanalysis of a Hierarchical Identity-Based Encryption Scheme ( IE ) // IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences. - 2010-04-01. - Vol. E93.A , iss. 4 . - ISSN 1745-1337 0916-8508, 1745-1337 . - DOI : 10.1587 / transfun.E93.A.854 .

[:3-7] ¹ ² ³ Jyh-Haw Yeh. Security Vulnerability in Identity-Based Public Key Cryptosystems from Pairings // International Journal of Information and Education Technology. - S. 466-470 . - DOI : 10.7763 / ijiet.2013.v3.319 .

[:4-8] ¹ ² ³ ⁴ ⁵ ⁶ ⁷ Carl Youngblood. An Introduction to Identity-based Cryptography // CSEP 590TU.

[:5-9] ¹ ² ³ ⁴ ⁵ ⁶ ⁷ Mao, Wenbo. Modern cryptography: theory and practice . - Upper Saddle River, NJ: Prentice Hall PTR, 2004 .-- xxxviii, 707 pages p. - ISBN 0130669431 .