Batch Computations Revisited: Combining Key Computations and Batch Verifications

摘要

We consider the effect of combining the key computation step in particular key agreement protocols, such as ECMQV and static-DH, with verifying particular elliptic curve equations, such as those related to ECDSA signature verification. In particular, we show that one can securely combine ECDSA signature verification and ECMQV and static-ECDH key computations, resulting in significant performance improvements, due to saving on doubling operations and exploiting multiple point multiplication strategies. Rough estimates (for non-Koblitz curves) suggest that the incremental cost of ECDSA signature verification, when combined with ECDH key agreement, improves by a factor 2.3x compared to performing the ECDSA signature verification separately and by a factor 1.7x, when the latter is computed using the accelerated ECDSA signature verification technique described in [3]. Moreover, the total cost of combined ECDSA signature verification and ECDH key agreement improves by 1.4 x, when compared to performing these computations separately (and by 1.2x, if accelerated ECDSA signature verification techniques are used). This challenges the conventional wisdom that with ECC-based signature schemes, signature verification is always considerably slower than signature generation and slower than RSA signature verification. These results suggest that the efficiency advantage one once enjoyed using RSA-based certificates with ECC-based key agreement schemes may be no more: one might as well use an ECC-only scheme using ECDSA-based certificates. Results apply to all prime curves standardized by NIST, the NSA 'Suite B' curves, and the so-called Brainpool curves.