International Association
for Cryptologic Research

In early 2021, Apple announced the AirTag: a quarter-sized low-powered device that utilizes the privacy-preserving FindMy network to find physical objects. The release of Airtags has been highly controversial, in part because stalkers have misused them to track potential victims. In response to this threat, Apple came up with a strategy to detect stalkers at the cost of innocent AirTag users's privacy. Their methodology is currently in the process of being standardized by the IETF. In this talk, we will show that the hard trade-off presented by Apple is not necessary and that it is possible to efficiently achieve both privacy and stalker detection. We hope that by bringing this pressing issue to the attention of the community, we can spur more meaningful discussion on what privacy properties offline-finding networks should provide and incentivize the adoption of more privacy-preserving protocols.

Running secure multiparty computation (MPC) protocols with hundreds or thousands of players would allow leveraging large volunteer networks (such as blockchains and Tor) and help justify honest majority assumptions. However, most existing protocols have at least a linear (multiplicative) dependence on the number of players, making scaling difficult. Known protocols with asymptotic efficiency independent of the number of parties (excluding additive factors) require expensive circuit transformations that induce large overheads. We observe that the circuits used in many important applications of MPC such as training algorithms used to create machine learning models have a highly repetitive structure. We formalize this class of circuits and propose an MPC protocol that achieves O(|C|) total complexity for this class. We implement our protocol and show that it is practical and outperforms O(n|C|) protocols for modest numbers of players.