DLOG ⇒ OWF

Fully-black-box reduction · standard model · folklore · security loss: additive , the statistical distance of from uniform on

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