\newcommand{\mul}{\mathrm{mul}} \newcommand{\Enc}{\mathsf{Enc}} \newcommand{\Dec}{\mathsf{Dec}} \newcommand{\Gen}{\mathsf{Gen}} \newcommand{\Samp}{\mathsf{Samp}} \newcommand{\pp}{\mathrm{pp}} \newcommand{\univ}{\mathrm{univ}} \newcommand{\tinv}{\text{ inv}} \newcommand{\tnotinv}{\text{ not}\tinv} \newcommand{\tall}{\text{all }} \newcommand{\tsome}{\text{some }}

One-Way Functions

Motivation: Given the impossibility of efficient but perfectly secure encryption, we want to relax our security definition. Intuitively, we want to

  1. encrypt long plaintext many times using a single short key, and
  2. perform “fast” encryption and decryption given the legitimate key, and
  3. ensure that the recovering of plaintext is “hard” without the key.

One-time pads achieves 2 and 3 but not 1. However, OTP achieves 3 only bcs the key space is as large as message. Since we want 1, the key space is relatively small. Very vague, we want a encryption that is easy to compute (to achieve 1) but hard to find any k,mk,m that Enck(m)=c\Enc_k(m) = c. (This is vague bcs we can still try any kk' to decrypt cc.)

This suggests that we require functions that are

“easy” to compute but “hard” to invert.

That is called “one-wayness” in this lecture. We next define easy and hard computation in terms of efficiency and probability.

Definition of One-Way Functions

We try to define OWF using efficient computation and efficient adversary.

The first may come from NP-hardness.

Attempt: (Worst-Case)

A function f:{0,1}{0,1}f : \bits \to \bits is one-way if both of the following hold:

  1. Easy to compute. There is a PPT CC that computes f(x)f (x) on all inputs x{0,1}x \in \bits.
  2. Hard to Invert. No nuPPT adversary A\cA, for all nNn\in\N and x{0,1}nx \in \bit^n,

    Pr[A(1n,f(x))f1(f(x))]=1.\Pr[\cA(1^n, f (x)) \in f^{-1}( f (x))] = 1.

This is implied by NP⊈BPPNP \not\subseteq BPP, which is a long-open complexity problem. Majority of xx are easy (even we set prob 11/poly\ge 1 - 1/poly), open if it is useful for encryption.

Note: nuPPT can store any poly, so there may be more than poly are hard.

Attempt:

A function f:{0,1}{0,1}f : \bits \to \bits is one-way if both of the following hold:

  1. Easy to compute. There is a PPT CC that computes f(x)f (x) on all inputs x{0,1}x \in \bits.
  2. Hard to Invert. For all nuPPT adversary A\cA, for all nNn\in\N and x{0,1}nx \in \bit^n,

    Pr[A(1n,f(x))f1(f(x))]2n.\Pr[\cA(1^n, f (x)) \in f^{-1}( f (x))] \leq 2^{-n}.

Impossible: too strong, A\cA is NU and could have many (x,f(x))(x, f(x)) pairs. Note: A\cA takes 1n1^n as the security parameter in case f(x)n|f(x)| \ll n.

Randomize xx:

Attempt:

2. Hard to Invert. For any nuPPT adversary A\cA, for all nNn\in\N,

Pr[x{0,1}n;yf(x):f(A(1n,y))=y]2n.\Pr[x \gets \bit^n; y \gets f(x) : f(\cA(1^n, y)) = y] \leq 2^{-n}.

Still too strong: A\cA can take poly time to slash some of the possible xx.

We may relax by poly(n)/2npoly(n) / 2^n or 20.1n2^{-0.1 n} on the RHS, but they still too strong to find a candidate. We formalize “very small” by negligible functions, recalled below.

Definition: Negligible Function

Func ϵ(n)\eps(n) is negligible if for every cc, there exists some n0n_0 s.t. n>n0,ϵ(n)1/nc\forall n > n_0, \eps(n) \le 1/n^c.

Note: ϵ\eps is smaller than any inverse poly for sufficiently large nn.

Note: when the probability is 1ϵ(n)\ge 1-\eps(n), we often call it “overwhelming”.

Now we are ready to define OWFs.

Definition: (Strong) One-Way Function

A function f:{0,1}{0,1}f : \bits \to \bits is one-way if both of the following hold:

  1. Easy to compute. There is a PPT CC that computes f(x)f (x) on all inputs x{0,1}x \in \bits.
  2. Hard to Invert. For any nuPPT adversary A\cA, there exists a negligible function ϵ\eps that for any nNn\in\N,

    Pr[x{0,1}n;yf(x):f(A(1n,y))=y]ϵ(n).\Pr[x \gets \bit^n; y \gets f(x) : f(\cA(1^n, y)) = y] \leq \eps(n).

Note: each A\cA has a different ϵ\eps. The definition is asymptotic.

The above definition is standard in literature, but it is still hard to construct: any adversary can only invert a tiny fraction. Many natural candidates, such as factoring, does not meet this. We relax it:

Definition: Weak One-Way Function

A function f:{0,1}{0,1}f : \bits \to \bits is weak one-way if (… same as strong OWF.)

2. Hard to Invert. There exists a polynomial q:NNq: \N \to \N such that for any nuPPT adversary A\cA, for sufficiently large nNn\in \N,

Pr[x{0,1}n;yf(x):f(A(1n,y))=y]11/q(n).\Pr[x \gets \bit^n; y \gets f(x) : f(\cA(1^n, y)) = y] \leq 1 - 1/q(n).

Note: here the prob. 11/q1-1/q is the same for all adv A\cA, but in the strong OWF, the prob. ϵ\eps is different and depends on A\cA.

Example: some functinos are easy to invert

For any string x{0,1}x \in \bits, there are many easy-to-compute functions:

  • Identity, f(x):=xf(x) := x
  • Constant, f(x):=0f(x) := 0
  • Constant output length, f:{0,1}{0,1}4f: \bits \to \bit^4

All of them are easy to invert. Actually, for constant output length, we can invert with constant probability even without looking at f(x)f(x).

Example: Expanding input or output length

Suppose f:{0,1}n{0,1}(n)f: \bit^n \to \bit^{\ell(n)} for all nNn \in \N is a OWF, where (n)\ell(n) is a polynomial. We can obtain another OWF gg such that the output length is the same as input.

  • If output is longer, (n)>n\ell(n) > n, define gg to be g(x):=f(x[1...n]),x=(n).g(x) := f(x[1...n]), |x| = \ell(n).
  • If input is longer, (n)<n\ell(n) < n, define gg to be g(x):=f(x)0n(n).g(x) := f(x) \| 0^{n - \ell(n)}.

Clearly, such padding is poly-time computable since \ell is polynomial. The proof of “hard to invert” is a standard reduction.

Example: Any PRG is one-way

If g:{0,1}{0,1}g: \bit^* \to \bit^* is a PRG, then gg is a OWF.

Fact: OWFNPP\exists OWF \Rightarrow NP \neq P

Suppose that there exists a OWF ff, then there exists a language LNPL \in NP such that LPL \notin P.

The idea is to

  1. define the language LNPL \in NP using ff,
  2. assume for contradiction that NP=PNP = P so that we have a poly-time algorithm DD that decides LL,
  3. to construct a reduction that uses DD to invert ff, which is a contradiction.

A first attempt is to define

L:={f(x):x{0,1}}.L := \set{f(x) : x \in \bits}.

We have LNPL \in NP directly since for every yLy \in L, the witness of yy is xx such that f(x)=yf(x) = y, and correspondingly for yLy \notin L, there is no witness. However, such LL is unhelpful to invert ff: DD outputs 1 bit that does not tell us anything bout xx, and even worse, LL could be all binary strings when ff is a permutation (i.e., if ff is a one-way permutation, then deciding LL is trivial). To overcome it, we augment LL with all the prefixes of xx, that is,

L:={(f(x),x[1...i]):x{0,1},i[x]}.L := \set{(f(x), x[1...i]) : x \in \bits, i \in [|x|]}.

This way, for any y=f(x)y = f(x), the reduction can easily get the first bit of the pre-image by running iteratively D(y,b1),D(y,b1b2),D(y,b1b2b3)...D(y,b1b2b3...bn).D(y, b_1), D(y, b_1 b_2), D(y, b_1 b_2 b_3) ... D(y, b_1 b_2 b_3 ... b_n). In each iteration, the next bit ii is learned if D(y,b1...bi1bi)D(y, b_1 ... b_{i-1}b_i) accepts. This concludes the proof, and this proof can be extended to imply NP⊈BPPNP \not\subseteq BPP.

Primes and Factoring

The Prime Number Theorem

Define π(x)\pi(x) as the number of primes x\le x. PNT states that primes are dense.

Theorem: (Chebychev, 1848)

For all x>1x>1, π(x)>x2logx\pi(x) \gt \frac{x}{2 \log x}.

Note: the above is easier to prove, but the famous Prime Number Theorem is π(x)x/lnx\pi(x) \sim x / \ln x when xx \to \infty. The above log\log is base 2.

Assumption: Factoring

For any adv A\cA, there exists a negligible function ϵ\eps s.t.

Pr[(p,q)Πn2;rpq:A(r){p,q}]<ϵ(n),\Pr[(p,q) \gets \Pi_n^2; r \gets pq : \cA(r) \in \set{p,q}] \lt \eps(n),

where Πn:={p<2n:p prime}\Pi_n := \set{p \lt 2^n : p \text{ prime}} is the set of primes less than 2n2^n.

Define mul:N2N\mul: \N^2 \to \N by

mul(x,y)={1if x=1 or y=1(eliminating the trivial factor)xyo.w.\mul(x,y) = \begin{cases} 1 & \text{if } x = 1 \text{ or } y = 1 \text{(eliminating the trivial factor)}\\ x \cdot y & \text{o.w.} \end{cases}

Easy to compute. For many (x,y)(x,y) are “easy” to invert: w.p. at least 3/4 when xyxy even. It is not strong OWF.

Theorem:

If the factoring assumption is true, then mul\mul is a weak OWF.

mul\mul is easy to compute. Hard to invert?

Assume for contradiction (AC), for all poly qq, exists nuPPT AA, s.t. for infinitely many nNn\in \N,

Pr[(x,y){0,1}n;z=xy:mul(A(12n,z))=z]>11q(n).\Pr[(x,y)\gets \bit^n; z = xy : \mul(A(1^{2n}, z)) = z] \gt 1- \frac{1}{q(n)}.

Note: the negation of weak OWF.

Then, we construct an adversary BB breaks factoring.

Algorithm B(12n,z)B(1^{2n}, z):

  1. Sample (x,y){0,1}n(x,y) \gets \bit^n
  2. If both x,yx,y prime, let zˉz\bar z \gets z; otherwise, let zˉmul(x,y)\bar z \gets \mul(x,y).
  3. Run (xˉ,yˉ)A(12n,zˉ)(\bar x, \bar y) \gets A(1^{2n}, \bar z)
  4. Output (xˉ,yˉ)(\bar x, \bar y) if both x,yx,y are prime and z=xˉyˉz = \bar x \bar y.

We intentionally make the input to AA uniform in {0,1}2n\bit^{2n}.

By Chebychev, both x,yx,y prime w.p. >1/(2log2n)2=1/(4n2)\gt 1/ (2 \log 2^n)^{2} = 1/(4n^2). Hence, BB fails to pass zz to AA w.p. at most 11/(4n2)1 - 1/(4n^2).

By eq (AC), AA fails to invert zˉ\bar z w.p. at most 1/q(n)1/q(n). Choose q(n):=8n2q(n) := 8n^2 and AA correspondingly.

By union bound, the failure probability of BB is at most

Pr[zzˉA fails]Pr[zzˉ]+Pr[A fails]11/(4n2)+1/8n2=11/8n2,\Pr[z\neq \bar z \cup A \text{ fails}] \le \Pr[z\neq \bar z] + \Pr[A \text{ fails}] \le 1 - 1/(4n^2)+1/8n^2 = 1 - 1/8n^2,

and thus BB breaks factoring w.p. at least 1/8n21/8n^2, greater than negl, contradicting Factoring Assumption.

Note: the above reduction assumes efficient primality testing. That is not necessary, left as exercise.

Note: the pattern is common in crypto. Reduction from Assumption (factoring) to Construction (OWF) is bread and butter in this course.

From Weak OWF to Strong OWF

The existence of OWF is long-open. We will show that strong and weak OWFs are existentially equivalent. Clearly, any strong OWF satisfies weak. The challenge is from weak to strong.

We begin with a warmup.

Claim:

If {fn:{0,1}n{0,1}l}nN\set{f_n: \bit^n \to \bit^l}_{n\in\N} is a strong OWF, then g(x1,x2):=(f(x1),f(x2))g(x_1,x_2) := (f(x_1), f(x_2)) is also a strong OWF.

Assume for contradiction (AC), there exist poly p(n)p(n) and a nuPPT adv AA such that for infinitely many nNn\in\N,

Pr[x1,x2{0,1}n;y=g(x1,x2):g(A(12n,y))=y]>1/p(n).\Pr[x_1,x_2 \gets \bit^n; y = g(x_1,x_2) : g(A(1^{2n}, y)) = y] \gt 1/p(n).

We construct nuPPT BB that inverts ff.

Algorithm B(1n,y)B(1^n, y):

  1. x2{0,1}nx_2 \gets \bit^n and y2=f(x2)y_2 = f(x_2).
  2. Run x1,x2A(12n,(y,y2))x'_1, x'_2 \gets A(1^{2n}, (y,y_2)).
  3. Output x1x'_1 if f(x1)=yf(x'_1) = y.

For uniform z{0,1}nz\gets \bit^n, the above (y,y2)(y,y_2) is the same distribution as obtaining the output g(x1,x2)g(x_1,x_2) by sampling (x1,x2){0,1}2n(x_1,x_2)\gets \bit^{2n}.

Also, when AA inverts (y,y2)(y,y_2), we have that BB inverts zz successfully. By (AC), AA inverts w.p. >1/p\gt 1/p, greater than any negligible function, and it contradicts that ff is a strong OWF.

Note: this is a typical template to prove security by reduction. The quantifiers of (AC) is often the same (to negate negligible).

Observation: the definition of weak states that exist poly q(n)q(n) for all nuPPT; that is, even weak, there is a good fraction, 1/q1/q, of instances that are hard for all.

Idea: we repeat the weak ff for poly many instances and ask the Adv to invert all, so that Adv fails with high prob.

Theorem:

For any weak OWF fn:{0,1}n{0,1}lf_n: \bit^n \to \bit^l, there exists a poly m(n)m(n) such that

g(x1,...,xm):=(f(x1),...,f(xm))g(x_1, ..., x_m) := (f(x_1), ..., f(x_m))

from g:{0,1}mn{0,1}mlg: \bit^{mn} \to \bit^{ml} is a strong OWF.

Note: by def, there exists a poly q(n)q(n) s.t. no adv can invert ff w.p. 11/q(n)1-1/q(n).

Proof:

Assume for contradiction (AC), there exists a nuPPT adv AA and poly p(n)p(n) s.t. for inf many nNn\in\N, AA inverts gg w.p. 1/p\ge 1/p, i.e.,

Pr[{xi{0,1}n,yif(xi)}i[m],y(y1...ym):g(A(1n,y))=y]1/p(n).\Pr[\set{x_i\gets\bit^n, y_i \gets f(x_i)}_{i\in[m]}, y \gets (y_1...y_m) : g(A(1^n, y)) = y] \ge 1/p(n).

We want to construct a nuPPT BB to invert y=f(x)y=f(x) for uniform x{0,1}nx \gets \bit^n by running AA. So, the idea is to transform yy into an output of gg, that is (y1,...,ym)(y_1,..., y_m). How? (y,y,...,y)(y,y, ..., y)? (y,y2,...,ym)(y,y_2, ..., y_m)?

We construct B0B_0 as below to run AA.

Algorithm B0(1n,y)B_0(1^n, y):

  1. j[m]j \gets [m]
  2. x1,...,xm{0,1}nx_1, ..., x_m \gets \bit^{n}
  3. let yif(xi)y_i \gets f(x_i) for all ii
  4. let yjyy_j \gets y
  5. run x1,..,xmA(1mn,(y1,...,ym))x'_1, .., x'_m \gets A(1^{mn}, (y_1,..., y_m))
  6. if f(xj)=yf(x'_j) = y, output xjx_j, otherwise output \bot.

Note: B0B_0 inverts yy w.p. roughly 1/p1/p by (AC), where the probability is taken over yy and the random tapes. However, our goal is to invert w.p. 11/q1/p1-1/q \gg 1/p. Hence, repeating B0(y)B_0(y) is necessary.

Algorithm B(1n,y)B(1^n, y):

  1. repeatedly run B0(y)B_0(y) poly r1(n)r_1(n) many times using fresh randomness
  2. output the first non \bot output of B0B_0.

Note: we use the same yy as input, and that makes the probability analysis involved since the repetition is dependent.

By (AC), inverting gg is easy, intuitively there are many (x,y=f(x))(x,y=f(x)) that can be inverted by B0(y)B_0(y). Clearly that holds for AA, but as mentioned, we need to prove it for B0B_0.

The following claim is the key.

Claim: (many easy instances)

Suppose that (AC) holds. There exists a “large” set GnG_n of “easy” instances,

Gn:={x{0,1}n:Prx,y=f(x)[f(B0(y))=y]1/r2(n)}G_n := \set{x \in \bit^n : \Pr_{x, y=f(x)}[f(B_0(y)) = y] \geq 1/r_2(n)}

for some poly r2(n)r_2(n), and G(11/2q)2n|G| \geq (1 - 1/2q)\cdot 2^n.

If the claim holds, then BB can invert by repeating B0B_0:

Prx,y[B not inv]=Pr[B not invxG]+Pr[B not invxG]Pr[B not invxG]+Pr[xG](11/r2)r1+1/2qen+1/2q1/q\begin{align*} \Pr_{x,y}[B \tnotinv] & = \Pr[B \tnotinv \cap x \in G] + \Pr[B \tnotinv \cap x \notin G] \\ & \le \Pr[B \tnotinv | x \in G] + \Pr[x \notin G] \\ & \le (1-1/r_2)^{r_1} + 1/2q \\ & \le e^{-n} + 1/2q \le 1/q \end{align*}

We will choose r1(n):=nr2(n)r_1(n) := n \cdot r_2(n) to get (11/r2)r1en(1-1/r_2)^{r_1} \le e^{-n}.

Then, BB inverts w.p. >11/q\gt 1-1/q, and it is contradicting that ff is weak OWF. It remains to prove the claim.

Proof of Claim:

Intuition: GnG_n is B0B_0, but essentially B0B_0 is running AA. If G0G_0 is small, then AA should not invert w.p. 1/p\ge 1/p, and thus contra (AC).

Assume for contra (AC2), G0<(11/2q)2n|G_0| \lt (1-1/2q) \cdot 2^n. We have

Pr[A inv]=Pr[A invall xiGn]+Pr[A invsome xiGn]\Pr[ A \tinv] = \Pr[A \tinv \cap \tall x_i \in G_n] + \Pr[A \tinv \cap \tsome x_i \notin G_n]

Since the “easy” set GnG_n is small, it is unlikely all xix_i are easy. Formally, by (AC2)

Pr[A invall xiG]Pr[all xiG](11/2q)men.\begin{align*} \Pr[A \tinv \cap \tall x_i \in G] \le \Pr[\tall x_i \in G] \le (1-1/2q)^m \le e^{-n}. \end{align*}

Note: this is where the repetition mm kicks in (in the construction of gg), and we choose m(n):=n2q(n)m(n) := n \cdot 2q(n) to get the ineq.

Also, by union bound,

Pr[A invsome xiG]iPr[A invxiG]iPr[A invxiG]\begin{align*} \Pr[A \tinv \cap \tsome x_i \notin G] \le \sum_i \Pr[A \tinv \cap x_i \notin G] \le \sum_i \Pr[A \tinv | x_i \notin G] \end{align*}

Observe that Pr[A invxiG]\Pr[A \tinv | x_i \notin G] is very close to Pr[B0(y) invxG]\Pr[B_0(y) \tinv | x \notin G] as that of the claim. The only difference is that B0B_0 plant yy in random position. Indeed, for any fixed i[m]i \in [m],

Pr[x1,...,xm{0,1}n,y1f(x1),...,ymf(xm):A(y1,...,ym) invxiG]=Pr[j[m] in B:B0(y) invxGj=i]\begin{align*} \Pr[x_1,...,x_m\gets\bit^n, y_1\gets f(x_1), ..., y_m\gets f(x_m): A(y_1,...,y_m) \tinv | x_i \notin G]\\ = \Pr[j\gets[m] \text{ in } B : B_0(y) \tinv | x \notin G \cap j = i] \end{align*}

and thus

Pr[B0 invxG]=iPr[B0 invj=ixG]=iPr[B0 invj=ixG]/Pr[xG]=iPr[B0 invj=ixG](Pr[j=ixG]/Pr[xG])=iPr[A invxiG]Pr[j=i]=(1/m)iPr[A invxiG]\begin{align*} &\Pr[B_0 \tinv | x \notin G] \\ &= \sum_i \Pr[B_0 \tinv \cap j = i | x \notin G] \\ &= \sum_i \Pr[B_0 \tinv \cap j = i \cap x \notin G] / \Pr[x \notin G] \\ &= \sum_i \Pr[B_0 \tinv | j = i \cap x \notin G] \cdot \left(\Pr[j = i \cap x \notin G] / \Pr[x \notin G]\right)\\ &= \sum_i \Pr[A \tinv | x_i \notin G] \Pr[j=i] = (1/m) \sum_i \Pr[A \tinv | x_i \notin G] \end{align*}

We thus conclude

Pr[A invsome xiG]mPr[B0 invxG]<m1/r2.\begin{align*} \Pr[A \tinv \cap \tsome x_i \notin G] \le m \cdot \Pr[B_0 \tinv | x \notin G] \lt m \cdot 1 / r_2. \end{align*}

and thus

Pr[A inv]<en+m1/r2.\Pr[A \tinv] \lt e^{-n} + m \cdot 1/ r_2.

We choose r2(n)=2mp(n)r_2(n) = 2m \cdot p(n) so that Pr[A inv]<1/p\Pr[A \tinv] \lt 1/p, contradicting (AC).

Discuss The above parameter m(n):=n2q(n)m(n) := n\cdot 2q(n) is number of repetition on the weak OWF ff. Hence, the smaller the mm, the more efficienct the gg. Can we achieve a smaller mm?

A Universal OWF

Cryptographers seldom sleep well

–Silvio Micali, personal communication to Joe Kilian, 1988

The above shows that, if we believe factoring is hard, then we can construct a one-way function. Unfortunately, we do not know how to prove factoring is hard, and [Shor ‘94] is indeed an evidence that factoring might be easy. Fortunately for cryptographers, even if factoring is in polynomial time, we may still have OWFs that are constructed from other assumptions (since factoring is not powerful enough to solve many other problems). Still, given so many candidate OWFs, can we have a OWF that is as strong as all of them? Also, there are many candidate OWFs we don’t yet know. Can we construct a OWF that is as strong as any OWF, even those we don’t yet know?

That is the idea of Universal One-Way Functions. Alternatively speaking, we want to construct a OWF from the assumption that the existence of OWFs (notice the difference between the existence and the construction). It is like a “complete” function of OWFs. Similar to proving the first NP-complete problem, here we show a universal OWF (and then we can construct other OWFs from here). It is amazing as we get the strongest of all candidate OWFs.

The idea is to construct a function that computes all easy-to-compute functions. Since any OWF must be easy to compute with a constant size TM, using random strings, we can sample such TM with almost constant probability even we do not know which TM it is.

Function: funivf_\univ

Input: yy, let n:=yn := |y|.

  1. Interpret yy as a pair (M,x)(M,x) of Turing machine and bitstring, where M=logn|M| = \log n
  2. Run MM on xx for T=n2T=n^2 steps
  3. If MM halts in TT steps, output (M,M(x))(M,M(x)); otherwise, output \bot.

Theorem: A Universal Weak OWF

If there exists a OWF, then the above function funivf_\univ is a weak OWF.

To prove it, we will use the following lemma.

Lemma: Strong OWF in time O(n2)O(n^2)

If there exists a strongly one-way function gg , then there exists a strongly one-way function gg' that is computable in time O(n2)O(n^2).

Intuition: If there exists a strong OWF gg in time O(n2)O(n^2), then there exists (at least) a TM MgM_g that computes gg in O(n2)O(n^2) steps such that the description length Mg=d|M_g| = d is a constant. WLOG, assume the description of any TM can be padded with a special \bot symbol to arbitrary long. For any sMgs \ge |M_g|, let Mg,sM_{g,s} be the description of MgM_g padded to ss bits. Then, for all sufficiently large nn, the logn\log n-bit random prefix of yy is exactly Mg,lognM_{g,\log n} w.p. 1/n1/n. Hence, funiv(y)f_\univ(y) is hard to invert.

Formally, assume for contra (AC), for all poly q(n)q(n), there exists NUPPT AA s.t. for infinitely many nNn\in\N,

Pr[y{0,1}n,zfuniv(y):funiv(A(1n,z))=z]>11/q.\Pr[y\gets \bit^n, z \gets f_\univ(y) : f_\univ(A(1^n, z)) = z] \gt 1 - 1/q.

We construct NUPPT BB that inverts zg(x)z' \gets g(x) for x{0,1}nlognx\gets \bit^{n-\log n} by

  1. Run yA(1n,(Mg,z))y \gets A(1^n, (M_g,z')).
  2. Interpret yy as (M,x)(M, x).
  3. If M=MgM = M_g and z=g(x)z' = g(x), output xx; otherwise, output \bot.

Notice We uses MgM_g in BB because BB is asked to invert gg, which means that we know gg in this proof. Alternatively, we prove it without AC in lecture, and there is only probability analysis which does not depend on gg.

By (AC), we have

1/qPr[A not inv]Pr[A not invy=(Mg,)]Pr[y=(Mg,)]=Pr[A not invy=(Mg,)](1/n).\begin{align*} 1/q & \ge \Pr[A \tnotinv] \\ & \ge \Pr[A \tnotinv | y = (M_g, \star)] \Pr[y = (M_g, \star)] \\ & = \Pr[A \tnotinv | y = (M_g, \star)] \cdot (1/n). \end{align*}

Notice that

Pr[A not invy=(Mg,)]=Pr[x{0,1}nlogn,zg(x):B not inv].\Pr[A \tnotinv | y = (M_g, \star)] = \Pr[x\gets\bit^{n-\log n}, z' \gets g(x) : B \tnotinv].

Hence, we have

Pr[B not inv]n/q(n).\Pr[B \tnotinv] \le n / q(n).

Choosing q(n)=n2q(n) = n^2 and AA correspondingly, we have BB inverts w.p. at least 11/n1-1/n, that is greater than 1/p(m)1/p(m) for some polynomial pp and the input size m:=nlognm:= n - \log n of gg, contradicts gg is a strong OWF.

Proof of Lemma (Strong OWF in time O(n2)O(n^2))

Suppose we can compute gg in time ncn^c for some const c>2c \gt 2. Then, for any input x{0,1}ncx \bit^{n^c}, interpret x=x1x2x = x_1\|x_2 s.t. x1=ncn|x_1| = n^c - n, and then define g(x)=g(x1x2):=x1g(x2).g'(x) = g'(x_1\|x_2) := x_1 \| g(x_2). Let m=ncm=n^c be the input size of gg' It is easy to see that gg' is computable in O(m2)O(m^2) time, and it follows by standard reduction that gg' is hard to invert if gg is a OWF.

Note: The above construction is impractical due to inefficiency. Suppose there exists a OWF that is easy to compute by a TM of 1000 bits. The above needs a “sufficiently long” input so that logn1000\log n \ge 1000 to be a weak OWF, but that means the universal OWF is only hard for n=x21000n = |x| \ge 2^{1000}.

Discuss Can we find a more efficient construction of UOWF?

Collection of OWFs

To construct OWFs efficiently, many mathematical / computational assumptions are considered. The intuition is to consider efficiently sampleable distributions instead of uniformly random strings. The typical syntax is PPT algos (Gen,Samp)(\Gen, \Samp):

  • ppGen(1n)\pp \gets \Gen(1^n)
  • xSamp(1n,pp)x \gets \Samp(1^n, \pp)
  • fpp:{0,1}n{0,1}f_\pp : \bit^n \to \bit^\ast

And then, for all NUPPT adversary AA, there exists a negligible function ϵ\eps such that

Pr[ppGen(1n),xSamp(1n,pp),yfpp(x):fpp(A(1n,pp,y))=1]ϵ(n).\Pr[\pp\gets\Gen(1^n), x \gets \Samp(1^n, \pp), y \gets f_\pp(x) : f_\pp(A(1^n, \pp, y)) = 1] \le \eps(n).

For example, given the factoring assumption, we can construct a collection of OWF by

  • let Gen\Gen output nn directly,
  • let Samp\Samp output two nn-bit primes uniformly at random (using primality testing), and
  • let fppf_\pp be the nn-bit multiplication.

Other collections (such as RSA, discrete logarithm, or Rabin) are more involved in their constructions, and they provide additional “properties” on top of OWF.

Primality Testing

Definition: Group

A group GG is a set of elements with a binary operator \ast that satisfies the following properties:

  1. Closuer: a,bG,abG\forall a,b \in G, a \ast b \in G
  2. Identity: 1G\exists 1 \in G s.t. aG,1a=a1=a\forall a \in G, 1 \ast a = a \ast 1 = a.
  3. Associativity: a,b,cG,(ab)c=a(bc)\forall a, b, c \in G, (a\ast b) \ast c = a \ast (b \ast c).
  4. Inverse: aG,bG\forall a \in G, \exists b \in G s.t. ab=ba=1a \ast b = b \ast a = 1.

Definition: Euler’s Totient Function

Let Zn:={aN:a<n,gcd(a,n)=1}Z_n^* := \set{a \in \N : a < n, \gcd(a,n)=1} be the multiplicative group modulo nn. Let ϕ(n):=Zn\phi(n) := |Z_n^*| be the Euler’s totient.

Note: ϕ(n)=p1k11(p11)p2k21(p21)...\phi(n) = p_1^{k_1-1}(p_1-1) \cdot p_2^{k_2-1}(p_2-1) ... for n=p1k1p2k2...n = p_1^{k_1} \cdot p_2^{k_2} ... where pip_i are distinct primes.

Theorem: Chinese Remainder Theorem (CRT), or Extended Euclidean Algo

For any n1,n2Nn_1, n_2 \in \N s.t. gcd(n1,n2)=1\gcd(n_1, n_2) = 1,

Zn1n2Zn1×Zn2,Z_{n_1 n_2}^\ast \cong Z_{n_1}^\ast \times Z_{n_2}^\ast,

and we have poly time algos to transform from one representation to the other.

Theorem: (Euler)

nN,aZn,aϕ(n)=1mod  n\forall n \in \N, \forall a \in Z_n^*, a^{\phi(n)} = 1 \mod n

Let aZna \in Z_n^\ast, and let S:={ax:xZn}S := \set{ax : x \in Z_n^\ast}. We have S=ZnS = Z_n^* (otherwise, we have x1x2x_1 \neq x_2 but ax1=ax2ax_1 = ax_2, a contradiction given a1a^{-1} exists). Then, by commutative for the first equality,

xZnx=bSb=xZnax=aϕ(n)xZnx.\prod_{x \in Z_n^\ast} x = \prod_{b \in S} b = \prod_{x \in Z_n^\ast} ax = a^{\phi(n)} \prod_{x \in Z_n^\ast} x.

That implies aϕ(n)=1a^{\phi(n)} = 1.

Corollary: (Fermat’s Little Theorem)

For all prime pp,

aZp,ap1=1mod  p\forall a \in Z_p^*, a^{p-1} = 1 \mod p

Definition:

For any composite nNn \in \N, we say that aZna \in Z_n^* is a witness if an11mod  na^{n-1} \neq 1 \mod n.

Lemma: strict subgroup is small

Let GG be a finite group. If HGH \subset G is a strict subgroup of GG, then HG/2|H| \le |G| / 2.

Let bGb \in G be an element s.t. bHb \notin H. Consider elements in the set B:={ab:aH}B:=\set{ab : a \in H}. If there exists abHab \in H, then we have a1ab=bHa^{-1}ab = b \in H, contradiction. Hence, BH=B \cap H = \emptyset, and it remains to show that B=H|B| = |H|. Suppose for contradiction that B<H|B| < |H|, then there exist a1a2Ha_1\neq a_2 \in H s.t. a1b=a2ba_1 b = a_2 b, a contradiction since we can multiply b1b^{-1} on both sides.

Lemma:

For all nNn\in \N, if there exists a witness, then there are at least ϕ(n)/2\phi(n) / 2 witnesses.

Let HZnH \subset Z_n^* be the subset of none witnesses. We have 1H1 \in H, and HH is a subgroup modular nn. Given that there exists a witness, HH is a strict subgroup. We can then show that any strict subgroup is at most half size of the supergroup, ie, Hϕ(n)/2|H| \le \phi(n) / 2.

Definition: Strong witness

For any composite nNn \in \N, write n1=2rdn-1 = 2^r \cdot d for some integer rNr\in \N and odd dd. We say that aZna \in Z_n^* is a strong witness if

ad±1mod  n , and  a2id1mod  n for all i=1,2,...,r1\begin{align*} & a^d \neq \pm 1 \mod n ~\text{, and }~\\ & a^{2^i \cdot d} \neq -1 \mod n \text{ for all } i = 1,2,...,r-1 \end{align*}

Lemma: (warm up)

If aa is a witness, then aa is also a strong witness.

Assume for contradiction that aa is not a strong witness. Then the sequence ad,a2d,...,a2rda^d, a^{2d}, ..., a^{2^r d} is either

  • (±1,1,1,...,1)(\pm 1, 1, 1, ..., 1), or
  • (,,...,1,1,1,...,1)(\star, \star, ..., -1, 1,1, ..., 1).

Hence, aa is not a witness, a contradiction.

Lemma: (Miller-Rabin, every prime has no strong witness)

If nn prime, then there is no strong witness in ZnZ_n^*.

If nn prime, then the only solution to x2=1mod  nx^2 = 1 \mod n is ±1\pm 1 (need proof). By Fermat’s Little Theorem, for any aZna \in Z_n^*, a2rd=1mod  na^{2^r d} = 1 \mod n, and a2r1d=±1mod  na^{2^{r-1} d} = \pm 1 \mod n. If 1-1, then it is not a strong witness. Otherwise, 11, we can continue the next square root r2r-2, and so on, until ada^d, which must be ±1\pm 1.

It remains to show that every composite has many strong witnesses. The first step is to exclude perfect powers. The second step is to show that other composites have many strong witnesses.

Lemma:(Miller-Rabin, every composite has many strong witnesses)

If nn is composite such that n=n1n2n = n_1 \cdot n_2 for some coprime n1,n2n_1,n_2, then there are at least half strong witness in ZnZ_n^*.

Let H:={aZn:a is a not a strong witness}H:=\set{a \in Z_n^\ast : a \text{ is a not a strong witness}}. We will show that there exists HˉH\bar H \supset H s.t. Hˉ\bar H is a strict subgroup of ZnZ_n^*, which is sufficient (as HHˉZn/2|H| \le |\bar H| \le |Z_n^\ast|/2).

Let 2rd=n12^r d = n-1. For each aHa \in H, consider the sequence ad,a2d,...,a2rda^d, a^{2d}, ..., a^{2^r d}. Let jj be the largest index such that

aH,a2jd=1mod  n\exists a \in H, a^{2^j d} = -1 \mod n

(so that for all aHa\in H, a2j+1d=1mod  na^{2^{j+1}d} = 1 \mod n).

Such j<rj < r exists because (1)d=1mod  n(-1)^d = -1 \mod n since dd odd. Now, define

J:=2jd, and Hˉ:={a:aJ=±1mod  n}.J := 2^j\cdot d, \text{ and } \bar H:= \set{a : a^J = \pm 1 \mod n}.

Clearly, $H \subseteq \bar H$. Also, $\bar H$ is a subgroup (need proof). It remains to show that $\bar H$ is strict. Let $a\in \bar H$ be an element s.t. $a^J = -1 \mod n$ (where $a$ exists by def of $H$). Let $a_1 \in Z_{n_1}^\ast$ be the element s.t.

a=a1mod  n1.a = a_1 \mod n_1.

Then, we have

a1J=aJ=1mod  n1,a_1^J = a^J = -1 \mod n_1,

where the second equality holds by n=n1n2n=n_1n_2 and gcd(n1,n2)=1\gcd(n_1,n_2)=1. Let b1=a1mod  n1b_1=a_1 \mod n_1 and b2=1mod  n2b_2=1 \mod n_2, and let

b=b1mod  n1=b2mod  n2b = b_1 \mod n_1 = b_2 \mod n_2

by CRT. Then, we have

bJ=b1J=1mod  n1=b2J=1mod  n2.\begin{align*} b^J & = b_1^J = -1 \mod n_1 \\ & = b_2^J = 1 \mod n_2. \end{align*}

Because 1=1mod  n1=1mod  n21 = 1 \mod n_1 = 1 \mod n_2 and 1=1mod  n1=1mod  n2-1 = -1 \mod n_1 = -1 \mod n_2 are unique, bJ±1mod  nb^J \neq \pm 1 \mod n, which implies bHˉb \notin \bar H.

Algorithm: Miller-Rabin Primality Testing

Input: nn

  1. Output ‘No’ if nn even.
  2. Output ‘No’ if n=xyn = x^y is a perfect power for some x,yNx,y \in \N.
  3. Write n1n-1 as 2rd2^r d.
  4. Repeat λ\lambda times:
    • Sample uniformly aZna \gets Z_n^\ast (by computing gcd(a,n)\gcd(a,n)).
    • If aa is a strong witness, output ‘No’.
  5. Output ‘Yes’.

Theorem: For any prime nn, this algo outputs ‘Yes’ w.p. 1. For any composite nn, this algo outputs ‘Yes’ w.p. 2λ\le 2^{-\lambda}.

See also: Solovay-Strassen Primality Test

Article on Wikipedia

For odd nn and integer aa, let J(a,n)J(a,n) be the Jacobi symbol. The Solovay-Strassen primality test checks the given input nn by

  1. Sample random aa
  2. Compute J(a,n)J(a,n)
  3. Output “NOT PRIME” if a(n1)/2J(a,n)mod  na^{(n-1)/2} \neq J(a,n) \mod n.

Similar to Miller-Rabin, any prime nn always passes the test: J(a,n)J(a,n) is exactly the Legengre symbol, and the test is Euler’s criteria. For composit nn, there are witnesses and liars such that aa is a witness iff aa yields NOT PRIME. It can be shown that 1) the existence of witness and 2) the liars are a subgroup. That implies that there are at least half witnesses.

Ref: Martin Dietzfelbinger, Primality Testing in Polynomial Time