Anonymization of Streaming Data

• US 20150278549A1
• Filed: 03/26/2014
• Published: 10/01/2015
• Est. Priority Date: 03/26/2014
• Status: Active Grant

• Current Assignee: WSOU Investments, LLC (WSOU Holdings, LLC)
• Original Assignee: Alcatel-Lucent USA, Inc. (Nokia Corporation)
• Inventors: Kolesnikov, Vladimir Y., Wilfong, Gordon T.
• Granted Patent: US 9,361,480 B2
• Time in Patent Office: 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 (p_i, s_i) of a data stream, where p_i comprises an identifying portion and s_i comprises associated sensitive information; assigning the identifying portion, p_i, to a region S_i of a partitioned space S; 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 assigned region S_i. Optionally a permutation function π randomizes the order that regions S₁, S₂, . . . , S_t in the partitioned space S are stored so that an adversary cannot obtain information by observing the data being stored in particular regions. The regions S₁, S₂, . . . , S_t have corresponding center points C₁, C₂, . . . , C_t, and a nearest center C_i 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 C_i.

Claims

1. A method, comprising:

receiving a data element (p_i, s_i) of a data stream, where p_i comprises an identifying portion and s_i comprises associated sensitive information;

assigning said identifying portion, p_i, to a region S_i of a partitioned space S;

encrypting said associated sensitive information s_i as e(s_i); and

storing said encrypted associated sensitive information e(s_i) in a list associated with said assigned region S_i.

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

3. The method of claim 2, wherein said region S_i is one of a plurality of regions S₁, S₂, . . . , S_t and 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 C_i to p_i,

wherein said list is associated with said computed nearest center C_i.

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

6. The method of claim 4, where there are a number of center points C₁, C₂, . . . , C_t such that for any point pin S there is a center C_i so that p is at most distance d to C_i, for a fixed distance d.

7. The method of claim 6, wherein said fixed distance d is a user-specified parameter.

8. The method of claim 6, wherein said fixed distance d is a limit on how different transformed identifying information must be from said identifying portion for each data element.

9. 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.

10. 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.

11. The method of claim 1, wherein said data element (p_i, s_i) is stored to said list as part of a set, wherein members of said set have a same transformed identifying part.

12. 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.

13. A system, comprising:

a memory; and

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

receive a data element (p_i, s_i) of a data stream, where p_i comprises an identifying portion and s_i comprises associated sensitive information;

assign said identifying portion, p_i, to a region S_i of a partitioned space S;

encrypt said associated sensitive information s_i as e(s_i); and

store said encrypted associated sensitive information e(s_i) in a list associated with said assigned region S_i.

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

15. The system of claim 14, wherein said region S_i is one of a plurality of regions S₁, S₂, . . . , S_t and wherein said permutation function comprises a randomly chosen permutation function on [1, t].

16. The system of claim 13, 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 C_i to p_i,

wherein said list is associated with said computed nearest center C_i.

17. The system of claim 16, wherein points in a region S_i are at least as close to C_i as to any other center.

18. The system of claim 16, where there are a number of center points C₁, C₂, . . . , C_t such that for any point p in S there is a center C_i so that p is at most distance d to C_i, for a fixed distance d.

19. The system of claim 18, wherein said fixed distance d is a limit on how different transformed identifying information must be from said identifying portion for each data element.

20. The system of claim 13, 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.

21. The system of claim 13, 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.

22. The system of claim 13, wherein said data element (p_i, s_i) is stored to said list as part of a set, wherein members of said set have a same transformed identifying part.