The security of cryptographic protocols is based on the conjectured intractability of some mathematical problem, typically a single problem. However, in some cases, novel constructions emerge out of the surprising interplay of seemingly disparate mathematical structures and conjectured hard problems on these. Though unusual, this cooperation between assumptions, when it happens, can lead to progress on important open problems. This sometimes paves the way for subsequent improvements, which may even eliminate the multiplicity and reduce security to a single assumption. In this talk, we will examine some interesting examples of the above phenomenon. An early example can be found in the primitive of fully homomorphic encryption (FHE). where Gentry and Halevi (FOCS, 2011) provided a beautiful construction that eliminated the "squashing" step from Gentry's original FHE blueprint (STOC, 2009) by designing a hybrid of "somewhat homomorphic encryption" based on Learning with Errors (LWE), and "multiplicatively homomorphic encryption", based on Decision Diffie Hellman (DDH). More recently, Agrawal and Yamada (EUROCRYPT 2020) provided the first construction of optimal broadcast encryption from standard assumptions, by leveraging a serendipitous interplay of LWE and assumptions based on bilinear maps. Lastly, we will examine some very recent constructions of indistin-guishability obfuscation which rely on such interaction - the construction by Brakerski et al (EUROCRYPT 2020) and subsequent improvement by Gay and Pass (Eprint 2020), based on LWE and the Decisional Composite Residues (DCR) problem, and the construction by Jain, Lin and Sahai (Eprint 2020) which is based on LWE. Symmetric external Diffie Hellman (SXDH). Learning Parity with Noise (LPN) and the existence of Boolean PRG with polynomial stretch in NC_0. We will conclude with a discussion about future directions.
展开▼
