Fault Attacks on Hyperelliptic Curve Discrete Logarithm Problem over Finite Fields

作者：Wang Mingqiang^*; Xue Haiyang; Zhan Tao

来源：China Communications, 2012, 9(11): 150-161.

• hyperelliptic curve
• discrete logarithm
• finite field
• genus
• cryptosystem

In this paper, we present two explicit invalid-curve attacks on the genus 2 hyperelliptic curve over a finite field. First, we propose two explicit attack models by injecting a one-bit fault in a given divisor. Then, we discuss the construction of an invalid curve based on the faulted divisor. Our attacks are based on the fact that the Hyperelliptic Curve Scalar Multiplication (HECSM) algorithm does not utilin the curve parameters and We consider three hyperelliptic curves as the attack targets. For curve with security level 186 (in bits), our attack method can get the weakest invalid curve with security level 42 (in bits); there are 93 invalid curves with security level less than 50. We also estimate the theoretical probability of getting a weak hyperelliptic curve whose cardinality is a smooth integer. Finally, we show that the complexity of the fault attack is subexponential if the attacker can freely inject a fault in the input divisor. Cryptosystems based on the genus 2 hyperelliptic curves cannot work against our attack algorithm in practice.

• 出版日期2012-11
• 单位山东大学; 中国科学院信息工程研究所