Is there any way to hash from a string $\in \{0,1\}^{*}$ into a supersingular elliptic curve $E(F_p)$ such that the hash function behaves(provably) like a random oracle, and is efficient?

Using Maurer's indifferentiability framework 1, one can prove that a cryptosystem using a random oracle is secure if the random oracle is replaced by an "indifferentiable" hash function. Brier et. al. 2 prove the conditions for a hash function to be indifferentiable from a random oracle, i.e. to put it simply, the hash function has to use an "admissable encoding" of elliptic curve points. They also provide a construction based on Icart's function that appears to work only on ordinary elliptic curves.

My question is, does there exist similar such constructions for supersingular elliptic curves? The Boneh-Franklin IBE requires the use of a hash function to a supersingular elliptic curve. They construct a hash function and prove that their IBE scheme is secure using the new construction. However, they do not prove that this construction is "indifferentiable" from a random oracle, or that this construction can be used in any other cryptographic scheme without altering its security.


Elligator works just fine for any (including supersingular) elliptic curve with a point of order $2$, with the sole exception of $j=1728$. The latter special case can also be done; see Section 4.2 here.

(The requirement that the curve has a point of order $2$ is trivially fulfilled for supersingular $E/\mathbb F_p$ where $p>3$ is prime, since this implies $\#E(\mathbb F_p)=p+1$ which is always even.)

| improve this answer | |

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.