HW1-Question 1

HW1-Question 1

daniel_c1 11 Nov 2019 12:09

Hi,

1. What exactly does it mean that E tosses n coins (represented by r) on top of the key sk? Is r connected to sk?
2. Is r choosed randomly (with uniform distribution) like sk is choosed randomly from {0, 1}^n?

Thanks

Re: HW1-Question 1

nbitansky 11 Nov 2019 12:39

1. No. $r$ is chosen independently (this is the usual model of probabilistic algorithms —- they sample coins independently of their input, which in this case is $sk,m$).
2. Yes.

If you're not familiar with probabilistic algorithms, you can read more about them in wikipedia or in Sipser's book for example.