Improved elliptic curve hashing and point representation
详细信息 查看全文
- 作者：Mehdi Tibouchi ; Taechan Kim
- 关键词：Elliptic curve cryptography ; Point encoding ; Elligator ; Character sums
- 刊名：Designs, Codes and Cryptography
- 出版年：2017
- 出版时间：January 2017
- 年：2017
- 卷：82
- 期：1-2
- 页码：161-177
- 全文大小：
- 刊物类别：Mathematics and Statistics
- 刊物主题：Combinatorics; Coding and Information Theory; Data Structures, Cryptology and Information Theory; Data Encryption; Discrete Mathematics in Computer Science; Information and Communication, Circuits;
- 出版者：Springer US
- ISSN：1573-7586
- 卷排序：82
文摘
For a large class of functions \(f:\mathbb {F}_q\rightarrow E(\mathbb {F}_q)\) to the group of points of an elliptic curve \(E/\mathbb {F}_q\) (typically obtained from certain algebraic correspondences between E and \(\mathbb {P}^1\)), Farashahi et al. (Math Comput 82(281):491–512, 2013) established that the map \((u,v)\mapsto f(u)+f(v)\) is regular, in the sense that for a uniformly random choice of \((u,v)\in \mathbb {F}_q^2\), the elliptic curve point \(f(u)+f(v)\) is close to uniformly distributed in \(E(\mathbb {F}_q)\). This result has several applications in cryptography, mainly to the construction of elliptic curve-valued hash functions and to the “Elligator Squared” technique by Tibouchi (in: Christin and Safavi-Naini (eds) Financial cryptography. LNCS, vol 8437, pp 139–156. Springer, Heidelberg, 2014) for representating uniform points on elliptic curves as close to uniform bitstrings. In this paper, we improve upon Farashahi et al.’s character sum estimates in two ways: we show that regularity can also be obtained for a function of the form \((u,v)\mapsto f(u)+g(v)\) where g has a much smaller domain than \(\mathbb {F}_q\), and we prove that the functions f considered by Farashahi et al. also satisfy requisite bounds when restricted to large intervals inside \(\mathbb {F}_q\). These improved estimates can be used to obtain more efficient hash function constructions, as well as much shorter “Elligator Squared” bitstring representations.