Valency Hub
alphaFeedback
PDF

WorksComputer Science

On the (Quantum) Communication Complexity of Secure MPC from a Random Oracle

Alexander Hoover, Giuseppe Persiano, Kevin Yeo

Published Fresh — added to the Hub within the last 30 daysv1106 min read

AI contributions
  • Claude
  • Gemini · multiple versions
  • Claude Fable 5.1 · bare
View details

Abstract

Information-theoretic MPC among nn parties with tt corruptions can securely evaluate a circuit CC with O(∣C∣⋅t/(n−t))O(|C| \cdot t/(n-t)) online communication in the preprocessing model and O(∣C∣⋅t/(n−2t))O(|C| \cdot t/(n-2t)) communication in the honest majority setting. Damgård, Larsen and Nielsen (CRYPTO 2019) showed that both communication bounds are tight for inner products. Fully homomorphic encryption and other assumptions known to imply public-key cryptography beat both communication bounds, but the communication complexity with symmetric-key cryptography alone is less understood. For MPC with preprocessing, we prove that the same Ω(∣C∣⋅t/(n−t))Ω(|C| \cdot t/(n-t)) lower bound holds in the random oracle model, so a random oracle cannot reduce the online communication. For honest majority MPC relative to a random oracle, we present an Ω(∣C∣)Ω(|C|) communication lower bound that is matched by a new construction for degree-2 polynomials (including inner products) when n=O(log⁡λ)n = O(\log λ), beating the information-theoretic bound. We also study quantum MPC. First, we prove that information-theoretic protocols with quantum communication (and preprocessing) cannot reduce communication compared to their classical counterparts. Furthermore, we extend our lower bound for MPC with preprocessing to protocols with a quantum-accessible random oracle, but use only classical communication. In contrast, with both quantum communication and a post-quantum one-way function, we present a simple two-party protocol that evaluates the two-party instance of these circuits with poly(λ,log⁡∣C∣)\mathrm{poly}(λ, \log |C|) communication, beating these lower bounds. Finally, such communication savings do not come for free. We prove that there exist circuits CC such that every blackbox protocol with o(∣C∣)o(|C|) quantum communication must perform Ω(∣C∣)Ω(|C|) cryptographic operations.

Introduction

Secure multi-party computation (MPC) is a well-studied problem in cryptography that considers n≥2n \ge2 parties whose goal is to securely evaluate some function that is represented as a circuit C. For security, the goal is to guarantee any subset of t<nt < n corrupted parties cannot learn any more information than may already be learned from the inputs and outputs of the corrupted parties. MPC is a core primitive for cryptography as it lies at the heart of practically-motivated privacy-preserving systems (including ad conversion [93], federated learning [31], inventory matching [122], password leak check [128] and telemetry gathering [45]) as well as being closely connected to other theoretical areas (such as circuit complexity [7], coding theory [91], communication complexity [10] and proof systems [95]).

A central problem for MPC is minimizing the communication complexity necessary to securely evaluate any circuit CC. In particular, one can consider the amount of additional communication cost necessary for secure evaluation of CC using MPC compared to plaintext solutions. Without security, a trivial protocol is for one party to send their input to another party that can compute the circuit locally. As a simple example, if we consider two-party MPC where one party has a much smaller input, then the plaintext solution has communication sublinear in the circuit size. Going back to MPC, a natural question is what are the settings and cryptographic assumptions where sublinear circuit communication (similar to the plaintext solution) is possible? Furthermore, one can also wonder in what MPC settings must the communication cost be linear (or even super-linear) in the circuit size. In our work, we will exclusively focus on circuits whose size is linear in the input size to avoid the more challenging question of whether super-linear circuits are required for specific problems (this remains a long-standing open problem in theoretical computer science).

Classical MPC. The communication complexity of MPC has been well-studied in a long line of works considering a wide range of settings and security properties (see [132, 84, 29, 39, 73] and references therein as some examples). For information-theoretically secure MPC (without any cryptographic assumptions) in the honest majority setting, there have been many constructions that achieve O~(∣C∣⋅t/(n−2t))\widetilde{O}(|C| \cdot t/(n-2t)) communication for any n>2tn > 2t (including [64, 59, 80, 79, 41, 27, 85]). It is well known that dishonest majority MPC requires computational assumptions [29, 48]. Nevertheless, one can consider the preprocessing model where parties may communicate to generate correlated randomness prior to receiving their inputs. Using the preprocessing, one can construct MPC protocols that achieve information-theoretically secure online phases with O~(∣C∣⋅t/(n−t))\widetilde{O}(|C| \cdot t/(n-t)) online communication for any n>tn > t (see [69, 21, 92 KO S16, 107, 86, 70, 37] as examples). However, all these dishonest majority MPC protocols with information-theoretically secure online phases require a secure preprocessing phase that must be instantiated with computational assumptions (or even stronger requirements such as trusted setup). Damgård, Larsen and Nielsen [61] proved communication lower bounds for information-theoretic MPC showing that the above communication costs are tight. In particular, they show that information-theoretically secure evaluation of the inner product problem requires communication Ω(∣C∣⋅t/(n−2t))\Omega(|C| \cdot t/(n-2t)) in the honest majority setting (i.e., n>2tn > 2t) and online communication Ω(∣C∣⋅t/(n−t))\Omega(|C| \cdot t/(n-t)) in the preprocessing model with n>tn > t.

To contrast the above results, one can also consider building MPC using stronger cryptographic assumptions with the goal of reducing communication costs. For example, if one assumes fully homomorphic encryption [74], it is trivial to construct an MPC protocol whose communication cost is nearly identical to the plaintext solution (ignoring security parameter factors incurred by encryption) by having one party encrypt their input and send it to the other party for local circuit evaluation. However, all such homomorphic encryption schemes require computational assumptions that are known to imply public-key cryptography. Finally, several prior works (such as [92, 26 Co u19, 53 DIJ L23, 9]) obtain o(∣C∣)o(|C|) communication for circuits that are super-linear in the input size, but all of them have communication linear in the input size and so do not help for the linear-size circuits we consider (see § 3).

Given the above state of affairs for MPC, it leaves open the question of whether one can improve the communication costs of MPC using symmetric-key cryptography. Song and Ye [127] show that, with security parameter λ\lambda, one can construct honest majority MPC with n=2t+O(1)n = 2t + O(1) communicating O(∣C∣⋅(log⁡q+λ))O(|C| \cdot(\log q + \lambda)) field elements for fields of order q≥2λq \ge2^\lambda using a random oracle. For Boolean circuits, this was further improved to a constant round protocol with O(∣C∣λ)O(|C|\lambda) communication in [81]. Both these protocols using random oracles achieve communication independent of nn and tt. So, they obtain communication asymptotically impossible for information-theoretic MPC with n=2t+O(1)n = 2t + O(1) for large enough t=ω(λ)t = \omega(\lambda). However, these communication improvements using random oracles have been limited to the honest majority setting. For dishonest majority MPC, 1-out-of-2 oblivious transfer is complete [101, 96, 32, 87] and cannot be built from only a random oracle [97], so we consider the online communication of MPC with preprocessing, where the online phase may use only the random oracle but the preprocessing may use other computational assumptions. This leaves the following question.

What is the communication complexity of honest majority MPC with a random oracle, and can a random oracle reduce the online communication of MPC with preprocessing?

MPC with Quantum Resources. Next, we can consider the MPC problem of classical functionalities where parties have access to quantum computation (and communication). It is already well known that (post-quantum) one-way functions substantially improve MPC with quantum communication. In particular, quantum oblivious transfer (OT) may be built from post-quantum one-way functions [82, 17]. In turn, quantum OT can be used to build MPC with quantum communication for classical functionalities using prior works that build protocols from blackbox OT [84, 101]. As an immediate result, it is possible to construct dishonest majority MPC with quantum communication using only one-way functions [82, 17]. In fact, this can also be extended to enable MPC for quantum functionalities using MPC for classical functionalities [55]. In contrast, classical dishonest majority MPC requires public-key cryptography, as discussed above.

While quantum communication is known to reduce the computational assumptions required for dishonest majority MPC, the communication complexity remains the same. In particular, these MPC protocols with quantum communication still follow the same template as used for building classical MPC from OT [84, 101]. Thus, they incur the same communication costs (modulo the different communication costs of the underlying quantum and classical OT). This leaves the following question.

Can quantum communication or quantum access to a one-way function reduce the communication of MPC below the information-theoretic lower bounds?

Our Contributions

In this work, we present results for both classical MPC as well as MPC with quantum computation (and communication). Throughout our work, we will consider semi-honest security. For our lower bounds, we will consider weaker adversaries with non-adaptive corruptions and protocols with arbitrary preprocessing algorithms that may use strong computational assumptions (or even unbounded computational power). We only restrict the protocol such that the only cryptography used in the online phase is the random oracle. Furthermore, our lower bounds only assume the adversary observes the online phase. These restrictions only make our lower bounds stronger. For our constructions, we prove them adaptively secure.

Classical MPC. Our main goal is to understand the impact of symmetric-key cryptography on the communication complexity of MPC. We start by studying MPC with preprocessing with t<nt < n, including the dishonest majority setting. As a reminder, dishonest majority MPC implies OT that cannot be built in a blackbox way from one-way functions [97]. However, one can consider MPC where OT is used only in the preprocessing stage. Then, is it possible to use one-way functions to reduce the online communication of MPC compared to MPC protocols with information-theoretically secure online phases? We show that this is impossible in general with the following lower bound, which matches the known lower bound for MPC with preprocessing that obtain information-theoretically secure online phases.

Theorem 1.1 (Informal). For every field Fq\mathbb{F}_q of size qq, there exists a circuit CC over Fq\mathbb{F}_q such that every nn-party MPC with preprocessing using a random oracle that securely evaluates CC against t<nt < n corruptions must have Ω(∣C∣log⁡q⋅t/(n−t))\Omega(|C|\log q \cdot t/(n-t)) online communication.

As a technical lemma for the above lower bound, we also prove a linear lower bound on the communication of single-server PIR with correlated randomness in the random oracle model. In particular, this shows that correlated randomness cannot help reduce communication in single-server PIR. Without it, any single-server PIR whose total communication is below the database size yields oblivious transfer by a blackbox reduction [63], so none exists relative to a random oracle [97, 33]; blackbox constructions from trapdoor permutations likewise need the server to send Ω(N)\Omega(N) bits [88]. To our knowledge, the bound with correlated randomness was not previously known, as the reduction to OT fails there: there exist constructions for OT with correlated randomness (such as OT extension) that only use one-way functions during online evaluation [23, 94]. As a note, the correlated randomness shared between the client and server must be independent of the database (corresponding to the preprocessing model of MPC). If the correlated randomness may depend on the server’s database, there are known single-server PIR constructions with sublinear communication using one-way functions [135 RMS24, 89, 131].

Theorem 1.2 (Informal). There does not exist a single-server PIR with correlated randomness in the random oracle model for a database with NN bb-bit entries using o(N⋅b)o(N \cdot b) communication.

In contrast, as discussed above, random oracles already reduce the communication of honest majority MPC with n=2t+O(1)n = 2t + O(1) to O(∣C∣⋅λ)O(|C| \cdot\lambda) bits for Boolean circuits [81] and O(∣C∣(log⁡q+λ))O(|C|(\log q + \lambda)) field elements for q≥2q \ge2 [127], independent of nn and tt and, thus, below the information-theoretic Ω(∣C∣⋅t/(n−2t))\Omega(|C| \cdot t/(n - 2t)) bound [61] when t=ω(λ)t = \omega(\lambda). Note, our lower bound in Theorem 1.1 for the setting of n=2t+O(1)n = 2t + O(1) states that Ω(∣C∣log⁡q)\Omega(|C| \log q) communication is required for circuits over Fq\mathbb{F}_q. We actually present a slightly stronger lower bound that holds for all values of n>2tn > 2t.

Theorem 1.3 (Informal). For every field Fq\mathbb{F}_q of size qq, there exists a circuit CC over Fq\mathbb{F}_q such that every nn-party honest majority MPC with preprocessing using a random oracle that securely evaluates CC against t<n/2t < n/2 non-adaptive corruptions must have Ω(∣C∣log⁡q)\Omega(|C| \log q) online communication.

As a result, there remains a multiplicative gap of Ω(λ)\Omega(\lambda) between the best constructions and our lower bound. Prior works have shown that this O(λ)O(\lambda) factor per gate is not required, but only in orthogonal settings. Recent work [115] for garbled circuits shows that O(∣C∣log⁡λ)O(|C| \log\lambda) communication is possible for two-party computation using OT correlations and a random oracle against unbounded adversaries that make poly⁡(λ)\operatorname{poly}(\lambda) random oracle queries. However, generalizing to nn-party protocols using standard frameworks [34, 57] would incur an additional multiplicative O(n)O(n) factor. It is also possible to obtain O(∣C∣)O(|C|) communication for Boolean circuits with suboptimal honest majority corruption thresholds of t=(1/2−η)nt = (1/2 - \eta)n for constant 0<η<1/20 < \eta< 1/2 as shown in [ZYFZ26]. However, this simply matches the prior information-theoretic Ω(∣C∣⋅t/(n−2t))=Ω(∣C∣)\Omega(|C| \cdot t/(n - 2t)) = \Omega(|C|) lower bound in [61]. Using preprocessing, one can construct protocols for Boolean circuits with O(∣C∣)O(|C|) online communication assuming exponentially-sized preprocessing [92] or the class of layered circuits [54].4 Finally, O(∣C∣)O(|C|) communication is possible if we assume circuits with no multiplications as linearly homomorphic secret sharing schemes enable addition for free [29] whereas protocols for constant-depth Boolean circuits achieve O(∣C∣⋅poly⁡(log⁡(∣C∣)))O(|C| \cdot\operatorname{poly}(\log(|C|))) communication [30].

To our knowledge, it remains open whether one can obtain O(∣C∣log⁡q)O(|C| \log q) communication using random oracles for circuits with any multiplications in the honest majority setting n=2t+O(1)n = 2t + O(1) without preprocessing. We show that there exists an MPC protocol that securely evaluates degree-2 functions over Fq\mathbb{F}_q (equivalently, circuits with multiplicative depth 1) with O(∣C∣log⁡q)O(|C| \log q) communication matching our lower bound.

Theorem 1.4 (Informal). For n=O(log⁡λ)n = O(\log\lambda) and any field Fq\mathbb{F}_q of size qq, there exists an nn-party protocol using a random oracle that securely evaluates any circuit CC over Fq\mathbb{F}_q for a degree-2 function in which each multiplication gate reads the inputs of O(1)O(1) parties, secure against t<n/2t < n/2 adaptive corruptions, with O(∣C∣log⁡q)O(|C| \log q) communication.

The above shows that our lower bound from Theorem 1.3 in the honest majority setting is asymptotically tight for the class of degree-2 functions (or circuits with multiplicative depth 1). Our construction using random oracles obtains a provable communication gap compared to its information-theoretic counterpart with n=2t+O(1)n = 2t + O(1) for any super-constant number of parties t=ω(1)t = \omega(1) whereas prior works [127, 81] required larger t=ω(λ)t = \omega(\lambda). As a caveat, our construction’s communication grows exponentially in nn and, thus, only obtains O(∣C∣log⁡q)O(|C| \log q) communication when n=O(log⁡λ)n = O(\log\lambda).

Furthermore, we note that the inner product functionality used in our lower bounds as well as the prior information-theoretic ones in [61] may be computed using degree-2 functions. In fact, our construction is inspired by constructing a low-communication protocol for a three-party function considered in prior lower bounds [68, 61]. We leave it open whether one can extend our O(∣C∣log⁡q)O(|C| \log q) communication protocol to arbitrary circuits or obtain a higher ω(∣C∣log⁡q)\omega(|C| \log q) communication lower bound when assuming no preprocessing. If we wish to obtain higher ω(∣C∣log⁡q)\omega(|C| \log q) communication lower bounds for honest majority MPC with n=O(log⁡λ)n = O(\log\lambda), then we need to consider polynomials of degree 3 or more. However, the required proof techniques would need to understand the circuit structure that leads to much harder long-standing problems in theoretical computer science about circuit depths.

Quantum MPC. We also study MPC for classical functionalities where parties have access to quantum computation. First, we consider whether quantum communication alone may be useful to reduce the communication costs of information-theoretic MPC. In particular, we show that this is impossible:

Theorem 1.5 (Informal). For every field Fq\mathbb{F}_q of size qq, there exists a circuit CC over Fq\mathbb{F}_q such that every statistically secure nn-party MPC with quantum communication that securely evaluates CC against tt corruptions must have:

  1. Ω(∣C∣log⁡q⋅t/(n−t))\Omega(|C| \log q \cdot t/(n-t)) online communication in the preprocessing model, even with quantum preprocessing, for any n>tn > t.

  1. Ω(∣C∣log⁡q⋅t/(n−2t))\Omega(|C| \log q \cdot t/(n-2t)) communication without preprocessing in the honest majority setting for any n>2tn > 2t.5

The above lower bounds match the known communication complexity of information-theoretic MPC with classical communication in [61]. In other words, quantum communication (and computation) does not immediately help reduce communication costs for MPC.

Next, we consider whether a quantum-accessible random oracle could help reduce communication costs. As our next result, we show this is not the case for MPC with quantum computation and classical communication (QCCC). Similar to our above classical lower bound, we show that a quantum-accessible random oracle does not help reduce the communication costs in the MPC with preprocessing model.

Theorem 1.6 (Informal). Assuming there does not exist a secure two-party key agreement with classical communication using a quantum-accessible random oracle, for every field Fq\mathbb{F}_q of size qq, there exists a circuit CC over Fq\mathbb{F}_q such that every nn-party MPC with classical communication and preprocessing using a quantum-accessible random oracle that securely evaluates CC against t<nt < n corruptions must have Ω(∣C∣log⁡q⋅t/(n−t))\Omega(|C| \log q \cdot t/(n-t)) online communication.

As a note, our above lower bound only applies to MPC protocols where the preprocessing step produces classical outputs for each party. This is required as we are focusing on MPC with classical online communication as quantum teleportation enables simulating quantum online communication using quantum preprocessing and classical online communication [13]. Furthermore, we only consider lower bounds for MPC with preprocessing and not the honest majority setting as our O(∣C∣)O(|C|) classical communication construction in Theorem 1.4 with n=2t+O(1)n = 2t + O(1) and n=O(log⁡λ)n = O(\log\lambda) can also be made secure against adversaries with a quantum-accessible random oracle.

We note that there have been several recent works proving impossibilities for key agreement using classical communication with a quantum-accessible random oracle that make our lower bound unconditional in some settings. For MPC protocols with perfect correctness, our lower bound follows from the impossibility of perfectly correct key agreement [111]. In the setting of MPC with non-zero error, our lower bounds also follow if we make certain restrictions on the quantum queries to the random oracle as done for prior impossibility results for key agreement proved in [109, 104]. Using the contrapositive of our theorem, any QCCC MPC protocol with preprocessing that beats this bound yields a QCCC key agreement in the quantum-accessible random oracle model, so reducing the communication of QCCC MPC would require building such key agreement.

Next, we consider MPC with quantum communication (QCQC) where all parties have quantum access to a random oracle. In this case, we show that it is indeed possible to reduce the communication costs using a post-quantum one-way function. We present a simple two-party MPC protocol built on the QPIR protocol in [ABG26] whose communication is smaller than all the prior lower bounds in certain settings:

Theorem 1.7 (Informal). Consider any circuit CC for two parties with input bit sizes of s1≤s2s_1 \le s_2 and mm output bits. Assuming the existence of a post-quantum one-way function, there exists a two-party MPC protocol with quantum communication implementing CC with communication O(λ⋅m⋅s1)+poly⁡(λ)O(\lambda\cdot m \cdot s_1) + \operatorname{poly}(\lambda), independent of ∣C∣|C| and s2s_2, and computation 2s1⋅poly⁡(λ,∣C∣)2^{s_1} \cdot\operatorname{poly}(\lambda, |C|).

We note that the communication cost of the above two-party protocol essentially matches the trivial FHE solution where one party sends their input encrypted to the other party. For the setting where one party’s input is smaller s1≪s2s_1 \ll s_2, we immediately obtain an o(∣C∣)o(|C|) communication protocol as ∣C∣=Ω(s1+s2)|C| = \Omega(s_1 + s_2). As a caveat, our construction requires computation exponential in the smaller party’s input size. However, we obtain polynomial time protocols if the smaller party’s input size is s1=O(log⁡λ)s_1 = O(\log\lambda). Moreover, the two-party instance of the circuit used in our lower bounds, in which both inputs are long, also has a protocol with poly⁡(λ,log⁡∣C∣)\operatorname{poly}(\lambda, \log|C|) qubits of communication, as each party only needs to retrieve one bit of the other’s input. Note, prior classical MPC protocols that could obtain o(∣C∣)o(|C|) communication [54] including those with exponential time [24, 119] or preprocessing [92] have communication costs linear in the total input size. Thus, they use Ω(∣C∣)\Omega(|C|) communication for linear size circuits. In contrast, our quantum protocol obtains communication sublinear in the input size using a one-way function (without any preprocessing). Finally, our above two-party protocol can be easily adapted to the setting of quantum preprocessing and classical online communication using quantum teleportation, showing that the restriction to classical preprocessing in our QCCC lower bound is necessary.

Lastly, we explore whether it is possible to also reduce the computational costs of MPC protocols using quantum communication. Even though our above protocol obtains o(∣C∣)o(|C|) communication, we still require at least Ω(∣C∣)\Omega(|C|) computation across both parties (and larger in many settings). In fact, our protocol requires a large number of one-way function invocations. We show that this is inherent by showing that any small communication protocol requires performing a large number of cryptographic operations.

References

  1. [1]Dorit Aharonov, Zvika Brakerski, Kai-Min Chung, Ayal Green, Ching-Yi Lai, and Or Sattath. On quantum advantage in information theoretic single-server PIR. In Yuval Ishai and Vincent Rijmen, editors, Advances in Cryptology – EUROCRYPT 2019, Part III, volume 11478 of Lecture Notes in Computer Science, pages 219–246, Darmstadt, Germany, May 19–23, 2019. Springer, Cham, Switzerland.arxiv.org/abs/1902.09768
  2. [3]Benny Applebaum, Zvika Brakerski, and Rotem Tsabary. Degree 2 is complete for the round-complexity of malicious MPC. In Yuval Ishai and Vincent Rijmen, editors, Advances in Cryptology – EUROCRYPT 2019, Part II, volume 11477 of Lecture Notes in Computer Science, pages 504–531, Darmstadt, Germany, May 19–23, 2019. Springer, Cham, Switzerland.DOI
  3. [5]Carlos Aguilar-Melchor, Philippe Gaborit, and Javier Herranz. Additively homomorphic encryption with d-operand multiplications. In Tal Rabin, editor, Advances in Cryptology – CRYPTO 2010, volume 6223 of Lecture Notes in Computer Science, pages 138–154, Santa Barbara, CA, USA, August 15–19, 2010. Springer Berlin Heidelberg, Germany.DOI
  4. [6]Andris Ambainis, Mike Hamburg, and Dominique Unruh. Quantum security proofs using semi-classical oracles. In Alexandra Boldyreva and Daniele Micciancio, editors, Advances in Cryptology – CRYPTO 2019, Part II, volume 11693 of Lecture Notes in Computer Science, pages 269–295, Santa Barbara, CA, USA, August 18–22, 2019. Springer, Cham, Switzerland.DOI
  5. [7]Benny Applebaum, Yuval Ishai, and Eyal Kushilevitz. Cryptography in NC⁰. In 45th Annual Symposium on Foundations of Computer Science, pages 166–175, Rome, Italy, October 17–19, 2004. IEEE Computer Society Press.
  6. [8]Gilad Asharov and Yehuda Lindell. A full proof of the BGW protocol for perfectly secure multiparty computation. Journal of Cryptology, 30(1):58–151, January 2017.
  7. [9]Damiano Abram, Lawrence Roy, and Peter Scholl. Succinct homomorphic secret sharing. In Marc Joye and Gregor Leander, editors, Advances in Cryptology – EUROCRYPT 2024, Part VI, volume 14656 of Lecture Notes in Computer Science, pages 301–330, Zurich, Switzerland, May 26–30, 2024. Springer, Cham, Switzerland.DOI
  8. [10]Benny Applebaum and Prashant Nalini Vasudevan. Placing conditional disclosure of secrets in the communication complexity universe. Journal of Cryptology, 34(2):11, April 2021.DOI
  9. [11]Charles H. Bennett and Gilles Brassard. Quantum cryptography: Public key distribution and coin tossing. In Proceedings of the IEEE International Conference on Computers, Systems and Signal Processing, pages 175–179, Bangalore, India, 1984. Reprinted in Theoretical Computer Science 560 (2014), 7–11.
  10. [12]Âmin Baumeler and Anne Broadbent. Quantum private information retrieval has linear communication complexity. Journal of Cryptology, 28(1):161–175, January 2015.DOI
  11. [13]Charles H. Bennett, Gilles Brassard, Claude Crépeau, Richard Jozsa, Asher Peres, and William K. Wootters. Teleporting an unknown quantum state via dual classical and Einstein-Podolsky-Rosen channels. Physical Review Letters, 70(13):1895–1899, 1993.pubmed.ncbi.nlm.nih.gov/10053414
  12. [15]Elette Boyle, Geoffroy Couteau, Niv Gilboa, Yuval Ishai, Lisa Kohl, and Peter Scholl. Correlated pseudorandom functions from variable-density LPN. In 61st Annual Symposium on Foundations of Computer Science, pages 1069–1080, Durham, NC, USA, November 16–19, 2020. IEEE Computer Society Press.DOI
  13. [16]Elette Boyle, Geoffroy Couteau, Niv Gilboa, and Yuval Ishai. Compressing vector OLE. In David Lie, Mohammad Mannan, Michael Backes, and XiaoFeng Wang, editors, ACM CCS 2018: 25th Conference on Computer and Communications Security, pages 896–912, Toronto, ON, Canada, October 15–19, 2018. ACM Press.DOI
  14. [17]James Bartusek, Andrea Coladangelo, Dakshita Khurana, and Fermi Ma. One-way functions imply secure computation in a quantum world. In Tal Malkin and Chris Peikert, editors, Advances in Cryptology – CRYPTO 2021, Part I, volume 12825 of Lecture Notes in Computer Science, pages 467–496, Virtual Event, August 16–20, 2021. Springer, Cham, Switzerland.arxiv.org/abs/2011.13486
  15. [18]Elette Boyle, Geoffroy Couteau, and Pierre Meyer. Sublinear secure computation from new assumptions. In Eike Kiltz and Vinod Vaikuntanathan, editors, TCC 2022: 20th Theory of Cryptography Conference, Part II, volume 13748 of Lecture Notes in Computer Science, pages 121–150, Chicago, IL, USA, November 7–10, 2022. Springer, Cham, Switzerland.DOI
  16. [19]Elette Boyle, Geoffroy Couteau, and Pierre Meyer. Sublinear-communication secure multiparty computation does not require FHE. In Carmit Hazay and Martijn Stam, editors, Advances in Cryptology – EUROCRYPT 2023, Part II, volume 14005 of Lecture Notes in Computer Science, pages 159–189, Lyon, France, April 23–27, 2023. Springer, Cham, Switzerland.DOI
  17. [20]Dan Boneh, Özgür Dagdelen, Marc Fischlin, Anja Lehmann, Christian Schaffner, and Mark Zhandry. Random oracles in a quantum world. In Dong Hoon Lee and Xiaoyun Wang, editors, Advances in Cryptology – ASIACRYPT 2011, volume 7073 of Lecture Notes in Computer Science, pages 41–69, Seoul, South Korea, December 4–8, 2011. Springer Berlin Heidelberg, Germany.
  18. [21]Rikke Bendlin, Ivan Damgård, Claudio Orlandi, and Sarah Zakarias. Semi-homomorphic encryption and multiparty computation. In Kenneth G. Paterson, editor, Advances in Cryptology – EUROCRYPT 2011, volume 6632 of Lecture Notes in Computer Science, pages 169–188, Tallinn, Estonia, May 15–19, 2011. Springer Berlin Heidelberg, Germany.
  19. [22]Donald Beaver. Efficient multiparty protocols using circuit randomization. In Joan Feigenbaum, editor, Advances in Cryptology – CRYPTO’91, volume 576 of Lecture Notes in Computer Science, pages 420–432, Santa Barbara, CA, USA, August 11–15, 1992. Springer Berlin Heidelberg, Germany.
  20. [23]Donald Beaver. Correlated pseudorandomness and the complexity of private computations. In 28th Annual ACM Symposium on Theory of Computing, pages 479–488, Philadelphia, PA, USA, May 22–24, 1996. ACM Press.DOI
  21. [24]Donald Beaver, Joan Feigenbaum, Joe Kilian, and Phillip Rogaway. Security with low communication overhead. In Alfred J. Menezes and Scott A. Vanstone, editors, Advances in Cryptology – CRYPTO’90, volume 537 of Lecture Notes in Computer Science, pages 62–76, Santa Barbara, CA, USA, August 11–15, 1991. Springer Berlin Heidelberg, Germany.
  22. [25]Elette Boyle, Niv Gilboa, and Yuval Ishai. Function secret sharing. In Elisabeth Oswald and Marc Fischlin, editors, Advances in Cryptology – EUROCRYPT 2015, Part II, volume 9057 of Lecture Notes in Computer Science, pages 337–367, Sofia, Bulgaria, April 26–30, 2015. Springer Berlin Heidelberg, Germany.
  23. [26]Elette Boyle, Niv Gilboa, and Yuval Ishai. Breaking the circuit size barrier for secure computation under DDH. In Matthew Robshaw and Jonathan Katz, editors, Advances in Cryptology – CRYPTO 2016, Part I, volume 9814 of Lecture Notes in Computer Science, pages 509–539, Santa Barbara, CA, USA, August 14–18, 2016. Springer Berlin Heidelberg, Germany.DOI
  24. [27]Gabrielle Beck, Aarushi Goel, Abhishek Jain, and Gabriel Kaptchuk. Order-C secure multiparty computation for highly repetitive circuits. In Anne Canteaut and François-Xavier Standaert, editors, Advances in Cryptology – EUROCRYPT 2021, Part II, volume 12697 of Lecture Notes in Computer Science, pages 663–693, Zagreb, Croatia, October 17–21, 2021. Springer, Cham, Switzerland.
  25. [28]Dan Boneh, Eu-Jin Goh, and Kobbi Nissim. Evaluating 2-DNF formulas on ciphertexts. In Joe Kilian, editor, TCC 2005: 2nd Theory of Cryptography Conference, volume 3378 of Lecture Notes in Computer Science, pages 325–341, Cambridge, MA, USA, February 10–12, 2005. Springer Berlin Heidelberg, Germany.
  26. [29]Michael Ben-Or, Shafi Goldwasser, and Avi Wigderson. Completeness theorems for non-cryptographic fault-tolerant distributed computation (extended abstract). In 20th Annual ACM Symposium on Theory of Computing, pages 1–10, Chicago, IL, USA, May 2–4, 1988. ACM Press.
  27. [30]Omer Barkol and Yuval Ishai. Secure computation of constant-depth circuits with applications to database search problems. In Victor Shoup, editor, Advances in Cryptology – CRYPTO 2005, volume 3621 of Lecture Notes in Computer Science, pages 395–411, Santa Barbara, CA, USA, August 14–18, 2005. Springer Berlin Heidelberg, Germany.DOI
  28. [31]Keith Bonawitz, Vladimir Ivanov, Ben Kreuter, Antonio Marcedone, H. Brendan McMahan, Sarvar Patel, Daniel Ramage, Aaron Segal, and Karn Seth. Practical secure aggregation for privacy-preserving machine learning. In Bhavani M. Thuraisingham, David Evans, Tal Malkin, and Dongyan Xu, editors, ACM CCS 2017: 24th Conference on Computer and Communications Security, pages 1175–1191, Dallas, TX, USA, October 31 – November 2, 2017. ACM Press.DOI
  29. [32]Fabrice Benhamouda and Huijia Lin. k-round multiparty computation from k-round oblivious transfer via garbled interactive circuits. In Jesper Buus Nielsen and Vincent Rijmen, editors, Advances in Cryptology – EUROCRYPT 2018, Part II, volume 10821 of Lecture Notes in Computer Science, pages 500–532, Tel Aviv, Israel, April 29 – May 3, 2018. Springer, Cham, Switzerland.DOI
  30. [33]Boaz Barak and Mohammad Mahmoody-Ghidary. Merkle puzzles are optimal - an O(n²)-query attack on any key exchange from a random oracle. In Shai Halevi, editor, Advances in Cryptology – CRYPTO 2009, volume 5677 of Lecture Notes in Computer Science, pages 374–390, Santa Barbara, CA, USA, August 16–20, 2009. Springer Berlin Heidelberg, Germany.DOI
  31. [34]Donald Beaver, Silvio Micali, and Phillip Rogaway. The round complexity of secure protocols (extended abstract). In 22nd Annual ACM Symposium on Theory of Computing, pages 503–513, Baltimore, MD, USA, May 14–16, 1990. ACM Press.
  32. [35]Mihir Bellare and Phillip Rogaway. Random oracles are practical: A paradigm for designing efficient protocols. In Dorothy E. Denning, Raymond Pyle, Ravi Ganesan, Ravi S. Sandhu, and Victoria Ashby, editors, ACM CCS 93: 1st Conference on Computer and Communications Security, pages 62–73, Fairfax, Virginia, USA, November 3–5, 1993. ACM Press.
  33. [36]Charles H. Bennett and Stephen J. Wiesner. Communication via one- and two-particle operators on Einstein-Podolsky-Rosen states. Physical Review Letters, 69(20):2881–2884, 1992.pubmed.ncbi.nlm.nih.gov/10046665
  34. [37]Alexander Bienstock and Kevin Yeo. Weakly super-invertible matrices and constant communication dishonest majority MPC. In Serge Fehr and Pierre-Alain Fouque, editors, Advances in Cryptology – EUROCRYPT 2025, Part V, volume 15605 of Lecture Notes in Computer Science, pages 421–452, Madrid, Spain, May 4–8, 2025. Springer, Cham, Switzerland.DOI
  35. [38]Ran Canetti. Security and composition of multiparty cryptographic protocols. Journal of Cryptology, 13(1):143–202, January 2000.
  36. [39]David Chaum, Claude Crépeau, and Ivan Damgård. Multiparty unconditionally secure protocols (extended abstract). In 20th Annual ACM Symposium on Theory of Computing, pages 11–19, Chicago, IL, USA, May 2–4, 1988. ACM Press.DOI
  37. [40]Pierre Charbit, Geoffroy Couteau, Pierre Meyer, and Reza Naserasr. A note on low-communication secure multiparty computation via circuit depth-reduction. In Elette Boyle and Mohammad Mahmoody, editors, TCC 2024: 22nd Theory of Cryptography Conference, Part IV, volume 15367 of Lecture Notes in Computer Science, pages 167–199, Milan, Italy, December 2–6, 2024. Springer, Cham, Switzerland.DOI
  38. [41]Ignacio Cascudo, Ronald Cramer, Chaoping Xing, and Chen Yuan. Amortized complexity of information-theoretically secure MPC revisited. In Hovav Shacham and Alexandra Boldyreva, editors, Advances in Cryptology – CRYPTO 2018, Part III, volume 10993 of Lecture Notes in Computer Science, pages 395–426, Santa Barbara, CA, USA, August 19–23, 2018. Springer, Cham, Switzerland.DOI
  39. [42]Ran Canetti, Ivan Damgård, Stefan Dziembowski, Yuval Ishai, and Tal Malkin. On adaptive vs. non-adaptive security of multiparty protocols. In Birgit Pfitzmann, editor, Advances in Cryptology – EUROCRYPT 2001, volume 2045 of Lecture Notes in Computer Science, pages 262–279, Innsbruck, Austria, May 6–10, 2001. Springer Berlin Heidelberg, Germany.
  40. [43]Ronald Cramer, Ivan Damgård, and Yuval Ishai. Share conversion, pseudorandom secret-sharing and applications to secure computation. In Joe Kilian, editor, TCC 2005: 2nd Theory of Cryptography Conference, volume 3378 of Lecture Notes in Computer Science, pages 342–362, Cambridge, MA, USA, February 10–12, 2005. Springer Berlin Heidelberg, Germany.DOI
  41. [44]Ronald Cramer, Serge Fehr, Yuval Ishai, and Eyal Kushilevitz. Efficient multi-party computation over rings. In Eli Biham, editor, Advances in Cryptology – EUROCRYPT 2003, volume 2656 of Lecture Notes in Computer Science, pages 596–613, Warsaw, Poland, May 4–8, 2003. Springer Berlin Heidelberg, Germany.
  42. [45]Henry Corrigan-Gibbs and Dan Boneh. Prio: Private, robust, and scalable computation of aggregate statistics. In 14th USENIX symposium on networked systems design and implementation (NSDI 17), pages 259–282, 2017.
  43. [46]Henry Corrigan-Gibbs, Alexandra Henzinger, and Dmitry Kogan. Single-server private information retrieval with sublinear amortized time. In Orr Dunkelman and Stefan Dziembowski, editors, Advances in Cryptology – EUROCRYPT 2022, Part II, volume 13276 of Lecture Notes in Computer Science, pages 3–33, Trondheim, Norway, May 30 – June 3, 2022. Springer, Cham, Switzerland.
  44. [48]Benny Chor and Eyal Kushilevitz. A zero-one law for Boolean privacy (extended abstract). In 21st Annual ACM Symposium on Theory of Computing, pages 62–72, Seattle, WA, USA, May 15–17, 1989. ACM Press.
  45. [49]Benny Chor and Eyal Kushilevitz. A communication-privacy tradeoff for modular addition. Information Processing Letters, 45(4):205–210, 1993.DOI
  46. [50]Henry Corrigan-Gibbs and Dmitry Kogan. Private information retrieval with sublinear online time. In Anne Canteaut and Yuval Ishai, editors, Advances in Cryptology – EUROCRYPT 2020, Part I, volume 12105 of Lecture Notes in Computer Science, pages 44–75, Zagreb, Croatia, May 10–14, 2020. Springer, Cham, Switzerland.
  47. [51]Geoffroy Couteau and Naman Kumar. 10-party sublinear secure computation from standard assumptions. In Leonid Reyzin and Douglas Stebila, editors, Advances in Cryptology – CRYPTO 2024, Part IX, volume 14928 of Lecture Notes in Computer Science, pages 39–73, Santa Barbara, CA, USA, August 18–22, 2024. Springer, Cham, Switzerland.DOI
  48. [52]Geoffroy Couteau, Naman Kumar, and Xiaxi Ye. Multiparty homomorphic secret sharing and more from LPN and MQ. In Benny Applebaum and Huijia (Rachel) Lin, editors, TCC 2025: 23rd Theory of Cryptography Conference, Part II, volume 16269 of Lecture Notes in Computer Science, pages 498–530, Aarhus, Denmark, December 1–5, 2025. Springer, Cham, Switzerland.DOI
  49. [53]Geoffroy Couteau and Pierre Meyer. Breaking the circuit size barrier for secure computation under quasi-polynomial LPN. In Anne Canteaut and François-Xavier Standaert, editors, Advances in Cryptology – EUROCRYPT 2021, Part II, volume 12697 of Lecture Notes in Computer Science, pages 842–870, Zagreb, Croatia, October 17–21, 2021. Springer, Cham, Switzerland.DOI
  50. [54]Geoffroy Couteau. A note on the communication complexity of multiparty computation in the correlated randomness model. In Yuval Ishai and Vincent Rijmen, editors, Advances in Cryptology – EUROCRYPT 2019, Part II, volume 11477 of Lecture Notes in Computer Science, pages 473–503, Darmstadt, Germany, May 19–23, 2019. Springer, Cham, Switzerland.
  51. [55]Yfke Dulek, Alex B. Grilo, Stacey Jeffery, Christian Majenz, and Christian Schaffner. Secure multi-party quantum computation with a dishonest majority. In Anne Canteaut and Yuval Ishai, editors, Advances in Cryptology – EUROCRYPT 2020, Part III, volume 12107 of Lecture Notes in Computer Science, pages 729–758, Zagreb, Croatia, May 10–14, 2020. Springer, Cham, Switzerland.DOI
  52. [56]Jesko Dujmovic and Mohammad Hajiabadi. Lower-bounds on public-key operations in PIR. In Marc Joye and Gregor Leander, editors, Advances in Cryptology – EUROCRYPT 2024, Part VI, volume 14656 of Lecture Notes in Computer Science, pages 65–87, Zurich, Switzerland, May 26–30, 2024. Springer, Cham, Switzerland.DOI
  53. [57]Ivan Damgård and Yuval Ishai. Constant-round multiparty computation using a black-box pseudorandom generator. In Victor Shoup, editor, Advances in Cryptology – CRYPTO 2005, volume 3621 of Lecture Notes in Computer Science, pages 378–394, Santa Barbara, CA, USA, August 14–18, 2005. Springer Berlin Heidelberg, Germany.
  54. [58]Quang Dao, Yuval Ishai, Aayush Jain, and Huijia Lin. Multi-party homomorphic secret sharing and sublinear MPC from sparse LPN. In Helena Handschuh and Anna Lysyanskaya, editors, Advances in Cryptology – CRYPTO 2023, Part II, volume 14082 of Lecture Notes in Computer Science, pages 315–348, Santa Barbara, CA, USA, August 20–24, 2023. Springer, Cham, Switzerland.
  55. [59]Ivan Damgård, Yuval Ishai, and Mikkel Krøigaard. Perfectly secure multiparty computation and the computational overhead of cryptography. In Henri Gilbert, editor, Advances in Cryptology – EUROCRYPT 2010, volume 6110 of Lecture Notes in Computer Science, pages 445–465, French Riviera, May 30 – June 3, 2010. Springer Berlin Heidelberg, Germany.DOI
  56. [61]Ivan Damgård, Kasper Green Larsen, and Jesper Buus Nielsen. Communication lower bounds for statistically secure MPC, with or without preprocessing. In Alexandra Boldyreva and Daniele Micciancio, editors, Advances in Cryptology – CRYPTO 2019, Part II, volume 11693 of Lecture Notes in Computer Science, pages 61–84, Santa Barbara, CA, USA, August 18–22, 2019. Springer, Cham, Switzerland.DOI
  57. [62]Ivan Bjerre Damgård, Boyang Li, and Nikolaj Ignatieff Schwartzbach. More communication lower bounds for information-theoretic MPC. In Stefano Tessaro, editor, ITC 2021: 2nd Conference on Information-Theoretic Cryptography, volume 199 of Leibniz International Proceedings in Informatics (LIPIcs), pages 2:1–2:18, Seattle, WA, USA, July 23–26, 2021. Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik.
  58. [63]Giovanni Di Crescenzo, Tal Malkin, and Rafail Ostrovsky. Single database private information retrieval implies oblivious transfer. In Bart Preneel, editor, Advances in Cryptology – EUROCRYPT 2000, volume 1807 of Lecture Notes in Computer Science, pages 122–138, Bruges, Belgium, May 14–18, 2000. Springer Berlin Heidelberg, Germany.DOI
  59. [64]Ivan Damgård and Jesper Buus Nielsen. Scalable and unconditionally secure multiparty computation. In Alfred Menezes, editor, Advances in Cryptology – CRYPTO 2007, volume 4622 of Lecture Notes in Computer Science, pages 572–590, Santa Barbara, CA, USA, August 19–23, 2007. Springer Berlin Heidelberg, Germany.DOI
  60. [65]Ivan Damgård, Jesper Buus Nielsen, Rafail Ostrovsky, and Adi Rosén. Unconditionally secure computation with reduced interaction. In Marc Fischlin and Jean-Sébastien Coron, editors, Advances in Cryptology – EUROCRYPT 2016, Part II, volume 9666 of Lecture Notes in Computer Science, pages 420–447, Vienna, Austria, May 8–12, 2016. Springer Berlin Heidelberg, Germany.DOI
  61. [67]Frédéric Dupuis, Jesper Buus Nielsen, and Louis Salvail. Secure two-party quantum evaluation of unitaries against specious adversaries. In Tal Rabin, editor, Advances in Cryptology – CRYPTO 2010, volume 6223 of Lecture Notes in Computer Science, pages 685–706, Santa Barbara, CA, USA, August 15–19, 2010. Springer Berlin Heidelberg, Germany.DOI
  62. [68]Deepesh Data, Manoj Prabhakaran, and Vinod M. Prabhakaran. On the communication complexity of secure computation. In Juan A. Garay and Rosario Gennaro, editors, Advances in Cryptology – CRYPTO 2014, Part II, volume 8617 of Lecture Notes in Computer Science, pages 199–216, Santa Barbara, CA, USA, August 17–21, 2014. Springer Berlin Heidelberg, Germany.arxiv.org/abs/1311.7584
  63. [69]Ivan Damgård, Valerio Pastro, Nigel P. Smart, and Sarah Zakarias. Multiparty computation from somewhat homomorphic encryption. In Reihaneh Safavi-Naini and Ran Canetti, editors, Advances in Cryptology – CRYPTO 2012, volume 7417 of Lecture Notes in Computer Science, pages 643–662, Santa Barbara, CA, USA, August 19–23, 2012. Springer Berlin Heidelberg, Germany.DOI
  64. [70]Daniel Escudero, Vipul Goyal, Antigoni Polychroniadou, Yifan Song, and Chenkai Weng. SuperPack: Dishonest majority MPC with constant online communication. In Carmit Hazay and Martijn Stam, editors, Advances in Cryptology – EUROCRYPT 2023, Part II, volume 14005 of Lecture Notes in Computer Science, pages 220–250, Lyon, France, April 23–27, 2023. Springer, Cham, Switzerland.DOI
  65. [71]Daniel Escudero, Vipul Goyal, Antigoni Polychroniadou, and Yifan Song. TurboPack: Honest majority MPC with constant online communication. In Heng Yin, Angelos Stavrou, Cas Cremers, and Elaine Shi, editors, ACM CCS 2022: 29th Conference on Computer and Communications Security, pages 951–964, Los Angeles, CA, USA, November 7–11, 2022. ACM Press.
  66. [72]Michael J. Freedman, Yuval Ishai, Benny Pinkas, and Omer Reingold. Keyword search and oblivious pseudorandom functions. In Joe Kilian, editor, TCC 2005: 2nd Theory of Cryptography Conference, volume 3378 of Lecture Notes in Computer Science, pages 303–324, Cambridge, MA, USA, February 10–12, 2005. Springer Berlin Heidelberg, Germany.DOI
  67. [73]Matthew K. Franklin and Moti Yung. Communication complexity of secure computation (extended abstract). In 24th Annual ACM Symposium on Theory of Computing, pages 699–710, Victoria, BC, Canada, May 4–6, 1992. ACM Press.DOI
  68. [74]Craig Gentry. Fully homomorphic encryption using ideal lattices. In Michael Mitzenmacher, editor, 41st Annual ACM Symposium on Theory of Computing, pages 169–178, Bethesda, MD, USA, May 31 – June 2, 2009. ACM Press.DOI
  69. [75]Sanjam Garg, Sam Gunn, and Mingyuan Wang. Black-box crypto is useless for pseudorandom codes. In Benny Applebaum and Huijia (Rachel) Lin, editors, TCC 2025: 23rd Theory of Cryptography Conference, Part IV, volume 16271 of Lecture Notes in Computer Science, pages 205–224, Aarhus, Denmark, December 1–5, 2025. Springer, Cham, Switzerland.
  70. [76]Alex B. Grilo, Kathrin Hövelmanns, Andreas Hülsing, and Christian Majenz. Tight adaptive reprogramming in the QROM. In Mehdi Tibouchi and Huaxiong Wang, editors, Advances in Cryptology – ASIACRYPT 2021, Part I, volume 13090 of Lecture Notes in Computer Science, pages 637–667, Singapore, December 6–10, 2021. Springer, Cham, Switzerland.DOI
  71. [77]Niv Gilboa and Yuval Ishai. Distributed point functions and their applications. In Phong Q. Nguyen and Elisabeth Oswald, editors, Advances in Cryptology – EUROCRYPT 2014, volume 8441 of Lecture Notes in Computer Science, pages 640–658, Copenhagen, Denmark, May 11–15, 2014. Springer Berlin Heidelberg, Germany.DOI
  72. [78]Yael Gertner, Yuval Ishai, Eyal Kushilevitz, and Tal Malkin. Protecting data privacy in private information retrieval schemes. In 30th Annual ACM Symposium on Theory of Computing, pages 151–160, Dallas, TX, USA, May 23–26, 1998. ACM Press.
  73. [79]Juan A. Garay, Yuval Ishai, Rafail Ostrovsky, and Vassilis Zikas. The price of low communication in secure multi-party computation. In Jonathan Katz and Hovav Shacham, editors, Advances in Cryptology – CRYPTO 2017, Part I, volume 10401 of Lecture Notes in Computer Science, pages 420–446, Santa Barbara, CA, USA, August 20–24, 2017. Springer, Cham, Switzerland.DOI
  74. [80]Daniel Genkin, Yuval Ishai, and Antigoni Polychroniadou. Efficient multi-party computation: From passive to active security via secure SIMD circuits. In Rosario Gennaro and Matthew J. B. Robshaw, editors, Advances in Cryptology – CRYPTO 2015, Part II, volume 9216 of Lecture Notes in Computer Science, pages 721–741, Santa Barbara, CA, USA, August 16–20, 2015. Springer Berlin Heidelberg, Germany.DOI
  75. [81]Vipul Goyal, Junru Li, Rafail Ostrovsky, and Yifan Song. Towards building scalable constant-round MPC from minimal assumptions via round collapsing. In Yael Tauman Kalai and Seny F. Kamara, editors, Advances in Cryptology – CRYPTO 2025, Part IV, volume 16003 of Lecture Notes in Computer Science, pages 70–104, Santa Barbara, CA, USA, August 17–21, 2025. Springer, Cham, Switzerland.DOI
  76. [82]Alex B. Grilo, Huijia Lin, Fang Song, and Vinod Vaikuntanathan. Oblivious transfer is in MiniQCrypt. In Anne Canteaut and François-Xavier Standaert, editors, Advances in Cryptology – EUROCRYPT 2021, Part II, volume 12697 of Lecture Notes in Computer Science, pages 531–561, Zagreb, Croatia, October 17–21, 2021. Springer, Cham, Switzerland.arxiv.org/abs/2011.14980
  77. [83]Uma Girish, Alex May, Natalie Parham, and Henry Yuen. New bounds on private simultaneous quantum message passing. Cryptology ePrint Archive, Paper 2026/1236, 2026.arxiv.org/abs/2606.12557
  78. [84]Oded Goldreich, Silvio Micali, and Avi Wigderson. How to play any mental game or A completeness theorem for protocols with honest majority. In Alfred Aho, editor, 19th Annual ACM Symposium on Theory of Computing, pages 218–229, New York City, NY, USA, May 25–27, 1987. ACM Press.
  79. [85]Vipul Goyal, Antigoni Polychroniadou, and Yifan Song. Unconditional communication-efficient MPC via hall’s marriage theorem. In Tal Malkin and Chris Peikert, editors, Advances in Cryptology – CRYPTO 2021, Part II, volume 12826 of Lecture Notes in Computer Science, pages 275–304, Virtual Event, August 16–20, 2021. Springer, Cham, Switzerland.DOI
  80. [86]Vipul Goyal, Antigoni Polychroniadou, and Yifan Song. Sharing transformation and dishonest majority MPC with packed secret sharing. In Yevgeniy Dodis and Thomas Shrimpton, editors, Advances in Cryptology – CRYPTO 2022, Part IV, volume 13510 of Lecture Notes in Computer Science, pages 3–32, Santa Barbara, CA, USA, August 15–18, 2022. Springer, Cham, Switzerland.
  81. [87]Sanjam Garg and Akshayaram Srinivasan. Two-round multiparty secure computation from minimal assumptions. Journal of the ACM, 69(5):1–30, 2022.
  82. [88]Iftach Haitner, Jonathan J. Hoch, and Gil Segev. A linear lower bound on the communication complexity of single-server private information retrieval. In Ran Canetti, editor, TCC 2008: 5th Theory of Cryptography Conference, volume 4948 of Lecture Notes in Computer Science, pages 445–464, San Francisco, CA, USA, March 19–21, 2008. Springer Berlin Heidelberg, Germany.
  83. [89]Alexander Hoover, Sarvar Patel, Giuseppe Persiano, and Kevin Yeo. Plinko: Single-server PIR with efficient updates via invertible PRFs. In Serge Fehr and Pierre-Alain Fouque, editors, Advances in Cryptology – EUROCRYPT 2025, Part VI, volume 15606 of Lecture Notes in Computer Science, pages 3–33, Madrid, Spain, May 4–8, 2025. Springer, Cham, Switzerland.
  84. [90]Alexander Hoover, Giuseppe Persiano, and Kevin Yeo. Lower bounds for PIR with preprocessing from blackbox cryptography. In 67th IEEE Symposium on Foundations of Computer Science (to appear), 2026.arxiv.org/abs/2607.06451
  85. [91]Yuval Ishai and Eyal Kushilevitz. On the hardness of information-theoretic multiparty computation. In Christian Cachin and Jan Camenisch, editors, Advances in Cryptology – EUROCRYPT 2004, volume 3027 of Lecture Notes in Computer Science, pages 439–455, Interlaken, Switzerland, May 2–6, 2004. Springer Berlin Heidelberg, Germany.
  86. [92]Yuval Ishai, Eyal Kushilevitz, Sigurd Meldgaard, Claudio Orlandi, and Anat Paskin-Cherniavsky. On the power of correlated randomness in secure computation. In Amit Sahai, editor, TCC 2013: 10th Theory of Cryptography Conference, volume 7785 of Lecture Notes in Computer Science, pages 600–620, Tokyo, Japan, March 3–6, 2013. Springer Berlin Heidelberg, Germany.DOI
  87. [93]Mihaela Ion, Ben Kreuter, Ahmet Erhan Nergiz, Sarvar Patel, Shobhit Saxena, Karn Seth, Mariana Raykova, David Shanahan, and Moti Yung. On deploying secure computing: Private intersection-sum-with-cardinality. In 2020 IEEE European Symposium on Security and Privacy (EuroS&P), pages 370–389. IEEE, 2020.DOI
  88. [94]Yuval Ishai, Joe Kilian, Kobbi Nissim, and Erez Petrank. Extending oblivious transfers efficiently. In Dan Boneh, editor, Advances in Cryptology – CRYPTO 2003, volume 2729 of Lecture Notes in Computer Science, pages 145–161, Santa Barbara, CA, USA, August 17–21, 2003. Springer Berlin Heidelberg, Germany.
  89. [95]Yuval Ishai, Eyal Kushilevitz, Rafail Ostrovsky, and Amit Sahai. Zero-knowledge from secure multiparty computation. In David S. Johnson and Uriel Feige, editors, 39th Annual ACM Symposium on Theory of Computing, pages 21–30, San Diego, CA, USA, June 11–13, 2007. ACM Press.
  90. [96]Yuval Ishai, Manoj Prabhakaran, and Amit Sahai. Founding cryptography on oblivious transfer - efficiently. In David Wagner, editor, Advances in Cryptology – CRYPTO 2008, volume 5157 of Lecture Notes in Computer Science, pages 572–591, Santa Barbara, CA, USA, August 17–21, 2008. Springer Berlin Heidelberg, Germany.DOI
  91. [97]Russell Impagliazzo and Steven Rudich. Limits on the provable consequences of one-way permutations. In 21st Annual ACM Symposium on Theory of Computing, pages 44–61, Seattle, WA, USA, May 15–17, 1989. ACM Press.
  92. [98]Yuval Ishai, Elaine Shi, and Daniel Wichs. PIR with client-side preprocessing: Information-theoretic constructions and lower bounds. In Leonid Reyzin and Douglas Stebila, editors, Advances in Cryptology – CRYPTO 2024, Part IX, volume 14928 of Lecture Notes in Computer Science, pages 148–182, Santa Barbara, CA, USA, August 18–22, 2024. Springer, Cham, Switzerland.DOI
  93. [99]Rahul Jain, Jaikumar Radhakrishnan, and Pranab Sen. Privacy and interaction in quantum communication complexity and a theorem about the relative entropy of quantum states. In 43rd Annual Symposium on Foundations of Computer Science, pages 429–438, Vancouver, BC, Canada, November 16–19, 2002. IEEE Computer Society Press.DOI
  94. [100]Iordanis Kerenidis and Ronald De Wolf. Exponential lower bound for 2-query locally decodable codes via a quantum argument. In Proceedings of the thirty-fifth annual ACM symposium on Theory of computing, pages 106–115, 2003.
  95. [101]Joe Kilian. Founding cryptography on oblivious transfer. In 20th Annual ACM Symposium on Theory of Computing, pages 20–31, Chicago, IL, USA, May 2–4, 1988. ACM Press.DOI
  96. [102]Iordanis Kerenidis, Mathieu Laurière, François Le Gall, and Mathys Rennela. Information cost of quantum communication protocols. Quantum Information and Computation, 16(3&4):181–196, 2016.DOI
  97. [103]Akinori Kawachi and Harumichi Nishimura. Communication complexity of private simultaneous quantum messages protocols. In Stefano Tessaro, editor, ITC 2021: 2nd Conference on Information-Theoretic Cryptography, volume 199 of Leibniz International Proceedings in Informatics (LIPIcs), pages 20:1–20:19, Seattle, WA, USA, July 23–26, 2021. Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik.arxiv.org/abs/2105.07120
  98. [104]Fuyuki Kitagawa, Ryo Nishimaki, Agi Villanyi, and Takashi Yamakawa. Towards the impossibility of imperfectly complete key agreement in the QROM. arXiv:2608.17610, 2026.arxiv.org/abs/2608.17610
  99. [106]Marcel Keller, Emmanuela Orsini, and Peter Scholl. MASCOT: Faster malicious arithmetic secure computation with oblivious transfer. In Edgar R. Weippl, Stefan Katzenbeisser, Christopher Kruegel, Andrew C. Myers, and Shai Halevi, editors, ACM CCS 2016: 23rd Conference on Computer and Communications Security, pages 830–842, Vienna, Austria, October 24–28, 2016. ACM Press.
  100. [107]Marcel Keller, Valerio Pastro, and Dragos Rotaru. Overdrive: Making SPDZ great again. In Jesper Buus Nielsen and Vincent Rijmen, editors, Advances in Cryptology – EUROCRYPT 2018, Part III, volume 10822 of Lecture Notes in Computer Science, pages 158–189, Tel Aviv, Israel, April 29 – May 3, 2018. Springer, Cham, Switzerland.DOI
  101. [108]Eyal Kushilevitz. Privacy and communication complexity. SIAM Journal on Discrete Mathematics, 5(2):273–284, 1992.
  102. [109]Longcheng Li, Qian Li, Xingjian Li, and Qipeng Liu. How (not) to build quantum PKE in Minicrypt. In Leonid Reyzin and Douglas Stebila, editors, Advances in Cryptology – CRYPTO 2024, Part VII, volume 14926 of Lecture Notes in Computer Science, pages 152–183, Santa Barbara, CA, USA, August 18–22, 2024. Springer, Cham, Switzerland.arxiv.org/abs/2405.20295
  103. [110]Longcheng Li, Qian Li, Xingjian Li, and Qipeng Liu. Cryptomania vs. Minicrypt in a quantum world. Cryptology ePrint Archive, Report 2025/639, 2025.arxiv.org/abs/2504.05710
  104. [111]Longcheng Li, Qian Li, Xingjian Li, and Qipeng Liu. Impossibility of perfectly complete many-round key agreement in the QROM. arXiv:2608.03824, 2026.arxiv.org/abs/2608.03824
  105. [112]Wei-Kai Lin, Ethan Mook, and Daniel Wichs. Black box crypto is useless for doubly efficient PIR. In Serge Fehr and Pierre-Alain Fouque, editors, Advances in Cryptology – EUROCRYPT 2025, Part VI, volume 15606 of Lecture Notes in Computer Science, pages 65–93, Madrid, Spain, May 4–8, 2025. Springer, Cham, Switzerland.
  106. [113]Hoi-Kwong Lo. Insecurity of quantum secure computations. Physical Review A, 56(2):1154, 1997.DOI
  107. [114]Junru Li and Yifan Song. Honest majority constant-round MPC with linear communication from one-way functions. In Benny Applebaum and Huijia (Rachel) Lin, editors, TCC 2025: 23rd Theory of Cryptography Conference, Part I, volume 16268 of Lecture Notes in Computer Science, pages 3–32, Aarhus, Denmark, December 1–5, 2025. Springer, Cham, Switzerland.
  108. [115]Junru Li and Yifan Song. Breaking the ω(|c|κ) barrier on garbled circuit size in the random oracle model. Cryptology ePrint Archive, Report 2026/1297, 2026. CRYPTO 2026.
  109. [116]Moni Naor. Bit commitment using pseudorandomness. Journal of Cryptology, 4(2):151–158, January 1991.DOI
  110. [117]Ashwin Nayak. Optimal lower bounds for quantum automata and random access codes. In 40th Annual Symposium on Foundations of Computer Science, pages 369–377, New York, NY, USA, October 17–19, 1999. IEEE Computer Society Press.
  111. [118]Michael A. Nielsen and Isaac L. Chuang. Quantum Computation and Quantum Information: 10th Anniversary Edition. Cambridge University Press, 2010.
  112. [119]Moni Naor and Kobbi Nissim. Communication preserving protocols for secure function evaluation. In 33rd Annual ACM Symposium on Theory of Computing, pages 590–599, Crete, Greece, July 6–8, 2001. ACM Press.DOI
  113. [120]Moni Naor and Benny Pinkas. Oblivious transfer and polynomial evaluation. In 31st Annual ACM Symposium on Theory of Computing, pages 245–254, Atlanta, GA, USA, May 1–4, 1999. ACM Press.DOI
  114. [122]Antigoni Polychroniadou, Gilad Asharov, Benjamin E. Diamond, Tucker Balch, Hans Buehler, Richard Hua, Suwen Gu, Greg Gimler, and Manuela Veloso. Prime match: A privacy-preserving inventory matching system. In Joseph A. Calandrino and Carmela Troncoso, editors, USENIX Security 2023: 32nd USENIX Security Symposium, pages 6417–6434, Anaheim, CA, USA, August 9–11, 2023. USENIX Association.arxiv.org/abs/2310.09621
  115. [124]Giuseppe Persiano and Kevin Yeo. Limits of preprocessing for single-server PIR. In Joseph (Seffi) Naor and Niv Buchbinder, editors, 33rd Annual ACM-SIAM Symposium on Discrete Algorithms, pages 2522–2548, Virtual Conference / Alexandria, VA, USA, January 9–12, 2022. ACM-SIAM.DOI
  116. [126]Omer Reingold, Luca Trevisan, and Salil P. Vadhan. Notions of reducibility between cryptographic primitives. In Moni Naor, editor, TCC 2004: 1st Theory of Cryptography Conference, volume 2951 of Lecture Notes in Computer Science, pages 1–20, Cambridge, MA, USA, February 19–21, 2004. Springer Berlin Heidelberg, Germany.DOI
  117. [127]Yifan Song and Xiaxi Ye. Honest majority MPC with Õ(|C|) communication in minicrypt. In Serge Fehr and Pierre-Alain Fouque, editors, Advances in Cryptology – EUROCRYPT 2025, Part V, volume 15605 of Lecture Notes in Computer Science, pages 453–483, Madrid, Spain, May 4–8, 2025. Springer, Cham, Switzerland.DOI
  118. [128]Kurt Thomas, Jennifer Pullman, Kevin Yeo, Ananth Raghunathan, Patrick Gage Kelley, Luca Invernizzi, Borbala Benko, Tadek Pietraszek, Sarvar Patel, Dan Boneh, and Elie Bursztein. Protecting accounts from credential stuffing with password breach alerting. In Nadia Heninger and Patrick Traynor, editors, USENIX Security 2019: 28th USENIX Security Symposium, pages 1556–1571, Santa Clara, CA, USA, August 14–16, 2019. USENIX Association.
  119. [130]Andreas Winter. Tight uniform continuity bounds for quantum entropies: Conditional entropy, relative entropy distance and energy constraints. Communications in Mathematical Physics, 347(1):291–313, 2016.DOI
  120. [131]Zhikun Wang and Ling Ren. Single-server client preprocessing PIR with tight space-time trade-off. In Serge Fehr and Pierre-Alain Fouque, editors, Advances in Cryptology – EUROCRYPT 2025, Part VI, volume 15606 of Lecture Notes in Computer Science, pages 94–122, Madrid, Spain, May 4–8, 2025. Springer, Cham, Switzerland.DOI
  121. [132]Andrew C Yao. Protocols for secure computations. In 23rd annual symposium on foundations of computer science (sfcs 1982), pages 160–164. IEEE, 1982.
  122. [133]Kevin Yeo. Lower bounds for (batch) PIR with private preprocessing. In Carmit Hazay and Martijn Stam, editors, Advances in Cryptology – EUROCRYPT 2023, Part I, volume 14004 of Lecture Notes in Computer Science, pages 518–550, Lyon, France, April 23–27, 2023. Springer, Cham, Switzerland.DOI
  123. [134]Mark Zhandry. How to record quantum queries, and applications to quantum indifferentiability. In Alexandra Boldyreva and Daniele Micciancio, editors, Advances in Cryptology – CRYPTO 2019, Part II, volume 11693 of Lecture Notes in Computer Science, pages 239–268, Santa Barbara, CA, USA, August 18–22, 2019. Springer, Cham, Switzerland.DOI
  124. [135]Mingxun Zhou, Andrew Park, Wenting Zheng, and Elaine Shi. Piano: Extremely simple, single-server PIR with sublinear server computation. In 2024 IEEE Symposium on Security and Privacy, pages 4296–4314, San Francisco, CA, USA, May 19–23, 2024. IEEE Computer Society Press.DOI

Paper details

Publication

vlnc:W_sk7xmh2u
v1 · latestHistory (1)

published · Fresh — added to the Hub within the last 30 days

added ·

Usage

views · 0

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

CC BY 4.0

Original source

Taxonomy

  • Computer Science

Authors

AI contributions

Claude, Gemini (multiple versions), Claude Fable 5.1 (bare) · View statement →

Looking for related papers…
Contents