Indifferentiable hashing to ordinary elliptic $\mathbb{F}_{\!q}$-curves of $j=0$ with the cost of one exponentiation in $\mathbb{F}_{\!q}$

Dmitrii Koshelev

Abstract

Let $\mathbb{F}_{\!q}$ be a finite field and $E_b\!: y^2 = x^3 + b$ be an ordinary (i.e., non-supersingular) elliptic curve (of $j$-invariant $0$) such that $\sqrt{b} \in \mathbb{F}_{\!q}$ and $q \not\equiv 1 \: (\mathrm{mod} \ 27)$. For example, these conditions are fulfilled for the curve BLS12-381 ($b=4$). It is a de facto standard in the real world pairing-based cryptography at the moment. This article provides a new constant-time hash function $H\!: \{0,1\}^* \to E_b(\mathbb{F}_{\!q})$ indifferentiable from a random oracle. Its main advantage is the fact that $H$ computes only one exponentiation in $\mathbb{F}_{\!q}$. In comparison, the previous fastest constant-time indifferentiable hash functions to $E_b(\mathbb{F}_{\!q})$ compute two exponentiations in $\mathbb{F}_{\!q}$. In particular, applying $H$ to the widely used BLS multi-signature with $m$ different messages, the verifier should perform only $m$ exponentiations rather than $2m$ ones during the hashing phase.

Available format(s)
Category
Implementation
Publication info
Preprint.
Keywords
cubic residue symbol and cubic rootsindifferentiability from a random oraclepairing-based cryptography
Contact author(s)
dimitri koshelev @ gmail com
History
2021-09-29: last of 7 revisions
See all versions
Short URL
https://ia.cr/2021/301

CC BY

BibTeX

@misc{cryptoeprint:2021/301,
author = {Dmitrii Koshelev},
title = {Indifferentiable hashing to ordinary elliptic $\mathbb{F}_{\!q}$-curves of $j=0$ with the cost of one exponentiation in $\mathbb{F}_{\!q}$},
howpublished = {Cryptology ePrint Archive, Paper 2021/301},
year = {2021},
note = {\url{https://eprint.iacr.org/2021/301}},
url = {https://eprint.iacr.org/2021/301}
}

Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.