Abstract : Let Kt(x) denote the Levin-Kolmogorov Complexity of the string x, and let MKtP denote the language of pairs (x,k) having the property that Kt(x) <= k.

We demonstrate that:

• MKtP \notin HeurBPP (i.e., MKtP is *two-sided error* mildly average-case hard) iff infinititely-often OWFs exist.

• MKtP \notin AvgBPP (i.e., MKtP is *errorless* mildly average-case hard) iff EXP != BPP.

Taken together, these results show that the only “gap” towards getting (infinitely-often) OWFs from the assumption that EXP != BPP is the seemingly “minor” technical gap between two-sided error and errorless average-case hardness of the MKtP problem.

Joint work with Yanyi Liu.

Abstract : Homomorphic encryption (HE) protects data in-use, but can be computationally expensive. To avoid the costly bootstrapping procedure that refreshes ciphertexts, some works have explored client-aided outsourcing protocols, where the client intermittently refreshes ciphertexts for a server that is performing homomorphic computations. But is this approach secure against malicious servers?

We present a CPA-secure encryption scheme that is completely insecure in this setting. We define a new notion of security, called funcCPA, that we prove is sufficient. Additionally, we show:

– Homomorphic encryption schemes that have a certain type of circuit privacy – for example, schemes in which ciphertexts can be “sanitized” – are funcCPA-secure.

– In particular, assuming certain existing HE schemes are CPA-secure, they are also funcCPA-secure.

– For certain encryption schemes, like Brakerski-Vaikuntanathan, that have a property that we call oblivious secret key extraction, funcCPA-security implies circular security – i.e., that it is secure to provide an encryption of the secret key in a form usable for bootstrapping (to construct fully homomorphic encryption).

In summary, funcCPA-security lies strictly between CPA-security and CCA2-security (under reasonable assumptions), and has an interesting relationship with circular security, though it is not known to be equivalent.

Based on a joint work with Shai Halevi, Craig Gentry and Margarita Vald

Abstract: In distributed differential privacy, the parties perform analysis over their joint data while preserving the privacy for both datasets. Interestingly, for a few fundamental two-party functions such as inner product and Hamming distance, the accuracy of the distributed solution lags way behind what is achievable in the client-server setting. McGregor, Mironov, Pitassi, Reingold, Talwar, and Vadhan [FOCS '10] proved that this gap is inherent, showing upper bounds on the accuracy of (any) distributed solution for these functions. These limitations can be bypassed when settling for computational differential privacy, where the data is differentially private only in the eyes of a computationally bounded observer, using public-key cryptography primitives.

We prove that the use of public-key cryptography is necessary for bypassing the limitation of McGregor et al., showing that a non-trivial solution for the inner-product, or the Hamming distance, implies the existence of a key-agreement protocol. Our bound implies a combinatorial proof for the fact that non-Boolean inner product of independent (strong) Santha-Vazirani sources is a good condenser. We obtain our main result by showing that the inner-product of a (single, strong) SV source with a uniformly random seed is a good condenser, even when the seed and source are dependent.

Joint work with Iftach Haitner, Jad Silbak and Eliad Tsfadia.

Abstract: We overview a recent line of work for obtaining malicious security in multi-party computation with low communication overhead, by use of sublinear zero-knowledge proofs on distributed data. We focus on recent results in the setting of a dishonest majority.

Based on joint work with Niv Gilboa, Yuval Ishai, and Ariel Nof.