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

Access this Article

Author(s)

    • MORITA Hiraku
    • Dept. of Computational Science and Engineering, Nagoya University|Information Technology Research Institute (ITRI), National Institute of Advanced Industrial Science and Technology (AIST)
    • C.N. SCHULDT Jacob
    • Information Technology Research Institute (ITRI), National Institute of Advanced Industrial Science and Technology (AIST)
    • MATSUDA Takahiro
    • Information Technology Research Institute (ITRI), National Institute of Advanced Industrial Science and Technology (AIST)
    • HANAOKA Goichiro
    • Information Technology Research Institute (ITRI), National Institute of Advanced Industrial Science and Technology (AIST)
    • IWATA Tetsu
    • Dept. of Computational Science and Engineering, Nagoya University

Abstract

<p>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.</p>

Journal

  • IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences

    IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences E100.A(1), 73-90, 2017

    The Institute of Electronics, Information and Communication Engineers

Codes

Page Top