Talks

The hardness of the Learning with Errors (LWE) problem is by now a cornerstone of the cryptographic landscape, allowing to construct cryptographic schemes with properties unknown under other assumptions, and being conjectured to be resilient to quantum attacks. LWE is essentially the task of solving a noisy system of random linear equations over uniformly random secret variables (“the LWE secret”), evaluated modulo some integer. In applications the secret variables usu- ally correspond to the secret key of the cryptographic scheme. It is therefore of great importance to understand what happens when the secret variables are not sampled uniformly (but still have some entropy). This is relevant for settings where an adversary manages to obtain partial information on the secret (a.k.a key leakage), for various theoretical ap- plications, and also for practical use where for efficiency or convenience it is easier to sample the secret from some non-uniform distribution. This so called “Entropic LWE” problem has been studied in a number of works, starting with Goldwasser et al. (ICS 2010). However, so far it was only known how to prove the hardness of Entropic LWE for secret distributions supported inside a ball of small radius. In this work we resolve the hardness of Entropic LWE with arbitrary long secrets, in the following sense. We show an entropy bound that guarantees the security of arbitrary Entropic LWE. This bound is higher than what is required in the ball-bounded setting, but we show that this is essentially tight. Tightness is shown unconditionally for highly-composite moduli, and using black-box impossibility for arbitrary moduli. Technically, we show that the entropic hardness of LWE relies on a simple to describe lossiness property of the distribution of secrets itself. This is simply the probability of recovering a random sample from this distribution s, given s + e, where e is Gaussian noise (i.e. the quality of the distribution of secrets as an error correcting code for Gaussian noise). We hope that this characterization will make it easier to derive entropic LWE results more easily in the future. We also use our techniques to show new results for the ball-bounded setting, essentially showing that under a strong enough assumption even polylogarithmic entropy suffices.

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.

Historically, new particles and forces in the Standard Model have most often revealed themselves at high-energy particle colliders. Certain phenomena beyond the Standard Model, however, are best studied by using carefully designed low-energy precision measurements, or via their imprints on astrophysical and cosmological observables. In this talk, I will provide a concise overview of some of the new experiments and searches devised to look for new physics beyond the Standard Model. In particular, I will discuss recent developments in the new experimental and theoretical program of cosmological collider physics and how we can use the cosmological collider as a tool to study the structure of the Higgs potential at very high energies.

 

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.