Post-quantum secure private stream aggregation

• US 10,630,655 B2
• Filed: 05/15/2018
• Issued: 04/21/2020
• Est. Priority Date: 05/18/2017
• Status: Active Grant

• Current Assignee: Robert Bosch GmbH
• Original Assignee: Robert Bosch GmbH
• Inventors: Becker, Daniela, Guajardo Merchan, Jorge
• Primary Examiner(s): Pyzocha, Michael
• Application Number:
  US15/979,761
• Publication Number:
  US 20180337899A1
• Time in Patent Office: 707 Days
• CPC Class Codes: G06N 10/00 Quantum computing, i.e. information processing based on quantum-mechanical phenomena
• CPC Class Codes: H04L 63/0414 during transmission, i.e. party's identity is protected against eavesdropping, e.g. by using temporary identifiers, but is known to the other party or parties involved in the communication
• CPC Class Codes: H04L 63/0428 wherein the data content is protected, e.g. by encrypting or encapsulating the payload
• CPC Class Codes: H04L 63/0457 wherein the sending and receiving network entities apply dynamic encryption, e.g. stream encryption cryptographic mechanisms or cryptographic arrangements for stream encryption H04L9/065
• CPC Class Codes: H04L 67/01 Protocols
• CPC Class Codes: H04L 67/10 in which an application is distributed across nodes in the network software deployment G06F8/60; multiprogramming arrangements G06F9/46
• CPC Class Codes: H04L 9/008 involving homomorphic encryption
• CPC Class Codes: H04L 9/0825 using asymmetric-key encryption or public key infrastructure [PKI], e.g. key signature or public key certificates
• CPC Class Codes: H04L 9/0852 Quantum cryptography transmission systems employing electromagnetic waves other than radio waves, e.g. light, infrared H04B10/00; wavelength-division multiplex systems H04J14/02; WDM arrangements H04J14/03
• CPC Class Codes: H04L 9/0869 involving random numbers or seeds
• CPC Class Codes: H04L 9/14 using a plurality of keys or algorithms
• CPC Class Codes: H04L 9/304 based on error correction codes, e.g. McEliece
• CPC Class Codes: H04L 9/3093 involving Lattices or polynomial equations, e.g. NTRU scheme

Abstract

A method for operating an aggregator in a private stream aggregation (PSA) system has been developed. The method includes receiving a plurality of encrypted messages from a plurality of clients, each encrypted message corresponding to a vector in a learning with errors (LWE) public key, adding, the plurality of encrypted messages to generate an aggregate data set, extracting a summation of a plurality of error vectors in the plurality of encrypted messages from the aggregate data set, decrypting the summation of the encrypted data contained in the plurality of encrypted messages using a private key stored in the memory of the aggregator to generate a plaintext sum of noisy data generated by the plurality of clients, and generating, with the processor, an output of the plaintext sum of noisy data that preserves differential privacy of each client in the plurality of clients.

Claims

1. A method for operating an aggregator in a private stream aggregation (PSA) system comprising:

receiving, with a network interface in the aggregator, a plurality of encrypted messages from a plurality of clients, each client in the plurality of clients transmitting one encrypted message in the plurality of encrypted messages, each encrypted message corresponding to a vector in a learning with errors (LWE) public key;

adding, with a processor in the aggregator, the plurality of encrypted messages to generate an aggregate data set corresponding to a sum of the plurality of encrypted messages;

extracting, with the processor, a summation of a plurality of error vectors in the plurality of encrypted messages from the aggregate data set using a predetermined matrix stored in a memory of the aggregator corresponding to a portion of the LWE public key in each encrypted message and a predetermined secret key stored in the memory, the predetermined secret key corresponding to a sum of a plurality of secret keys used by the plurality of clients to generate the plurality of encrypted messages;

multiplying, with the processor, a predetermined gadget matrix stored in the memory with the summation of the plurality of error vectors to generate a summation of encrypted data contained in the plurality of encrypted messages;

decrypting, with the processor, the summation of the encrypted data contained in the plurality of encrypted messages using a private key stored in the memory of the aggregator to generate a plaintext sum of noisy data generated by the plurality of clients; and

generating, with the processor, an output of the plaintext sum of noisy data that preserves differential privacy of each client in the plurality of clients.

2. The method of claim 1, the extracting further comprising:

subtracting, with the processor, a product of the matrix corresponding to the LWE public key multiplied by the predetermined secret key from the aggregate data set to generate the summation of the plurality of error vectors.

3. The method of claim 1, the decrypting further comprising:

performing an LWE decryption process, with the processor, to decrypt the summation of the encrypted data using the private key stored in the memory to generate the plaintext sum of noisy data generated by the plurality of clients.

4. The method of claim 2, wherein the LWE decryption process is a Brakerski-Gentry-Vaikuntanathan (BGV) decryption process.

5. The method of claim 1, wherein the error vector in each encrypted message of the plurality of messages encodes a value in an integer numeric range p selected from one of [0, 5], [0, 37], or [0, 65537].

6. The method of claim 1, wherein the error vector in each encrypted message of the plurality of messages encodes a value that is represented by a plurality of bits of binary data.

7. A method for operating a first client in a private stream aggregation (PSA) system comprising:

encrypting, with a processor in the first client, noisy plaintext data using a first public key stored in a memory of the first client to generate an encrypted data vector;

sampling, with the processor in the first client, the encrypted data vector to generate an error vector with a Gaussian distribution based on the encrypted data vector;

generating, with the processor in the first client, a vector of a learning with errors (LWE) public key using a predetermined matrix stored in the memory of the first client, a predetermined secret key stored in the memory of the first client, and the error vector, the LWE public key being different than the first public key; and

transmitting, with a network interface in the first client, a first encrypted message including the vector of the LWE public key to an aggregator.

8. The method of claim 7 further comprising:

generating, with the processor in the first client, a random integer using a discrete Laplace mechanism; and

adding, with the processor in the first client, the random integer to plaintext data stored in the memory of the first client to generate the noisy plaintext data.

9. The method of claim 7, the generating of the vector of the LWE public key further comprising:

generating, with the processor in the first client, the vector of the LWE public key by adding the error vector to a product of the predetermined matrix multiplied by the predetermined secret key.

10. The method of claim 7 further comprising:

encrypting, with a processor in the first client, the noisy plaintext data using an LWE encryption process with the first public key stored in the memory of the first client to generate the encrypted data vector.

11. The method of claim 10, wherein the LWE encryption process is a Brakerski-Gentry-Vaikuntanathan (BGV) encryption process.

12. The method of claim 7, wherein the vector of the LWE public key encodes a value in an integer numeric range p selected from one of [0, 5], [0, 37], or [0, 65537].

13. The method of claim 7, wherein the vector of the LWE public key encodes a value that is represented by a plurality of bits of binary data.

14. The method of claim 7 further comprising:

receiving, with a network interface in the aggregator, a plurality of encrypted messages including the first encrypted message and at least one additional encrypted message from a plurality of clients including the first client and at least one additional client, each encrypted message corresponding to a vector in an LWE public key;

adding, with a processor in the aggregator, the plurality of encrypted messages to generate an aggregate data set corresponding to a sum of the plurality of encrypted messages;

extracting, with the processor in the aggregator, a summation of a plurality of error vectors in the plurality of encrypted messages from the aggregate data set using a predetermined matrix stored in a memory of the aggregator, the predetermined matrix corresponding to a portion of the LWE public key in each encrypted message, and a predetermined secret key stored in the memory of the aggregator, the predetermined secret key corresponding to a sum of a plurality of secret keys used by the plurality of clients to generate the plurality of encrypted messages;

multiplying, with the processor in the aggregator, a predetermined gadget matrix stored in the memory of the aggregator with the summation of the plurality of error vectors to generate a summation of encrypted data contained in the plurality of encrypted messages;

decrypting, with the processor in the aggregator, the summation of the encrypted data contained in the plurality of encrypted messages using a private key stored in the memory of the aggregator to generate a plaintext sum of noisy data generated by the plurality of clients; and

generating, with the processor in the aggregator, an output of the plaintext sum of noisy data, the aggregator being unable to identify a portion of the output that corresponds to the noisy plaintext data from the first client.

15. The method of claim 14, the decrypting further comprising:

performing an LWE decryption process, with the processor in the aggregator, to decrypt the summation of the encrypted data using the private key stored in the memory of the aggregator to generate the plaintext sum of noisy data generated by the plurality of clients.

16. The method of claim 15, wherein the LWE decryption process is a Brakerski-Gentry-Vaikuntanathan (BGV) decryption process.

17. An aggregator in a private stream aggregation (PSA) system comprising:

a network interface configured to receive encrypted messages from a data network;

a memory configured to store;

a predetermined matrix corresponding to a portion of a learning with errors (LWE) public key;

a predetermined gadget matrix;

a predetermined secret key; and

a private key; and

a processor operatively connected to the network interface and the memory, the processor being configured to;

receive a plurality of encrypted messages from a plurality of clients with the network interface, each client in the plurality of clients transmitting one encrypted message in the plurality of encrypted messages, each encrypted message corresponding to a vector in an LWE public key;

add the plurality of encrypted messages to generate an aggregate data set corresponding to a sum of the plurality of encrypted messages;

extract a summation of a plurality of error vectors in the plurality of encrypted messages from the aggregate data set using the predetermined matrix stored in the memory corresponding to a portion of the LWE public key in each encrypted message, and the predetermined secret key stored in the memory, the predetermined secret key corresponding to a sum of a plurality of secret keys used by the plurality of clients to generate the plurality of encrypted messages;

multiply the predetermined gadget matrix stored in the memory with the summation of the plurality of error vectors to generate a summation of encrypted data contained in the plurality of encrypted messages;

decrypt the summation of the encrypted data contained in the plurality of encrypted messages using the private key stored in the memory to generate a plaintext sum of noisy data generated by the plurality of clients; and

generate an output of the plaintext sum of noisy data that preserves differential privacy of each client in the plurality of clients.

18. The aggregator of claim 17, the processor being further configured to:

subtract a product of the matrix corresponding to the LWE public key multiplied by the predetermined secret key from the aggregate data set to generate the summation of the plurality of error vectors.

19. The aggregator of claim 17, the processor being further configured to:

perform an LWE decryption process to decrypt the summation of the encrypted data using the private key stored in the memory to generate the plaintext sum of noisy data generated by the plurality of clients.

20. The aggregator of claim 19, wherein the LWE decryption process is a Brakerski-Gentry-Vaikuntanathan (BGV) decryption process.