Limits on the efficiency of (ring) LWE-based non-interactive key exchange (Q2051406)

Making non-interactive an interactive protocol, i.e. achieving the security goal in a single-round communication, is a common practice in the realm of public key cryptography. A practice that, at the time of writing, does not seem apply to key-exchange protocols based on the learning with errors problem (LWE), where all protocols are interactive. In this paper, the authors investigates the case of LWE-based key exchange protocols, with modulus polynomial in the security parameter, where key reconciliation is used from the parties to agree on the secret key, with the aim of proving that the intrinsic nature of the construction will force the protocol to be interactive, and to provide a non-interactive construction otherwise. The authors consider different natural reconciliation scenarios, proving that in each case the underlying protocol cannot be made non-interactive, i.e. it will require additional steps: in the first one, discussed in Section 4, they assume that the reconciliation function is defined as the product of the received LWE sample with the private LWE secret. It is information theoretically proved that, no matter the computational efficiency of the function, such a reconciliation cannot exists. In the second scenario (see Section 5), they consider the case of reconciliation functions not depending on the noises \(e_1\), \(e_2\), and they prove, assuming the hardness of LWE, that this is again not possible. In the last case of Section 6, they observe that the existence of a reconciliation which depends on all the inputs cannot be ruled out. However, some concerns on the computational complexity of the reconciliation function are raised.