One-Way Functions

$f:\{0,1{\}}^{\ast }\to \{0,1{\}}^{\ast }$

A function that can be computed in polynomial time but computationally infeasible for a PPT adversary to invert, i.e. find a pre-image of value $y$.

Inverting experiment ${\text{Invert}}_{\mathcal{A},f}(n)$:

• Choose uniform $x\in \{0,1{\}}^n$, compute $y=f(x)$
• $\mathcal{A}$ gets $f,y$, outputs $x^{\prime }$
• $\mathcal{A}$ succeeds if $f(x^{\prime })=y$

Any function is one-way if:

• easy to compute

• hard to invert

• But any function that isn’t one-way doesn’t have to be easy to invert. There can an inverse polynomial probability of finding pre-image of function for certain values of x for $f$ to not be one-way.

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

• $f$ is one-way permutation, when $|f(x)|=|x|$ and one-one. then $\forall x\in \{0,1{\}}^n:f(x)=y⟹f^{-1}(y)=x$.

• One-way function families are used to output candidate one-way functions: $\text{Gen,Samp,}f$:

  • $\text{Gen}(1^n)$: outputs parameter $I:|I|\ge n$. Each I corresponds to $D_I,R_I$ domain and range of function $f_I$.
  • $\text{Samp}(I)$: outputs uniformly distributed elements of $D_I$
  • $f$: inputs $x\in D_I$, outputs $y\in R_I:=f_I(x)$.

• $\Pi$ is a permutation family if $R_I=D_I$ and $f:D_I\to D_I$ is a bijection.

• Similar experiment to: ${\text{Invert}}_{\mathcal{A},\Pi }(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 NP-complete, 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 non-invertible.

  • Classic example to this is Subset-Sum Problem where $f_{ss}(x_1,\dots ,x_n,J)=\left(x_1,\dots ,x_n,\left[{\sum }_{j\in J}{x}_j\mathrm{mod}{2}^n\right]\right)$. This problem is NP-complete.
  • 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$, hard-core predicates are exactly that. They’re the function that defines the information that is hidden by $f$.

• Hard-core predicates: a function $\text{hc}(x)$ of a function $f$ that can be computed in polynomial time, and for every PPT adversary, ${\mathrm{Pr}}_{x\leftarrow \{0,1{\}}^n}[\mathcal{A}(1^n,f(x))=hc(x)]\le \frac{1}{2}+\text{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 one-way.

OWF→PR (pseudorandom)

Let’s understand how each of these constructions happen and their proofs.

• Goldreich-Levin Theorem states that if OWF exist, then there exists a function $g$ and hard-core predicate $\text{gl}$ of $g$. defined as, $g(x)=(f(x),r)$ and $gl(x,r)\stackrel{def}{=}{⨁}_{i=1}^n{x}_i\cdot r_i$, i.e. if $f$ is OWF, then $f(x)$ hides the XOR of a random subset of $x$.
• $\text{OWP}\to {\text{PRG}}_{+1}$: Main result of [Goldreich-Levin][GL89] was to show how a pseudorandom generator of length $n+1$ can be calculated from a one-way permutation, such that $G(s)\stackrel{def}{=}f(s)\Vert \text{hc}(s)$ with $l(n)=n+1$.
• ${\text{PRG}}_{+1}\to {\text{PRG}}_{\text{poly}(n)}$: [Blum-Micali][BM82] showed that it’s possible to construct a PRG of any polynomial $\text{poly}$ with $l(n)=\text{poly}(n)$ from a PRG of $l(n)=n+1$.
• $\text{PRG}\to \text{PRF}$: For creating CPA-secure encryption, PRFs are needed, [Goldreich-Goldwasser-Micali][GGM86] showed how to construct PRF from PRG.
• $\text{PRF}\to \text{PRP}$: it was shown by [Luby-Rackoff][LR98], how to construct PRPs from PRFs.

Goldreich-Levin Theorem

To Prove: if $f$ is a OWF, then there exists a function $g(x,r)=(f(x),r)$, $\text{gl}(x,r)={⨁}_{i=1}^n{x}_i\cdot r_i$ of $g$.

Can be proven by modelling 2 adversaries ${\mathcal{A}}^{\prime },\mathcal{A}$ where $\mathcal{A}(f(x),r)=\text{gl}(x,r)$, i.e. $\mathcal{A}$ can give hard-core predicate and ${\mathcal{A}}^{\prime }(1^n,f(x))\in f^{-1}(f(x))$, i.e. if $\mathcal{A}$ can output hard-core predicate of $g$, then ${\mathcal{A}}^{\prime }$ can invert $f$ with some probability.

Prove this using three intermediate results:

• If $\mathcal{A}$ can output $gl$ with probability 1 always, then ${\mathcal{A}}^{\prime }$ works for all n and for all x.
• Tighten ${\mathcal{A}}^{\prime }s$ probability such that ${\mathrm{Pr}}_{x,r\leftarrow \{0,1{\}}^n}[\mathcal{A}(f(x),r)=\text{gl}(x,r)]\ge \frac{3}{4}+\frac{1}{p(n)}$ for some polynomial $p(\cdot )$, then ${\mathrm{Pr}}_{x\leftarrow \{0,1{\}}^n}[{\mathcal{A}}^{\prime }(1^n,f(x))\in f^{-1}(f(x))]\ge \frac{1}{4\cdot p(n)}$
• Make $\mathcal{A}$ more involved by $\mathrm{Pr}[\mathcal{A}(f(x),r)=\text{gl}(x,r)]\ge \frac{1}{2}+\frac{1}{p(n)}$, then $\mathrm{Pr}[{\mathcal{A}}^{\prime }(1^n,f(x))\in f^{-1}(f(x))]\ge \frac{1}{p^{\prime }(n)}$.
• This proves that if $\mathcal{A}$ can output $gl$ of $g$ with some non-negligible probability which is better than guessing the hard-core predicate, then $f$ can be inverted with some non-negligible probability, and hence, OWF exist if $\mathcal{A}$ doesn’t exist.

Complete proof: TODO

PRG from OWF

To prove: if $f$ is a OWP with hard-core predicate $\text{hc}$, then algorithm $G(x)=f(x)\Vert \text{hc}(x)$ is a PRG with $l(n)=n+1$.

${\mathrm{Pr}}_{r\leftarrow \{0,1{\}}^{n+1}}[D(r)=1]-{\mathrm{Pr}}_{s\leftarrow \{0,1{\}}^n}[D(f(s)\Vert hc(s))=1]\le \text{negl}(n)$

• First prove that above relation is equivalent to $\mathrm{Pr}[D(f(s)\Vert hc(s))=1]-\mathrm{Pr}[D(f(s)\Vert \overline{hc}(s))=1]\le \text{negl}(n)$.
• Then, create a reduction proof with adversary $\mathcal{A}$ that can output $hc(s)$, if $D$ can differentiate between $f(s)\Vert hc(s)$ and $f(s)\Vert \overline{hc}(s)$.
• so, $\mathrm{Pr}[\mathcal{A}(f(s))=hc(s)]=\frac{1}{2}\cdot (\mathrm{Pr}[D(f(s)\Vert hc(s))-D(f(s)\Vert \overline{hc}(s))])$. this means that if D outputs 0 then $\mathcal{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 $\text{poly}(n)$

References

• Intro to Modern Cryptography: Chapter 8