One-Way Functions
Motivation: Given the impossibility of efficient but perfectly secure encryption, we want to relax our security definition. Intuitively, we want to
- encrypt long plaintext many times using a single short key, and
- perform “fast” encryption and decryption given the legitimate key, and
- 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 that . (This is vague bcs we can still try any to decrypt .)
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 is one-way if both of the following hold:
- Easy to compute. There is a PPT that computes on all inputs .
Hard to Invert. No nuPPT adversary , for all and ,
This is implied by , which is a long-open complexity problem. Majority of are easy (even we set prob ), 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 is one-way if both of the following hold:
- Easy to compute. There is a PPT that computes on all inputs .
Hard to Invert. For all nuPPT adversary , for all and ,
Impossible: too strong, is NU and could have many pairs. Note: takes as the security parameter in case .
Randomize :
Attempt:
2. Hard to Invert. For any nuPPT adversary , for all ,
Still too strong: can take poly time to slash some of the possible .
We may relax by or 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 is negligible if for every , there exists some s.t. .
Note: is smaller than any inverse poly for sufficiently large .
Note: when the probability is , we often call it “overwhelming”.
Now we are ready to define OWFs.
Definition: (Strong) One-Way Function
A function is one-way if both of the following hold:
- Easy to compute. There is a PPT that computes on all inputs .
Hard to Invert. For any nuPPT adversary , there exists a negligible function that for any ,
Note: each has a different . 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 is weak one-way if (… same as strong OWF.)
2. Hard to Invert. There exists a polynomial such that for any nuPPT adversary , for sufficiently large ,
Note: here the prob. is the same for all adv , but in the strong OWF, the prob. is different and depends on .
Example: some functinos are easy to invert
For any string , there are many easy-to-compute functions:
- Identity,
- Constant,
- Constant output length,
All of them are easy to invert. Actually, for constant output length, we can invert with constant probability even without looking at .
Example: Expanding input or output length
Suppose for all is a OWF, where is a polynomial. We can obtain another OWF such that the output length is the same as input.
- If output is longer, , define to be
- If input is longer, , define to be
Clearly, such padding is poly-time computable since is polynomial. The proof of “hard to invert” is a standard reduction.
Example: Any PRG is one-way
If is a PRG, then is a OWF.
Fact:
Suppose that there exists a OWF , then there exists a language such that .
The idea is to
- define the language using ,
- assume for contradiction that so that we have a poly-time algorithm that decides ,
- to construct a reduction that uses to invert , which is a contradiction.
A first attempt is to define
We have directly since for every , the witness of is such that , and correspondingly for , there is no witness. However, such is unhelpful to invert : outputs 1 bit that does not tell us anything bout , and even worse, could be all binary strings when is a permutation (i.e., if is a one-way permutation, then deciding is trivial). To overcome it, we augment with all the prefixes of , that is,
This way, for any , the reduction can easily get the first bit of the pre-image by running iteratively In each iteration, the next bit is learned if accepts. This concludes the proof, and this proof can be extended to imply .
Primes and Factoring
The Prime Number Theorem
Define as the number of primes . PNT states that primes are dense.
Theorem: (Chebychev, 1848)
For all , .
Note: the above is easier to prove, but the famous Prime Number Theorem is when . The above is base 2.
Assumption: Factoring
For any adv , there exists a negligible function s.t.
where is the set of primes less than .
Define by
Easy to compute. For many are “easy” to invert: w.p. at least 3/4 when even. It is not strong OWF.
Theorem:
If the factoring assumption is true, then is a weak OWF.
is easy to compute. Hard to invert?
Assume for contradiction (AC), for all poly , exists nuPPT , s.t. for infinitely many ,
Note: the negation of weak OWF.
Then, we construct an adversary breaks factoring.
Algorithm :
- Sample
- If both prime, let ; otherwise, let .
- Run
- Output if both are prime and .
We intentionally make the input to uniform in .
By Chebychev, both prime w.p. . Hence, fails to pass to w.p. at most .
By eq (AC), fails to invert w.p. at most . Choose and correspondingly.
By union bound, the failure probability of is at most
and thus breaks factoring w.p. at least , 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 is a strong OWF, then is also a strong OWF.
Assume for contradiction (AC), there exist poly and a nuPPT adv such that for infinitely many ,
We construct nuPPT that inverts .
Algorithm :
- and .
- Run .
- Output if .
For uniform , the above is the same distribution as obtaining the output by sampling .
Also, when inverts , we have that inverts successfully. By (AC), inverts w.p. , greater than any negligible function, and it contradicts that 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 for all nuPPT; that is, even weak, there is a good fraction, , of instances that are hard for all.
Idea: we repeat the weak for poly many instances and ask the Adv to invert all, so that Adv fails with high prob.
Theorem:
For any weak OWF , there exists a poly such that
from is a strong OWF.
Note: by def, there exists a poly s.t. no adv can invert w.p. .
Proof:
Assume for contradiction (AC), there exists a nuPPT adv and poly s.t. for inf many , inverts w.p. , i.e.,
We want to construct a nuPPT to invert for uniform by running . So, the idea is to transform into an output of , that is . How? ? ?
We construct as below to run .
Algorithm :
- let for all
- let
- run
- if , output , otherwise output .
Note: inverts w.p. roughly by (AC), where the probability is taken over and the random tapes. However, our goal is to invert w.p. . Hence, repeating is necessary.
Algorithm :
- repeatedly run poly many times using fresh randomness
- output the first non output of .
Note: we use the same as input, and that makes the probability analysis involved since the repetition is dependent.
By (AC), inverting is easy, intuitively there are many that can be inverted by . Clearly that holds for , but as mentioned, we need to prove it for .
The following claim is the key.
Claim: (many easy instances)
Suppose that (AC) holds. There exists a “large” set of “easy” instances,
for some poly , and .
If the claim holds, then can invert by repeating :
We will choose to get .
Then, inverts w.p. , and it is contradicting that is weak OWF. It remains to prove the claim.
Proof of Claim:
Intuition: is , but essentially is running . If is small, then should not invert w.p. , and thus contra (AC).
Assume for contra (AC2), . We have
Since the “easy” set is small, it is unlikely all are easy. Formally, by (AC2)
Note: this is where the repetition kicks in (in the construction of ), and we choose to get the ineq.
Also, by union bound,
Observe that is very close to as that of the claim. The only difference is that plant in random position. Indeed, for any fixed ,
and thus
We thus conclude
and thus
We choose so that , contradicting (AC).
Discuss The above parameter is number of repetition on the weak OWF . Hence, the smaller the , the more efficienct the . Can we achieve a smaller ?
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:
Input: , let .
- Interpret as a pair of Turing machine and bitstring, where
- Run on for steps
- If halts in steps, output ; otherwise, output .
Theorem: A Universal Weak OWF
If there exists a OWF, then the above function is a weak OWF.
To prove it, we will use the following lemma.
Lemma: Strong OWF in time
If there exists a strongly one-way function , then there exists a strongly one-way function that is computable in time .
Intuition: If there exists a strong OWF in time , then there exists (at least) a TM that computes in steps such that the description length is a constant. WLOG, assume the description of any TM can be padded with a special symbol to arbitrary long. For any , let be the description of padded to bits. Then, for all sufficiently large , the -bit random prefix of is exactly w.p. . Hence, is hard to invert.
Formally, assume for contra (AC), for all poly , there exists NUPPT s.t. for infinitely many ,
We construct NUPPT that inverts for by
- Run .
- Interpret as .
- If and , output ; otherwise, output .
Notice We uses in because is asked to invert , which means that we know in this proof. Alternatively, we prove it without AC in lecture, and there is only probability analysis which does not depend on .
By (AC), we have
Notice that
Hence, we have
Choosing and correspondingly, we have inverts w.p. at least , that is greater than for some polynomial and the input size of , contradicts is a strong OWF.
Proof of Lemma (Strong OWF in time )
Suppose we can compute in time for some const . Then, for any input , interpret s.t. , and then define Let be the input size of It is easy to see that is computable in time, and it follows by standard reduction that is hard to invert if 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 to be a weak OWF, but that means the universal OWF is only hard for .
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 :
And then, for all NUPPT adversary , there exists a negligible function such that
For example, given the factoring assumption, we can construct a collection of OWF by
- let output directly,
- let output two -bit primes uniformly at random (using primality testing), and
- let be the -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 is a set of elements with a binary operator that satisfies the following properties:
- Closuer:
- Identity: s.t. .
- Associativity: .
- Inverse: s.t. .
Definition: Euler’s Totient Function
Let be the multiplicative group modulo . Let be the Euler’s totient.
Note: for where are distinct primes.
Theorem: Chinese Remainder Theorem (CRT), or Extended Euclidean Algo
For any s.t. ,
and we have poly time algos to transform from one representation to the other.
Theorem: (Euler)
Let , and let . We have (otherwise, we have but , a contradiction given exists). Then, by commutative for the first equality,
That implies .
Corollary: (Fermat’s Little Theorem)
For all prime ,
Definition:
For any composite , we say that is a witness if .
Lemma: strict subgroup is small
Let be a finite group. If is a strict subgroup of , then .
Let be an element s.t. . Consider elements in the set . If there exists , then we have , contradiction. Hence, , and it remains to show that . Suppose for contradiction that , then there exist s.t. , a contradiction since we can multiply on both sides.
Lemma:
For all , if there exists a witness, then there are at least witnesses.
Let be the subset of none witnesses. We have , and is a subgroup modular . Given that there exists a witness, is a strict subgroup. We can then show that any strict subgroup is at most half size of the supergroup, ie, .
Definition: Strong witness
For any composite , write for some integer and odd . We say that is a strong witness if
Lemma: (warm up)
If is a witness, then is also a strong witness.
Assume for contradiction that is not a strong witness. Then the sequence is either
- , or
- .
Hence, is not a witness, a contradiction.
Lemma: (Miller-Rabin, every prime has no strong witness)
If prime, then there is no strong witness in .
If prime, then the only solution to is (need proof). By Fermat’s Little Theorem, for any , , and . If , then it is not a strong witness. Otherwise, , we can continue the next square root , and so on, until , which must be .
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 is composite such that for some coprime , then there are at least half strong witness in .
Let . We will show that there exists s.t. is a strict subgroup of , which is sufficient (as ).
Let . For each , consider the sequence . Let be the largest index such that
(so that for all , ).
Such exists because since odd. Now, define
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.
Then, we have
where the second equality holds by and . Let and , and let
by CRT. Then, we have
Because and are unique, , which implies .
Algorithm: Miller-Rabin Primality Testing
Input:
- Output ‘No’ if even.
- Output ‘No’ if is a perfect power for some .
- Write as .
- Repeat times:
- Sample uniformly (by computing ).
- If is a strong witness, output ‘No’.
- Output ‘Yes’.
Theorem: For any prime , this algo outputs ‘Yes’ w.p. 1. For any composite , this algo outputs ‘Yes’ w.p. .
See also: Solovay-Strassen Primality Test
For odd and integer , let be the Jacobi symbol. The Solovay-Strassen primality test checks the given input by
- Sample random
- Compute
- Output “NOT PRIME” if .
Similar to Miller-Rabin, any prime always passes the test: is exactly the Legengre symbol, and the test is Euler’s criteria. For composit , there are witnesses and liars such that is a witness iff 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