HW 1 Q1

HW 1 Q1

Guy Oren (guest) 13 Mar 2019 09:05

Hi,

I am not sure that I understand the definition of h. what is b?
Or more precisely, If we want to apply h to x from {0, 1}* how we do that?

Thanks,
Guy

Re: HW 1 Q1

eliadtsf 13 Mar 2019 12:02

Hi,
First, h_{p,g,y} is a function that maps a bit b \in {0,1} and an n-bit number x \in Z_p^* into an n-bit number in Z_p^* (I will add it later to the exercise). Since it is a one-bit compressing function, it must have collisions. Yet, the goal is to show that it is hard to find them (assuming DL is hard). The function does not defined for arbitrary strings in {0,1}*. CRH can be a property of functions of the form H = {H_n: {0,1}^m -> {0,1}^n} for a fixed m=m(n) (in our case, m = n+1), and not just for all strings domain.

Eliad.