ABSTRACT
This chapter discusses the general problem of hashing into elliptic curves, particularly in the context of pairing-based cryptography. On the one hand, it is easy to see why this will typically break security proofs in the random oracle model. Indeed, at some point in a random oracle model security reduction, the simulator will typically want to “program” the random oracle by setting some of its outputs to specific values. In this case, it will want to set the value H(m) for some input m to a certain elliptic curve point P. A rather inefficient countermeasure that can be considered is to run all l iterations of the try-and-increment algorithm every time. On the other hand, it is often not clear how this problem translates into an actual security weakness for a protocol using the hash function.
