light-weight exercise set for June 2nd

[עודד גולדרייך‎]

Please submit the following homework assignment on June 2nd.

Basically, I'd like you to do Exer 1 and 2 (in chapter 7).
They are supposed to be very easy.

Let me clarify that in Exercise 1, I mean that a function
(or circuit) $f$ from $m$-bit string to $n$-bit strings defines
a natural distribution on $n$-bit strings; i.e., $f(U_m)$.
The content of Exer 1 is getting a sample of this distribution
without revealing the coins used to generate it
(i.e., obtaining $f(r)$, for uniformly distributed $r\in\{0,1\}^m$,
without revealing $r$).

Those who think that "oblivious signing" as defined in Exer 2
is "idiotic/bad" (i.e., why would you want to sign arbitrary
documents)
may consider a version in which the signer is willing to sign any
document that satisfies some property (i.e., satisfies a predicate P),
but we want the signer to remain oblivious of the specific document.
That is, if the docomunt $x$ satisfies $P(x)=1$ then a signature
to $x$ should be produced, otherwise the answer should be "sorry".
Cast this refined version as a functionality (as in Exer 1)...

[Ron Rothblum]

Hi Everyone,

Since there seems to be some confusion here are some clarifications:

1. You only need to cast the problems in terms of secure computation and not actually present protocols.
2. In both exercises start by considering the case in which both parties get the same sample and generalize to sampling from a joint distribution.
3. The difference between the two exercises is that in the second one the distribution also depends on the parties inputs (and not just on randomness).

Ron

[Oded Goldreich]

Let me further clarify Ron's 2nd point:

In both exercises start by considering the case in which both parties

should obtain the same sample (as their local output)

and generalize to sampling from a joint distribution

(i.e., the distribution is over pairs,

and the i-th party gets the i-th element in the sampled pair).

2011/5/30 Ron Rothblum <roth...@gmail.com>