×

Secure private database querying system with content hiding bloom filters

  • US 9,535,658 B2
  • Filed: 09/28/2012
  • Issued: 01/03/2017
  • Est. Priority Date: 09/28/2012
  • Status: Expired due to Fees
First Claim
Patent Images

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 all claims
  • 4 Assignments
Timeline View
Assignment View
    ×
    ×