NIKE from Affine Determinant Programs

A multi-party non-interactive key-exchange (NIKE) scheme enables N users to securely exchange a secret key K in a non-interactive manner. It is well-known that NIKE schemes can be obtained assuming the existence of indistinguishability obfuscation (iO). In this work, we revisit the original, iO-based, provably-secure NIKE construction by Boneh and Zhandry, aiming to simplify it. The core idea behind our protocol is to replace the functionality of the obfuscator with the one of an affine determinant program (ADP). Although ADPs have been designed with the purpose of attaining indistinguishability obfuscation, such implication is left open for general circuits. The ingredients enabling to prove the security of our scheme stem into a more careful analysis of the branching programs needed to build ADPs. In particular, we show:
1) An intuitive indistinguishability notion defined for ADPs of puncturable pseudorandom functions (PRFs) is sufficient to prove security for NIKE.
2) A set of simple conditions based on ADP's branching program topology that are sufficient for proving indistinguishability of ADPs. We leave open the question of finding ADPs satisfying them.