We study the communication complexity of secure function evaluation (SFE). Consider a setting where Alice has a short input xA, Bob has an input xB and we want Bob to learn some function y = f(xA, xB) with large output size. For example, Alice has a small secret decryption key, Bob has a large encrypted database and we want Bob to learn the decrypted data without learning anything else about Alice’s key. In a trivial insecure protocol, Alice can just send her short input xA to Bob. However, all known SFE protocols have communication complexity that scales with size of the output y, which can potentially be much larger. Is such “output-size dependence” inherent in SFE? Surprisingly, we show that output-size dependence can be avoided in the honest-butcurious setting. In particular, using indistinguishability obfuscation (iO) and fully homomorphic encryption (FHE), we construct the first honest-but-curious SFE protocol whose communication complexity only scales with that of the best insecure protocol for evaluating the desired function, independent of the output size. Our construction relies on a novel way of using iO via a new tool that we call a “somewhere statistically binding (SSB) hash”, and which may be of independent interest. On the negative side, we show that output-size dependence is inherent in the fully malicious setting, or even already in an honest-but-deterministic setting, where the corrupted party follows the protocol as specified but fixes its random tape to some deterministic value. Moreover, we show that even in an offline/online protocol, the communication of the online phase must have output-size dependence. This negative result uses an incompressibility argument and it generalizes several recent lower bounds for functional encryption and (reusable) garbled circuits, which follow as simple corollaries of our general theorem.
We study the communication complexity of secure function evaluation (SFE). Consider a setting where Alice has a short input xA, Bob has an input xB and we want Bob to learn some function y = f(xA, xB) with large output size. For example, Alice has a small secret decryption key, Bob has a large encrypted database and we want Bob to learn the decrypted data without learning anything else about Alice’s key. In a trivial insecure protocol, Alice can just send her short input xA to Bob. However, all known SFE protocols have communication complexity that scales with size of the output y, which can potentially be much larger. Is such “output-size dependence” inherent in SFE? Surprisingly, we show that output-size dependence can be avoided in the honest-butcurious setting. In particular, using indistinguishability obfuscation (iO) and fully homomorphic encryption (FHE), we construct the first honest-but-curious SFE protocol whose communication complexity only scales with that of the best insecure protocol for evaluating the desired function, independent of the output size. Our construction relies on a novel way of using iO via a new tool that we call a “somewhere statistically binding (SSB) hash”, and which may be of independent interest. On the negative side, we show that output-size dependence is inherent in the fully malicious setting, or even already in an honest-but-deterministic setting, where the corrupted party follows the protocol as specified but fixes its random tape to some deterministic value. Moreover, we show that even in an offline/online protocol, the communication of the online phase must have output-size dependence. This negative result uses an incompressibility argument and it generalizes several recent lower bounds for functional encryption and (reusable) garbled circuits, which follow as simple corollaries of our general theorem.
We study the communication complexity of secure function evaluation (SFE). Consider a setting where Alice has a short input χA, Bob has an input χB and we want Bob to learn some function y = f(χA, χB) with large output size. For example, Alice has a small secret decryption key, Bob has a large encrypted database and we want Bob to learn the decrypted data without learning anything else about Alice's key. In a trivial insecure protocol, Alice can just send her short input χA to Bob. However, all known SFE protocols have communication complexity that scales with size of the output y, which can potentially be much larger. Is such 'output-size dependence' inherent in SFE'
We consider the problem of private function evaluation (PFE) in the two-party setting. Here, informally, one party holds an input x while the other holds a circuit describing a function f; the goal is for one (or both) of the parties to learn f(x) while revealing nothing more to either party. In contrast to the usual setting of secure computation — where the function being computed is known to both parties — PFE is useful in settings where the function (i.e., algorithm) itself must remain secret, e.g., because it is proprietary or classified. It is known that PFE can be reduced to standard secure computation by having the parties evaluate a universal circuit, and this is the approach taken in most prior work. Using a universal circuit, however, introduces additional overhead and results in a more complex implementation. We show here a completely new technique for PFE that avoids universal circuits, and results in constant-round protocols with communication/computational complexity linear in the size of the circuit computing f. This gives the first constant-round protocol for PFE with linear complexity (without using fully homomorphic encryption), even restricted to semi-honest adversaries. 1
We prove two classes of lower bounds on the communication complexity of information-theoretically secure multiparty computation. The first lower bound applies to perfect passive secure multiparty computation in the standard model with n = 2t+1 parties of which t are corrupted. We show a lower bound that applies to secure evaluation of any function, assuming that each party can choose to learn or not learn the output. Specifically, we show that there is a function H^* such that for any protocol that evaluates y_i = b_i ⋅ f(x₁,...,x_n) with perfect passive security (where b_i is a private boolean input), the total communication must be at least 1/2 ∑_{i = 1}ⁿ H_f^*(x_i) bits of information. The second lower bound applies to the perfect maliciously secure setting with n = 3t+1 parties. We show that for any n and all large enough S, there exists a reactive functionality F_S taking an S-bit string as input (and with short output) such that any protocol implementing F_S with perfect malicious security must communicate Ω(nS) bits. Since the functionalities we study can be implemented with linear size circuits, the result can equivalently be stated as follows: for any n and all large enough g ∈ ℕ there exists a reactive functionality F_C doing computation specified by a Boolean circuit C with g gates, where any perfectly secure protocol implementing F_C must communicate Ω(n g) bits. The results easily extends to constructing similar functionalities defined over any fixed finite field. Using known techniques, we also show an upper bound that matches the lower bound up to a constant factor (existing upper bounds are a factor lg n off for Boolean circuits). Both results also extend to the case where the threshold t is suboptimal. Namely if n = kt+s the bound is weakened by a factor O(s), which corresponds to known optimizations via packed secret-sharing.
We introduce a new cryptographic primitive called laconic function evaluation (LFE). Using LFE, Alice can compress a large circuit f into a small digest. Bob can encrypt some data x under this digest in a way that enables Alice to recover f(x) without learning anything else about Bob's data. For the scheme to be laconic, we require that the size of the digest, the run-time of the encryption algorithm and the size of the ciphertext should all be small, much smaller than the circuit-size of f. We construct an LFE scheme for general circuits under the learning with errors (LWE) assumption, where the above parameters only grow polynomially with the depth but not the size of the circuit. We then use LFE to construct secure 2-party and multi-party computation (2PC, MPC) protocols with novel properties: We construct a 2-round 2PC protocol between Alice and Bob with respective inputs xA, xBin which Alice learns the output f(xA, xB) in the second round. This is the first such protocol which is “Bob-optimized”, meaning that Alice does all the work while Bob's computation and the total communication of the protocol are smaller than the size of the circuit f or even Alice's input xA. In contrast, prior solutions based on fully homomorphic encryption are “Alice-optimized”. . We construct an MPC protocol, which allows N parties to securely evaluate a function f(x1, ..., xN) over their respective inputs, where the total amount of computation performed by the parties during the protocol execution is smaller than that of evaluating the function itself! Each party has to individually pre-process the circuit f before the protocol starts and post-process the protocol transcript to recover the output after the protocol ends, and the cost of these steps is larger than the circuit size. However, this gives the first MPC where the computation performed by each party during the actual protocol execution, from the time the first protocol message is sent until the last protocol message is received, is smaller than the circuit size.
How could quantum cryptography help us achieve what are not achievable in classical cryptography? In this work we study the classical cryptographic problem that two parties would like to perform secure computations with long outputs. As a basic primitive and example, we first consider the following problem which we call secure function sampling with long outputs: suppose f:{0,1}n→{0,1}m is a public, efficient classical function, where m is big; Alice would like to sample x from its domain and sends f(x) to Bob; what Bob knows should be no more than f(x) even if it behaves maliciously. Classical cryptography, like FHE and succinct arguments [Gen09,Kil92,HW15], allows us to achieve this task within communication complexity O(n+m); could we achieve this task with communication complexity independent of m? In this work, we first design a quantum cryptographic protocol that achieves secure function sampling with approximate security, within O(n) communication (omitting the dependency on the security parameter and error tolerance). We also prove the classical impossibility using techniques in [HW15], which means that our protocol indeed achieves a type of quantum advantage. Building on the secure function sampling protocol, we further construct protocols for general secure two-party computations [Yao86,GB01] with approximate security, with communication complexity only depending on the input length and the targeted security. In terms of the assumptions, we construct protocols for these problems assuming only the existence of collapsing hash functions [Unr16]; what's more, we also construct a classical-channel protocol for these problems additionally assuming the existence of noisy trapdoor claw-free functions [BCMVV,BKVV].
One-sided output secure function evaluation is a cryptographic primitive where the two mutually distrustful players, Alice and Bob, both have a private input to a bivariate function. Bob obtains the value of the function for the given inputs, while Alice receives no output. It is known that this primitive cannot be securely implemented if the two players only have access to noiseless classical and quantum communication. In this work, we first show that Bob can extract the function values for all his possible inputs from any implementation of a non-trivial function that is correct and preserves the privacy of Bob's input. Our result holds in the non-asymptotic setting where the players have finite resources and the error is a constant. Then we consider protocols for secure function evaluation in a setup where the two players have access to trusted distributed randomness as a resource. Building upon the first result, we prove a bound on the efficiency of such cryptographic reductions for any non-trivial function in terms of the conditional entropies of the trusted randomness. From this result, we can derive lower bounds on the number of instances of different variants of OT needed to securely implement a given function.