Subset sum ⇒ OWF

Fully-black-box reduction · standard model · folklore · security loss: none

Statement

The function on is a one-way function exactly when subset sum is hard for , since its inversion game is the search game: a preimage of is with — folklore.