Fine-Grained Non-interactive Key Exchange, Revisited

We revisit the construction of multiparty non-interactive key-exchange protocols with fine-grained security, which was recently studied in (Afshar et al., Eurocrypt 2023). Their work introduced a 4party non-interactive key exchange with quadratic hardness, and proved it secure in Shoup's generic group model. This positive result was complemented with a proof that n-party non-interactive key exchange with superquadratic security cannot exist in Maurer's generic group model, for any n ≥ 3. Because Shoup's model is stronger than Maurer's model, this leaves a gap between the positive and the negative result, and their work left as an open question the goal of closing this gap, and of obtaining fine-grained non-interactive key exchange without relying on idealized models. In this work, we make significant progress on both questions. We obtain two main results:

-A 4-party non-interactive key exchange protocol with quadratic security gap, assuming the existence of exponentially secure injective pseudorandom generators, and the subexponential hardness of the computational Diffie-Hellman assumption. In addition, our scheme is conceptually simpler, and can be generalized to other settings (with more parties or from other assumptions). -Assuming the existence of non-uniformly secure injective pseudorandom generators with exponential hardness, we further show that our protocol is secure in Maurer's model, albeit with a smaller hardness gap (up to N 1.6 ), making progress on filling the gap between the positive and the negative result of (Afshar et al., Eurocrypt 2023). Somewhat intriguingly, proving the security of our scheme in Maurer's idealized model turns out to be significantly harder than proving its security in the standard model.

Informally, in the generic group model, the parties and the adversary have oracle access to the group operations. In Maurer's model, the group elements are represented as values in an array (stored in the oracle) and the parties cannot see them, but can test the equality between elements using oracle queries. In Shoup's model, a representation of the group elements computed through oracle queries via a random injective mapping is given to the parties (letting them in particular test locally the equality between group elements). Together, these result demonstrate that in contrast with the standard setting of security against 4 For example, a primitive with a quadratic gap between the runtime of the honest parties and that of the best-possible adversary could be realistically usable: running 2 40 operations requires a moderate amount of time on a standard computers, while (2 40 ) 2 = 2 80 remains out of reach of anyone but state-level organizations.