Paper 2014/910

Adaptive Multiparty Non-interactive Key Exchange Without Setup In The Standard Model

Vanishree Rao

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 work, we settle the longstanding open question: we present the first multiparty NIKE protocol that is adaptively secure with no setup and in the standard model. Our construction is based on indistinguishability obfuscation and obliviously-patchable puncturable pseudorandom functions, a new notion that we introduce. We employ novel techniques of using indistinguishability obfuscation, which are interesting in their own right and which we 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. We present a concrete construction of these pseudorandom functions using multilinear maps and their recent approximations -- the leveled-graded encoding schemes. Note that pseudorandom functions amount to an interactive assumption. We shall establish via a meta-reduction technique that, in natural settings, an interactive assumption is necessary (even with setup).

Note: Reorganized the Introduction slightly.