$f:{0,1}_{∗}→{0,1}_{∗}$
A function that can be computed in polynomial time but computationally infeasible for a PPT adversary to invert, i.e. find a preimage of value $y$.
Inverting experiment $Invert_{A,f}(n)$:
 Choose uniform $x∈{0,1}_{n}$, compute $y=f(x)$
 $A$ gets $f,y$, outputs $x_{′}$
 $A$ succeeds if $f(x_{′})=y$
Any function is oneway if:

easy to compute

hard to invert

But any function that isn’t oneway doesn’t have to be easy to invert. There can an inverse polynomial probability of finding preimage of function for certain values of x for $f$ to not be oneway.

Since $f$ is actually statistically invertible, by trying all values of $x∈{0,1}_{n}$, we’re intereted in computational hardness.

$f$ is oneway permutation, when $∣f(x)∣=∣x∣$ and oneone. then $∀x∈{0,1}_{n}:f(x)=y⟹f_{−1}(y)=x$.

Oneway function families are used to output candidate oneway functions: $Gen,Samp,f$:
 $Gen(1_{n})$: outputs parameter $I:∣I∣≥n$. Each I corresponds to $D_{I},R_{I}$ domain and range of function $f_{I}$.
 $Samp(I)$: outputs uniformly distributed elements of $D_{I}$
 $f$: inputs $x∈D_{I}$, outputs $y∈R_{I}:=f_{I}(x)$.

$Π$ is a permutation family if $R_{I}=D_{I}$ and $f:D_{I}→D_{I}$ is a bijection.

Similar experiment to: $Invert_{A,Π}(n)$.

OWFs are usually based on certain problems that are deemed to be hard, i.e. computationally hard. This is because even if a problem is NPcomplete, we only know it can’t be solved in polynomial time with the current known algorithms but still not mathematically proven whether solution to the problem is almost always noninvertible.
 Classic example to this is SubsetSum Problem where $f_{ss}(x_{1},…,x_{n},J)=(x_{1},…,x_{n},[∑_{j∈J}x_{j}mod2_{n}])$. This problem is NPcomplete.
 Thus, usual OWF are based on other hard problems like DLP.

To define better OWFs, one need to identify what sort of information does $f$ hides about input $x$, hardcore predicates are exactly that. They’re the function that defines the information that is hidden by $f$.

Hardcore predicates: a function $hc(x)$ of a function $f$ that can be computed in polynomial time, and for every PPT adversary, $Pr_{x←{0,1}_{n}}[A(1_{n},f(x))=hc(x)]≤21 +negl(n)$, i.e. boolean functions that are hard to guess right.

Note that: HC isn’t necessarily defined for OWFs, but for permutations, hc is only defined, if it’s oneway.
OWF→PR (pseudorandom)
Let’s understand how each of these constructions happen and their proofs.
 GoldreichLevin Theorem states that if OWF exist, then there exists a function $g$ and hardcore predicate $gl$ of $g$. defined as, $g(x)=(f(x),r)$ and $gl(x,r)def⨁_{i=1}x_{i}⋅r_{i}$, i.e. if $f$ is OWF, then $f(x)$ hides the XOR of a random subset of $x$.
 $OWP→PRG_{+1}$: Main result of [GoldreichLevin][GL89] was to show how a pseudorandom generator of length $n+1$ can be calculated from a oneway permutation, such that $G(s)deff(s)∥hc(s)$ with $l(n)=n+1$.
 $PRG_{+1}→PRG_{poly(n)}$: [BlumMicali][BM82] showed that it’s possible to construct a PRG of any polynomial $poly$ with $l(n)=poly(n)$ from a PRG of $l(n)=n+1$.
 $PRG→PRF$: For creating CPAsecure encryption, PRFs are needed, [GoldreichGoldwasserMicali][GGM86] showed how to construct PRF from PRG.
 $PRF→PRP$: it was shown by [LubyRackoff][LR98], how to construct PRPs from PRFs.
GoldreichLevin Theorem
To Prove: if $f$ is a OWF, then there exists a function $g(x,r)=(f(x),r)$, $gl(x,r)=⨁_{i=1}x_{i}⋅r_{i}$ of $g$.
Can be proven by modelling 2 adversaries $A_{′},A$ where $A(f(x),r)=gl(x,r)$, i.e. $A$ can give hardcore predicate and $A_{′}(1_{n},f(x))∈f_{−1}(f(x))$, i.e. if $A$ can output hardcore predicate of $g$, then $A_{′}$ can invert $f$ with some probability.
Prove this using three intermediate results:
 If $A$ can output $gl$ with probability 1 always, then $A_{′}$ works for all n and for all x.
 Tighten $A_{′}s$ probability such that $Pr_{x,r←{0,1}_{n}}[A(f(x),r)=gl(x,r)]≥43 +p(n)1 $ for some polynomial $p(⋅)$, then $Pr_{x←{0,1}_{n}}[A_{′}(1_{n},f(x))∈f_{−1}(f(x))]≥4⋅p(n)1 $
 Make $A$ more involved by $Pr[A(f(x),r)=gl(x,r)]≥21 +p(n)1 $, then $Pr[A_{′}(1_{n},f(x))∈f_{−1}(f(x))]≥p_{′}(n)1 $.
 This proves that if $A$ can output $gl$ of $g$ with some nonnegligible probability which is better than guessing the hardcore predicate, then $f$ can be inverted with some nonnegligible probability, and hence, OWF exist if $A$ doesn’t exist.
Complete proof: TODO
PRG from OWF
To prove: if $f$ is a OWP with hardcore predicate $hc$, then algorithm $G(x)=f(x)∥hc(x)$ is a PRG with $l(n)=n+1$.
$Pr_{r←{0,1}_{n+1}}[D(r)=1]−Pr_{s←{0,1}_{n}}[D(f(s)∥hc(s))=1]≤negl(n)$
 First prove that above relation is equivalent to $Pr[D(f(s)∥hc(s))=1]−Pr[D(f(s)∥hc(s))=1]≤negl(n)$.
 Then, create a reduction proof with adversary $A$ that can output $hc(s)$, if $D$ can differentiate between $f(s)∥hc(s)$ and $f(s)∥hc(s)$.
 so, $Pr[A(f(s))=hc(s)]=21 ⋅(Pr[D(f(s)∥hc(s))−D(f(s)∥hc(s))])$. this means that if D outputs 0 then $A$ outputs $R$
Now our goal is to prove that if PRG of expansion factor of N+1 exsits then a PRG of expansion factor $poly(n)$