DLOG ⇒ OWF
Statement
Let be a group generator for which DLOG is hard, let be the number of random bits it uses, and let , where bounds the bit length of every order that outputs. The function on , with and read as an integer, is a one-way function, with inversion advantage at most the DLOG advantage plus : is within statistical distance of uniform on , and any preimage of has in the same group of order , so — folklore.
Notes
- For a general group generator, a PRG follows from this function through OWF ⇒ PRG — HILL99. For DLOG in , the Blum–Micali generator is a direct construction — BM84.