Vanishree Rao: Adaptive Multiparty Non-Interactive Key Exchange without Setup in the Standard Model

Abstract: Non-interactive key exchange (NIKE) is a fundamental notion in Cryptography. This notion was introduced by Diffie and Hellman in 1976. They proposed the celebrated 2-party NIKE protocol and left open as a fascinating question, whether NIKE could be realized in the multiparty setting. NIKE has since then been an active area of research with an ultimate goal of obtaining best possible security in the multiparty setting. Although this has evaded researchers for many decades, advancements have been made through relaxations in multiple directions such as restricting to 3-parties, static/semi-static model (where the adversary needs to commit to the set of parties he wishes to be challenged upon ahead of time), random-oracle model, allowing initial setup, etc.

In this talk, we shall see the first multiparty NIKE protocol that is adaptively secure and in the standard model. (Time permitting, we shall also see how to remove the setup.) 

Our construction is based on indistinguishability obfuscation and obliviously-patchable puncturable pseudorandom functions, a new notion that we introduce.

We shall witness employing a novel technique of using indistinguishability obfuscation, which is interesting in its own right and which I believe would find wider applications in other settings. One such technique pertains overcoming, the somewhat inherent, drawback of non-adaptivity of the puncturing technique introduced by Sahai and Waters [STOC'14]. Central to this technique is our new notion of obliviously-patchable puncturable pseudorandom functions. 

Paper minus talk: In my paper, I encourage you to take a look at a concrete construction of these special pseudorandom functions using multilinear maps and their recent approximations -- the leveled-graded encoding schemes. Note that pseudorandom functions amount to an interactive assumption. The paper also establishes via a meta-reduction technique that, in natural settings, an interactive assumption is necessary (even with setup).