Equidistribution Among Cosets of Elliptic Curve Points in Intervals

Journal of mathematical cryptology

article

Taechan Kim ; Mehdi Tibouchi

关键词: Character Sums;    Statistical Distance;    Elliptic Curve Cryptography;    Fault Analysis;   

DOI  :  10.1515/jmc-2019-0020

学科分类：社会科学、人文和艺术（综合）

来源: De Gruyter

【 摘 要 】

In a recent paper devoted to fault analysis of elliptic curve-based signature schemes, Takahashi et al. (TCHES 2018) described several attacks, one of which assumed an equidistribution property that can be informally stated as follows: given an elliptic curve E over ? q in Weierstrass form and a large subgroup H ⊂ E (? q ) generated by G ( x G , y G ), the points in E (? q ) whose x -coordinates are obtained from x G by randomly flipping a fixed, sufficiently long substring of bits (and rejecting cases when the resulting value does not correspond to a point in E (? q )) are close to uniformly distributed among the cosets modulo H . The goal of this note is to formally state, prove and quantify (a variant of) that property, and in particular establish sufficient bounds on the size of the subgroup and on the length of the substring of bits for it to hold. The proof relies on bounds for character sums on elliptic curves established by Kohel and Shparlinski (ANTS–IV).

【 授权许可】

CC BY|CC BY-NC-ND