Searchable EncryptionSE加密搜索課件

1、Searchable EncryptionSchool of Computing Science & EngineeringOutline Motivations Solution space General model for SE Architectures for SE Research challenge SummaryMotivationsWith the development of cloud computing, DAS (Database as a Service) is widely deployed.Untrusted the third-party.SolutionsA

2、pproaches based on new encryption techniques; (2) Information hiding based approaches: store additional auxiliary information along with encrypted data in form of indices. General model for SEsingle writer/single reader (S/S) In S/S scheme, the secret key owner is allowed to create searchable conten

3、t and to generate trapdoors to search.multiwriter/single reader (M/S) Multiple users ( in possession of the public key) can generate searchable ciphertexts, which can be searched by the private key holder.single writer/multireader (S/M) In S/M scheme, the secret key owner is allowed to create search

4、able content, whereas a user-defined group is allowed to generate trapdoors.multiwriter/multireader (M/M) Each user has its own unique key to encrypt, search, and decrypt data , and it requires a trusted key management server.SE architecturesS/S scheme Basic idea: The idea is to encrypt each word se

5、parately and then embed a hash value (with a special format) inside the ciphertext. To search, the server can extract this hash value and check if the value is of this special form (which indicates a match).S/S scheme (Cont.)Encryption processTo searchS/S scheme (Cont.) Efficiency: The encryption an

6、d search algorithm is linear in the total number of words per document. To encrypt, one encryption, one XOR, and two pseudo-random functions have to be computed per word per document. The search requires one XOR and one pseudo-random functions per word per document. Security: The scheme uses no form

7、al security definition. After several queries, it is possible to learn the words inside the documents with statistical analysis.S/M scheme Basic idea: This kind of scheme uses Bloom filter with group ciphers. The schemes use another entity (third party), a so-called query router that protects the id

8、entity of the clients and checks their authorization on behalf of the server. Thus, the scheme allows one to search other users data anonymously.M/S scheme Basic idea: The idea is to use identity-based encryption, in which the keyword acts as the identity. Due to the use of PKE, each user is allowed

9、 to create searchable content with the recipients public key. To search, only the private key holder is able to generate a trapdoor to search inside the encrypted data.M/S scheme (Cont.) (1) The sender encrypts his or her message with a standard public key system and appends the PEKS of each keyword

10、. (2) The receiver uses the master secret key to derive a secret key for a specific keyword it wants to search for. The resulting secret key is used as the trapdoor and sent to the server.M/S scheme (Cont.) Efficiency: The encryption requires the server to perform one pairing computation, two expone

11、ntiations, and two hashes per keyword. The search complexity is linear (one map, one hash) in the number of keywords per document. Security: It requires a secure channel to transmit the trapdoors, so that an eavesdropper cannot get hold of a trapdoor. The trapdoor for a keyword are never refreshed,

12、so it is vulnerable to an off-line keyword-guessing attack.M/M schemeUsing deterministic encryption: a deterministic hash of the keyword is appended to the encryption of the keyword.Proxy re-encryption: ciphertexts from different users can be transformed to ciphertexts under the server key, which al

13、low multiple users to create searchable encrypted content.Bilinear map: Using a bilinear map to make sure that users using different query keys still generate the same index for a keyword.Homomorphic encryption (HE) HE is a special type of encryption that allows one to perform an algebraic operation

14、 on ciphertexts without decrypting them. The major issue when using somewhat or fully HE as is that the resulting search schemes require a search time linear in the length of the dataset. This is too slow for practical application.Research ChallengesEfficiency: Efficiency is measured by the computat

15、ional and communication complexity of the scheme.Security: Different security models.Query expressiveness: What kind of search queries are supported.Current literatures focus on searching in encrypted data, not querying over encrypted data. Tradeoffs of SESecurity versus efficiencySecurity versus qu

16、ery expressivenessEfficiency versus query expressiveness In current approaches, it is often the case that more expressive queries result in either less efficiency or less security.SummaryUsing indices: Instead of searching in the encrypted data itself, the actual search is performed in an added index.Using trapdoor encryption: A possible goal of trapdoor encryption is to allow a user to search for a particular keyword, without giving him the opportunity to find any other keyword.Summary (Cont.)Using secret sharing: The data is queried by us