An adaptive attack on 2-SIDH. Issue 4 (1st October 2020)

• Record Type: Journal Article
• Authors: Dobson, Samuel; Galbraith, Steven D.; LeGrow, Jason; Ti, Yan Bo; Zobernig, Lukas
• Is Part Of: International journal of computer mathematics. Volume 5:Issue 4(2020)
• Page Start: 282
• Page End: 299
• Publication Date: 2020-10-01
• Subjects: Cryptography -- elliptic curves -- key exchange -- post-Quantum -- Isogeny-based cryptography; Computer systems -- Periodicals; Computer systems; Periodicals; 004
• DOI: 10.1080/23799927.2020.1822446
• Languages: English
• ISSNs: 2379-9927

Abstract

Abstract : We present a polynomial-time adaptive attack on the 2-SIDH protocol. The 2-SIDH protocol is a special instance of the countermeasure proposed by Azarderakhsh, Jao and Leonardi to perform isogeny-based key exchange with static keys in the presence of an adaptive attack. This countermeasure has also been recently explicitly proposed by Kayacan. Our attack extends the adaptive attack by Galbraith, Petit, Shani and Ti (GPST) to recover a static secret key using malformed points. The extension of GPST is non-trivial and requires learning additional information. In particular, the attack needs to recover intermediate elliptic curves in the isogeny path, and points on them. We also discuss how to extend the attack to k -SIDH when k >2 and explain that the attack complexity is exponential in k .