1 Introduction
1.1 Problem identification
1.2 Key idea and contribution
-
Compared to computational complexity during the search process, our schemes' is O(1), while other previous papers' is at least O(n).
-
Our experiments represent our scheme is approximately 935 times faster than Golle's scheme and about 16 times faster than Song's scheme for 10,000 documents.
-
By re-encrypting keywords or documents with the group manager (GM)'s secret key k c , we resolved the encrypted database group search problem in cloud service.
-
Whenever every membership change, our schemes can support a secure group search without re-encrypting all documents.
-
We made definitions on group search secrecy and keyword index search privacy and analyzed them.
1.3 Related works
2 Preliminaries
2.1 Keyword index search scheme
2.2 System environments
2.2.1 Multiple user setting
2.2.2 Cloud datacenter service and modified DAS model
2.3 Notations
-
TG: a huge hierarchical group
-
g i : i th small group of G
-
: a small group g i at j th session
-
D n : n th documents
-
W n : keywords list of D n
-
: i th keyword of W n
-
d n : identifier of D n
-
gk i : group session key of a small group g i
-
ik i : index generation key of a small group g i
-
dk i : documents encryption key of a small group g i
-
: group session key of g i at j th session
-
: index generation key of g i at j th session
-
: documents encryption key of g i at j th session
-
k c : GM's secret key
-
f (·): pseudorandom function (PRF)
-
h(·): one-way hash function
2.4 Definitions
-
Property 1 : Anybody can deduce that an earlier value k i belongs to the one-way key chain by using the later value k j of the chain and by checking h j-i (k j ) which equals k i with the later value k j .
-
Property 2 : Given the latest released value k i of a one-way key chain, an adversary cannot find a later value k j such that h j-i (k j ) equals k i . Even when value ki+1is released, the second pre-image collision resistant property prevents an adversary from finding different from ki+1such that h(ki+1) equals k i .
2.5 Algorithm
-
SysPara( 1 k ). It takes an input as a security parameter k and outputs a system parameter λ. λ determines elements in order to set the encrypted database system such as the size of database, encryption/decryption algorithm, functions, the size of parameters, and so on.
-
KeyGen( λ ). Taking λ as an input, this algorithm generates users' group session key set {g k }, index generation key set {ik}, and document encryption key set {dk}.
-
IndGen( ik, W ). Inputs of algorithm IndGen are an index generation key ik and a keyword set W. Output is index list table.
-
DocEnc( dk, D ). Given a document encryption key dk and a document D, this algorithm outputs an encrypted document.
-
TrapGen( w, ik ). This algorithm takes a keyword w and index generation key ik. It encrypts the keyword w with index generation key ik and returns the encryption value, which is the trapdoor T w for the keyword w.
-
Retrieval( T w ). This algorithm takes input as trapdoor T w . If there exist matching values to the trapdoor T w in an index list, then it outputs the encrypted documents that are mapped to the identifiers of the matching values in the index list table.
-
Dec( E(D), dk ). Given a document encryption key dk and encrypted document E(D), it outputs a plaintext document D.
3 Construction Of Practical Keyword Index Search-I (PKIS-I)
3.1 Uploading phase
3.1.1 SysPara(1k) construction
3.1.2 KeyGen(λ) construction
3.1.3 IndGen(ik, W) and DocEnc(dk, D) construction
3.1.4 Database update
Index | Identifier of document |
---|---|
... | ... |
... | ... |
... | ... |
... | ... |
... | ... |
Identifier of documents | Encrypted document |
---|---|
... | ... |
... | ... |
... | ... |
... | ... |
3.2 Downloading phase
3.2.1 TrapGen(w, ik) construction
3.2.2 Retrieval(Tw) and Dec(E(D), dk) construction
4 Construction Of Practical Keyword Index Search--II (PKIS-II)
4.1 Uploading phase
4.1.1 SysPara(1k) construction
4.1.2 KeyGen(λ) construction
4.1.3 IndGen(ik, W) and DocEnc(dk, D) construction
4.1.4 Database update
4.2 Downloading phase
4.2.1 TrapGen(w, ik) construction
4.2.2 Retrieval(Tw) and Dec(E(D), dk) construction
5 Security Analysis
5.1 Group search secrecy
-
○ Group key secrecy: It must be computationally infeasible for a passive adversary to discover any secret group key.
-
○ Forward secrecy: Any passive adversary being in possession of a subset of old group keys must not be able to discover any subsequent group key.
-
○ Backward secrecy: Any passive adversary being in possession of a subset of subsequent group keys must not be able to discover any preceding group key.
-
○ Key independence: Any passive adversary being in possession of any subset of group keys must not be able to discover any other group key.
-
○ Forward secrecy provides security for subtractive events (leave), since it prevents former group members from computing the updated group key. Similarly, backward secrecy provides security for additive events (join), because it prevents new members from discovering the previously used group keys [27].
-
Forward search secrecy : For any group , the probability that a participant can generate valid trapdoors for (j +1)th session is negligible when the participant knows valid group search key , where and 0 < j < q. and fall under in PKIS-I and falls under in PKIS-II.
-
Backward search accessibility : For any group , the probability that a participant can generate valid trapdoors for (j - l)th session is 1 - η (n) when the participant knows valid group search key , where and 0 < l < j. and fall under in PKIS-I and falls under in PKIS-II.
-
Group search secrecy: For a datacenter server DS, when a revelation of group search key happens, the probability that DS can guess correctly the encrypted documents of group g i at the j th session is negligible.
5.1.1 PKIS-I
-
Forward search secrecy: By the Property 2 of Definition 1, if the latest released group search key is , any participant cannot know a later value such that . Therefore, the probability that a participant can generate valid trapdoors for the next (j + 1)th session is negligible, where .
-
Backward search accessibility: By the Property 1 of Definition 1, if the latest released group search key is , any participant can deduce an earlier value by applying the later value to one-way hash key chain like this; . Therefore, the probability that a participant can generate valid trapdoors for (j - l)th session is 1 - η(n), where and 0 < l < j.
-
Group search secrecy: In PKIS-I, GM re-encrypts all documents and indexes including trapdoors with his secret key k c . Although one of group members reveals his/her group search keys to a datacenter server DS, DS cannot learn anything because DS does not know GM's secret key k c . Therefore, the probability that DS can guess correctly the encrypted documents of group g i at the j th session is negligible when is revealed to DS.
5.1.2 PKIS-II
-
Forward search secrecy: If membership changes occur, a new group session key is generated and distributed securely to valid members according to a given protocol, and leaving members cannot get a new group session key. Hence, the leaving member cannot generate the valid trapdoor for a new session because GM decrypts a trapdoor with the group's newly updated session key.
-
Backward search accessibility: For joining members, a new group session key is generated and distributed securely to valid members according to a given protocol, and the new joiners can also retrieve all of the previous documents because group search keys ik and dk are unchangeable in PKIS-II. If a joiner is authenticated as a valid user with his/her group session key, GM queries DS with a trapdoor instead of the user. The trapdoor is encrypted by unchangeable index generation key ik.
-
Group search secrecy: Members of a group cannot know their group search keys ik and dk in PKIS-II and only GM knows them. Even if a leaving member or another malicious member reveals his group session key gk to DS, DS cannot know the contents of the documents or trapdoor because they are encrypted with the group search keys ik and dk that group members do not know. Therefore, the probability that a datacenter server DS can guess correctly the encrypted data of a group g i at the j th session is negligible when is revealed to DS.
5.2 Keyword index search privacy
5.2.1 Retrieval access control
-
User access control.
-
Server search control.
5.2.2 Unobservability
5.2.3 Unlinkability--index indistinguishability
6 Experiments Of Performance
6.1 Setting of experiments
Agent | Processor | Intel Pentium 4 CPU 2.66 GHz |
---|---|---|
RAM | 512 MB | |
Language | C++ | |
Crypto. Eng. | OpenSSL Crypto Library(AES-CBC-128) | |
Database | Product | MS SQL Server 2000 |
Interface | WinAPI | |
Library | MS-SQL DB Library for C | |
Cryptographic | PRF | AES (128 bits) |
Parameter | Hash function | SHA-1 (160 bits) |
The number of keywords | 7 | |
Dataset | The number of common keywords | ≥ 435 |
The number of documents | 2500 = 5000 = 7500 = 10000 | |
The number of sessions | 1 = 10 = 100 = 1000 |
6.2 Analysis on PKIS-I and PKIS-II
Scheme | PKIS-I | PKIS-II | |||
---|---|---|---|---|---|
No. of sessions | 1 | 10 | 100 | 1000 | |
2500 documents | 5.8 | 8.0 | 9.9 | 38.6 | 6.8 |
5000 documents | 6.9 | 10.3 | 13.9 | 42.6 | 7.8 |
7500 documents | 7.4 | 13.9 | 16.3 | 49.3 | 8.4 |
10000 documents | 7.9 | 13.9 | 18.3 | 52.7 | 8.8 |
6.3 Comparison of our scheme with other schemes
6.3.1 The results of implementation
Song | Golle | Waters | SSS-I | SSS-II | PKIS-II | PKIS-IIP | |
---|---|---|---|---|---|---|---|
2500 documents | 47 | 2094 | 79 | 270 | 1721 | 6.8 | 2.8 |
5000documents | 62 | 4439 | 157 | 536 | 3269 | 7.8 | 3.8 |
7500documents | 109 | 6991 | 204 | 814 | 5088 | 8.4 | 4.3 |
10000documents | 147 | 8229 | 297 | 969 | 6756 | 8.8 | 4.8 |