On the Security of Schnorr Signatures, DSA, and ElGamal Signatures against Related-Key Attacks

Hiraku MORITA  Jacob C.N. SCHULDT  Takahiro MATSUDA  Goichiro HANAOKA  Tetsu IWATA  

IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences   Vol.E100-A   No.1   pp.73-90
Publication Date: 2017/01/01
Online ISSN: 1745-1337
DOI: 10.1587/transfun.E100.A.73
Type of Manuscript: Special Section PAPER (Special Section on Cryptography and Information Security)
related-key attacks,  Schnorr signatures,  DSA,  ElGamal signatures.,  

Full Text: PDF>>
Buy this Article

In the ordinary security model for signature schemes, we consider an adversary that tries to forge a signature on a new message using only his knowledge of other valid message and signature pairs. To take into account side channel attacks such as tampering or fault-injection attacks, Bellare and Kohno (Eurocrypt 2003) formalized related-key attacks (RKA), where stronger adversaries are considered. In the RKA security model for signature schemes, we consider an adversary that can also manipulate the signing key and obtain signatures computed under the modified key. RKA security is defined with respect to the related-key deriving functions which are used by an adversary to manipulate the signing key. This paper considers RKA security of three established signature schemes: the Schnorr signature scheme, a variant of DSA, and a variant of ElGamal signature scheme. First, we show that these signature schemes are secure against a weak notion of RKA with respect to polynomial functions. Second, we demonstrate that, on the other hand, none of the Schnorr signature scheme, DSA, nor the ElGamal signature scheme achieves the standard notion of RKA security with respect to linear functions, by showing concrete attacks on these. Lastly, we show that slight modifications of the Schnorr signature scheme, (the considered variant of) DSA, and the variant of ElGamal signature scheme yield fully RKA secure schemes with respect to polynomial functions.