regarding Exer 2, and towards Exer 3

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

As I said in our last meeting, solving Exer 2 requires resolving
some annoying technical problems. I do want you to try to do so,
but I don't want you to spend too much time on it.
So if you cannot do it, you may assume the following *unjustified*
simplification assumption by which the gap on the first pair of
neighboring
hybrids is "large enough" (say at least as large as the average gap
between
neighboring hybrids). Note that this assumption cannot be justified
and is
made here onbly for sake of making the exercise easier.


Now to Exer 3 (to be submitted on 28/12).
In the meeting and in the book, pseudorandom functions
are defined as collctions of the form $\{f_s:\{0,1\}^{|s|}\to\{0,1\}^{|
s|}\}$
Consider generalized notions that refer to
1. For any function $\ell$ that is at most polynomial,
consider collctions of the form $\{f_s:\{0,1\}^{|s|}\to\{0,1\}
^{\ell(|s|})\}$.
2. Collctions of the form $\{f_s:\{0,1\}^{*}\to\{0,1\}^{|s|}\}$
(i.e., each #f_s$ maps the set of all strings to a single bit).
Present adequate definitions in each case and present adequate
constructions based on existence of pseudorandom generators.
(You may either modify the construction presented for the case treated
in the meeting and book, or just use such a pseudorandom function as
a building block.)

[Yuval Madar]

The latex is very hard to read. Is there any way to render it? (I am
seeing code instead of equations)

In 2, it appears that you wrote that each f_s maps all strings to a |
s|-long string, but you wrote that it maps them to a single bit. Which
is correct?

[Ron Rothblum]

On Mon, Dec 20, 2010 at 8:28 PM, Yuval Madar <yuv...@gmail.com> wrote:

The latex is very hard to read. Is there any way to render it? (I am
seeing code instead of equations)

If you're using MS Windows, you can "compile" the latex code into PDF or similar formats using
e.g., MikTeX. Alternatively there are fancy editors that also do the same job... Let me know if you
need help with that.
 

In 2, it appears that you wrote that each f_s maps all strings to a |
s|-long string, but you wrote that it maps them to a single bit. Which
is correct?

This is a typo, the function maps strings of length s to single bits.

Ron

[Ilan]

Now I am confused.... The function doesn't map any lenght string to a single bit? 

By bits you mean a sequence of bits or a single bit per map?

Thanks,

Ilan 

Sent from my iPod

[Ron Rothblum]

Sry I meant that it maps any length string to a single bit...

Ron

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

I was told that a solution to the new home assignement
(to be submitted on 28/12) can be found in my book.
That's more/less true. Since there is no point in copying text from
the book,
I wish to ask that you focus on presenting solutions that build on
the "standard" PRF (i.e., $f_s$ mapping $|s|$-bit string to $|s|$-bit
strings).
Please:
i) Present a solution to the original item (1) by using only a
standard PRF
(while noting that you can also get a PRG from that PRF...),
and prove its "security" (i.e., its pseudorandom feature).
ii) Same for the following variant on (2):
(2') collections $f_s$ that map strings of length SMALLER than $|s|
$
to a single bit.
That is, I make your life easier by asking to map ONLY strings of
length smaller than $|s|$,
rather than strings of arbitrary length.

BONUS/OPTIONAL: Do the original (2), but under the restriction above
(i.e., modify a given standard PRF rather than copy the book's
solution).

Recall: PRF === pseudorandom function,
PRG === pseudorandom generator.