Method and system for searching encrypted data
The present teaching relates to searching encrypted data. In one example, a search request is received for encrypted documents. An encrypted query is generated based on the search request. The encrypted query is sent to a server that stores a first encrypted index and a second encrypted index. The first encrypted index maps encrypted keywords to full blocks each of which has a same size and is fully filled with encrypted document identities (IDs). The second encrypted index maps encrypted keywords to partial blocks each of which has the same size and is partially filled with encrypted document IDs. Based on the encrypted query, one or more encrypted document IDs are determined by searching against both the first encrypted index and the second encrypted index. A search result is generated based on the one or more encrypted document IDs. The search result is provided in response to the search request.
1. A method, implemented on a machine having at least one processor, storage, and a communication platform connected to a network for updating an index, the method comprising:
receiving a document;
determining an encrypted keyword based on the document;
updating, based on the encrypted keyword, a partial block in a path of an encrypted index;
padding the partial block with one or more dummy document identifiers (IDs);
encrypting the partial block comprising the one or more dummy document IDs to generate an encrypted partial block; and
providing the encrypted partial block to a server to be inserted within the encrypted index based on the path.
2. The method of claim 1 , wherein an index location inside the path of the encrypted index is determined and the partial block is read from the index location such that the encrypted partial block is inserted within the encrypted index based on the index location.
3. The method of claim 2 , further comprising:
receiving the encrypted partial block from the server; and
adding the path to a list of paths associated with deferred reads.
4. The method of claim 3 , further comprising:
determining that an event associated with an update to the encrypted partial block occurred;
re-mapping the encrypted partial block based on the list of paths associated with deferred reads in response to the event; and
providing the re-mapped encrypted partial block to the server.
5. The method of claim 3 , wherein providing further comprises:
shuffling partial blocks in the path of the encrypted partial block to be written to the encrypted index; and
shuffling blocks in other paths included within the list of paths.
6. The method of claim 1 , wherein the encrypted index is built based on an encrypted oblivious Random Access Memory (RAM).
7. The method of claim 1 , wherein shuffling included by a read of the encrypted partial block is deferred to a beginning of an update.
8. A machine-readable tangible and non-transitory medium having information for updating an index, wherein the information, when read by the machine, causes the machine to:
receive a document;
determine an encrypted keyword based on the document;
update, based on the encrypted keyword, a partial block in a path of an encrypted index;
pad the partial block with one or more dummy document identifiers (IDs);
encrypt the partial block comprising the one or more dummy document IDs to generate an encrypted partial block; and
provide the encrypted partial block to a server to be inserted within the encrypted index based on the path.
9. The medium of claim 8 , wherein an index location inside the path of the encrypted index is determined and the partial block is read from the index location such that the encrypted partial block is inserted within the encrypted index based on the index location.
10. The medium of claim 9 , wherein the information, when read by the machine, further causes the machine to:
receive the encrypted partial block from the server; and
add the path to a list of paths associated with deferred reads.
11. The medium of claim 10 , wherein the information, when read by the machine, further causes the machine to:
determine that an event associated with an update to the encrypted partial block occurred;
re-map the encrypted partial block based on the list of paths associated with deferred reads in response to the event; and
provide the re-mapped encrypted partial block to the server.
12. The medium of claim 10 , wherein the information associated with encrypted partial block being provided to the server, when read by the machine, further causes the machine to:
shuffle partial blocks in the path of the encrypted partial block to be written to the encrypted index; and
shuffle blocks in other paths included within the list of paths.
13. The medium of claim 8 , wherein the encrypted index is built based on an encrypted oblivious Random Access Memory (RAM).
14. The medium of claim 8 , wherein shuffling included by a read of the encrypted partial block is deferred to a beginning of an update.
15. A system for updating an index, comprising:
a keyword extractor, implemented by one or more processors, configured to receive a document;
an updated keyword identifier, implemented by one or more processors, configured to determine an encrypted keyword based on the document and update, based on the encrypted keyword, a partial block in a path of an encrypted index; and
a partial block writer, implemented by one or more processors, configured to:
pad the partial block with one or more dummy document identifiers (IDs);
encrypt the partial block comprising the one or more dummy document IDs to generate an encrypted partial block; and
provide the encrypted partial block to a server to be inserted within the encrypted index based on the path.
16. The system of claim 15 , wherein an index location inside the path of the encrypted index is determined and the partial block is read from the index location such that the encrypted partial block is inserted within the encrypted index based on the index location.
17. The system of claim 16 , further comprising:
a server-side block reader, implemented by one or more processors, configured to:
receive the encrypted partial block from the server; and
add the path to a list of paths associated with deferred reads.
18. The system of claim 17 , wherein:
an event associated with an update to the encrypted partial block occurred is determined;
the encrypted partial block based on the list of paths associated with deferred reads in response to the event is re-mapped; and
the re-mapped encrypted partial block is provided to the server.
19. The system of claim 17 , wherein:
partial blocks in the path of the encrypted partial block to be written to the encrypted index are shuffled; and
blocks in other paths included within the list of paths are shuffled.
20. The system of claim 15 , wherein:
the encrypted index is built based on an encrypted oblivious Random Access Memory (RAM); and
shuffling included by a read of the encrypted partial block is deferred to a beginning of an update.