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
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.
Efficient Computation and Efficient Adversaries
We want to provide “efficient computation” to the honest users.
Definition: Deterministic Algorithm
An algo
is a deterministic Turing Machine with input and output as bit strings, .
Note: TM is by definition uniform, that is, its description size is constant for all unbounded long inputs.
Definition: Polynomial Running-Time
runs in time if , halts within steps. runs in polynomial time if there exists a constant such that runs in time .
Definition: Efficient Computation
We say an algo is efficient if it runs in polynomial time.
Justification of poly time:
- Indep of computation models (TM, circuit, …)
- Closed under compositions of algos
- From human experience: poly-time become cubic, but super-poly remain hard
As discussed in perfect secrecy, we need randomized algo to construct encryption (and more generally crypto).
Definition: Randomized (or Probabilistic) Algorithm
A randomized algorithm
, also called a probabilistic polynomial-time Turing Machine and abbreviated as PPT, is a deterministic algorithm equipped with an extra random tape. Each bit of the random tape is uniformly and independently chosen. We denote the computation by
but sometimes omit . Note that the running-time is bounded by a poly for all .
As an example, we define efficient and correct encryption.
Definition: Efficient Private-key Encryption.
is called an efficient private-key encryption scheme if:
is PPT s.t. for every , it samples . is PPT s.t. , outputs . is PPT s.t. , outputs . - Correctness:
, ,
Note: the notation
Adversaries: Non-Uniform
Next we want to model adversaries with a stronger capability than honest.
Definition: Non-Uniform PPT
A non-uniform PPT machine (abbreviated nuPPT)
is a sequence of algos s.t.:
computes on inputs of length , and - exists a polynomial
s.t. the description size and the time is also less than . We write to denote the computation . Alternatively, an nuPPT algo can be defined as a uniform PPT
that takes an additional advice string of poly length for each input length .
Purpose: non-uniform gives adv extra power and models many real scenario, e.g., Eve may have a list of known (plain, cipher) pairs.
Discuss: the advice may not be computable in poly time (if poly-time, then no need to take advice as input). NU is closed under reduction.
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
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,
Randomize
Attempt:
2. Hard to Invert. For any nuPPT adversary
, for all ,
Still too strong:
We may relax by
Definition: Negligible Function
Func
is negligible if for every , there exists some s.t. .
Note:
Note: when the probability is
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
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.
Primes and Factoring
Define
Easy to compute. For many
Assumption: Factoring
For any adv
, there exists a negligible function s.t. where
is the set of primes less than .
The Prime Number Theorem
Define
Theorem: (Chebychev, 1848)
For all
, .
Note: the above is easier to prove, but the famous Prime Number Theorem is
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
Idea: we repeat the weak
Theorem:
For any weak OWF
, there exists a poly such that from
is a strong OWF.
Note: by def, there exists a poly
Proof:
Assume for contradiction (AC), there exists a nuPPT adv
We want to construct a nuPPT
We construct
Algorithm
:
- let
for all - let
- run
- if
, output , otherwise output .
Note:
Algorithm
:
- repeatedly run
poly many times using fresh randomness - output the first non
output of .
Note: we use the same
By (AC), inverting
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
We will choose
Then,
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).
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:
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,
. Also, is a subgroup (need proof). It remains to show that is strict. Let be an element s.t. (where exists by def of ). Let 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
A Universal OWF
The idea is to construct a function that computes all easy-to-compute functions.
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
Formally, assume for contra (AC), for all poly
We construct NUPPT
- Run
. - Interpret
as . - If
and , output ; otherwise, output .
Notice We uses
By (AC), we have
Notice that
Hence, we have
Choosing
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
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
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.