Paper 2021/678
Faster indifferentiable hashing to elliptic $\mathbb{F}_{\!q^2}$curves
Dmitrii Koshelev
Abstract
Let $\mathbb{F}_{\!q}$ be a finite field and $E\!: y^2 = x^3 + ax + b$ be an elliptic $\mathbb{F}_{\!q^2}$curve of $j(E) \not\in \mathbb{F}_{\!q}$. This article provides a new constanttime hash function $\mathcal{H}\!: \{0,1\}^* \to E(\mathbb{F}_{\!q^2})$ indifferentiable from a random oracle. Furthermore, $\mathcal{H}$ can be computed with the cost of $3$ exponentiations in $\mathbb{F}_{\!q}$. In comparison, the actively used (indifferentiable constanttime) simplified SWU hash function to $E(\mathbb{F}_{\!q^2})$ computes $2$ exponentiations in $\mathbb{F}_{\!q^2}$, i.e., it costs $4$ ones in $\mathbb{F}_{\!q}$. In pairingbased cryptography one often uses the hashing to elliptic $\mathbb{F}_{\!q^2}$curves $E_b\!: y^2 = x^3 + b$ (of $j$invariant $0$) having an $\mathbb{F}_{\!q^2}$isogeny $\tau\!: E \to E_b$ of small degree. Therefore the composition $\tau \circ \mathcal{H}\!: \{0,1\}^* \to \tau\big( E(\mathbb{F}_{\!q^2}) \big)$ is also an indifferentiable constanttime hash function.
Metadata
 Available format(s)
 Category
 Implementation
 Publication info
 Preprint. MINOR revision.
 Keywords
 constanttime implementationindifferentiability from a random oracleisogeniespairingbased cryptographyWeil restriction
 Contact author(s)
 dishport @ ya ru
 History
 20211208: last of 2 revisions
 20210525: received
 See all versions
 Short URL
 https://ia.cr/2021/678
 License

CC BY
BibTeX
@misc{cryptoeprint:2021/678, author = {Dmitrii Koshelev}, title = {Faster indifferentiable hashing to elliptic $\mathbb{F}_{\!q^2}$curves}, howpublished = {Cryptology ePrint Archive, Paper 2021/678}, year = {2021}, note = {\url{https://eprint.iacr.org/2021/678}}, url = {https://eprint.iacr.org/2021/678} }