Strong Known Related-Key Attacks and the Security of ECDSA

Abstract

The classical related-key attack (RKA) model fails to capture some real world systems that introduce related secret keys by design. In some blockchain applications, public keys are generated in a way that the corresponding secret keys are additively related. The difference between two secret keys are known to some third parties. In this paper, we propose the Strong Known Related-Key Attack (Strong KRKA) model to capture this scenario. ECDSA has long been considered to be inferior to Schnorr signature in terms of security, in sprite of its popularity in the standardization and real world usage. In this paper we show that Schnorr signature is not secure in the Strong KRKA model. In contrast, the security of ECDSA in the Strong KRKA model can be reduced to the unforgeability of ECDSA under chosen message attack. This theoretical result gives a different view of the relative security level of ECDSA and Schnorr, since ECDSA was developed in 1992.