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.

Dual EC DRBG is widely believed to have been backdoored by the U.S. National Security Agency. But there was another number theoretic PRG proposed alongside Dual EC that has seen surprisingly little attention: the Micali-Schnorr generator, standardized as MS DRBG, which is based on the hardness of RSA. It appears in early drafts of the ANSI X9.82 standard (but was eventually removed in favor of Dual EC) and the final version of ISO 18031 (alongside Dual EC). The MS DRBG standard follows a pattern eerily reminiscent of Dual EC: it incorporates a series of recommended public parameters that are intended to be used in production as the RSA modulus N. Given the known vulnerabilities in Dual EC and the identical provenance, it is reasonable to ask whether MS DRBG is vulnerable to an analogous attack: Does knowledge of the factors of (or malicious construction of) the recommended moduli imply a practical attack on the MS DRBG generator? Surprisingly, this question is not easy to answer. The security proofs of course do not go through if the factors are known, but all obvious attack strategies fail. In this talk, we give historical background on MS DRBG and describe progress toward finding the backdoor (or proving it doesn't exist). We show that any backdoor must somehow exploit the algebraic structure of RSA, rather than just the attacker's ability to invert the RSA operation. We exhibit two such backdoors in related constructions. Ultimately we were unsuccessful in fully finding a plausible backdoor in MS DRBG (or proving one doesn't exist), but we hope this talk will bring more attention to this interesting open problem with potential real-world impact.

Zero-Knowledge (ZK) Proofs for disjunctive statements have been a focus of a long line of research. Classical results such as Cramer {\em et al.} [CRYPTO'94] and Abe {\em et al.} [AC'02] design generic compilers that transform certain classes of ZK proofs into ZK proofs for disjunctive statements. However, communication complexity of the resulting protocols in these results ends up being proportional to the total size of all the proofs in the disjunction. More recently, a series of works (e.g. Heath {\em et al.} [EC'20]) has exploited special properties of garbled circuits to construct efficient ZK proofs for disjunctions, where the proof size is only proportional to the length of the largest clause in the disjunction. However, these techniques do not appear to generalize beyond garbled circuits. In this work, we focus on achieving the best of both worlds. We design a \textit{general framework} that compiles a large class of {unmodified} $\Sigma$-protocols, each for an individual statement, into a new $\Sigma$-protocol that proves a disjunction of these statements. Our framework can be used both when each clause is proved with the same $\Sigma$-protocol and when different $\Sigma$-protocols are used for different clauses. The resulting $\Sigma$-protocol is concretely efficient and has communication complexity proportional to the communication required by the largest clause, with additive terms that are only logarithmic in the number of clauses. We show that our compiler can be applied to many well-known $\Sigma$-protocols, including classical protocols (\emph{e.g.} Schnorr and Guillou-Quisquater) and modern MPC-in-the-head protocols such as the recent work of Katz, Kolesnikov and Wang [CCS'18] and the Ligero protocol of Ames {\em et al.} [CCS'17] Finally, since all of the protocols in our class can be made non-interactive in the random oracle model using the Fiat-Shamir transform, our result yields the first generic non-interactive zero-knowledge protocol for disjunctions where the communication only depends on the size of the largest clause.

One-time programs, originally formulated by Goldwasser et al.~\cite{goldwasser2008one}, are a powerful cryptographic primitive with compelling applications. Known solutions for one-time programs, however, require specialized secure hardware that is not widely available (or, alternatively, access to blockchains and very strong cryptographic tools). In this work we investigate the possibility of realizing one-time programs from a recent and now more commonly available hardware functionality: the {\em counter lockbox}. A counter lockbox is a stateful functionality that protects an encryption key under a user-specified password, and enforces a limited number of incorrect guesses. Counter lockboxes have become widely available in consumer devices and cloud platforms. We show that counter lockboxes can be used to realize one-time programs for general functionalities. We develop a number of techniques to reduce the number of counter lockboxes required for our constructions, that may be of independent interest.

Steganography is often dismissed as the outcast of cryptographic research topics: after extensive research in the 1990’s and 2000’s, work on steganography has largely ground to a halt and work on encrypted systems took precedence. Unfortunately, encrypted system are now under threat, by censorship in authoritarian countries and legal constraints in liberal countries. While steganographic systems might offer a remedy to these threats, the long history of theoretical steganographic research has resulted in no practical steganographic systems capable of embedding messages into realistic communication distributions, such as human-readable text. In our recent work at CCS21, we took first steps towards remedying this shortfall, identifying several important research directions that must be studied in order to instantiate such systems. In our talk, we hope to reinvigorate community’s excitement over steganographic research by describing the promise of steganographic systems, demonstrating our system, and highlighting the interesting problems left to solve.

In 2019, US Attorney General William Barr authored an open letter to Facebook, requesting the company delay its plans to deploy additional end-to-end encryption technology. A key objection raised by the Barr memo was that end-to-end encryption technologies “[put] our citizens and societies at risk by severely eroding a company’s ability to detect and respond to illegal content and activity, such as child sexual exploitation and abuse, terrorism, and foreign adversaries’ attempts to undermine democratic values and institutions.” In addition to reiterating a previous law-enforcement position regarding “exceptional access” to encrypted records, the Barr letter outlined a new request: for technology providers to “​embed the safety of the public in system designs, thereby enabling you to continue to act against illegal content effectively with no reduction to safety, and facilitating the prosecution of offenders and safeguarding of victims.” In the two years since Barr’s letter, the scientific, policy and industrial communities have grappled with the implications of this request. A major topic of concern is whether existing server-side media scanning technologies — used to detect the presence of known child sexual abuse material (CSAM) — can be adapted to work in end-to-end encrypted systems. This work is largely referred to by the term “client-side scanning.” (We use this designation to refer to any system that performs scanning on plaintext at the client, even if some realizations may use two-party protocols.) This debate came to a head in August 2021 when Apple announced the inclusion of a new on-device CSAM scanning technology that is slated for inclusion in iOS 15. In this presentation the authors propose to discuss the background and provide a taxonomy of security and privacy risks related to client-side scanning systems.

The increased deployment of end-to-end encryption has ignited a debate between technology firms and law enforcement agencies over the need for lawful access to encrypted communications. Unfortunately, existing solutions to this problem suffer from serious technical risks, such as the possibility of operator abuse and theft of escrow key material. In this work we investigate the problem of constructing law enforcement access systems that mitigate the possibility of unauthorized surveillance. We first define a set of desirable properties for an abuse-resistant law enforcement access system (ARLEAS), and motivate each of these properties. We then formalize these definitions in the Universal Composability framework, and present two main constructions that realize this definition. The first construction enables {\em prospective} access, allowing surveillance only if encryption occurs after a warrant has been issued and activated. The second, more powerful construction, allows {\em retrospective} access to communications that occurred prior to a warrant's issuance. To illustrate the technical challenge of constructing the latter type of protocol, we conclude by investigating the minimal assumptions required to realize these systems.

Existing approaches to secure multiparty computation (MPC) require all participants to commit to the entire duration of the protocol. As interest in MPC continues to grow, it is inevitable that there will be a desire to use it to evaluate increasingly complex functionalities, resulting in computations spanning several hours or days. Such scenarios call for a *dynamic* participation model for MPC where participants have the flexibility to go offline as needed and (re)join when they have available computational resources. Such a model would also democratize access to privacy-preserving computation by facilitating an ``MPC-as-a-service'' paradigm --- the deployment of MPC in volunteer-operated networks (such as blockchains, where dynamism is inherent) that perform computation on behalf of clients. In this work, we initiate the study of *fluid MPC*, where parties can dynamically join and leave the computation. The minimum commitment required from each participant is referred to as *fluidity*, measured in the number of rounds of communication that it must stay online. Our contributions are threefold: - We provide a formal treatment of fluid MPC, exploring various possible modeling choices. - We construct information-theoretic fluid MPC protocols in the honest-majority setting. Our protocols achieve *maximal fluidity*, meaning that a party can exit the computation after receiving and sending messages in one round. - We implement our protocol and test it in multiple network settings.

Zoom’s platform provides video conferencing services for hundreds of millions of daily meeting participants. They use Zoom to conduct business, learn among classmates scattered by recent events, connect with friends and family, collaborate with colleagues, and in some cases, discuss critical matters of state. Zoom is working hard to improve meeting security for its users. In May 2020, Zoom published an incrementally deployable proposal\footnote{\url{https://github.com/zoom/zoom-e2e-whitepaper}}, describing not only a design for its improved end-to-end encryption (E2EE), but also a plan to build an auditable and persistent notion of identity for all Zoom users, which will provide additional security even against active attacks from a compromised Zoom server. In this talk, I will first describe our improved end-to-end design, report on our progress deploying it, and comment on some lessons we learned along the way. Then, I will look to the future and present our vision for user identity protocols. I will argue why it matters, discuss the issues which make this problem hard, and how we plan to address them.