Secure private database querying system with content hiding bloom filters
First Claim
1. 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 at least two keywords A and B from the client;
evaluating bit positions of the keywords A and B in the Bloom filter to obtain masked Bloom filter indices for the keywords A and B;
participating in Secure Function Evaluation (SFE) with the client, wherein the Secure Function Evaluation employs at least one garbled circuit representing the formula, wherein the server has an input comprising the masked Bloom filter indices for the at least two keywords A and B and wherein the client has an input comprising the random mask pad P and wherein the Secure Function Evaluation performed by the server with the client comprises the following steps;
removing the random mask pad P from the masked Bloom filter indices input by the server;
determining when there is a matching Bloom filter for each of the at least two keywords A and B;
applying the formula evaluation to determine when the formula is satisfied; and
generating a result, wherein the result does not reveal whether each term of the formula is matched by the Bloom filter tree.
4 Assignments
0 Petitions
Accused Products
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.
24 Citations
18 Claims
-
1. 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 at least two keywords A and B from the client; evaluating bit positions of the keywords A and B in the Bloom filter to obtain masked Bloom filter indices for the keywords A and B; participating in Secure Function Evaluation (SFE) with the client, wherein the Secure Function Evaluation employs at least one garbled circuit representing the formula, wherein the server has an input comprising the masked Bloom filter indices for the at least two keywords A and B and wherein the client has an input comprising the random mask pad P and wherein the Secure Function Evaluation performed by the server with the client comprises the following steps; removing the random mask pad P from the masked Bloom filter indices input by the server; determining when there is a matching Bloom filter for each of the at least two keywords A and B; applying the formula evaluation to determine when the formula is satisfied; and generating a result, wherein the result does not reveal whether each term of the formula is matched by the Bloom filter tree. - View Dependent Claims (2, 3, 4, 5)
-
-
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 at least two 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 Secure Function Evaluation employs at least one garbled circuit representing the formula, wherein the server evaluates bit positions of the at least two keywords A and B in the Bloom filter to obtain an input comprising masked Bloom filter indices for the at least two 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 performed by the client with the server comprises the following steps; removing the random mask pad P from the masked Bloom filter indices input by the server; determining when there is a matching Bloom filter for each of the at least two keywords A and B; applying the formula evaluation to determine when the formula is satisfied; and generating a result, wherein the result does not reveal whether each term of the formula is matched by the Bloom filter tree. - View Dependent Claims (7, 8, 9, 10)
-
-
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 at least two keywords A and B from the client; evaluate bit positions of the keywords A and B in the Bloom filter to obtain masked Bloom filter indices for the at least two keywords A and B; participate in Secure Function Evaluation (SFE) with the client, wherein the Secure Function Evaluation employs at least one garbled circuit representing the formula, wherein the server has an input comprising the masked Bloom filter indices for the at least two keywords A and B and wherein the client has an input comprising the random mask pad P and wherein the Secure Function Evaluation performed by the server with the client comprises the following steps; removing the random mask pad P from the masked Bloom filter indices input by the server; determining when there is a matching Bloom filter for each of the at least two keywords A and B; applying the formula evaluation to determine when the formula is satisfied; and generating a result, wherein the result does not reveal whether each term of the formula is matched by the Bloom filter tree. - View Dependent Claims (12, 13, 14)
-
-
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 at least two 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 Secure Function Evaluation employs at least one garbled circuit representing the formula, wherein the server evaluates bit positions of the at least two keywords A and B in the Bloom filter to obtain an input comprising masked Bloom filter indices for the at least two 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 performed by the client with the server comprises the following steps; removing the random mask pad P from the masked Bloom filter indices input by the server; determining when there is a matching Bloom filter for each of the at least two keywords A and B; applying the formula evaluation to determine when the formula is satisfied; and generating a result, wherein the result does not reveal whether each term of the formula is matched by the Bloom filter tree. - View Dependent Claims (16, 17, 18)
-
Specification