Functions with this property do not exist in Pessiland, the “worst of all possible worlds” according to Russell Impagliazzo’s “five worlds” paper. Miklós Ajtai names a family of functions proposed to have this property based on the short integer solution problem. A theorem that guarantees the existence of a hardcore predicate for every function with this property is named for Goldreich and Levin, who also proposed enumerating all computable Turing machines to construct a (*) “universal” function with this property. Modular squaring is part of a collection of functions thought to have this property named for Rabin, whose existence would imply that P ≠ NP. Multiplication has this property if factoring is “hard.” For 10 points, name this property possessed by functions ubiquitous in cryptography, which are easy to compute but difficult to invert. ■END■
ANSWER: one-way functions [or OWFs; accept trapdoor functions; accept Ajtai’s one-way function or Rabin’s one-way function or Levin’s universal one-way function]
<Science - Other Science - Math>
= Average correct buzz position