3
$\begingroup$

In the ideal/real proof paradigm we sometimes find simulators with the capacity of set adversary random tape.

My question: when do we have to consider the necessity of simulators set adversary random-tape?. We know that malicious adversary can substitute random-tape setup by whatever he want, but: are there cases where it's needed to consider this capacity with semi-honest adversary?

$\endgroup$
4
$\begingroup$

In the vast majority of cases, the simulator sets the random tape of the adversary simply because it has to (by the definition). So, the simulator sets it in the beginning to be uniform, and this is then ignored from then on.

There is one cases that I know of that this is actually really important, and this is non-black-box zero knowledge. Specifically, in Boaz Barak's thesis, he has a number of constructions. The construction which works for uniform verifiers has the property that the verifier has to have a short description. In order to make this work, the random tape of the verifier is actually chosen by the simulator pseudorandomly (rather than truly randomly) since this then has a short description.

I don't know of anywhere else that this is important. In general, choose it at random and ignore from then on...

$\endgroup$
  • $\begingroup$ I am not totally sure of this, but it seems to me that if we omit the requirement that the random tape of the corrupted party be simulatable, the OT protocol of Even-Goldreich-Lempel could be proven secure using a (non-enhanced) trapdoor permutation, which we know is false (that's why enhanced TDP were introduced in the first place). $\endgroup$ – fkraiem Feb 23 '16 at 0:31
  • $\begingroup$ @fkraiem: you MUST set the random tape of the adversary to be uniform in EGL. In general, semi-honest protocols can completely break otherwise. However, you don't need to do anything special with the tape. See Section 4.3 in eprint.iacr.org/2016/046.pdf (which has a full proof of EGL in tutorial style). $\endgroup$ – Yehuda Lindell Feb 23 '16 at 11:30
  • $\begingroup$ @McFly: You are most welcome!!! $\endgroup$ – Yehuda Lindell Feb 23 '16 at 11:30
  • $\begingroup$ Yes, what I meant was that the reason the definition requires us to set the adversary's random tape appropriately is that if it did not, obviously insecure protocols would satisfy it (such as EGL with a non-enhanced TDP). $\endgroup$ – fkraiem Feb 23 '16 at 11:58

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.