Apple Inc.

Georgetown University

Abhradeep Guha Thakurta

Umesh Suresh Vaishampayan

Gaurav Kapoor

Andrew H Vyrros

Vipul Ved Prakash

Julien F Freudiger

Arnaud Legendre

Steven Duplinsky

Vivek Rangarajan Sridhar

Doug Davidson

Julien Freudinger

Yannick L Sierra

Michael Brouwer

John C Hurley

Keaton F Mowery

Yaacov Nissim Kobliner

Uri Stemmer

Raef Bahi Youssef Bassily

One embodiment provides a system that implements a 1-bit protocol for differential privacy for a set of client devices that transmit information to a server. Implementations may leverage specialized instruction sets or engines built into the hardware or firmware of a client device to improve the efficiency of the protocol. For example, a client device may utilize these cryptographic functions to randomize information sent to the server. In one embodiment, the client device may use cryptographic functions such as hashes including SHA or block ciphers including AES to provide an efficient mechanism for implementing differential privacy.

Efficient implementation for differential privacy using cryptographic functions

Technologies are disclosed for computing heavy hitter histograms using locally private randomization. Under this strategy, 'agents' can each hold a 'type' derived from a large dictionary. By performing an algorithm, an estimate of the distribution of data can be obtained. Two algorithms implement embodiments for performing methods involving differential privacy for one or more users, and usually are run in the local model. This means that information is collected from the agents with added noise to hide the agents' individual contributions to the histogram. The result is an accurate enough estimate of the histogram for commercial or other applications relating to the data collection of one or more agents. Specifically, the proposed algorithms improve on the performance (measured in computation and memory requirements at the server and the agent, as well as communication volume) of previously solutions.

Locally private determination of heavy hitters

Systems and methods are disclosed for a server learning new words generated by user client devices in a crowdsourced manner while maintaining local differential privacy of client devices. A client device can determine that a word typed on the client device is a new word that is not contained in a dictionary or asset catalog on the client device. New words can be grouped in classifications such as entertainment, health, finance, etc. A differential privacy system on the client device can comprise a privacy budget for each classification of new words. If there is privacy budget available for the classification, then one or more new terms in a classification can be sent to new term learning server, and the privacy budget for the classification reduced. The privacy budget can be periodically replenished.

Learning new words

Systems and methods are disclosed for generating term frequencies of known terms based on crowdsourced differentially private sketches of the known terms. An asset catalog can be updated with new frequency counts for known terms based on the crowdsourced differentially private sketches. Known terms can have a classification. A client device can maintain a privacy budget for each classification of known terms. Classifications can include emojis, deep links, locations, finance terms, and health terms, etc. A privacy budget ensures that a client does not transmit too much information to a term frequency server, thereby compromising the privacy of the client device.

Emoji frequency detection and deep link frequency

The system described may implement a 1-bit protocol for differential privacy for a set of client devices that transmit information to a server. Implementations of the system may leverage specialized instruction sets or engines built into the hardware or firmware of a client device to improve the efficiency of the protocol. For example, a client device may utilize these cryptographic functions to randomize information sent to the server. In one embodiment, the client device may use cryptographic functions such as hashes including SHA or block ciphers including AES. Accordingly, the system provides an efficient mechanism for implementing differential privacy.

Growing community of inventors

San Jose, CA, United States of America

Abhradeep Guha Thakurta