SECURE PRIVATE DATABASE QUERYING SYSTEM WITH CONTENT HIDING BLOOM FITERS

• US 20140108435A1
• Filed: 09/28/2012
• Published: 04/17/2014
• Est. Priority Date: 09/28/2012
• Status: Active Grant

• Current Assignee: Alcatel-Lucent SA (Nokia Corporation)
• Original Assignee: Alcatel-Lucent SA (Nokia Corporation)
• Inventors: Kolesnikov, Vladimir Y.
• Granted Patent: US 9,535,658 B2
• Time in Patent Office: Days
• US Class Current: 707/754
• CPC Class Codes: G06F 16/245 Query processing
• CPC Class Codes: G06F 21/6227 where protection concerns the structure of data, e.g. records, types, queries
• CPC Class Codes: G06F 7/24 Sorting, i.e. extracting data from one or more carriers, rearranging the data in numerical or other ordered sequence, and rerecording the sorted data on the original carrier or on a different carrier or set of carriers sorting methods in generalG06F7/36 takes precedence
• CPC Class Codes: H04L 2209/42 Anonymization, e.g. involving pseudonyms
• CPC Class Codes: H04L 9/008 involving homomorphic encryption
• CPC Class Codes: H04L 9/0894 Escrow, recovery or storing of secret information, e.g. secret key escrow or cryptographic key storage

Abstract

Secure private database querying on a database for a query having a formula evaluation on at least two keywords A and B comprises: a server receiving a Bloom filter tree comprised of encrypted Bloom filters of encrypted keywords from the database, wherein each Bloom filter in the Bloom filter tree is separately masked by a random mask pad P; receiving an encrypted version of the keywords A and B from the client; and obtaining masked Bloom filter indices for the keywords A and B. The client and server participate in secure function evaluation (SFE) with the client. The server has an input comprising the masked Bloom filter indices for the keywords A and B and the client has an input comprising the random mask pad P. The secure function evaluation comprises: removing the random mask pad P from the masked Bloom filter indices input by the server; determining if there is a matching Bloom filter for each of the keywords A and B; and applying the formula evaluation to determine if the formula is satisfied.

Claims

1. A method performed by a server for secure private database querying by a client on a database for a query having a formula evaluation on at least two keywords A and B, comprising:

receiving a Bloom filter tree comprised of encrypted Bloom filters of encrypted keywords from the database, wherein each Bloom filter in the Bloom filter tree is separately masked by a random mask pad P;

receiving an encrypted version of the keywords A and B from the client;

obtaining masked Bloom filter indices for the keywords A and B;

participating in secure function evaluation (SFE) with the client, wherein the server has an input comprising the masked Bloom filter indices for the keywords A and B and wherein the client has an input comprising the random mask pad P and wherein the secure function evaluation comprises the following steps;

removing the random mask pad P from the masked Bloom filter indices input by the server;

determining if there is a matching Bloom filter for each of the keywords A and B;

applying the formula evaluation to determine if the formula is satisfied; and

generating a result.

2. The method of claim 1, wherein each of the Bloom filters in the Bloom filter tree is separately masked by a random mask pad P based on a node index of the Bloom filter.

3. The method of claim 1, wherein the step of removing the random mask pad P from the masked Bloom filter indices input by the server further employs an XOR function.

4. The method of claim 1, wherein the step of removing the random mask pad P from the masked Bloom filter indices input by the server further comprises applying an XOR function to the masked indices for keywords A and B and the separate indices for keywords A and B.

5. A tangible machine-readable recordable storage medium for secure private database querying by a client on a database for a query having a formula evaluation on at least two keywords A and B, wherein one or more software programs when executed by one or more processing devices implement the steps of the method of claim 1.

6. A method performed by a client for secure private database querying with a server on a database for a query having a formula evaluation on at least two keywords A and B, comprising:

providing an encrypted version of the keywords A and B to the server, wherein the server represents the database as a Bloom filter tree comprised of encrypted Bloom filters of encrypted keywords from the database, wherein each Bloom filter in the Bloom filter tree is separately masked by a random mask pad P;

participating in secure function evaluation (SFE) with the server, wherein the server has an input comprising masked Bloom filter indices for the keywords A and B from the Bloom filter tree and wherein the client has an input comprising the random mask pad P and wherein the secure function evaluation comprises the following steps;

removing the random mask pad P from the masked Bloom filter indices input by the server;

determining if there is a matching Bloom filter for each of the keywords A and B;

applying the formula evaluation to determine if the formula is satisfied; and

generating a result.

7. The method of claim 6, wherein each of the Bloom filters in the Bloom filter tree is separately masked by a random mask pad P based on a node index of the Bloom filter.

8. The method of claim 6, wherein the step of removing the random mask pad P from the masked Bloom filter indices input by the server further employs an XOR function.

9. The method of claim 6, wherein the step of removing the random mask pad P from the masked Bloom filter indices input by the server further comprises applying an XOR function to the masked indices for keywords A and B and the separate indices for keywords A and B.

10. A tangible machine-readable recordable storage medium for secure private database querying with a server on a database for a query having a formula evaluation on at least two keywords A and B, wherein one or more software programs when executed by one or more processing devices implement the steps of the method of claim 6.

11. A server system for secure private database querying by a client on a database for a query having a formula evaluation on at least two keywords A and B, comprising:

a memory; and

at least one hardware device, coupled to the memory, operative to;

receive a Bloom filter tree comprised of encrypted Bloom filters of encrypted keywords from the database, wherein each Bloom filter in the Bloom filter tree is separately masked by a random mask pad P;

receive an encrypted version of the keywords A and B from the client;

obtain masked Bloom filter indices for the keywords A and B;

participate in secure function evaluation (SFE) with the client, wherein the server has an input comprising the masked Bloom filter indices for the keywords A and B and wherein the client has an input comprising the random mask pad P and wherein the secure function evaluation comprises the following steps;

remove the random mask pad P from the masked Bloom filter indices input by the server;

determine if there is a matching Bloom filter for each of the keywords A and B;

apply the formula evaluation to determine if the formula is satisfied; and

generate a result.

12. The server system of claim 11, wherein each of the Bloom filters in the Bloom filter tree is separately masked by a random mask pad P based on a node index of the Bloom filter.

13. The server system of claim 11, wherein random mask pad P is removed from the masked Bloom filter indices input by the server further employs an XOR function.

14. The server system of claim 11, wherein the random mask pad P is removed from the masked Bloom filter indices input by applying an XOR function to the masked indices for keywords A and B and the separate indices for keywords A and B.

15. A client system for secure private database querying by a client on a database for a query having a formula evaluation on at least two keywords A and B, comprising:

a memory; and

at least one hardware device, coupled to the memory, operative to;

provide an encrypted version of the keywords A and B to the server, wherein the server represents the database as a Bloom filter tree comprised of encrypted Bloom filters of encrypted keywords from the database, wherein each Bloom filter in the Bloom filter tree is separately masked by a random mask pad P;

participate in secure function evaluation (SFE) with the server, wherein the server has an input comprising masked Bloom filter indices for the keywords A and B from the Bloom filter tree and wherein the client has an input comprising the random mask pad P and wherein the secure function evaluation comprises the following steps;

remove the random mask pad P from the masked Bloom filter indices input by the server;

determine if there is a matching Bloom filter for each of the keywords A and B;

apply the formula evaluation to determine if the formula is satisfied; and

generate a result.

16. The client system of claim 15, wherein each of the Bloom filters in the Bloom filter tree is separately masked by a random mask pad P based on a node index of the Bloom filter.

17. The client system of claim 15, wherein the random mask pad P is removed from the masked Bloom filter indices input by the server further employs an XOR function.

18. The client system of claim 15, wherein the random mask pad P is removed from the masked Bloom filter indices input by applying an XOR function to the masked indices for keywords A and B and the separate indices for keywords A and B.