Anonymization of streaming data

• US 9,361,480 B2
• Filed: 03/26/2014
• Issued: 06/07/2016
• Est. Priority Date: 03/26/2014
• Status: Active Grant

• Current Assignee: WSOU Investments, LLC (WSOU Holdings, LLC)
• Original Assignee: Alcatel-Lucent SA (Nokia Corporation)
• Inventors: Wilfong, Gordon T., Kolesnikov, Vladimir Y.
• Primary Examiner(s): Rahman, Shawnchoy
• Application Number:
  US14/225,720
• Publication Number:
  US 20150278549A1
• Time in Patent Office: 804 Days
• US Class Current: 1/1
• CPC Class Codes: G06F 21/6254 by anonymising data, e.g. decorrelating personal data from the owner's identification
• CPC Class Codes: H04L 2209/42 Anonymization, e.g. involving pseudonyms
• CPC Class Codes: H04L 65/60 Network streaming of media packets
• CPC Class Codes: H04L 9/00 Cryptographic mechanisms or cryptographic arrangements for secret or secure communications; Network security protocols

Abstract

Techniques are provided for anonymizing streamed data. In various embodiments, data are anonymized by receiving a data element of a data stream including a plurality of said data elements (p_i, s_i), where p_i comprises an identifying portion and s_i comprises an associated sensitive information portion; obtaining a partitioned space S including t regions; assigning the identifying portion, p_i, to a selected region; encrypting the associated sensitive information s_i as e(s_i); and storing the encrypted associated sensitive information e(s_i) in a list associated with the selected region but not storing the associated identifying portion, p_i, in the list. The regions have corresponding center points, and a nearest center to p_i is optionally determined. The encrypted associated sensitive information e(s_i) may be stored in a list associated with the nearest center.

Claims

1. A method, comprising:

receiving a data element of a data stream including a plurality of said data elements (p_i, s_i), where p_i comprises an identifying portion of an i^th data element and s_i comprises an associated sensitive information portion of said i^th data element;

obtaining, by at least one processing device, a partitioned space S including t regions S₁, S₂, . . . , S_t;

assigning, by at least one processing device, said identifying portion, p_i, to a selected one of said regions;

encrypting, by at least one processing device, said associated sensitive information portion s_i as e(s_i); and

storing, by at least one processing device, said encrypted associated sensitive information portion e(s_i) in a non-transitory electronic memory device in a list associated with said selected region but not storing said associated identifying portion, p_i, in said list after using said associated identifying portion, p_i, to assign said associated identifying portion, p_i, to said selected region.

2. The method of claim 1, further comprising the step of mapping said list associated with said selected region to a storage location of said memory device using one or more of a permutation function and a hash table.

3. The method of claim 2, wherein said permutation function comprises a randomly chosen permutation function on [1, t].

4. The method of claim 1, further comprising the steps of:

obtaining a number of center points C₁, C₂, . . . , C_t corresponding to regions S₁, S₂, . . . , S_t in said partitioned space S; and

computing a nearest center to p_i,

wherein said list is associated with said computed nearest center.

5. The method of claim 4, wherein points in a region corresponding to said nearest center are at least as close to said nearest center as to any other of said center points.

6. The method of claim 4, where there are a number of said regions having corresponding center points C₁, C₂, . . . , C_t such that for any identifying portion p in said partitioned space S there is a region having a corresponding center point C so that p is at most a fixed distance d to said corresponding center point C.

7. The method of claim 6, wherein said fixed distance d is an adjustable parameter.

8. The method of claim 1, further comprising the step of outputting an identifier of a given list and decrypted sensitive data values from the given list on the condition that one or more predefined anonymity criterion are satisfied by said given list.

9. The method of claim 1, further comprising one or more of:

adding dummy entries to one or more lists;

deleting entries from one or more lists; and

maintaining one or more entries in one or more lists that have been output.

10. A non-transitory machine-readable recordable storage medium for anonymizing data in a data stream, wherein one or more software programs when executed by one or more processing devices implement the steps of the method of claim 1.

11. A system, comprising:

a memory; and

at least one hardware processing device, coupled to the memory, operative to;

receive a data element of a data stream including a plurality of said data elements (p_i, s_i), where p_i comprises an identifying portion of an data element and s_i comprises an associated sensitive information portion of said i^th data element;

obtain, by at least one processing device, a partitioned space S including t regions S₁, S₂, . . . , S_t;

assign, by at least one processing device, said identifying portion, p_i, to a selected one of said regions;

encrypt, by at least one processing device, said associated sensitive information portion s_i as e(s_i); and

store, by at least one processing device, said encrypted associated sensitive information portion e(s_i) in a non-transitory electronic memory device in a list associated with said selected region but not storing said associated identifying portion, p_i, in said list after using said associated identifying portion, p_i, to assign said associated identifying portion, p_i, to said selected region.

12. The system of claim 11, wherein said at least one hardware device is further configured to map said list associated with said selected region to a storage location of said memory device using one or more of a permutation function and a hash table.

13. The system of claim 12, wherein said permutation function comprises a randomly chosen permutation function on [1, t].

14. The system of claim 11, wherein said at least one hardware device is further configured to:

obtain a number of center points C₁, C₂, . . . , C_t in said partitioned space S comprising regions S₁, S₂, . . . , S_t; and

compute a nearest center to p_i,

wherein said list is associated with said computed nearest center.

15. The system of claim 14, wherein points in a region corresponding to said nearest center are at least as close to said nearest center as to any other of said center points.

16. The system of claim 14, where there are a number of said regions having corresponding center points C₁, C₂, . . . , C_t such that for any identifying portion p in said partitioned space S there is a region having a corresponding center point C so that p is at most a fixed distance d to said corresponding center point C.

17. The system of claim 11, wherein said at least one hardware device is further configured to output an identifier of a given list and decrypted sensitive data values from the given list on the condition that one or more predefined anonymity criterion are satisfied by said given list.

18. The system of claim 11, wherein said at least one hardware device is further configured to perform one or more of the following functions:

add dummy entries to one or more lists;

delete entries from one or more lists; and

maintain one or more entries in one or more lists that have been output.

19. A method for configuring a processing system to operate as a streaming data anonymization system, comprising:

configuring at least one processing system element to receive a data element of a data stream including a plurality of said data elements (p_i, s_i), where p_i comprises an identifying portion of an i^th data element and s_i comprises an associated sensitive information portion of said i^th data element;

configuring at least one processing system element to obtain a partitioned space S including t regions S₁, S₂, . . . ,S_t;

configuring at least one processing system element to assign said identifying portion, p_i, to a selected one of said regions;

configuring at least one processing system element to encrypt said associated sensitive information portion s_i as e(s_i); and

configuring at least one processing system element to store said encrypted associated sensitive information portion e(s_i) in a non-transitory electronic memory device in a list associated with said selected region but not storing said associated identifying portion, p_i, in said list after using said associated identifying portion, p_i, to assign said associated identifying portion, p_i, to said selected region.

20. The method of claim 19, further comprising the step of configuring at least one processing system element to map said list associated with said selected region to a storage location of said memory device using one or more of a permutation function and a hash table.

21. The method of claim 19, further comprising the steps of:

configuring at least one processing system element to obtain a number of center points C₁, C₂, . . . , C_t corresponding to regions S₁, S₂, . . . , S_t in said partitioned space S; and

configuring at least one processing system element to compute a nearest center to p_i,

wherein said list is associated with said computed nearest center.

22. The method of claim 19, further comprising the step of configuring at least one processing system element to output an identifier of a given list and decrypted sensitive data values from the given list on the condition that one or more predefined anonymity criterion are satisfied by said given list.