Protecting your device information with Private Set Membership

Posted by Kevin Yeo and Sarvar Patel, Private Computing Team 

At Google, keeping you safe online is our top priority, so we continuously build the most advanced privacy-preserving technologies into our products. Over the past few years, we've utilized innovations in cryptographic research to keep your personal information private by design and secure by default. As part of this, we launched Password Checkup, which protects account credentials by notifying you if an entered username and password are known to have been compromised in a prior data breach. Using cryptographic techniques, Password Checkup can do this without revealing your credentials to anyone, including Google. Today, Password Checkup protects users across many platforms including Android, Chrome and Google Password Manager.

Another example is Private Join and Compute, an open source protocol which enables organizations to work together and draw insights from confidential data sets. Two parties are able to encrypt their data sets, join them, and compute statistics over the joint data. By leveraging secure multi-party computation, Private Join and Compute is designed to ensure that the plaintext data sets are concealed from all parties.

In this post, we introduce the next iteration of our research, Private Set Membership, as well as its open-source availability. At a high level, Private Set Membership considers the scenario in which Google holds a database of items, and user devices need to contact Google to check whether a specific item is found in the database. As an example, users may want to check membership of a computer program on a block list consisting of known malicious software before executing the program. Often, the set’s contents and the queried items are sensitive, so we designed Private Set Membership to perform this task while preserving the privacy of our users.

Protecting your device information during enrollment
Beginning in Chrome 94, Private Set Membership will enable Chrome OS devices to complete the enrollment process in a privacy-preserving manner. Device enrollment is an integral part of the out-of-box experience that welcomes you when getting started with a Chrome OS device.

The device enrollment process requires checking membership of device information in encrypted Google databases, including checking if a device is enterprise enrolled or determining if a device was pre-packaged with a license. The correct end state of your Chrome OS device is determined using the results of these membership checks.

During the enrollment process, we protect your Chrome OS devices by ensuring no information ever leaves the device that may be decrypted by anyone else when using Private Set Membership. Google will never learn any device information and devices will not learn any unnecessary information about other devices. ​​To our knowledge, this is the first instance of advanced cryptographic tools being leveraged to protect device information during the enrollment process.

A deeper look at Private Set Membership
Private Set Membership is built upon two cryptographic tools:

• Homomorphic encryption is a powerful cryptographic tool that enables computation over encrypted data without the need for decryption. As an example, given the encryptions of values X and Y, homomorphic encryption enables computing the encryption of the sum of X and Y without ever needing to decrypt. This preserves privacy as the data remains concealed during the computation. Private Set Membership is built upon Google’s open source homomorphic encryption library.
• Oblivious hashing is a cryptographic technique that enables two parties to jointly compute a hash, H(K, x), where the sender holds the key, K, and the receiver holds the hash input, x. The receiver will obtain the hash, H(K, x), without learning the key K. At the same time, the input x will be hidden from the sender.

Take a look at how Private Set Membership utilizes homomorphic encryption and oblivious hashing to protect data below:

For a deeper look into the technology behind Private Set Membership, you can also access our open source code.

Privacy properties
By using Private Set Membership, the following privacy properties are obtained:

• No data leaves the device when checking membership. We designed Private Set Membership using advanced cryptographic techniques to ensure that data never leaves the device in an unencrypted manner when performing membership checks. As a result, the data on your device will be concealed from everyone, including Google.
• Devices learn only membership information and nothing else. Private Set Membership was designed to prevent devices from learning any unnecessary information about other devices when querying. For each query, devices learn only the results of the membership check and no other information.

Using Private Set Membership to solve more problems
Private Set Membership is a powerful tool that solves a fundamental problem in a privacy-preserving manner. This is just the beginning of what’s possible using this technology. Private Set Membership can help preserve user privacy across a wide array of applications. For example:

• Checking allow or block lists. In this setting, users check membership in an allow or block list to determine whether to proceed with the desired action. Private Set Membership enables this check without any information about the software leaving the device.
• Control flows with conditional membership checks. Control flows are a common computer science concept that represent arbitrary computer programs with conditional branching. In many cases, the conditional branches require checking membership of sensitive data to determine the next step of the algorithm. By utilizing Private Set Membership, we enable execution of these algorithms while ensuring data never leaves the user’s device.

We still have a ways to go before Private Set Membership is used for general membership checks by devices. At Google, we are exploring a number of potential use cases to protect your privacy using Private Set Membership. We are excited to continue advancing the state-of-the-art cryptographic research to keep you safe.

Acknowledgements

The work in this post is the result of a collaboration between a large group of current and former Google engineers, research scientists and others including: Amr Aboelkher, Asra Ali, Ghous Amjad, Yves Arrouye, Roland Bock, Xi Chen, Maksim Ivanov, Dennis Kalinichenko, Nirdhar Khazanie, Dawon Lee, Tancrède Lepoint, Lawrence Lui, Pavol Marko, Thiemo Nagel, Mariana Raykova, Aaron Segal, Joon Young Seo, Karn Seth, and Jason Wong.