and Varun Narayanan
We tackle the following broad question about cryptographic primitives: is it possible to achieve security against arbitrary poly(n) circuit-size adversaries with O(log n) size messages? It is common knowledge that the answer is unless information-theoretic security is possible. In this work, we revisit this question by considering the setting of cryptography with public information and computational security.
Our main results include the following:
1. For the task of constructing protocols in the Private Simultaneous Message (PSM) model. We show that O(log n) bits suffice if we allow public information and computational security.
2. For the task of 3-party MPC, where 2 parties have inputs and the third party receive the output, we present a protocol with an offline stage that produces shared randomness for the input parties and public information, followed by a one-round protocol after receiving the input (a single message from each input party to the output party) with very short, i.e. O(log n) bits, online communication. Previously known solutions (even allowing correlated randomness) used at least two rounds of communication.
3. For the task of constructing so-called Forbidden Graph Secret-Sharing, the best known computational scheme without public information has share size poly(n) (assuming one-way functions). We present a computational Forbidden Graph Secret-Sharing scheme with public information and share size of only O(log n). On the negative side, we show that computational threshold secret-sharing schemes even with public information require share size Ω(log log n).
Our constructions are based on the conjectured hardness of variants of the planted clique problem, that was extensively studied in the Complexity Theory and Statistical Inference communications but was less commonly used in Crypto. We believe that such conjectures have the potential of finding other cryptographic applications.