Computer Science

Secure multiparty computation (MPC) often relies on sources of correlated randomness for better efficiency and simplicity. This is particularly useful for MPC with no honest majority, where input-independent correlated randomness enables a lightweight “non-cryptographic” online phase once the inputs are known. However, since the amount of correlated randomness typically scales with the circuit size of the function being computed, securely generating correlated randomness forms an efficiency bottleneck, involving a large amount of communication and storage. A natural tool for addressing the above limitations is a pseudorandom correlation generator (PCG). A PCG allows two or more parties to securely generate long sources of useful correlated randomness via a local expansion of correlated short seeds and no interaction. PCGs enable MPC with silent preprocessing, where a small amount of interaction used for securely sampling the seeds is followed by silent local generation of correlated pseudorandomness. We propose a new class of concretely efficient PCGs for a number of useful correlations based on different flavors of the learning parity with noise assumption. In particular, we present a PCG for oblivious transfer correlations, and show how it can be turned into the first efficient 2-round OT extension protocol of any kind. Further, we provide efficient constructions of PCGs for a broader class of correlations, such as oblivious linear evaluation correlations and authenticated Beaver triples over large fields, based on variants of the ring-LPN assumption. Based on joint works with Elette Boyle, Geoffroy Couteau, Niv Gilboa, Yuval Ishai, Peter Rindal, and Peter Scholl.

The notion of traitor tracing (TT) was introduced by Chor, Fiat, and Naor in the early 90s with the goal of solving the accountability problem in broadcast systems. In a TT system for N users, every user has his/her own secret key. Content providers can encrypt messages using a public key, while each user can decrypt using his/her secret key. Suppose some of the N users collude to construct a pirate decoding box. The most notable property of such systems is the presence of a special algorithm, called Trace, which can identify at least one of the secret keys used to construct the pirate decoding box. Although TT has numerous applications beyond broadcast TV systems, all previous TT systems either had large ciphertexts, or relied on non-standard assumptions. Recently, in a joint work with Venkata Koppula and Brent Waters, we introduced a new form of functional encryption (FE) that we called Mixed FE, and using Mixed FE we built the first fully collusion resistant compact TT scheme provably secure under the learning with errors (LWE) assumption. In this talk, we revisit the notion of Mixed FE and discuss some applications of the concept in introducing tracing capabilities in a wide variety of encryption systems.

In this talk we will discuss the notion of lockable obfuscation. In a lockable obfuscation scheme there exists an obfuscation algorithm Obf that takes as input a program PP and string called `lock ' , and outputs an obfuscated program P'. One can evaluate the obfuscated program P' on any input x where the output of evaluation is 1 iff P(x)=lock, otherwise the output is a rejecting symbol. The security requirement states that if `lock' is uniformly random, then the obfuscated program P' hides the program P. We will first discuss one of the applications of lockable obfuscation - anonymous encryption schemes. Next, we will see a construction of lockable obfuscation, followed by a proof of security based on the Learning with Errors (LWE) assumption. This talk is based on two concurrent works by Goyal-K-Waters and Wichs-Zirdelis.

In this talk I will first survey the cryptanalytic attacks on the candidate program obfuscators. I will then explain two attacks on the candidates obfuscators built on GGH15 multilinear maps, and mention two interesting open problems related to lattices and quantum algorithms.

Lattices have allowed us to realize several advanced notions of computation over encrypted data, notably fully homomorphic encryption, attribute-based encryption, as well as fully homomorphic signatures. In this tutorial, we will introduce and derive a simple equation at the core of all of these constructions.

In this work we study the quantum learnability of constant-depth classical circuits under the uniform distribution and in the distribution-independent framework of PAC learning. In order to attain our results, we establish connections between quantum learning and quantum-secure cryptosystems. We then achieve the following results. 1) Hardness of learning AC0 and TC0 under the uniform distribution. Our first result concerns the concept class TC0 (resp. AC0), the class of constant-depth and polynomial-sized circuits with unbounded fan-in majority gates (resp. AND, OR, NOT gates). We show that if there exists no quantum polynomial-time (resp. strong sub-exponential time) algorithm to solve the Ring Learning with Errors (RLWE) problem, then there exists no polynomial-time quantum learning algorithm for TC0 (resp. AC0) under the uniform distribution (even with access to quantum membership queries). The main technique in this result uses explicit pseudo-random functions that are believed to be quantum-secure to construct concept classes that are hard to learn quantumly under the uniform distribution. 2) Hardness of learning TC02 in the PAC setting. Our second result shows that if there exists no quantum polynomial time algorithm for the LWE problem, then there exists no polynomial time quantum PAC learning algorithm for the class TC02, i.e., depth-2 TC0 circuits. The main technique in this result is to establish a connection between the quantum security of public-key cryptosystems and the learnability of a concept class that consists of decryption functions of the cryptosystem. This gives a strong (conditional) negative answer to one of the "Ten Semi-Grand Challenges for Quantum Computing Theory" raised by Aaronson [Aar05], who asked if AC0 and TC0 can be PAC-learned in quantum polynomial time.