What is the specification (incl. requirements) of the identification problem with Alice, Bob and Eve?
What's Eve's probability of success in the identification problem of Alice, Bob and Eve where Alice and Bob agree on a shared secret?
What's the (Shannon) Entropy (incl. definition)?
What's min entropy?
What's the new requirement in the identification problem with Alice, Bob, Charlie and Eve?
What's the definition of the asymptotic version of one-way function?
What's the definition of the concrete version of one-way functions?
Why there are no one-way functions if P=NP?
If f is one-to-one it is a called a one-way permutation. In what complexity class does the problem of inverting one-way permutations reside?
NP, kann eine Lösung effizient überprüfen
If f is a one-way function, is f’ where f’(x) is f(x) with the last bit chopped a one-way function?
Ja, Beweis durch Kontraposition.
z. Z. f owf => f' owf
Kontraposition:
z. Z. f' not owf => f not owf
Bei geg. y = f(x),
invertiere chop_last_bit(y) und bekomme ein x'
x' ist mit Wkt. 1/2, x' mit f(x') = y
If f is a one-way function, is fᴸ where fᴸ(x) consists of the first half of the bits of f(x) a one-way function?
If f is a one way function is g(x) = f(f(x)) necessarily a one-way function?
Nein, können ein Beispiel für f geben, welches one-way ist: z. B. 0^n || z(snd_half(x)), wobei z one-way.
f(f(x)) ist dann konstant, folglich one-way.
What's the solution to the "password problem"? We have Alice, Bob, Charlie and Eve and we want Bob to move to the state Y if and only if Alice approves (thus protecting from Charlie and Eve).
What are example candidates for one-way functions?
One-way function based on subset sum (inverse: finding a subset sum)
Multiplication of two primes (inverse: prime factorization)
One-way function based on the discrete logarithm problem (inverse: find logarithm of given value and given its base)
sdfsdfsafddsaf
dsaffdsa
_dsafdsf_ sdfdsffdsfds
Last changed2 years ago
