Parallel Key Insulated ID-Based Public Key Cryptographic Primitive with Outsourced Equality Test ()
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
satisfies the following properties:
1) Bilinearity: For any
, a and
,
.
2) Non-Degenerate:
.
3) Computable: There is an efficient algorithm to compute
for any
.
3.2. Bilinear Diffie-Hellman (BDH) Problem
Let G and GT be two groups of prime order p. Let
be an admissible bilinear map and let g be a generator of G. The BDH problem in
is as follows: Given
for random
for any randomized algorithm A computes value
with advantage:
(1)
The BDH assumption holds if for all polynomial-time algorithm A, its advantage
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:
1) Setup
: It input a secured parameter
, total time period N, numbr of helper keys Q and returns the public parameter K, helper keys
and the temporal master key MSK.
2) Extract
: On input MSK, arbitrary
, system parameter K and returns a secret key
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
: The user generation algorithm on input the received secret key
, public paramter K, time period N and ID. The algorithm output helper key
.
4) BaseKeyUpdate
: On input the helper key
at a span
and index time span t. The algorithm output update key
.
5) UserKeyUpdate
: On input
, index t of the next span and update key
. It output the secret key
for the next span t corresponding to the user ID.
6) PKIEncrypt
: It input K, the index span t of the current time period, an identity
and plaintext
, and return the ciphertext
as
, where
.
7) PKIDecryption
: It takes a current private secret key
and ciphertext
as input and return plaintext
or a symbol
if the corresponding ciphertext is valid.
8) Test
: It takes ciphertext
and
outputted by user A and user B respectively. It output 1 if the corresponding message cooresponding to
and
are equal. It output 0, otherwise
.
Correctness:
1) When
the updated secret decryption key is generated with multiple helper. The BaseKeyUpdate algorithm on input ID as the public key, then;
,
where
and
.
2) Supposedly,
and
are trapdoors generated by the trapdoor algorithm given
and
as the public keys, then;
,
where
and
.
3) The
and
are supposedly trapdoors generated by the trapdoor algorithm given
and
as the public keys, then:
and
.
is negligible where
and
.
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
: The challenger runs the extract algorithm to generate the private decryption key
corresponding to the user with public key
. It forwards
to A.
3) Trapdoor Queries
: The challenger executes the above private decryption key queries on
to obtain
and subsequently generate the trapdoor
using
via trapdoor algorithm. Finally, the algorithm forwards
to A.
4) Decryption Queries
: The challenger executes decryption algorithm to decrypt the ciphertext
by executing extract algorithm to obtain the private secret key
relating to the public key
. Finally, it forwards plaintext
to A.
5) Challenge: A submits an identity
to which a challenge will be posed. The only constraints is that
was not seen in private decryption key queries in phase 1 but
may show in trapdoor queries in phase 1 or in decryption query
. The challenger then randomly chooses plaintext
and sets
. Finally, it forwards
to A as its challenge ciphertext.
6) Phase 2-Private decryption key queries
: Whereby
. The challenger respond similar to that of phase 1.
7) Trapdoor Queries
: The challenger then responds similar to phase 1.
8) Decryption Queries
: The challenger respond similar to phase 1.
9) Guess: A submits a guess
The scheme is W-ID-CCA secure if for all W-IND-CCA adversaries,
(2)
is negligible.
5. Construction
The detailed construction for the PKI-IBPKE-ET in this section includes:
1) Setup:
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
.
● The system generates two multiplicative groups G and GT with the same prime order p of
length bits and a bilinear map
. The system selects an arbitrary generator
.
● The algorithm exploits a keyed permutation
for a positive integers
and
. Set a random value
from
. Generate a MAC scheme
, where G is generate, S is sign and V verify. It obtain
by running
. Set the master token key
.
● The system chooses three hash functions:
,
,
where l is the length of random numbers, whereas p is the message length. The algorithm randomly picks
and set
,
. It publishes public parameter
and
. T is referred to as MAC tag.
2) Extract
: For a given string
, public parameter K and MSK. The algorithm compute
, set temporal master decryption key
where
are the master secret key and the intial time index period at t.
3) UserKeyGeneration
: On input
, the algorithm randomly chooses
and set:
(3)
where
and
.
The function F is assumed as a pseudorandom permutation.
The initial secret helper keys
and number of helper set to
.
4) BaseKeyUpdate
: On input helper key at
and a period index t. The helper key updater computes the jth helper base as:
(4)
where
and
.
5) UserKeyUpdate
: On input the period t, updated key at time t and a master decryption key with
. The algorithm parse:
and set
,
,
.
Hence
. Thus,
and
,
, where
.
The algorithm parse the current index period secret decryption key as:
(5)
where
and
.
6) PKITrapdoor
: For a given string
, MSK and index time t the algorithm computes
and set the trapdoor
,
is the second element of
, where
,
and
are distributed via a secured channel.
7) PKIEncrypt
: To encrypt
with a public identity ID, the algorithm selects two random numbers
. Then it computes:
,
where
,
,
.
Finally, it returns
.
where
for signing algorithm S of the employed MAC, the corresponding tag P is used to verify
. The function F is assumed to be a strong pseudorandom permutation and MAC is existentially unforgeable under chosen message attack.
8) PKIDecrypt
: On input the ciphertext CT, updated secret key
and a token
subsequantly, it computes:
,
.
Given
where
, the algorithm veriifies if:
if
. Then it checks whether
and
. Where
.
If both hold, the algorithm returns
, otherwise return
.
9) Test
: On input the ciphertext
, trapdoor
and a given senders ciphertext
. The algorithm test whether
by computing:
(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
and
. Given the following:
,
,
and
.
The algorithm output 1 if the following corresponding equation holds. Otherwise, it output 0.
.
Therefore:
.
where
and
.
Given the token
, the function output
and
If
, then:
.
Test
output 1.
3) For any
, Test
. This implies that:
.
Hence,
.
Therefore, we assume:
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
is a probabilistic polynomial time (PPT) adversary attacking the W-IND-CCA security of our scheme. Supposedly,
executes in time T and issues hash queries (qH) and decryption queries (qH). Let
depicts the benefit of
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
●
,
,
,
,
.
●
,
,
,
,
.
●
, where the oracle works as follows:
●
: On the tuple:
, where a same random value is returned, the same input could be asked multiple times but the same answer will be responded to.
●
: On input a ciphertext
, it returns the decryption algorithm to decrypt it using the secret key
given within an index time N and a helper key Q.
Let
be the event that
in Game
. However the probability in Game
is
. Hence, we modify Game
and obtain the proceeding game.
2) Game G1
●
,
,
,
,
.
●
,
,
,
,
,
,
.
●
, where the oracle works as:
●
: On input a triple
where if there is an entry
in the hash table R, h is returned, otherwise a random value h is selected and returned.
is added to R.
●
: On input a ciphertext
, a hash query on
is issued. Assuming the answer is
, then
is computed as
, then a validity check on whether
and
is executed. If it fails,
is returned: otherwise,
is returned.
The event that Game
occurs is denoted by
. However its observed that
, hence we deduce the probability of the random oracle as:
.
We subsequently modify the next game simulation in an indistinguishable way:
3) Game
●
,
,
,
,
.
●
,
,
,
,
,
,
,
.
●
.
The oracle response to queries as follows:
●
: Game
is identical to Game
. However if adversary queries for
, then the game is abrogated.
represents this event.
● This is also the same as Game
, however if adversary ask for decryption of
, where
,
is returned.
Chosen Ciphertext security (CCA) secure is paramount in this game because
is a random value in both Games, however the random oracle responds are unique and probabilistic because
is dependent on
and
. 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
●
,
,
,
,
,
.
●
,
,
,
,
,
.
●
.
●
: Game
is identical to Game
. However if adversary queries for
, then the game is abrogated. Let
be this event.
● This is also the same as Game
, however if adversary ask for decryption of
where
,
is returned.
The timestamp and the base key
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
and
. The probability of
occurring is negligible.
In this game, the challenge ciphertext identically distributed in Game
and
as
is a chosen random value in both Game
and Game
. The simulation of
is secure since
is uniquely determined by
and
in Game
and
,
, T and
in Game
. Therefore, if event
does not occur, Game
is identical to Game
. However, it is observed below that event
occurs with negligible probability.
We further simulates decryption queries in indistinquishable way from Game
. The decryption queries are separated into two types, which includes:
● Type 1:
is queried to
before a decryption query
is issued.
In this case,
is determined after
is queried to
. So the decryption oracle is perfectly simulated.
● Type 2:
is not queried to
when a decryption query
was issued. Subsequently,
is returned by the decryption oracle. The simulation will fail if
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
with an embedded degree of 2 is adopted. Also,
noted as a 160-bit Solinas prime with
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,
; size of public key,
; size of secret key,
; size of ciphertext,
: authorization, BDH; bilinear Diffie-Hellman,
: group G,
;
, 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
defined on a
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.