One way functions

Question 1

Key Idea of Modern Cryptography

Answer 1

Use the intractability of some problems for the advantage of constructing secure system

Question 2

3 basic issues in Cryptography

Answer 2

• Identification
• Authentication
• Encryption

Question 3

What does one need to specify to define the security of a system?

Answer 3

1. What constitutes a failure?
2. The power of the adversary
   - computational resources
   - access to the system
   - what it means to break the system

Question 4

Shannon Entropy

Answer 4

At a conceptual level, Shannon’s Entropy is simply the “amount of information” in a variable. More mundanely, that translates to the amount of storage (e.g. number of bits) required to store the variable, which can intuitively be understood to correspond to the amount of information in that variable

Question 5

Min Entropy

Answer 5

Let X be random variable over alphabet Γ with distribution Px

The min entropy of X is
Hmin(X) = - log max x Γ Px (x)

The min entropy represents the most likely value of X

Property: Hmin(X) ≤ H(X)

Question 6

High Min Entropy and Passwords

Answer 6

Claim: If Alice and Bob agree on X such that Hmin(X) ≥ m, then the probability that Eve succeeds in cheating is at most 2-m

Proof: Make Eve deterministic, by picking her best choice, X = x’.
Prob[X=x’] = PX (x’) ≤ max X Γ PX (x) = 2 –Hmin(X) ≤ 2-m

Conclusion: passwords should be chosen to have high min-entropy!

Question 7

Computational Models:Asymptotic

Answer 7

Turing Machines with random tape

For classical models: precise model does not matter up to polynomial factor

Question 8

Computational Models: Concrete: Boolean circuits

Answer 8

A function f:{0,1}n → {0,1}n is called a (t,ε) one-way function, if
f is a polynomial-time computable function (independent of t)
for every t-time algorithm A,
Prob[A(f(x))  f-1(f(x)) ] ≤ ε

where x is chosen uniformly in  {0,1}n and the probability is also over the internal coin flips of A

Can either think of t and ε as being fixed or as t(n), ε(n)

Question 9

One-way functions - asymptotic

Answer 9

A function f: {0,1}* → {0,1}* is called a one-way function, if
f is a polynomial-time computable function
thus, also polynomial relationship between input and output length

for every probabilistic polynomial-time algorithm A, every positive polynomial p(.), and all sufficiently large n’s
Prob[ A(f(x))  f-1(f(x)) ] ≤ 1/p(n)

where x is chosen uniformly in {0,1}n and the probability is also over the internal coin flips of A

Question 10

Claim: if P=NP then there

Answer 10

Claim: if P=NP then there are no one-way functions

Question 11

Examples of hard problems:

Answer 11

• subset sum
• discrete log
• factoring

Question 12

Subset sum one-way function

Answer 12

function  f:{0,1}mn+n → {0,1}mn+m 
f(a1, a2 ,…, an , b1, b2 ,…, bn ) = 
(a1, a2 ,…, an , ∑ i=1n bi ai   mod 2m )

Question 13

Discrete Log Problem OWF

Answer 13

If difficult, f(g,x) = (g, gx ) is a one-way function.

Question 14

Integer Factoring OWF

Answer 14

Let g(r) be a function mapping random bits into random primes. 
The function f(r1,r2) = g(r1) • g(r2) is one-way

Question 15

Weak One-way function

Answer 15

A function f: {0,1}n → {0,1}n is called a weak one-way function, if

f is a polynomial-time computable function, and
there exists a polynomial p( ), s.t. for every probabilistic polynomial-time algorithm A, and all sufficiently large n’s it holds that
Prob[A[f(x)]  f-1(f(x)) ] ≤ 1-1/p(n)

is valid, where x is chosen uniformly in {0,1}n and the probability is also over the internal coin flips of A.

Question 16

Make a strong OWF from a week one

Answer 16

An instance of a hardness amplification problem.

Simple idea: repetition. For some polynomial q(n) define
g(x1, x2, …, xq(n) )=f(x1), f(x2), …, f(xq(n))