Apple PSI

August 20, 2021

Earlier in August, Apple announced a technology to limit the spread of Child Sexual Abuse Material (CSAM) by detecting them before they are uploaded to iCloud. Child safety advocates have voiced their support for this technology while privacy advocates emphasize that this technology can be misused and there is no protection against this technology being used for other purposes by states around the world.

Many others have written about the system, how it works and the potential privacy and surveillance issues. As part of the system, Apple uses a variant of private set intersection (PSI) that when properly used can provide cryptographic privacy. I want to focus on this part of the system and whether its use provides even cryptographic privacy in this context.

PSI is a cryptographic technique where only the intersection of two data sets is revealed and nothing else about the data sets is revealed. Lets say that you and I are huge fans of Marcel Proust’s In Search of Lost Time. But, neither of us has the entire collection of seven volumes. We want to avoid embarrassing each other by mentioning Proust’s writing from the volumes that one of us has not read. We want to identify the books that both of us have read. We also don’t want to leak which other volumes we have read. For this purpose, we could run a PSI protocol to identify which volumes both of us have while not revealing anything else.

Apple PSI does something similar. In fact, it does even better. It does not even reveal the intersection, only the associated data when there is an intersection. However, I think that the assumptions required for the protocol to provide cryptographic privacy in this particular setting of Apple do not hold.

PSI protocols run between a server and a client are a specific instance of secure two-party computation (2PC), which allows two parties to run a protocol and compute a function, without revealing anything other than the outputs of the function. In the case of PSI, the output is the elements that are common among the participating entities. In the case of Apple PSI, if there are common elements between the sets held by the server and those on the client device, then the server is informed through the associated data while the elements themselves are not revealed to the server. The client receives no output.

When we run a PSI protocol, the client and server need to be available. In simpler words, both of them want to participate in the protocol at a desired time. The server and the client need to be independent and they should not collude with each other. Non-collusion is important in this discussion and it is a requirement if we are to prove any kind of security for these protocols, such as in Section 4.4 of The Apple PSI System.

Is this requirement of non-collusion satisfied in the technology proposed by Apple? The server is controlled by Apple. The client is also controlled by Apple. The end-user may be able to disable syncing with iCloud, but the end user cannot control whether or not to participate in the PSI protocol if they want to use iCloud. If the end user could control whether or not to participate in this technology, then Apple’s CSAM limiting technology will fail. So, Apple has good reasons to prevent user control. However, this also means that Apple cannot claim to provide the end user cryptographic privacy as the requirement for running PSI requires that the end-user wants to participate in the protocol and that the client does not collude with the server, which is not the case here.

Apple’s ability to run PSI at will, controlling the server and the client, is at the heart of the problem I see. The end-user did not sign up for this technology. The PSI protocol in this particular instance is a one-party protocol, where Apple controls both the end-points.

Apple’s use of PSI can potentially help us think more broadly about the deployment of 2PC or more generally secure multi-party protocols (MPC). The software for the end-points needs to be provided by someone. In the case of Apple PSI, it is provided by the same company. This means that beyond the guarantees offered by the cryptographic protocol, we also need to trust the company that provides the software for the end-points.

There are at least two approaches to resolve this issue. First, the software for the server and the client should be open-sourced so that they can be verified independently. This approach increases the public trust that the software is not acting maliciously even if both end-points are run by the same company. Second, in addition to open source software, standardization of MPC protocols can be helpful. Standardization of message and protocol formats will allow for software offered by different companies/entities to be interoperable. NIST multi-party threshold cryptography project and privacy-enhancing cryptography project are working on guidelines that has the potential to contribute towards a diverse ecosystem of implementations. But, this process will take time.

When deploying PSI protocols, we rely on the assumption that the client and server do not collude and that the end-user wants to participate in the protocol or the application that uses such a protocol. Even when cryptographic privacy is guaranteed, it does not necessarily guarantee that the system provides the end user privacy, especially when it involves running a software on their device that they may not want to run.

Thanks to Anders Dalskov and Amos Treiber for reading and providing feedback on earlier drafts.

Update on December 15, 2021: Updated link to the archived version of Apple’s child safety page from September 1, 2021 as all mention of CSAM detection has been removed from the page as of December 13, 2021.