| Abstract: |
We put forth and instantiate a new primitive of simultaneous-message, succinct (SMS) secure computation. Given a common reference string (CRS) setup phase, an SMS protocol for function f between two parties with inputs X, y has the following structure:
- Parties simultaneously exchange a single message,
- Communication is succinct, scaling with the shorter of the parties' inputs y, sublinear in the size of a long input X and output f(X,y),
- Without further interaction, the parties can locally derive additive secret shares of f(X,y).
SMS protocols enable a minimal communication structure for secure computation of the following scenario: Alice has a large private input X, Bob has a small private input y, and Charlie wants to learn f(X,y) for some public function f. Indeed, Alice and Bob simultaneously send each other a message using the CRS and their private inputs. Using the transcript and their private state, the parties obtain additive secret sharing of f(X,y), which they can send to Charlie incurring communication cost only twice that of the function output length. Importantly, the size of Alice's message does not grow with the size of her input X, and both Alice and Bob's first round message grow sub-linearly in the size of the output. In addition, Alice or Bob's view provides no information about the other party's input, even when they collude with Charlie.
We obtain the following results:
- Assuming Learning With Errors (LWE), we build an SMS protocol supporting evaluation of depth-d circuits. Alice's message is of size |f(X,y)|^(2/3) · poly(λ,d), and Bob's message is of size (|y| + |f(X,y)|^(2/3)) · poly(λ,d), where λ is the security parameter.
- Assuming sub-exponentially secure indistinguishability obfuscation and somewhere-statistically-binding hash functions, we build SMS protocols supporting arbitrary polynomial-sized batch functions of the form (f(x_1,y),...,f(x_L,y)), for X = (x_1,...,x_L). The size of both Alice and Bob's messages in this construction is |f| · poly(λ,log L).
We give several applications of SMS protocols, including:
- Trapdoor hash functions (TDH) (Döttling et al., Crypto'19) for the same function class as SMS, in turn obtaining the first construction of TDH beyond linear functions from LWE.
- A simple compiler for obtaining rate-1 fully homomorphic encryption (FHE) from any non-compact FHE scheme.
- Correlation-intractable hash functions that are secure against all efficiently searchable relations. |
