SD ⇒ OWF

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

Statement

Let , and let map to the weight- vector of rank in a fixed efficient ordering of , so that for uniform is within statistical distance of uniform on . The function is a one-way function exactly when SD is hard for : a preimage of is with a solution of , and ranking any solution gives such an — folklore.