True or False?
If P=NP, then One-Way Functions exist.
False
If Strong One-Way Function exist, Weak One-Way Functions exist.
True
If Weak One-Way Functions exist, Strong One-Way Functions exist.
A function f : {0,1}* →{0,1}* is called strongly one-way if the following two conditions hold:
(1) There exists a polynomial-time algorithm A such that on input x, algorithm A outputs f(x);
(2) There is a probabilistic polynomial-time algorithm A' such that for every positive polynomial p and all sufficiently large n's,
Pr[A'(f(Uₙ),1ⁿ) ∈ f⁻¹(f(Uₙ))] < ¹/p₍n₎
A function f : {0,1}* →{0,1}* is called weakly one-way if the following two conditions hold:
(2) There exists a polynomial p such that for every probabilistic polynomial-time algorithm A' and all sufficiently large n's,
Pr[A'(f(Uₙ),1ⁿ) ∉ f⁻¹(f(Uₙ))] > ¹/p₍n₎
A function is (strongly) one-way if and only if it is one-way in its iterates.
In the Alice-Bob-Eve-setting of this lecture, there is a one-time identification protocol that is absolutely secure, i.e. the probability that Eve succeeds is zero.
If f is One-Way on its iterates, then for any probabilistic polynomial-time algorithm A' on input f⁽²⁾(x) with x chosen uniformly at random, the probability of A' outputting any pre-image of f⁽³⁾(x) is negligible.
In the one-time identification scheme of Alice, Bob, and Eve, where Alice sends the secret m (chosen from random distribution M) to identify (no One-Way Function involved), Eve's probability of cheating equals this formula.
If f is a One-Way function, then for any probabilistic algorithm, the probability of inverting f is negligible.
Even if One-Way Function do not exist, we have a secure one-time identification protocol for the "Two Guards Problem" (i. e. the Alice-Bob-Charlie-Even scenario).
For any function h : {0,1}ⁿ → {0,1}ᵏ, we have for the probability ε of guessing h(m) that
ε ⩾ ¹/₂ᵏ
Any δ-universal family of hash functions is strongly universal.
The function SHA-512 : {0,1}* → {0,1}⁵¹² is strongly universal.
If f : {0,1}* → {0,1}* is a (strongly) One-Way Function, so is f'(x) = "f(x) without the last bit".
Last changed5 years ago
