Lecture 6
Review
is a weak one-way.
over random integers
Converting to strong one-way function
By factoring assumptions, strong one-way function
for infinitely many .
, .
Idea: With high probability, at least one pair are both prime.
Factoring assumption: has low chance of factoring
Use
Proof of strong one-way
- is efficiently computable, and we compute it poly-many times.
- Suppose it's not hard to invert. Then such that
We will use this to construct that breaks factoring assumption.
function B:
Receives N
Sample (x,y) q times
Compute z_i = f_mult(x_i,y_i) for each i
From i=1 to q
check if both x_i y_i are prime
If yes,
z_i = N
break // replace first instance
Let z = (z_1,z_2,...,z_q) // z_k = N hopefully
((x_1,y_1),...,(x_k,y_k),...,(x_q,y_q)) <- a(z)
if (x_k,y_k) was replaced
return x_k,y_k
else
return null
Let be the event that all pairs of sampled integers were not both prime.
Let be the event that failed to invert
Contradicting factoring assumption
We've defined one-way functions to hae domain for some .
Our strong one-way function
- Takes pairs of random integers
- Multiplies all pairs
- Hope at least pair are both prime b/c we know is hard to factor
General collection of strong one-way functions
, is the index set.
- We can effectively choose using .
- we ca efficiently sample .
- is efficiently computable
- For any n.u.p.p.t , negligible function .
Theorem
is a collection of strong one way function.
Ideas of proof:
- We can efficiently sample (with justifications)
- Factoring assumption
Algorithm for sampling a random prime
-
(n bit integer)
-
Check if is prime.
-
Deterministic poly-time procedure
-
In practice, a much faster randomized procedure (Miller-Rabin) used
-
-
If not, repeat. Do this for polynomial number of times
means and, means given that. usually interchangable with