We will analyze the correctness and security of the CLVPFC-PEKS scheme in this section.
6.2. Security
Lemma 1. Assuming that adversary can triumph in Game 1, then it is feasible to devise algorithm B, aimed at resolving the ECDDDH problem.
Proof. Let us hypothesize that the tuple constitutes an instance of the ECDDDH problem. In order to ascertain whether , algorithm B will assume the role of the challenger.
Setup: B executes the setup procedure to obtain public parameters along with and . B then forwards the parameter to while kee** secret. B selects , randomly and sets
, ,, and .
B sends , , and to , but and are unknown to .
Phase 1: Prior to conducting other queries, execute the user’s public key query utilizing the identity . Set up multiple lists to record the queries and corresponding responses. Each list starts off empty.
For a user public key query, B keeps a list of the tuple and, upon receiving an identity , performs the following steps.
Case 1. . , setting , and adding the tuple to the list , where ⟡ represents a null value.
Case 2. . B randomly chooses two different numbers , setting , and adds the tuple to the list .
Replace-Public-Key query: B keeps a list of tuple . When inputs , B replaces with and adds to the list .
Secret-Value query: When receives the request for the secret value associated with , B finds in the list and returns . If is replaced, B refuses to answer.
Partial-Private-Key query: B establishes a list of tuple when asks for the partial private key of . If , B fails and stops. Otherwise, B finds in the list , and runs the Extract-Partial-Private-Key algorithm, generating . B outputs and adds to the list .
Keyword Ciphertext Query: When asks for the keyword ciphertext, B operates the algorithm to generate keyword ciphertext .
Keyword Trapdoor Query: When asks for the trapdoor, B operates the algorithm to generate the trapdoor .
Test Query: gives the keyword ciphertext and keyword trapdoor , and B compares them using Algorithm 1.
Challenge: submits a tuple to B, where and are challenging keywords not requested in the previous trapdoor and keyword ciphertext query. If , B aborts. Otherwise, , B calculates and picks randomly. B computes
Let , which can obtain by combining similar terms. Then, B selects and computes . Set , . Thus, the corresponding keyword ciphertext of is . B returns the challenge ciphertexts to the adversary .
Phase 2: can continue to execute various queries, but there is a limitation that is not allowed to query the keyword ciphertext or trapdoor of or .
Guess: returns .
Solve CDH problem: If , B returns 1, otherwise 0. If , then
Therefore, is a valid keyword ciphertext. Suppose that the advantage of winning in the above game is . So,
.
If , then is an invalid keyword ciphertext. has no advantage in distinguishing from . Hence,
.
Probability: Let , and be the number of the user public key query, Replace-Public-Key query, and the Partial-Private-Key query, respectively. The two events are as follows:
: did not replace ’s public key and queried the partial-private-key for .
: .
It is not hard to obtain the following results.
,
, .
If wins Game 1 with an advantage of , then B has a probability greater than to determine whether . □
Lemma 2. Assuming that adversary can win Game 2, algorithm B can constructed to solve the ECDDDH problem by exploiting the adversary’s ability.
Proof. Suppose that the tuple is an example of an ECDDDH problem. To determine whether , B will play the part of the challenger.
Setup: B runs the setup program to obtain public parameters and . B selects , randomly, and sets
, ,, ,
B sends , , and to , while are unknown to .
Phase 1: Execute the user’s public key query before other queries using the identity . Set up multiple lists to store the queries and answers. All lists are initially empty.
User public key query: B maintains a list containing the tuple and takes the following actions when receiving an identity :
Case 1. . B chooses a number at random, sets , and adds the tuple to the list , where ⟡ represents a null value.
Case 2. . B chooses at random, sets , and adds the tuple to the list .
Replace-Public-Key query: Same as in Lemma 1.
Secret-Value query: B established a list of tuple . When asks the secret value for . If , B fails and stops. Otherwise, B finds in list , and returns .
Partial-Private-Key query: When asks the partial private key of , B finds in list , running the Extract-Partial-Private-Key algorithm and returning . If is replaced, B refuses to answer.
Keyword Ciphertext Query: Same as in Lemma 1.
Keyword Trapdoor Query: Same as in Lemma 1.
Test Query: Same as in Lemma 1.
Challenge: submits a tuple that meets the requirements of Game 2, where and are challenging keywords not asked in the previous trapdoor query and keyword ciphertext query. If , B aborts. Otherwise, , B computes , and picks randomly. B computes
.
Let , which can obtain by combining similar terms. Then, select at random and compute . Set , , and thus ’s keyword ciphertext is . B returns the challenge ciphertexts to the adversary .
Phase 2: Attacker can continue to execute various queries, but there is a limitation that attacker is not allowed to query the keyword ciphertext or trapdoor of or .
Guess: returns .
Solve the ECDDDH problem. If , B returns 1. Otherwise, 0. If , then
Therefore, is a valid keyword ciphertext. Suppose that the advantage of wins in the above game is , so
.
If , then is an invalid keyword ciphertext. has no advantage in distinguishing from . Hence,
.
Probability: Let , , be the number of user public key queries, Replace-Public-Key queries, and Secret-Value queries, respectively. The two events are as follows:
: did not replace ’s public key nor perform the Secret-Value query for .
: .
It is not hard to obtain the following results.
,
,
.
If has an advantage to win the game, then B has a probability greater than to determine whether . □
Theorem 2. Our CLVPFC-PEKS scheme is CKCA-CIND secure in a standard model if the ECDDDH problem is hard.
Proof. Theorem 2 holds from Lemma 1 and Lemma 2. □
Lemma 3. Assuming the adversary can win Game 3, then algorithm B can be constructed to solve the ECDDDH problem.
Proof. Suppose that the tuple is an example of an ECDDDH problem. To determine whether , B will play the part of the challenger.
Setup: B runs the setup program to obtain the public parameters , where and . Then, B randomly selects , and sets
, , ,
,
.
B sends , and to , but and are unknown to .
Phase 1: Execute the user’s public key query before other queries using the identity . Set up multiple lists to store the queries and answers. All lists are initially empty.
User public key query: B keeps a list of the tuple , and upon receiving an identity , performs the following steps.
Case 1. , B randomly chooses a number , setting , and adds the tuple to the list , where ⟡ represents a null value.
Case 2. , B randomly chooses two different numbers , setting , and adds the tuple to the list .
Replace-Public-Key query: Same as in Lemma 1.
Secret-Value query: Same as in Lemma 1.
Partial-Private-Key query: B establishes a list of tuple when asks for the partial private key of . If , B fails and stops. Otherwise, B finds in the list , and runs the Extract-Partial-Private-Key algorithm, generating . B outputs and adds to the list .
Keyword Ciphertext Query: Same as in Lemma 1.
Keyword Trapdoor Query: Same as in Lemma 1.
Test Query: Same as in Lemma 1.
Challenge: submits a tuple , where and are challenging keywords that are not requested in the previous trapdoor and keyword ciphertext query. If , B aborts. Otherwise, . Without losing generality, it is better to set as . B calculates . B picks randomly, and computes
B selects an element and sets ,
, where . Finally, B sends to the adversary .
Phase 2: Attacker can continue to execute various queries, but there is a limitation that attacker is not allowed to query the keyword ciphertext or trapdoor of or .
Guess: returns .
Solve CDH problem: If , B returns 1, otherwise 0. If , then
.
Therefore, is a valid keyword ciphertext. Suppose that the advantage of winning in the above game is . So,
.
If , then is an invalid trapdoor. has no advantage in distinguishing from . Hence,
.
Probability: Let , , and be the number of the User public key queries, Replace-Public-Key queries, and Partial-Private-Key queries, respectively. The two events are as follows:
: did not replace ’s public key and queries the partial-private-key for .
: .
It is not hard to obtain the following results.
,
,
.
If wins Game 1 with an advantage of , then B has a probability greater than to determine whether . □
Lemma 4. Assuming that adversary can win Game 4, then algorithm B can be constructed to solve the ECDDDH problem.
Proof. Suppose that the tuple is an example of an ECDDDH problem. To determine whether , B will play the part of the challenger.
Setup: B runs the setup program to obtain the public parameters , where and . Then, it randomly selects , and sets
, , ,
,
B sends , , and to , while are unknown to .
Phase 1: Execute the user’s public key query before other queries using the identity . Set up multiple lists to store the queries and answers. All lists are initially empty.
User public key query: B keeps a list of the tuple , and upon receiving an identity , performs the following steps.
Case 1. , B randomly chooses a number , setting , and adds the tuple to the list , where ⟡ represents a null value.
Case 2. , B randomly chooses two different numbers, , setting , and adds the tuple to the list .
Replace-Public-Key query: Same as in Lemma 1.
Secret-Value query: B establishes a list of tuple . When asks the secret value of , if , B fails and stops. Otherwise, B finds in the list , and returns . If is replaced, B refuses to answer.
Partial-Private-Key query: Same as in Lemma 2.
Keyword Ciphertext Query: Same as in Lemma 1.
Keyword Trapdoor Query: Same as in Lemma 1.
Test Query: Same as in Lemma 1.
Challenge: submits a tuple , where and are challenging keywords not requested in the previous trapdoor and keyword ciphertext query. If , B aborts. Otherwise, without losing generality, it is better to set as . B calculates . B picks randomly, and computes
B selects an element and sets ,
, where . Finally, B sends to adversary .
Phase 2: Attacker can continue to execute various queries, but there is a limitation that attacker is not allowed to query the keyword ciphertext or trapdoor of or .
Guess: returns .
Solve CDH problem: If , B returns 1, otherwise 0. If , then
.
Therefore, is a valid keyword ciphertext. Suppose that the advantage of winning the above game is . So,
.
If , then is an invalid keyword ciphertext. has no advantage in distinguishing from . Hence,
.
Probability: Let , , and be the number of user public key queries, Replace-Public-Key queries, and Secret-Value queries, respectively. The two events are as follows:
: did not replace ’s public key and queries the secret value for .
: .
It is not hard to obtain the following results.
,
,
.
If wins Game 4 with an advantage of , then B has a probability greater than to determine whether . □
Theorem 3. Our CLVPFC-PEKS scheme is CKA-TIND safe in the standard model if the ECDDDH problem is hard.
Proof. Theorem 3 holds from Lemma 3 and Lemma 4. □
Theorem 4. Under the ECDLP assumption, it is not computationally feasible for the CSS to forge valid proof information through the result verification mechanism.
Proof. The malicious CSS cannot forge a valid multi-signature on each returned record and pass the verification. Since it does not have the key of multiple data owners, it is computationally infeasible to forge a valid multi-signature. Therefore, the malicious CSS can only win the next security game by directly generating valid proof information according to the wrong search result instead of winning the next security game by forging multiple signatures. But, after the following analysis, this is also impossible.
Assume that the correct keyword ciphertext and its identity are and , where . The malicious CSS may forge wrong proof information on false search results , where
,
.
If the forged proof information
can successfully pass the result verification mechanism, the malicious CSS will win the security game; otherwise, it will fail. Suppose a malicious CSS wins the game. We then know that
The proof information of the correct keyword ciphertext C is , where
,
.
The signature of the correct keyword ciphertext can pass the verification mechanism, so we have
Subtract equation (
2) from equation (
3) to obtain
Because is not equal to , then or . Set , , then or . Suppose is not zero, then . If the probability of is , then the probability that we can break the ECDLP problem is , where q is the length of . This means that if the malicious CSS can pass the verification, we can break the ECDLP problem. □