Parallel Key Insulated ID-Based Public Key Cryptographic Primitive with Outsourced Equality Test

DOI: 10.4236/jcc.2020.812018   PDF   HTML   XML   31 Downloads   83 Views  

Abstract

Parallel key-insulation allows the use of multiple helper keys to protect private decryption keys during secret decryption key updates. This approach prevents decryption key leakage or exposure in insecure environment. We combined parallel key-insulated encryption (PKIE) with multiple helper keys and identity-based encryption with the equality test (IBE-ET) to obtain parallel key insulated ID-based public key encryption with outsourced equivalent test (PKI-IBPKE-ET). The scheme inherits the advantages of identity-based encryption (IBE), which simplifies certificate management for public key encryption. Furthermore, the parallel key-insulation with multiple helper mechanism was introduced in our scheme, which perfectly reduced the possibility of helper key exposure. Our scheme will enable the protection and periodic update of decryption keys in insecure environment. Our scheme achieves a weak indistinguishable identity chosen ciphertext (W-IND-ID-CCA) security in the random oracle model. Ultimately, it is observed that our scheme is feasible and practical through the experimental simulation and theoretical analysis.

Share and Cite:

Alornyo, S. , Mohammed, M. , Kodzo, B. , Sarpong, P. and Asante, M. (2020) Parallel Key Insulated ID-Based Public Key Cryptographic Primitive with Outsourced Equality Test. Journal of Computer and Communications, 8, 197-213. doi: 10.4236/jcc.2020.812018.

1. Introduction

Due to the rapid growth of cloud computing [1], storing a user data in the cloud such as photos, moving pictures and other instant electronic messages has attracted the attention of individuals and organizations. However, cloud servers cannot be fully trusted in providing confidentiality and privacy of users data outsourced to the cloud. In this era of traffic analytics and privacy concerns, it is advisable to outsource user’s data to the cloud encrypted. Public key cryptosystem has proven to be suitable for encrypting such data. But it may be unrealistic for data owners to access all the data from the cloud via download whenever there is a need to access their files. Therefore, it is desirable to design a scheme that supports the search function on the ciphertext in the cloud server without the need to divulge any information related to these ciphertexts.

Boneh and Franklin et al. [2] proposed the first public key cryptographic primitive using keyword search (PKE-KS). In their scheme, the user could encrypt the keyword and corresponding data under a specific user’s identity, meanwhile, each user is allowed to create a target keyword trapdoor by using their secret key and then outsource it to the cloud. Nonetheless, outsourced servers can only then do comparison of keywords with trapdoors under similar public key. This has become the bottleneck for the development of keyword search because there is the need to do keyword search with different public keys. To forestall this problem, [3] proposed a public key cryptographic primitive with equality test based on the pairing bilinearity. Compared to PKE-KS, the equality or equivalent test of PKE-ET can be performed among two encrypted data (ciphertexts) with the similar public key, and with different public keys.

Following the construction of Yang et al. [3] scheme, some proposed schemes with equivalent test have been constructed [4] [5] [6] [7]. Recently, Ma [8] notion of a cryptographic primitive with equality test (IBE-ET) outsourced to the cloud is the first to blend identity-based cryptographic primitive with public key cryptosystem with equivalent test and this inherited the gains of such schemes. Thus, the problem caused by key exposure could not be avoided in their scheme. Undoubtably, key exposure will lead to a destructive consequence. In view of that, Dodis et al. [9] proposed the primitive of key-insulated cryptographic scheme. In their scheme, secret keys consist of two parts namely, secret user key and helper key. The purpose of the secret key adoption is to change frequently so as to prevent the likelihood of key exposure whereas the helper is adopted to help update the secret keys to reduce the exposure of secret decryption keys. Constructing a key-insulated scheme with helper keys that supports public key cryptosystem with equality test is still an open problem. Therefore, a scheme needed to be devised that satisfies both equality test and key-insulation in public key cryptography.

2. Related Work

2.1. Parallel Key-Insulated Cryptosystem

It is of importance to lessen the destructive effect generated by key exposure. Dodis et al. [9] first designed the key-insulation cryptosystem. However, in their scheme, the total time period number is determined in advance. Later, [10] proposed new key-insulated crytographic scheme. In their scheme, the total time period number does not need to be given in advance. Since then, many research results about key-insulated encryption have been propounded. By introducing the concept of proxy cryptographic re-encryption scheme, Wang et al. [11] constructed a key-insulated proxy cryptographic re-encryption scheme (KIPRE). He et al. [12] combined key-insulated encryption with certificateless public key encryption (CL-PKE) and designed a new paradigm of certificateless key-insulated cryptographic encryption scheme (CLKIE). Hanaoka et al. [13] combined identity based cryptographic scheme with key-insulation and constructed a novel identity based key-insulation cryptosystem with a single helper. Benot et al. [14] also constructed another identity based key-insulation scheme without the adoption of the random oracles.

Introduction of a helper in key-insulated encryption schemes helps to curtail the problem of decryption keys exposure. Thus, temporal secret keys are maintained by users and are refreshed via a mutual interaction between the user and helper. In key-insulated cryptosystems, it is required to often update the keys to reduce the risk of temporal decryption key exposure. This phenomenom requires frequent increase of helper connection during secret key updates in an insecure environment, hence makes the helper key prone to key exposure attacks. To curtail the tendency of helper keys exposure, Hanoaka et al. [15] constructed parallel key-insulation encryption (PKIE) to avoid the problem of helper exposure. Their scheme ensured that two distinct helpers alternatively update the secret key. This avoided or curtailed the exposure of a single helper. Therefore, securing the helper has become a major concern in PKIE. Most PKIE schemes [14] [15] [16] [17] adopted the helper approach to avoid the exposure of temporal secret keys and helper keys. Recently, Ren et al. [18] proposed multiple helper keys to reduce the risk of using one or two helpers for key updates. A secured helper in key-insulated public key encryption (KIPE) plays a vital role in users secret key updates.

2.2. Equality Test

The first public key cryptograhic scheme with keyword search was announced by Boneh et al. [19]. In their construction, users are able to test the equivalance between two encrypted data which are ciphertext with the same public key. Later, some well-designed PKE-KS schemes were constructed [20] [21] with search functions on ciphertexts with different public keys. To solve this problem, [3] constructed encryption scheme with equality test. Their scheme allowed users to search the ciphertexts in different public keys. After that, a large amount of schemes corresponding to PKE-ET have been propounded [19] [22] [23] [24]. Although PKE-ET has excellent performance, there are some inherent problems with key certificate management, that put serious constraints with regards to efficiency and practice. To solve this problem, Ma [18] combined PKE-ET and identity-based scheme (IBE) [2] [25] and reported the first identity-based cryptographic scheme with equality test (IBE-ET). Different from the public key cryptosystem with equality test, identity based cryptosystem solved the problem of key certificate management in public key cryptosystem with equality test. Recently, there have been other applications of identity based cryptographic primitive to detect and prevent malware in encrypted traffic [26]. Also, [27] constructed a dual server identity based cryptosystem which can resist the inner keywords guessing attack so as to prevent an attack on keyword search in public key cryptosystems. In order to provide a scheme that achieves indistiguishable identity chosen ciphertext attack (IND-ID-CCA) security, Lee et al. [28] constructed a semi-generic cryptosystem with equality test. Unfortunately, their scheme could not prevent the damage that emanate from private key exposure. So far, there has not been any scheme that can solve private key exposure and helper keys exposure problem in identity (ID) based cryptosystem with equality test.

2.3. Our Contribution

To address these challenges, we propose parallel key insulated ID-based public key encryption with outsourced equality test (PKI-IBPKE-ET). In summary, our contributions to this work consist of three points: 1) We first incoporate the idea of identity-based (ID) parallel key-insulated cryptosystem with multiple helper keys into IBE-ET to construct PKI-IBPKE-ET scheme. Specifically, PKI-IBPKE-ET enables the cloud server to perform equivalence test on ciphertext. Meanwhile, PKI-IBPKE-ET can resist helper key exposure and private decryption key exposure; 2) Our scheme achieves Weak-IND-ID-CCA (W-IND-ID-CCA) security, which also prevents an insider attack [29]; 3) Finally, we give the experimental simulation and theoretical analysis which shows the feasibility and practicability of our novel scheme.

2.4. Paper Organization

The rest of this work is organized as follows; In Section 3, our scheme outlines preliminaries for the construction and the definitions of PKI-IBPKE-ET. In Section 4, the security model is outlined, Section 5 outlines our construction of PKI-IBPKE-ET and proof the security in Section 6. Section 7 compares our work with existing schemes. Section 8 gives a conclusion remark.

3. Scheme Preliminaries

3.1. Bilinear Map

Let G and GT be two multiplicative cyclic groups of prime order p. We assume that g is a generator of G. A bilinear map e : G × G G T satisfies the following properties:

1) Bilinearity: For any g G , a and b Z p , e ( g a , g b ) = e ( g , g ) a b .

2) Non-Degenerate: e ( g , g ) 1 .

3) Computable: There is an efficient algorithm to compute e ( g , g ) for any g G .

3.2. Bilinear Diffie-Hellman (BDH) Problem

Let G and GT be two groups of prime order p. Let e : G × G G T be an admissible bilinear map and let g be a generator of G. The BDH problem in [ p , G , G T , e ] is as follows: Given [ g , g a , g b , g c ] for random a , b , c Z p for any randomized algorithm A computes value e ( g , g ) a b c with advantage:

A D V A B D H = P r [ A ( g , g a , g b , g c ) = e ( g , g ) a b c ] . (1)

The BDH assumption holds if for all polynomial-time algorithm A, its advantage A D V A B D H is negligible.

3.3. Definitions

This section gives formal definitions of our proposed scheme. A parallel key-insulated with a multiple helper keys [18] were adopted in our model to do away with the exposure of a single or double helpers and to increase the security of user secret keys. The system model is sketched in Figure 1. Our method achieves weak chosen ciphertext security (i.e. W-IND-ID-CCA) under a specified security construction model.

In parallel key-insulated ID-based public key encryption with equality test (PKI-IBPKE-ET), we specify nine algorithms: Setup, Extract, UserKeyGeneration, BaseKeyUpdate, UserTempKeyUpdate, PKITrapdoor, PKIEncrypt, PKIDecrypt, Test, M and CT are the plaintext space and ciphertext space, respectively:

Figure 1. System model of PKI-IBPKE-ET.

1) Setup ( , N , Q ) : It input a secured parameter , total time period N, numbr of helper keys Q and returns the public parameter K, helper keys ( b k 0 , , b k Q 1 ) and the temporal master key MSK.

2) Extract ( M S K , K , I D ) : On input MSK, arbitrary I D { 0,1 } , system parameter K and returns a secret key m d k I D 0 to the user with a corresponding identity ID. The PKG also performs such algorithm. Subsequently, PKG send to the user with a corresponding identity ID via a dedicated secure channel.

3) UserKeyGeneration ( K , N , m d k I D ) : The user generation algorithm on input the received secret key m d k I D , public paramter K, time period N and ID. The algorithm output helper key B K 0 .

4) BaseKeyUpdate ( B K 0 , b k j , t ) : On input the helper key B K 0 at a span b k j and index time span t. The algorithm output update key U K t .

5) UserKeyUpdate ( m d k I D t 1 , t , U K t ) : On input m d k I D t 1 , index t of the next span and update key U K t . It output the secret key m d k I D t for the next span t corresponding to the user ID.

6) PKIEncrypt ( K , t , I D , M 1 ) : It input K, the index span t of the current time period, an identity I D { 0,1 } and plaintext M 1 M , and return the ciphertext C T t as C T t = ( t , C T 1 ) , where C T t C T .

7) PKIDecryption ( m d k I D t , t , C T t ) : It takes a current private secret key m d k I D t and ciphertext C T t as input and return plaintext M 1 M or a symbol if the corresponding ciphertext is valid.

8) Test ( C T t A , C T t B ) : It takes ciphertext C T t A and C T t B outputted by user A and user B respectively. It output 1 if the corresponding message cooresponding to C T t A and C T t B are equal. It output 0, otherwise .

Correctness:

1) When m d k I D t the updated secret decryption key is generated with multiple helper. The BaseKeyUpdate algorithm on input ID as the public key, then;

M 1 M : D e c r y p t ( C T , m d k I D t ) = M 1 ,

where C T = E n c r y p t ( I D , M 1 ) and C T t = ( t , C T ) .

2) Supposedly, t d r A and t d r B are trapdoors generated by the trapdoor algorithm given I D A and I D B as the public keys, then;

M 1 M : T e s t ( C T A , t d A , C T B , t d B ) = 1 ,

where C T A = E n c r y p t ( I D A , M 1 ) and C T B = E n c r y p t ( I D B , M 1 ) .

3) The t d r A and t d r B are supposedly trapdoors generated by the trapdoor algorithm given I D A and I D B as the public keys, then:

M 1 , M 1 M and M 1 M 1 . P r [ T e s t ( C T A , t d A , C T B , t d B ) = 1 ]

is negligible where C T A = E n c r y p t ( I D A , M 1 ) and C T B = E n c r y p t ( I D B , M 1 ) .

4. Security Models

1) Setup ( ) : The challenger on input a security parameter executes the setup algorithm. It gives the system parameters K to the adversary A and keep the master key MSK to himself.

2) Phase 1-Private secret decryption key queries ( I D A ) : The challenger runs the extract algorithm to generate the private decryption key m d k t a corresponding to the user with public key I D a . It forwards m d k t a to A.

3) Trapdoor Queries ( I D a ) : The challenger executes the above private decryption key queries on I D a to obtain m d k I D a and subsequently generate the trapdoor t d r a using m d k I D a via trapdoor algorithm. Finally, the algorithm forwards t d a to A.

4) Decryption Queries ( I D a , ( t , C T a ) ) : The challenger executes decryption algorithm to decrypt the ciphertext ( t , C T a ) by executing extract algorithm to obtain the private secret key m d k I D t a relating to the public key I D a . Finally, it forwards plaintext M 1 to A.

5) Challenge: A submits an identity I D c h to which a challenge will be posed. The only constraints is that I D c h was not seen in private decryption key queries in phase 1 but I D c h may show in trapdoor queries in phase 1 or in decryption query I D c h . The challenger then randomly chooses plaintext M c h M and sets C T = E n c r y p t ( I D c h , M c h , t o k I D ) . Finally, it forwards C T to A as its challenge ciphertext.

6) Phase 2-Private decryption key queries I D a : Whereby I D a I D c h . The challenger respond similar to that of phase 1.

7) Trapdoor Queries ( I D a , C T i ) ( I D c h , C T ) : The challenger then responds similar to phase 1.

8) Decryption Queries ( I D a , C T i ) ( I D c h , C T ) : The challenger respond similar to phase 1.

9) Guess: A submits a guess M 1 M

The scheme is W-ID-CCA secure if for all W-IND-CCA adversaries,

A D V P K I - I B P K E - E T A W - I D - C C A ( K ) = P r [ M 1 = M 1 ] (2)

is negligible.

5. Construction

The detailed construction for the PKI-IBPKE-ET in this section includes:

1) Setup: ( , Q , N ) The system input a secured parameter , number of helper key Q, a time period N as input and return public system parameter K. The initial master secret key is MSK and multiple helper keys are ( b k 0 , , b k Q 1 ) .

● The system generates two multiplicative groups G and GT with the same prime order p of length bits and a bilinear map e : G × G G T . The system selects an arbitrary generator g G .

● The algorithm exploits a keyed permutation F : { 0,1 } k × { 0,1 } n Z p for a positive integers K = k ( ) and L = ( n ( ) ) . Set a random value k 1 from { 0,1 } L . Generate a MAC scheme M A C = G S V , where G is generate, S is sign and V verify. It obtain k 2 by running G ( ) . Set the master token key M T K = ( k 1 , k 2 ) .

● The system chooses three hash functions: H 1 : { 0,1 } p Z p , H 2 : { 0,1 } G , H 3 : T × G T { 0,1 } p + l where l is the length of random numbers, whereas p is the message length. The algorithm randomly picks ( α , β ) Z p 2 and set g 1 = g α , g 2 = g β . It publishes public parameter K = ( T , p , G , G T , e , g , g 1 , g 2 , b k Q , M A C , H 1 , H 2 , H 3 ) and M S K = ( α , β ) . T is referred to as MAC tag.

2) Extract ( K , M S K , I D ) : For a given string I D { 0,1 } , public parameter K and MSK. The algorithm compute h I D = H 2 ( I D ) G , set temporal master decryption key m d k I D t = ( h I D t α , h I D t β ) where ( α , β ) are the master secret key and the intial time index period at t.

3) UserKeyGeneration ( K , m d k I D t , I D t ) : On input m d k I D t , the algorithm randomly chooses b k Q 1 { 0,1 } p and set:

B K 0 = g b k Q 1 , g 3 = g α ( i = 1 Q 0 ( g H 1 ( b k j ( i ) ) ) r 1 ) , g 4 = ( i = 1 Q 0 ) , (3)

where r 1 = F ( b k j , i ) and j = ( 1 mod Q ) .

The function F is assumed as a pseudorandom permutation.

The initial secret helper keys B K 0 = ( g 3 , g 4 ) and number of helper set to ( b k 0 , , b k Q 1 ) .

4) BaseKeyUpdate ( b k j , t ) : On input helper key at b k j and a period index t. The helper key updater computes the jth helper base as:

U K t = ( g 3 H 1 ( b k j ( t Q ) ) , g r t Q ) , (4)

where r t = F ( b k j , t Q ) and j = ( t mod Q ) .

5) UserKeyUpdate ( t , U K t , m d k 0 , I D ) : On input the period t, updated key at time t and a master decryption key with I D { 0,1 } . The algorithm parse:

U K t = ( H 1 t , H 1 t ) and set U T K U t 1 = ( g 3 t , g 4 t ) ,

g 4 t 1 = g 4 t 1 H 1 t , g 3 t 1 = g 3 t 1 H 1 t .

Hence U T K U t = ( g I D 4 t , g I D 3 t ) . Thus, g 3 = g α ( i = 1 Q t ( g H 1 ( b k j ( i ) ) ) r 1 ) and j = ( i mod Q ) , g 4 = ( ( i = 1 Q 0 g r 1 ) β ) , where r 1 = F ( b k j , i ) .

The algorithm parse the current index period secret decryption key as:

m d k I D t = ( h I D t α , h I D t β ) , (5)

where g 3 = h I D α ( t ) and g 4 = h I D β ( t ) .

6) PKITrapdoor ( I D , M S K , t ) : For a given string I D { 0,1 } , MSK and index time t the algorithm computes h I D = H 2 ( I D ) G and set the trapdoor t d I D = h I D β , t d I D is the second element of m d k , where m d k I D t , t d I D and t o k I D are distributed via a secured channel.

7) PKIEncrypt ( K , I D , M 1 ) : To encrypt M 1 with a public identity ID, the algorithm selects two random numbers ( r 1 , r 2 ) Z p . Then it computes:

C T 1 = g r 1 , C T 2 = Q 1 r 1 H 2 ( e ( g 4 , h I D ) r 1 )

where

Q 1 = ( ( i = 1 Q t B K j H 1 ( i ) ) M 1 ) , C T 3 = g r 2 ,

C T 4 = ( M 1 | | r 1 ) H 3 ( C T 1 | | C T 2 | | P | | e ( g 3 , h I D ) r 2 ) .

Finally, it returns

C T = ( C T 1 , C T 2 , C T 3 , C T 4 ) .

where P S ( k 2 , C T 3 ) for signing algorithm S of the employed MAC, the corresponding tag P is used to verify C T 3 . The function F is assumed to be a strong pseudorandom permutation and MAC is existentially unforgeable under chosen message attack.

8) PKIDecrypt ( C T , m d k I D , t o k I D ) : On input the ciphertext CT, updated secret key m d k I D and a token t o k e n = ( k 1 , k 2 ) subsequantly, it computes:

m | | r = C T 4 H 3 ( C T 1 | | C T 2 | | P | | e ( C T 3 , m d k I D t α ) ) ,

m | | r = H 3 ( e ( C T 3 , m d k I D t α ) ) .

Given P S ( k 2 , C T 3 ) where P = M A C k 2 ( C T 3 ) , the algorithm veriifies if: B = M A C k 2 ( C T 3 ) if B = P . Then it checks whether C T 1 = g r 1 and

C T 2 = Q 1 r 1 H 2 ( e ( C T 1 , h I D t β ) ) . Where Q 1 = ( i = 1 Q t B K j H 1 ( i ) ) M 1 .

If both hold, the algorithm returns M 1 , otherwise return .

9) Test ( C T A , t d I D A , C T B , t d I D B ) : On input the ciphertext C T A , trapdoor t d A and a given senders ciphertext C T B . The algorithm test whether M 1 A = M 1 B by computing:

T A = C T 2 A H 2 ( e ( C T 1 A , t d I D A ) ) , T B = C T 2 B H 2 ( e ( C T 1 B , t d I D B ) ) . (6)

The algorithm output 1 if the above corresponding equation holds, it output 0 otherwise.

Correctness:

The requirement for the above definition is shown below:

1) The first point is verifiable and straightforward as shown above.

2) With a well-formed ciphertext for I D A and I D B . Given the following:

T A = C T 2 A H 2 ( C T 1 A , t d I D A ) , T B = C T 2 B H 2 ( C T 1 B , t d I D B )

T A = Q 1 A r 1 A H 2 ( e ( g A r 1 , h I D A β ( t ) ) ) H 2 ( e ( g A r 1 , h I D A β ( t ) ) ) , T B = Q 1 B r 1 B H 2 ( e ( g B r 1 , h I D B β ( t ) ) ) H 2 ( e ( g B r 1 , h I D B β ( t ) ) )

T A = Q 1 A r 1 A and T B = Q 1 B r 1 B .

The algorithm output 1 if the following corresponding equation holds. Otherwise, it output 0.

e ( C T 1 A , T B ) = e ( C T 1 B , T A ) .

Therefore:

( C T 1 A , T B ) = e ( g r 1 A , Q 1 B r 1 B ) = e ( g , Q 1 B ) r 1 A r 1 B

e ( C T 1 B , T A ) = e ( g r 1 B , Q 1 A r 1 A ) = e ( g , Q 1 A ) r 1 A r 1 B .

where

Q 1 A = ( ( i = 1 Q t B K j H 1 ( i ) ) M 1 A ) and Q 1 B = ( ( i = 1 Q t B K j H 1 ( i ) ) M 1 B ) .

Given the token t o k I D = k 1 , the function output M A and M B

If Q 1 A = Q 1 B , then: e ( C T 1 A , T B ) = e ( C T 1 B , T A ) .

Test ( C T A , t d I D A , C T B , t d I D B ) output 1.

3) For any M A M B , Test ( C T A , t d I D A , C T B , t d I D B ) = 1 . This implies that:

e ( g , Q 1 A ) r 1 A = e ( g , Q 1 B ) r 1 B .

Hence,

P r [ e ( g , Q 1 A ) = ( g , Q 1 B ) ] = 1 2 .

Therefore, we assume:

P r [ T e s t ( C T A , t d I D A , C T B , t d I D B ) = 1 ]

is negligible.

6. Security Analysis

The PKI-IBPKE-ET scheme is W-IND-ID-CCA secure using the random oracle model assuming Bilinear Diffie-Helman Problem (BDHP) is negligible.

Proof Theory: It is assumed A is a probabilistic polynomial time (PPT) adversary attacking the W-IND-CCA security of our scheme. Supposedly, A executes in time T and issues hash queries (qH) and decryption queries (qH). Let A d v A W - I N D - C C A ( t , q H , q D ) depicts the benefit of A in W-IND-ID-CCA experiment.

Our proof of security is similar to [3]. The preliminaries of the original game are outlined as follows:

1) Game G0

α Z p * , g 1 = g α , T = N , B K = { b k 0 , , b k Q 1 } , R = .

M 1 G , r 0 Z p * , U 0 * = g r , V 0 * = M 1 r , W 0 * = H ( T , ( b k Q 1 ) , U 0 * , V 0 * , g 1 r ) ( M 1 r ) .

M 1 A o H , o 2 ( T , ( b k Q 1 ) , U 0 * , V 0 * , W 0 * ) , where the oracle works as follows:

O H : On the tuple: ( T , ( b k Q 1 ) , U 0 , V 0 , Y 0 ) G 4 , where a same random value is returned, the same input could be asked multiple times but the same answer will be responded to.

O 2 : On input a ciphertext ( T , ( b k Q 1 ) , U 0 , V 0 , W 0 ) , it returns the decryption algorithm to decrypt it using the secret key α given within an index time N and a helper key Q.

Let X o be the event that M 1 = M 1 in Game G 0 . However the probability in Game G 0 is P r [ S o ] . Hence, we modify Game G 0 and obtain the proceeding game.

2) Game G1

α Z p * , g 1 = g α , T = N , B K = { b k 0 , , b k Q 1 } , R = .

M 1 G , r 0 Z p * , U 0 * = g r , V 0 * = M 1 r , R 0 * [ 0,1 ] p + i , W 0 * = H ( T , ( b k Q 1 ) , U 0 * , V 0 * , g 1 r ) ( M 1 r ) , R 0 = R 0 ( T , ( b k Q 1 ) , U 0 * , V 0 * ( U 0 * ) α , R 0 * ) .

M 1 A O H , O 2 ( g 1 , ( b k Q 1 ) , T , U 0 * , V 0 * , W 0 * ) , where the oracle works as:

O H : On input a triple ( T , ( b k Q 1 ) , U 0 , V 0 , Y 0 ) G 4 where if there is an entry ( T , ( b k Q 1 ) , U 0 , V 0 , Y 0 , h ) in the hash table R, h is returned, otherwise a random value h is selected and returned.

( T , ( b k Q 1 ) , U 0 , V 0 , Y 0 , h ) is added to R.

O 2 : On input a ciphertext ( T , ( b k Q 1 ) , U 0 , V 0 , W 0 ) , a hash query on ( T , b k Q 1 , U 0 , V 0 , U 0 α ) is issued. Assuming the answer is h [ 0,1 ] p + i , then M 1 r is computed as h W , then a validity check on whether U 0 = g r and V 0 = M 1 r is executed. If it fails, is returned: otherwise, M 1 is returned.

The event that Game G 1 occurs is denoted by S 1 . However its observed that G 0 = G 1 , hence we deduce the probability of the random oracle as:

P r [ S 1 ] = P r [ S 0 ] .

We subsequently modify the next game simulation in an indistinguishable way:

3) Game G 2

α Z p * , g 1 = g α , T = N , B K = { b k 0 , , b k Q 1 } , R = .

M 1 G , r 0 Z p * , U 0 * = g r , V 0 * = M 1 r , W 0 * [ 0,1 ] p + i , R * [ 0,1 ] p + i , W 0 * = H ( T , ( b k Q 1 ) , U 0 * , V 0 * , g 1 r ) ( M 1 r ) , R 0 = R 0 ( t , ( b k Q 1 ) , U 0 * , V 0 * ( U 0 * ) α , W 0 * ) .

M 1 A O H , O 2 ( g 1 , T , ( b k Q 1 ) , U 0 * , V 0 * , W 0 * ) .

The oracle response to queries as follows:

O H : Game G 2 is identical to Game G 2 . However if adversary queries for ( U 0 * ,., ( U 0 * ) α ) , then the game is abrogated. ε represents this event.

● This is also the same as Game G 1 , however if adversary ask for decryption of ( U 0 * , V 0 * W 0 ) , where W 0 W 0 * , is returned.

Chosen Ciphertext security (CCA) secure is paramount in this game because W 0 * is a random value in both Games, however the random oracle responds are unique and probabilistic because W 0 * is dependent on U 0 and V 0 * . The probability of occurring is negligible.

We modify the simulation game in index time period with multiple helper or base key indistinguishable way in the proceeding game.

4) Game G3

α Z p * , g 1 = g α , T = N , B K = { b k 0 , , b k Q 1 } , R = , t N .

M 1 G , r 0 Z p * , U 0 * = g r , V 0 * = M 1 r , W 0 * [ 0,1 ] p + i , R 0 = R 0 ( t , ( b k Q 1 ) , U 0 * , V 0 * ( U 0 * ) α , W 0 * ) .

M 1 A O H , O 2 ( g 1 , T , ( b k j ) , U 0 * , V 0 * , W 0 * ) .

O H : Game G 3 is identical to Game G 2 . However if adversary queries for ( U 0 * , T , b k j , U 0 * ,., ( U 0 * ) α ) , then the game is abrogated. Let ε 1 be this event.

● This is also the same as Game G 2 , however if adversary ask for decryption of ( U 0 * , b k j , V 0 * , t ) where b k j b k j , is returned.

The timestamp and the base key ( b k j ) at a period j associated with the ciphertext improve the security of this game. t is a timestamp value associated with the ciphertext in both Games, however the random oracle response are unique and probabilistic because decryption queries are dependent on T , U 0 * , V 0 * and ( b k j ) . The probability of occurring is negligible.

In this game, the challenge ciphertext identically distributed in Game G 2 and G 3 as W 0 * is a chosen random value in both Game G 2 and Game G 3 . The simulation of O 2 is secure since W 0 * is uniquely determined by U 0 * and V 0 * in Game G 2 and U 0 * , V 0 * , T and b k j in Game G 3 . Therefore, if event ε 1 does not occur, Game G 3 is identical to Game G 1 . However, it is observed below that event ε 1 occurs with negligible probability.

We further simulates decryption queries in indistinquishable way from Game G 3 . The decryption queries are separated into two types, which includes:

● Type 1: ( T , U 0 , V 0 , U 0 α ) is queried to O H before a decryption query ( T , U 0 , V 0 , W 0 ) is issued.

In this case, W 0 is determined after ( T , U 0 , V 0 , U 0 α ) is queried to O H . So the decryption oracle is perfectly simulated.

● Type 2: ( U 0 , V 0 , U 0 α ) is not queried to O H when a decryption query ( U 0 , V 0 , W 0 , B K ) was issued. Subsequently, is returned by the decryption oracle. The simulation will fail if ( U 0 , V 0 , W 0 , B K ) is valid. Therefore, this happens with negligible probability.

7. Comparison

The efficiency of algorithms and time consumption of our scheme is compared with: Ma’s [8] scheme, which combined the public key cryptosystem with equality test and identity-based cryptographic primitive: Wu et al.’s [29] scheme, which proposed a scheme to resist the insider attack: and Li et al. [30] scheme. Our scheme unveils a parallel key-insulation cryptosystem with multiple helper to minimize the exposure of the helper keys and decryption keys. The comparative results on the efficiency of our method is shown in Table 1 and communication cost in Table 2. The above comparison shows that our scheme can resist IA with key-insulation, whereas others’ don’t have this ability. In addition, the schemes [8] [29] as well as our scheme implement chosen ciphertext security, which is stronger than chosen plaintext security [16] [30] and other related identity based parallel key-insulated primitive [16] via the random oracle model. To evaluate computation efficiency of these schemes, pairing-based cryptography (PBC) library [31] was used to quantify the time consumption of encryption, decryption and test operations. We examine the computational efficiency in these schemes, the Pairing-Based Cryptography (PBC) Library [30] is used to quantify the time consumption of encryption, decryption and test operations. We use the code of a program in VC++ 6.0 and executed on a computer (Windows 10 Pro, operating system), Capacity of Intel(R) Core (TM) i5-4460 CPU with 3.20 GHZ and 4Gb RAM. The code was executed several times and average time of execution extracted. With respect to the scheme and other pairing-based constructions with a security level of 1024-bit RSA, a supersingular curve z 2 = x 3 + x with an embedded degree of 2 is adopted. Also, q = 2 159 + 2 17 + 1 noted as a 160-bit Solinas prime with p = 12 q r 1 noted as a 512-bit prime. With regards to ECC-based schemes, an equivalent security level of Koblitz elliptic

Table 1. Efficiency comparison of algorithm of variant PKE-ETs.

Legends: In this table, “SCH”: scheme, “Exp1” and “Exp2”: exponent computation in group 1 and group 2, “P”: pairing computation, “PKI”: parallel key-insulated, “IA”: insider attack, “R”: random oracle model, “TD”: trapdoor, “ET”: equality test, “Y”: “Yes” as a supportive remark, “N” refers to “No” as not supportive, “I”: IND, “CA”: CPA, “C”: CCA.

Table 2. Communication cost comparison.

Legends: In this table, P K s i z e ; size of public key, S K s i z e ; size of secret key, C T s i z e ; size of ciphertext, D e l A u t h : authorization, BDH; bilinear Diffie-Hellman, G 0 : group G, Z p 0 ; Z p , ROM: random oracle model. W-IND-ID-CCA refers to weak indistinguishable chosen ciphertext attack against identity, OW-ID-CCA refers to one-way chosen ciphertext attack against identity and IND-ID-CPA refers to indistinguishable chosen plaintext attack against identity.

curve of y = x 3 + a x 2 + b defined on a F 2 163 is used to provide the same security level in the ECC group. The computational units are in millisecond (ms) and bytes respectively. The execution times of each respective algorithm were calculated and Matlab program was used to generate Figure2. The Figure(see Figure2) depicts the computation cost of decryption and test of our scheme comparable with other existing works, whereas our encryption computational cost seems higher. This is reasonable due to the additional computational overheads required to prevent helper keys exposure with the adoption of multiple helpers, which, however, is not the case in other works. In the aspect of the computation cost of decryption and test, our scheme is better than schemes in [29] [30]. Although time consumption of encryption and decryption operations of our scheme is higher than scheme proposed in [29], our scheme provides additional security to helper exposure.

Furthermore, our computational overhead cost results do not make our scheme superior to other related schemes in terms of computational cost analysis. However, this is pardonable due to the fact that additional computational cost values added to our scheme increases the computational variables. In this way, the computational cost in encryption and decryption are higher than the related scheme due to the extra multiple helper computation added to our scheme. However, the test computational cost is comparable to [8], but the other related scheme has a high computational test results. Therefore, our scheme is an improvement on the related public key cryptosystem with key-insulation. However, our scheme adds additional primitives on previous schemes such as equality test and the adoption of multiple helper to improve on the use of single or double helper in protecting decryption keys. In this way, our scheme is secure against the use of single helper in updating users decryption keys in key-insulated cryptosystems. Therefore, the superiority of our scheme is achieved in the lower pairing computations, insider attack resistant with delegated equality test, and a symmetric cryptographic primitive (MAC) addition to public key cryptosystem to construct our scheme.

Figure 2. Computational overhead of related schemes.

8. Conclusion

This paper introduced a scheme to solve the problem caused by private decryption

key exposure and helper key in identity based cryptosystem with equality test. Our scheme delegates equality test to the cloud server and also thwarts the insider attack phenomenon in public key encryption. Inspired by the notion of scheme in [8] and the use of a single helper with key-insulation [32], we put forward parallel key insulated ID-based public key cryptographic primitive with outsourced equality test (PKI-IBPKE-ET). The mechanism of parallel key-insulated with multiple helper was used to reduce the damage to helper keys and private key exposure. Besides, our scheme also has the ability to resist insider attack from semi-trusted cloud server, which makes it practical and suitable in cloud computing. Our scheme is proven secured in random oracle model. Theoretical analysis and experiment simulation both demonstrate that our scheme is secure and efficient.

Acknowledgements

Sincere thanks to the anonymous reviewers for their kind consideration and a special thanks to managing editor Hellen XU for a rare attitude of high quality.

Conflicts of Interest

The authors declare no conflicts of interest regarding the publication of this paper.

References

[1] Cao, X., Li, H., Dang, L. and Lin, Y. (2017) A Two-Party Privacy Preserving Set Intersection Protocol against Malicious Users in Cloud Computing. Computer Standards and Interfaces, 54, 41-45.
https://doi.org/10.1016/j.csi.2016.08.004
[2] Boneh, D. and Franklin, M. (2001) Identity-Based Encryption from the Weil Pairing. In: Annual International Cryptology Conference, Springer, Berlin, 213-229.
https://doi.org/10.1007/3-540-44647-8_13
[3] Yang, G., Tan, C.H., Huang, Q. and Wong, D.S. (2010) Probabilistic Public Key Encryption with Equality Test. In: Cryptographers’ Track at the RSA Conference, Springer, Berlin, 119-131.
https://doi.org/10.1007/978-3-642-11925-5_9
[4] Lipmaa, H. (2003) Verifiable Homomorphic Oblivious Transfer and Private Equality Test. In: International Conference on the Theory and Application of Cryptology and Information Security, Springer, Berlin, 416-433.
https://doi.org/10.1007/978-3-540-40061-5_27
[5] Tang, Q. (2012) Public Key Encryption Schemes Supporting Equality Test with Authorisation of Different Granularity. International Journal of Applied Cryptography, 2, 304-321.
https://doi.org/10.1504/IJACT.2012.048079
[6] Wu, L., Zhang, Y., Choo, K.K.R. and He, D. (2017) Efficient Identity-Based Encryption Scheme with Equality Test in Smart City. IEEE Transactions on Sustainable Computing, 3, 44-55.
https://doi.org/10.1109/TSUSC.2017.2734110
[7] Lee, H.T., Wang, H. and Zhang, K. (2018) Security Analysis and Modification of ID-Based Encryption with Equality Test from ACISP 2017. In: Australasian Conference on Information Security and Privacy, Springer, Cham, 780-786.
https://doi.org/10.1007/978-3-319-93638-3_46
[8] Ma, S. (2016) Identity-Based Encryption with Outsourced Equality Test in Cloud Computing. Information Sciences, 328, 389-402.
https://doi.org/10.1016/j.ins.2015.08.053
[9] Dodis, Y., Katz, J., Xu, S. and Yung, M. (2002) Key-Insulated Public Key Cryptosystems. In: International Conference on the Theory and Applications of Cryptographic Techniques, Springer, Berlin, 65-82.
https://doi.org/10.1007/3-540-46035-7_5
[10] Bellare, M. and Palacio, A. (2006) Protecting against Key-Exposure: Strongly Key-Insulated Encryption with Optimal Threshold. Applicable Algebra in Engineering, Communication and Computing, 16, 379-396.
https://doi.org/10.1007/s00200-005-0183-y
[11] Wang, Y., Yan, D., Li, F. and Xiong, H. (2017) A Key-Insulated Proxy Re-Encryption Scheme for Data Sharing in a Cloud Environment. IJ Network Security, 19, 623-630.
[12] He, L., Yuan, C., Xiong, H. and Qin, Z. (2017) An Efficient and Provably Secure Certificateless Key Insulated Encryption with Applications to Mobile Internet. IJ Network Security, 19, 940-949.
[13] Hanaoka, Y., Hanaoka, G., Shikata, J. and Imai, H. (2005) Identity-Based Hierarchical Strongly Key-Insulated Encryption and Its Application. In: International Conference on the Theory and Application of Cryptology and Information Security, Springer, Berlin, 495-514.
https://doi.org/10.1007/11593447_27
[14] Libert, B., Quisquater, J.J. and Yung, M. (2007) Parallel Key-Insulated Public Key Encryption without Random Oracles. In: International Workshop on Public Key Cryptography, Springer, Berlin, 298-314.
https://doi.org/10.1007/978-3-540-71677-8_20
[15] Hanaoka, G., Hanaoka, Y. and Imai, H. (2006) Parallel Key-Insulated Public Key Encryption. In: International Workshop on Public Key Cryptography, Springer, Berlin, 105-122.
https://doi.org/10.1007/11745853_8
[16] Weng, J., Liu, S., Chen, K. and Ma, C. (2006) Identity-Based Parallel Key-Insulated Encryption without Random Oracles: Security Notions and Construction. In: International Conference on Cryptology in India, Springer, Berlin, 409-423.
https://doi.org/10.1007/11941378_29
[17] Ren, Y. and Gu, D. (2010) CCA2 Secure (Hierarchical) Identity-Based Parallel Key-Insulated Encryption without Random Oracles. Journal of Systems and Software, 83, 153-162.
https://doi.org/10.1016/j.jss.2009.07.046
[18] Ren, Y., Wang, S. and Zhang, X. (2013) Practical Parallel Key-Insulated Encryption with Multiple Helper Keys. Computers and Mathematics with Applications, 65, 1403-1412.
https://doi.org/10.1016/j.camwa.2012.01.032
[19] Boneh, D., Di Crescenzo, G., Ostrovsky, R. and Persiano, G. (2004) Public Key Encryption with Keyword Search. In: International Conference on the Theory and Applications of Cryptographic Techniques, Springer, Berlin, 506-522.
https://doi.org/10.1007/978-3-540-24676-3_30
[20] Xu, P., Jin, H., Wu, Q. and Wang, W. (2012) Public-Key Encryption with Fuzzy Keyword Search: A Provably Secure Scheme under Keyword Guessing Attack. IEEE Transactions on Computers, 62, 2266-2277.
https://doi.org/10.1109/TC.2012.215
[21] Yu, Y., Ni, J., Yang, H., Mu, Y. and Susilo, W. (2014) Efficient Public Key Encryption with Revocable Keyword Search. Security and Communication Networks, 7, 466-472.
https://doi.org/10.1002/sec.790
[22] Qu, H., Yan, Z., Lin, X. J., Zhang, Q. and Sun, L. (2018) Certificateless Public Key Encryption with Equality Test. Information Sciences, 462, 76-92.
https://doi.org/10.1016/j.ins.2018.06.025
[23] Zhang, K., Chen, J., Lee, H.T., Qian, H. and Wang, H. (2019) Efficient Public Key Encryption with Equality Test in the Standard Model. Theoretical Computer Science, 755, 65-80.
https://doi.org/10.1016/j.tcs.2018.06.048
[24] Lin, X.J., Sun, L. and Qu, H. (2018) Generic Construction of Public Key Encryption, Identity-Based Encryption and Signcryption with Equality Test. Information Sciences, 453, 111-126.
https://doi.org/10.1016/j.ins.2018.04.035
[25] Waters, B. (2005) Efficient Identity-Based Encryption without Random Oracles. In: Annual International Conference on the Theory and Applications of Cryptographic Techniques, Springer, Berlin, 114-127.
https://doi.org/10.1007/11426639_7
[26] Alornyo, S., Asante, M., Hu, X. and Mireku, K.K. (2018) Encrypted Traffic Analytic Using Identity Based Encryption with Equality Test for Cloud Computing. 2018 IEEE 7th International Conference on Adaptive Science and Technology, Ghana, 22-24 August 2018, 1-4.
https://doi.org/10.1109/ICASTECH.2018.8507063
[27] Wu, L., Zhang, Y., Choo, K.K.R. and He, D. (2017) Efficient and Secure Identity-Based Encryption Scheme with Equality Test in Cloud Computing. Future Generation Computer Systems, 73, 22-31.
https://doi.org/10.1016/j.future.2017.03.007
[28] Lee, H.T., Ling, S., Seo, J.H. and Wang, H. (2016) Semi-Generic Construction of Public Key Encryption and Identity-Based Encryption with Equality Test. Information Sciences, 373, 419-440.
https://doi.org/10.1016/j.ins.2016.09.013
[29] Wu, T., Ma, S., Mu, Y. and Zeng, S. (2017) ID-Based Encryption with Equality Test against Insider Attack. In: Australasian Conference on Information Security and Privacy, Springer, Cham, 168-183.
https://doi.org/10.1007/978-3-319-60055-0_9
[30] Li, J., Zhang, F. and Wang, Y. (2006) A Strong Identity Based Key-Insulated Cryptosystem. In: International Conference on Embedded and Ubiquitous Computing, Springer, Berlin, 352-361.
https://doi.org/10.1007/11807964_36
[31] Lynn, B. (2013) PBC Library.
https://crypto.stanford.edu/pbc/
[32] Alornyo, S., Zhao, Y., Zhu, G. and Xiong, H. (2020) Identity Based Key-Insulated Encryption with Outsourced Equality Test. IJ Network Security, 22, 257-264.

  
comments powered by Disqus

Copyright © 2020 by authors and Scientific Research Publishing Inc.

Creative Commons License

This work and the related PDF file are licensed under a Creative Commons Attribution 4.0 International License.