Abstract We propose the first tight security proof for the ordinary two-message signed Diffie–Hellman key exchange protocol in the random oracle model. Our proof is based on the strong computational Diffie–Hellman assumption and the multiuser security of a digital signature scheme. With our security proof, the signed DH protocol can be deployed with optimal parameters, independent of the number of users or sessions, without the need to compensate any security loss. We abstract our approach with a new notion called verifiable key exchange. In contrast to a known tight three-message variant of the signed Diffie–Hellman protocol (Gjøsteen and Jager, in: Shacham, Boldyreva (eds) CRYPTO 2018, Part II. LNCS, Springer, Heidelberg, 2018), we do not require any modification to the original protocol, and our tightness result is proven in the “Single-Bit-Guess” model which we know can be tightly composed with symmetric cryptographic primitives to establish a secure channel. Finally, we extend our approach to the group setting and construct the first tightly secure group authenticated key exchange protocol.

This paper studies the security of efficient pairing implementations with compressed and standard representations against fault attacks. We show that these attacks solve the Fixed Argument Pairing Inversion and recover the first or second argument of the pairing inputs if we can inject double-faults on the loop counters. Compared to the first attack of Page and Vercauteren on supersingular elliptic curves in characteristic three, these are the first attacks which address efficient pairing implementations. Most efficient Tate pairings are computed using a Miller loop followed by a Final Exponentiation. Many papers show how it is possible to invert only the Miller loop and a recent paper of Lashermes et al. at CHES 2013 shows how to invert only the final exponentiation. During a long time, the final exponentiation was used as a countermeasure against the inversion of the Miller loop. However, the CHES attack cannot be used to invert this step on efficient and concrete implementations. Indeed, the two first steps of the Final Exponentiation use the Frobenius map to compute them efficiently. The drawback of the CHES 2013 attack is that it only works if these steps are implemented using very expensive inversions, but in general, these inversions are computed by using a conjugate since elements at the end of the first exponentiation are unicity roots. If this natural implementation is used, the CHES 2013 attack is avoided since it requires to inject a fault so that the faulted elements are not unicity roots. Consequently, it is highly probable that for concrete implementations, this attack will not work. For the same reasons, it is not possible to invert the Final Exponentiation in case of compressed pairing and both methods (conjugate and compressed) were proposed by Lashermes et al. as countermeasures against their attack. Here, we demonstrate that we can solve the FAPI-1 and FAPI-2 problems for compressed and standard pairing implementations. We demonstrate the efficiency of our attacks by using simulations with Sage on concrete implementations.