Method and apparatus for secure and privacy-preserving querying and interest announcement in content push and pull protocols

Patent metadata

Field	Value
Publication number	US-10181049-B1
Application number	US-201314084586-A
Country	US
Kind code	B1
Filing date	Nov 19, 2013
Priority date	Jan 26, 2012
Publication date	Jan 15, 2019
Grant date	Jan 15, 2019

Abstract

Described is a process for secure and privacy-preserving data retrieval operations in a network having a plurality of nodes. The process includes receiving a query at a querying node. The query is encrypted to generate an encrypted metadata query record. The encrypted metadata query record is transmitted to each queried node that is to be searched for data. A secure pattern matching protocol is used to search a database of metadata records to match a query answer to the metadata query record. The query answer is then encrypted. A query policy is verified for the querying node, with the encrypted answer being further encrypted based on the query policy. The further encrypted answer is transmitted to the querying node, which removes the outer layer of encryption, resulting in the original encrypted answer. The original encrypted answer is then decrypted to recover the query answer.

First claim

What is claimed is:

1. A computer implemented method for secure and privacy-preserving data retrieval operations in a network having a plurality of nodes, the method comprising an act of:
causing one or more processors to execute instructions encoded upon a non-transitory memory, such that upon execution, the one or more processors perform operations of:
receiving a query at a querying node, the query having a metadata query record with a plurality of metadata fields, and wherein the query is any of an exact query, an approximate query, a wildcard query, a substring matching query, and a range query;
homomorphically encrypting the metadata query record to generate a homomorphically encrypted metadata query record;
transmitting the homomorphically encrypted metadata query record to each queried node that is to be searched for data;
using a secure pattern matching protocol to search a database of metadata records to match a query answer to the metadata query record;
homomorphically encrypting the query answer to generate a homomorphically encrypted answer;
verifying a query policy for the querying node and providing an outer layer of encryption to the homomorphically encrypted answer based on the query policy to generate a further encrypted answer, wherein the query policy is enforced by performing operations of:
encrypting the query answer to the query using a one-time session key;
using an additive secret sharing scheme, separating the session key into a number of shares equal to or bigger than a number of fields in the node's query policy; and
for each field, the field's unique symmetric key is then used to encrypt one of the shares, whereby the querying node will only be able to recover the session key and decrypt the result if it has all of the keys for the fields in its query; and

transmitting the further encrypted answer to the querying node, which removes the outer layer of encryption, resulting in the homomorphically encrypted answer; and
decrypting the homomorphically encrypted answer to recover the query answer.

2. The computer implemented method as set forth in claim 1 , wherein the homomorphically encrypted answer is a table of binary vectors, one per metadata record in the database that indicates whether a record matched the query and a pointer to corresponding data.

3. The computer implemented method as set forth in claim 2 , wherein each node in the network is preloaded with a list of query policies for every node in the network, where each query policy is a list of metadata fields in metadata record that a particular node is allowed to query.

4. A computer program product for secure and privacy-preserving data retrieval operations in a network having a plurality of nodes, the computer program product comprising executable instructions encoded on a non-transitory computer readable medium, such that upon execution of the instructions, one or more processors perform operations of:
receiving a query at a querying node, the query having a metadata query record with a plurality of metadata fields, and wherein the query is any of an exact query, an approximate query, a wildcard query, a substring matching query, and a range query;
homomorphically encrypting the metadata query record to generate a homomorphically encrypted metadata query record;
transmitting the homomorphically encrypted metadata query record to each queried node that is to be searched for data;
using a secure pattern matching protocol to search a database of metadata records to match a query answer to the metadata query record;
homomorphically encrypting the query answer to generate a homomorphically encrypted answer;
verifying a query policy for the querying node and providing an outer layer of encryption to the homomorphically encrypted answer based on the query policy to generate a further encrypted answer, wherein the query policy is enforced by performing operations of:
encrypting the query answer to the query using a one-time session key;
using an additive secret sharing scheme, separating the session key into a number of shares equal to or bigger than a number of fields in the node's query policy; and
for each field, the field's unique symmetric key is then used to encrypt one of the shares, whereby the querying node will only be able to recover the session key and decrypt the result if it has all of the keys for the fields in its query; and

transmitting the further encrypted answer to the querying node, which removes the outer layer of encryption, resulting in the homomorphically encrypted answer; and
decrypting the homomorphically encrypted answer to recover the query answer.

5. The computer program product as set forth in claim 4 , wherein the homomorphically encrypted answer is a table of binary vectors, one per metadata record in the database that indicates whether a record matched the query and a pointer to corresponding data.

6. The computer program product as set forth in claim 5 , wherein each node in the network is preloaded with a list of query policies for every node in the network, where each query policy is a list of metadata fields in metadata record that a particular node is allowed to query.

7. A system for secure and privacy-preserving data retrieval operations in a network having a plurality of nodes, the system comprising:
one or more processors and a memory, the memory having executable instructions encoded thereon, such that upon execution of the instructions, the one or more processors perform operations of:
receiving a query at a querying node, the query having a metadata query record with a plurality of metadata fields, and wherein the query is any of an exact query, an approximate query, a wildcard query, a substring matching query, and a range query;
homomorphically encrypting the metadata query record to generate a homomorphically encrypted metadata query record;
transmitting the homomorphically encrypted metadata query record to each queried node that is to be searched for data;
using a secure pattern matching protocol to search a database of metadata records to match a query answer to the metadata query record;
homomorphically encrypting the query answer to generate a homomorphically encrypted answer;
verifying a query policy for the querying node and providing an outer layer of encryption to the homomorphically encrypted answer based on the query policy to generate a further encrypted answer, wherein the query policy is enforced by performing operations of:
encrypting the query answer to the query using a one-time session key;
using an additive secret sharing scheme, separating the session key into a number of shares equal to or bigger than a number of fields in the node's query policy; and
for each field, the field's unique symmetric key is then used to encrypt one of the shares, whereby the querying node will only be able to recover the session key and decrypt the result if it has all of the keys for the fields in its query; and

transmitting the further encrypted answer to the querying node, which removes the outer layer of encryption, resulting in the homomorphically encrypted answer; and
decrypting the homomorphically encrypted answer to recover the query answer.

8. The system as set forth in claim 7 , wherein the homomorphically encrypted answer is a table of binary vectors, one per metadata record in the database that indicates whether a record matched the query and a pointer to corresponding data.

9. The system as set forth in claim 8 , wherein each node in the network is preloaded with a list of query policies for every node in the network, where each query policy is a list of metadata fields in metadata record that a particular node is allowed to query.

1

Assignees

• Hrl Lab Llc

Inventors

• El Defrawy Karim
• Holland Gavin D

Classifications

• G06F2221/2111

  Location-sensitive, e.g. geographical location, GPS · CPC title

• G06F21/6245

  Protecting personal data, e.g. for financial or medical purposes · CPC title

• H04L9/085

  Secret sharing or secret splitting, e.g. threshold schemes · CPC title

• H04L9/008

  involving homomorphic encryption · CPC title

• G06F21/6227 Primary

  where protection concerns the structure of data, e.g. records, types, queries · CPC title