Privacy Reductions

[Yuval Madar]

Unless I missed something, it appears to me that privacy reductions,
as defined in definition 7.3.2, allow non-polynomial invocations of
the oracle. (Although each invocation is required to get polynomially-
sized inputs)

[Ron Rothblum]

Hi Yuval,

We think of each oracle invocation as a single execution step. Therefore the limiting factor is the use of the reduction - i.e. if we want the parties to run in polynomial-time then they can only invoke the oracle a polynomial number of times.

Does that help clarify?
Ron

[Yuval Madar]

Partially.
How are exponential time privacy reductions interesting?

Specifically, the last reduction we performed in the last exercise
(Following the suggestion in the book) is worst-case exponential time
(Though polynomial time on average) - if we keep failing at the OT
experiment. What makes this reduction interesting?

[Ron Rothblum]

Notice that the protocol in the hint takes more than n trials only with exponentially vanishing probability. In this case we can even get rid of this annoyance by changing the protocol so that after n trials the messages are sent in the clear. Functionality and running time are ok and privacy is maintained since our change only takes effect with exponentially vanishing probability (I suggest to think how to prove this formally).

Also let me mention that algorithms that runs in expected polynomial-time are of interest in cryptography and complexity even when we can't bound the worst case running time.

Ron