DETECTING DATA BREACHES

• US 20180268135A1
• Filed: 03/17/2017
• Published: 09/20/2018
• Est. Priority Date: 03/17/2017
• Status: Active Grant

• Current Assignee: Chronicle LLC
• Original Assignee: X Development LLC (Alphabet Inc.)
• Inventors: Nachenberg, Carey Stover, Gillett, Stephen
• Granted Patent: US 10,503,896 B2
• Time in Patent Office: Days
• CPC Class Codes: G06F 21/552 involving long-term monitoring or reporting
• CPC Class Codes: G06F 21/602 Providing cryptographic facilities or services
• CPC Class Codes: G06F 21/6245 Protecting personal data, e.g. for financial or medical purposes
• CPC Class Codes: G06F 2221/034 Test or assess a computer or a system
• CPC Class Codes: G06N 20/00 Machine learning
• CPC Class Codes: G06N 5/04 Inference or reasoning models

Abstract

The subject matter of this specification generally relates to data security. In some implementations, a method includes receiving, from data owners, a first cryptographically secure representation of data to be monitored for data breaches. Each first cryptographically secure representation can include a cryptographically secure data structure that represents a plurality of first data records maintained by the data owner. One or more second cryptographically secure representations of second data records are received from a user. A number of the second cryptographically secure representations that match a corresponding portion of the first cryptographically secure representation received from a data owner is determined. A determination is made that a data breach occurred for the data owner based on the number of the second cryptographically secure representations that match the corresponding portion of the first cryptographically secure representation received from the data owner.

Claims

1. A method for detecting data breaches, the method comprising:

receiving, from each of a plurality of data owners, a first cryptographically secure representation of data to be monitored for data breaches, each first cryptographically secure representation including a cryptographically secure data structure that represents a plurality of first data records maintained by the data owner;

receiving, from a user and for each of a plurality of second data records, one or more second cryptographically secure representations of the second data records;

determining a number of the second cryptographically secure representations that match a corresponding portion of the first cryptographically secure representation received from a data owner of the plurality of data owners; and

determining that a data breach occurred for the data owner based on the number of the second cryptographically secure representations that match the corresponding portion of the first cryptographically secure representation received from the data owner.

2. The method of claim 1, further comprising providing notification to the data owner notifying the data owner of the breach in response to determining that the breach occurred.

3. The method of claim 1, wherein each first cryptographically secure representation comprises a first probabilistic representation and each second cryptographically secure representation comprises a second probabilistic representation.

4. The method of claim 3, wherein each first probabilistic representation comprises a first Bloom filter.

5. The method of claim 4, wherein each second probabilistic representation comprises one or more bit numbers that each identifies a respective bit of a second Bloom filter that has been set based on the second data record represented by the second probabilistic representation.

6. The method of claim 4, wherein determining a number of the second cryptographically secure representations that match a corresponding portion of the cryptographically secure representation received from a data owner of the plurality of data owners comprises:

for each second probabilistic representation received from the user;

determining, for each data element of the second probabilistic representation, whether the data element matches a corresponding data element of the first Bloom filter; and

incrementing a count of a number of matching probabilistic representations when each data element of the second probabilistic representation matches the corresponding data element of the first Bloom filter.

7. The method of claim 1, wherein determining that a data breach occurred for the data owner based on the number of the second cryptographically secure representations that match the corresponding portion of the cryptographically secure representation received from the data owner comprises determining that the count meets or exceeds a predetermined threshold.

8. The method of claim 1, wherein determining that a data breach occurred for the data owner based on the number of the second cryptographically secure representations that match the corresponding portion of the cryptographically secure representation received from the data owner comprises determining that a percentage of the second cryptographically secure representations received from the user match the corresponding portion of the cryptographically secure representation received from the data owner.

9. The method of claim 1, wherein each data record of each of the first cryptographically secure representations includes a tuple having multiple related data items.

10. The method of claim 1, wherein the first cryptographically secure representation received from a given data owner represents, for each entity of a plurality of entities, multiple tuples of a data record for the entity, each tuple comprising a different set of data related to the entity and included in the data record.

11. The method of claim 1, further comprising providing compensation to the user in response to determining that the breach occurred for the data owner using the second cryptographically secure representations received from the user.

12. The method of claim 1, further comprising:

receiving, from the user, data specifying a requested compensation amount for detection of a breach using the second cryptographically secure representations received from the user; and

determining, for each data owner of the plurality of data owners and based on the requested compensation amount, whether to compare the second cryptographically secure representations to the first cryptographically secure representation received from the data owner.

13. A system comprising:

a data processing apparatus; and

a computer storage medium encoded with a computer program, the program comprising data processing apparatus instructions that when executed by the data processing apparatus cause the data processing apparatus to perform operations comprising;

receiving, from each of a plurality of data owners, a first cryptographically secure representation of data to be monitored for data breaches, each first cryptographically secure representation including a cryptographically secure data structure that represents a plurality of first data records maintained by the data owner;

receiving, from a user and for each of a plurality of second data records, one or more second cryptographically secure representations of the second data records;

determining a number of the second cryptographically secure representations that match a corresponding portion of the first cryptographically secure representation received from a data owner of the plurality of data owners; and

determining that a data breach occurred for the data owner based on the number of the second cryptographically secure representations that match the corresponding portion of the first cryptographically secure representation received from the data owner.

14. The system of claim 13, wherein the operations comprise providing notification to the data owner notifying the data owner of the breach in response to determining that the breach occurred.

15. The system of claim 13, wherein each first cryptographically secure representation comprises a first probabilistic representation and each second cryptographically secure representation comprises a second probabilistic representation.

16. The system of claim 15, wherein each first probabilistic representation comprises a first Bloom filter.

17. The system of claim 16, wherein each second probabilistic representation comprises one or more bit numbers that each identifies a respective bit of a second Bloom filter that has been set based on the second data record represented by the second probabilistic representation.

18. A method for detecting data breaches, the method comprising:

receiving, from a plurality of data owners, first cryptographically secure representations of data to be monitored for data breaches, each first cryptographically secure representation including a cryptographically secure data structure that represents a plurality of first data records maintained by the data owner;

receiving, from a user, a plurality of second data records;

generating, for each second data record received from the user, one or more second cryptographically secure representations of the second data record;

determining a number of the second cryptographically secure representations that match a corresponding portion of the first cryptographically secure representation received from a data owner of the plurality of data owners; and

determining that a data breach occurred for the data owner based on the number of the second cryptographically secure representations that match the corresponding portion of the first cryptographically secure representation received from the data owner.

19. The method of claim 18, further comprising providing notification to the data owner notifying the data owner of the breach in response to determining that the breach occurred.

20. The method of claim 18, wherein each first cryptographically secure representation comprises a first probabilistic representation and each second cryptographically secure representation comprises a second probabilistic representation.