TPMPC 2024

Talk title: A Bigger Picture of Secure Multi-Party Computation

Abstract: Secure multi-party computation is a mature area that enables computation over private data. Products utilizing secure computation techniques are now increasingly being built by tech companies for privacy-preserving data analytics and other purposes. For many years, progress in this area has focused on mechanisms for securely realizing different functionalities, i.e., on how to perform secure function evaluation. In this talk, we argue that other aspects of privacy-preserving computation deserve the attention of the research community. They include ensuring the trustworthiness of inputs to the computation, achieving security of linked computations, and selecting functions to ensure that the (authorized) information disclosure from the output is limited. We investigate the last component in more detail on the example of average salary computation, inspired by the Boston privacy-preserving gender pay gap study carried out in 2015-2017.

Bio: Marina Blanton is an Associate Professor in the Department of Computer Science and Engineering at the University at Buffalo (UB). She also serves as the Faculty Director of Women in Science and Engineering (WiSE) program at UB. Dr. Blanton received her MS in EECS from Ohio University in 2002, MS in CS from Purdue University in 2004, and PhD in CS from Purdue University in 2007. Her research interests are centrally in information security, privacy, and applied cryptography and recent projects span areas such as secure computation and outsourcing, integrity of outsourced computation and storage, and private biometric and genomic computation. Dr. Blanton has over 80 refereed publications, has served on the technical program committees of top conferences such as USENIX Security, IEEE S&P, and CCS, and is currently an associate editor of IEEE Transactions on Dependable and Secure Computing. She has received multiple awards for her research, including a 2013 AFOSR Young Investigator Award, the 2015 ACM CCS Test of Time Award, and a 2018 Google Faculty Research Award.

Talk title: On the round-complexity of secure multi-party computation

Abstract: In multi-party computation (MPC), multiple entities, each having some inputs want to jointly compute a function of these inputs with the guarantee that nothing aside from the output of the function will be leaked. In this talk, we are going to investigate how many messages the parties of an MPC need to exchange to securely realize any functionality with simulation-based security in the case where there is no setup and the majority of the parties can be corrupted. We will then consider a relaxation of the standard simulation-based paradigm, and show that this relaxation leads to more efficient MPC protocols that still realize non-trivial functionalities with meaningful security.

Bio: Michele Ciampi is a Chancellor’s Fellow (equivalent to Assistant Professor) at the School of Informatics at the University of Edinburgh. His work focuses on theoretical aspects of cryptography, including multi-party computation protocols, zero-knowledge proofs, and blockchain.

Talk title: The Communication Complexity of Oblivious Transfer

Abstract: Oblivious Transfer (OT) is the central primitive in the study of secure two-party computation; classical results in the area show that any secure two-party computation task can be realized from OT. However, until recently essentially all OT protocols (with very few exceptions) only achieved rate below 1/2. Here, the rate refers to the ratio between the communication size of the best insecure protocol and that of the protocol under consideration. The barrier at rate 1/2 is somewhat natural, as achieving OT with a rate above 1/2 implies highly desirable cryptographic concepts such as private information retrieval, which remain elusive from low-rate OT.

In this talk I will discuss a line of work which has led to communication-optimal OT protocols across a wide spectrum of assumptions and settings. Specifically, I will discuss the string-OT setting, the batch-OT setting as well as semi-honest security, statistical sender privacy and fully malicious security. A key concept pivotal to the development of communication-optimal OT is that of trapdoor hash functions, which have given rise to unexpected and compelling applications in their own right.

Bio: Nico Döttling is a tenured faculty at the Helmholtz Center for Information Security (CISPA) in Saarbrücken, where he leads a research group in the field of public-key cryptography and secure computation. After studying Computer Science at the Karlsruhe Institute of Technology (then Technical University of Karlsruhe), he finished his PhD in 2014 at the Karlsruhe Institute of Technology. His PhD thesis won the biennial Erika and Dr. Wolfgang Eichelberger Dissertation Award. After postdoctoral studies at Aarhus University and UC Berkeley, he joined Friedrich-Alexander-University Erlangen Nürnberg as an assistant professor in 2017 and CISPA as a tenure-track faculty in 2018. His research is currently supported by the European Union via an ERC Starting Grant for his project “Next-Generation Laconic Cryptography".

Talk title: Homomorphic Secret Sharing with Verifiable Evaluation

Abstract: A homomorphic secret sharing (HSS) scheme allows a client to delegate a computation to a group of untrusted servers while achieving input privacy as long as at least one server is honest. In recent years, many HSS schemes have been constructed that have, in turn, found numerous applications to cryptography. 

Prior work on HSS focuses on the setting where the servers are semi-honest. In this work we lift HSS to the setting of malicious evaluators. We propose the notion of *HSS with verifiable evaluation* (ve-HSS) that guarantees correctness of output *even when all the servers are corrupted*. ve-HSS retains all the attractive features of HSS and adds the new feature of succinct (public) verification of output. 

We present *black-box* constructions of ve-HSS by devising generic transformations for semi-honest HSS schemes (with negligible error). This provides a new non-interactive method for verifiable and private outsourcing of computation.

Bio: Aarushi Goel is a postdoctoral researcher in the Cryptography and Information Security Lab at NTT Research, mentored by Sanjam Garg. Previously, she was a Ph.D. student at Johns Hopkins University, where she was advised by Abhishek Jain. Her research interests span broadly across cryptography and related areas of security and theoretical computer science. 

Talk title: Practical Secure Machine Learning

Abstract: With the rise of data silos, it is becoming increasingly important to enable private data collaboration, i.e., securely computing on data owned by different entities without any exchange or sharing of data in the clear. While theoretically, secure multiparty computation (MPC) enables this scenario with strong formal security guarantees, its general application suffers from many challenges, namely, performance, scalability and ease-of-use. In my talk, I will primarily focus on computations occurring in collaborative machine learning, namely, ML inference, training and validation. Over the last decade, the crypto and security communities have worked hard to address these challenges for secure machine learning. In fact, one of our recent works shows that secure inference has reached a tipping point: latency of secure inference for certain model classes matches that of cleartext. In another work, we improve the latency and scalability of secure transformer inference by more than an order of magnitude and enable secure inference of GPT-2 model in 1.6 seconds. My talk will discuss these recent developments, how we get there and what problems remain.

Bio: Divya Gupta is a Principal Researcher at Microsoft Research India. Her research interest is cryptography and its applications to security and privacy. Currently her work at MSR focusses on secure multiparty computation and blockchains, and in particular, making cryptography practical, usable, and performant. She has published several papers in top computer science conferences such as Crypto, Eurocrypt, IEEE S&P, ACM CCS, OSDI, and so on and holds 3 US Patents. Before joining MSR, she was a postdoc at UC Berkeley hosted by Sanjam Garg. She completed her PhD at University of California at Los Angeles with Amit Sahai. Her PhD dissertation was recognized by the Dissertation Fellowship and the Dimitris N. Chorafas Dissertation Award, given for outstanding work in engineering sciences, medicine and the natural sciences. She got her bachelors and masters degree in Computer Science and Engineering from Indian Institute of Technology, Delhi.  

Talk title: Computation Efficient Structure-Aware PSI from Incremental Function Secret Sharing

Abstract: Structure-Aware Private Set Intersection (sa-PSI), recently introduced by Garimella et al. (Crypto'22), is a PSI variant where Alice's input set $S_A$ has a publicly known structure (for example, interval, ball or union of balls) and Bob's input $S_B$ is an unstructured set of elements. Prior work achieves sa-PSI where the communication cost only scales with the description size of $S_A$ instead of the set cardinality. However, the computation cost remains linear in the cardinality of $S_A$, which could be prohibitively large.

In this talk, we present a new semi-honest sa-PSI framework where both computation and communication costs only scale with the description size of $S_A$. Our main building block is a new primitive that we introduce called Incremental Boolean Function Secret Sharing (ibFSS), which is a generalization of FSS that additionally allows for evaluation on input prefixes. We formalize definitions and construct a weak ibFSS for a $d$-dimensional ball with $\ell_\infty$ norm, which may be of independent interest. Independently, we improve spatial hashing techniques (from prior work) when $S_A$ has structure union of $d$-dimensional balls in $(\{0,1\}^u)^d$, each of diameter $\delta$, from $\O(u \cdot d \cdot (\log \delta)^d)$ to $\O(\log \delta \cdot d)$ in terms of both computation and communication. Finally, we resolve several open questions from prior work, including handling a union of overlapping structures, enabling Bob to learn the intersection, and extending sa-PSI to functionalities like PSI-Cardinality and PSI-Sum of associated values.

Based on joint work with Gayathri Garimella and Benjamin Goff.

Bio: Peihan Miao is an assistant professor in the Department of Computer Science at Brown University. Her research interests lie broadly in cryptography, theory, and security, with a focus on secure multi-party computation. She received her PhD from the University of California, Berkeley in 2019. Before joining Brown, she had brief stints at the University of Illinois Chicago as an assistant professor and Visa Research as a staff research scientist. She is a recipient of a Meta Privacy Enhancing Technologies Award, Google Research Scholar Award, and Amazon Research Award.

Talk title: Distributed Discrete Logarithms and Applications, Part I / Part II

Abstract: In this two-parts talk we will introduce the "distributed discrete logarithm" problem (DDL) and present many of the exciting applications it has enabled in recent years. DDL is a crucial tool in recent share-conversion protocols and has enabled many exciting such as MPC with sub-linear complexity, homomorphic- and function secret-sharing, pseudorandom correlation generators, garbling, and more. We will give examples of DDL protocol from established assumptions, and dive into some of the applications.

Bio: Pierre Meyer is currently a Postdoc at Aarhus University, hosted by Claudio Orlandi. Previously, he completed his PhD at Reichman University and Université Paris Cité, advised by Elette Boyle and Geoffroy Couteau. His research mostly focuses on theoretical aspects of cryptography, and of MPC in particular.

Lawrence Roy is currently a postdoc at Aarhus University, Denmark. He completed his PhD at Oregon State University, advised by Mike Rosulek. His research interests include homomorphic secret sharing, oblivious transfer, and garbled circuits.

Talk title: On Broadcast and Identifiability in MPC

Abstract: Many existing deployments of Secure Multiparty Computation (MPC) protocols are susceptible to denial of service attacks unless they incorporate mechanisms to pinpoint cheating participants responsible for disruptions. However, identifying cheaters typically demands significant resources, which includes costly broadcast channels. Notably, use of broadcast is known to be necessary for unanimous identification of cheaters by all participants.

In this talk, we delve into the established correlations between the use of broadcast and identifiability within MPC protocols. Furthermore, we introduce a new notion of identifiability that does not require broadcast but nevertheless satisfies practical identifiability requirements.  Specifically, this notion enables an honest party to provably identify an attacker to any external auditor, even when the protocol operates solely over point-to-point channels. Additionally, our identification mechanism distinguishes between unresponsive participants and those actively deviating from the protocol, facilitating handling of such qualitative distinctions at higher logic levels. Finally, we demonstrate the application of this notion to a new honest majority ECDSA signing protocol that supports cheater identification.

Bio: Divya is currently an Assistant Professor at the University of Amsterdam, Netherlands. Prior to this, she was a postdoctoral researcher at the Aarhus Crypto group and completed her PhD at Indian Institute of Science, India. Her primary research interests include feasibility and efficiency of tasks related to secure MPC under various adversarial and network models. 

Talk title: Private Set Union (PSU)

Abstract: Private set intersection (PSI) and private set union (PSU) are two fundamental set operations with widespread applications in various privacy-sensitive contexts.  Over the last decade, a substantial body of research has focused on PSI, whereas PSU has received relatively little attention.  In this talk, I will review the existing literature on PSU protocols. Most recent PSU protocols have been tailored specifically for the two-party scenario, following the framework outlined by Kolesnikov et al. (Asiacrypt 2019) based on oblivious transfer (OT). Subsequently, I will present our new result on multi-party PSU (MPSU), enabling more than two parties to compute the union of their private datasets without revealing additional information. Our protocol avoids computationally expensive homomorphic operations or generic multi-party computation, thus providing an efficient solution for  MPSU. It  shows an improvement of up to $37.82\times$ in terms of running time and $389.85\times$ bandwidth cost compared to the existing state-of-the-art protocols.

Bio:  Ni Trieu is currently an Assistant Professor at Arizona State University (ASU). Her research interests lie in the area of cryptography and security, with a specific focus on secure computation and its applications such as private set operation, secure bio-computing. Her work has been published in top-tier Cryptography & Security conferences. She received my Ph.D. degree from Oregon State University. Before joining ASU, she was a postdoctoral researcher at UC Berkeley. 

Talk title: Achieving Asynchronous MPC with Linear Communication and Optimal Resilience

Abstract: Secure multiparty computation (MPC) allows a set of n parties to jointly compute a function over their private inputs. The seminal works of Ben-Or, Canetti and Goldreich [STOC '93] and Ben-Or, Kelmer and Rabin [PODC '94] settled the feasibility of MPC over asynchronous networks. Despite the significant line of work devoted to improving the communication complexity, current protocols with information-theoretic security and optimal resilience t<n/3 communicate \Omega(n^4C) field elements for a circuit with C multiplication gates. In contrast, synchronous MPC protocols with \Omega(nC) communication have long been known.

In this talk, I will introduce our recent progress that gives the first information-theoretic AMPC with communication complexity O(nC) field elements. Our construction is obtained from the following two results:

-       We first build an asynchronous complete secret-sharing (ACSS) protocol with linear communication complexity. ACSS allows a dealer to share a batch of Shamir sharings such that all parties eventually receive their shares. ACSS is an important building block in AMPC. We improve the previously best-known result by Choudhury and Patra [J. Cryptol '23], which requires O(n^3) elements per sharing, by a factor of n^2.

- We then provide a novel MPC protocol that makes black-box use of ACSS, where the cost per multiplication reduces to the cost of distributing a constant number of sharings via ACSS, improving a linear factor over the state of the art by Choudhury and Patra [IEEE Trans. Inf. Theory '17].

Bio: Yifan Song is an assistant professor at Tsinghua University. He received the Ph.D. degree from Carnegie Mellon University in 2022, advised by Prof. Vipul Goyal. Before that, he received the Bachelor degree from Yao Class at Tsinghua University in 2017. Yifan Song is generally interested in theoretical Cryptography and has a special focus on secure multiparty computation. He has published more than 10 papers in the top conferences of Cryptography. He was a committee member of Eurocrypt 2023 and PKC 2024, and served as an external reviewer for many top conferences in Cryptography.

Talk title: Sharing without Showing: Building Secure Collaborative Systems by Co-designing Systems and Cryptography

Abstract: The recent revolution in advanced data analytics and machine learning have made it possible to extract unprecedented value from user data. However, this comes at the cost of user privacy in many application workflows. In this talk, I will discuss some ideas around building systems that enable privacy-preserving computation via a co-design of systems and cryptography. In the first part of the talk, I will present Bolt (IEEE S&P 2024), a new system for privacy-preserving two-party inference for a large language model like BERT using secure multiparty computation (MPC). With our system, a user can safely outsource prediction to a third party without revealing their sensitive data and or learning about the third party’s proprietary model parameters. In the second part, I will talk about building systems for democratizing cryptography. In Silph (IEEE S&P 2023), we develop a framework that can automatically compile a program written in a high-level language to an optimized, hybrid MPC protocol that mixes multiple MPC primitives securely and efficiently. This makes it possible for any programmer with no expertise in cryptography to create efficient MPC protocols from scratch.

Bio: Wenting Zheng is an assistant professor in the Computer Science Department at CMU. Her research interests are in computer systems, security, and applied cryptography. She aims to bridge the gap between theory and practice through a co-design of cryptography and systems. She does so by building practical cryptosystems with provable security guarantees, designing novel cryptographic primitives and protocols, and building systems for democratizing and accelerating cryptography. She is a recipient of NSF CAREER Award, Google Research Scholar Award, Distinguished Paper Award at IEEE Euro S&P, IBM PhD Fellowship, and Berkeley Fellowship. She obtained her Ph.D. in EECS from UC Berkeley.