System and method for providing private inference control

• US 7,472,105 B2
• Filed: 10/19/2004
• Issued: 12/30/2008
• Est. Priority Date: 10/19/2004
• Status: Active Grant

• Current Assignee: Xerox Corporation (Xerox Holdings Corp.)
• Original Assignee: Palo Alto Research Center, Inc. (Xerox Holdings Corp.)
• Inventors: Staddon, Jessica Nicola, Woodruff, David P.
• Primary Examiner(s): Vo; Tim T
• Assistant Examiner(s): TRAN, ANHTAI V
• Application Number:
  US10/969,549
• Publication Number:
  US 20060085651A1
• Time in Patent Office: 1,533 Days
• Field of Search: 707/1, 707/10, 380/28, 380/255
• US Class Current: 1/1
• CPC Class Codes: G06F 21/6227 where protection concerns the structure of data, e.g. records, types, queries
• CPC Class Codes: H04L 9/008 involving homomorphic encryption
• CPC Class Codes: H04L 9/085 Secret sharing or secret splitting, e.g. threshold schemes
• CPC Class Codes: H04L 9/0894 Escrow, recovery or storing of secret information, e.g. secret key escrow or cryptographic key storage
• CPC Class Codes: H04L 9/3218 using proof of knowledge, e.g. Fiat-Shamir, GQ, Schnorr, ornon-interactive zero-knowledge proofs
• CPC Class Codes: Y10S 707/99931 Database or file accessing

Abstract

Records in a secure database include attributes. A query homomorphically encrypts indices identifying one record and attribute. A secret key is generated at a certain query count and is divided into randomly generated key shares. A key share sequence is homomorphically encrypted. A table is formed by encrypting the indices, secret key and attributes. The key shares are decrypted sufficient to recover the secret key subject to a non-inference enabling query. In a further embodiment, a query count is maintained. Records in a secure database include attributes, with an attributes set forming inference channels. A data structure includes ciphertext keys. A pseudorandom function seed and non-malleable encryption secret key are chosen. A query provides indices identifying one record and attribute. A secure function evaluation is executed. A table combines the attributes with the pseudorandom function applied to the seed and indices. A table entry for the indices is provided.

Claims

1. A system for providing private inference control, comprising:

a central processing unit; and

a memory coupled to the central processing unit;

the system further comprising;

a secure database comprising a plurality of records with each record comprising a plurality of attributes;

a plurality of queries that each comprises encrypted indices, which identify one such record and attribute by homomorphic encryption;

a query count of the queries;

an authorization generator configured to generate a secret key upon reaching the query count, to divide the secret key into randomly generated key shares and to provide a sequence of the key shares encrypted by homomorphic encryption;

a query processor configured to form a table of entries by encrypting the indices, the secret key and each of the attributes for each of the records of the database;

a query generator configured to execute a Symmetric Private Information Retrieval (SPIR) protocol on the table of entries, and to provide a plurality of query responses, which each comprise the attributes for each of the records of the table entries; and

a reconstructor configured to decrypt a plurality of the key shares comprising a number of the key shares sufficient to recover the secret key subject to a non-inference enabling query.

2. A system according to claim 1, wherein the query generator is further configured to execute a zero knowledge proof of knowledge that the ciphertexs are well-formed.

3. A system according to claim 1, wherein the query generator is further configured to form a public key and private key, and provides the public key to the secure database.

4. A system according to claim 1, wherein the authorization generator is further configured to set an empty secret key prior to reading the query count.

5. A system according to claim 4, wherein the key shares sequence are formed comprising a subset of the query count, and the key shares are recovered upon receiving the key share sequence.

6. A system according to claim 1,

wherein the query processor is further configured to generate a random value for the indices identifying each of the records and attributes in the secure database, and to include the random value with the homomorphic encryption of each such table entry corresponding to each such index.

7. A system according to claim 1, wherein the secure database entry is recovered by specifying the correct indices against the table upon recovering the secret key.

8. A method for providing private inference control, comprising:

maintaining a secure database comprising a plurality of records with each record comprising a plurality of attributes;

specifying a plurality of queries by encrypting indices identifying one such record and attribute for each query, by homomorphic encryption;

maintaining a query count of the queries;

generating a secret key upon reaching the query count;

dividing the secret key into randomly generated key shares and providing a sequence of the key shares, which are each encrypted by homomorphic encryption;

forming a table of entries by encrypting the indices, the secret key and each of the attributes for each of the records of the database;

executing a Symmetric Private Information Retrieval (SPIR) protocol on the table of entries;

providing a plurality of query responses which each comprises the attributes for each of the records of the table of entries; and

decrypting a plurality of the key shares comprising a number of the key shares sufficient to recover the secret key subject to a non-inference enabling query.

9. A method according to claim 8, further comprising:

executing a zero knowledge proof of knowledge that the ciphertexts are well-formed.

10. A method according to claim 8, further comprising:

forming a public key and private key; and

providing the public key to the secure database.

11. A method according to claim 8, further comprising:

setting an empty secret key prior to reading the query count.

12. A method according to claim 11, further comprising:

forming the key shares sequence comprising a subset of the query count; and

recovering the key shares upon receiving the key share sequence.

13. A method according to claim 8, further comprising:

generating a random value for the indices identifying each of the records and attributes in the secure database; and

including the random value with the homomorphic encryption of each such table entry corresponding to each such index.

14. A method according to claim 8, further comprising:

recovering the secure database entry by specifying the correct indices against the table upon recovering the secret key.

15. A computer readable storage medium storing code for executing on a computer system to perform the method according to claim 8.