Cryptology ePrint Archive: Report 2015/1135

On the Security of the Schnorr Signature Scheme and DSA against Related-Key Attacks

Hiraku Morita and Jacob C.N. Schuldt and Takahiro Matsuda and Goichiro Hanaoka and Tetsu Iwata

Abstract: In the ordinary security model for signature schemes, we consider an adversary that may 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 RKA for signature schemes, the adversary can also manipulate the signing key and obtain signatures for the modified key. This paper considers RKA security of two established signature schemes: the Schnorr signature scheme and (a well-known variant of) DSA. First, we show that these signature schemes are secure against a weak notion of RKA. Second, we demonstrate that, on the other hand, neither the Schnorr signature scheme nor DSA achieves the standard notion of RKA security, by showing concrete attacks on these. Lastly, we show that a slight modification of both the Schnorr signature scheme and (the considered variant of) DSA yields fully RKA secure schemes.

Category / Keywords: public-key cryptography / Related-key attacks, Schnorr signatures, DSA

Original Publication (with minor differences): ICISC 2015

Date: received 24 Nov 2015

Contact author: h_morita at echo nuee nagoya-u ac jp,jacob schuldt@aist go jp,t-matsuda@aist go jp,hanaoka-goichiro@aist go jp,iwata@cse nagoya-u ac jp

Available format(s): PDF | BibTeX Citation

Version: 20151126:193747 (All versions of this report)

Short URL: ia.cr/2015/1135

Discussion forum: Show discussion | Start new discussion


[ Cryptology ePrint archive ]