Cookie Consent

Buffl uses cookies to provide you with a better experience. You can find more information in our privacy policy.

Buffl
Buffl
Cryptography

First lecture

MJ
by Marl J.

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



Join Course
Preview

Author

Marl J.

Information

Last changed

Report course
© 2023 Buffl GmbH