Posted by: jonkatz | August 29, 2009

Workshop announcement

I was asked to advertise the workshop Faces of Modern Cryptography, to be held at CUNY in September.

I was most intrigued by Luca’s talk, which appears to be the only one about an as-of-yet-unpublished result. I noticed that Luca gave a rump session talk on the same topic at the Impagliazzo’s worlds workshop a few months ago. I suppose I could email Luca for more details, but in the meanwhile does anyone have more info?



  1. Luca’s talk sounds very interesting, indeed. The last paragraph of his abstract means that any PRG can be broken with distinguishing advantage 2^{-n/2}, which sounds surprising to me. I remember hearing this “fact” being mentioned by other people, but never really saw why it was a fact (or a proof of it, for that matter).

  2. Apparently, this is a well known result, but not explicitly stated, that any PRG can’t have advantage better than 2^{-n/2}. The proof is simple: such PRG must be secure against linear tests, meaning it is an epsilon-biased set, and elementary Fourier analysis (Parseval’s identity) shows that that the sum of squares of all NON-TRIVIAL Fourier coefficients of any EXPANDING function is at least a constant. The expanding part is needed to cancel the trivial coefficient (corresponding to all 0 parity) and still have something left.

    Thus, at least one square of Fourier coefficient is roughly 2^{-n}, meaning that the coefficient itself is at least 2^{-n/2}. But the Fourier coefficient precisely measures to bias w.r.t. to particular parity.

    I also could not find this anywhere, but out a note in a recent paper of mine. See section 7 here:

    Btw, I wonder if there is some real evidence that for existing/most block ciphers, unpredictability is much easier to break than pseudorandomness.


  3. Yevgeniy –

    There is an interesting question, if the above result generalizes to a PRG in the CRS model. Although the CRS seems pointless, wouldn’t it kill the above argument? Namely, the “bias w.r.t some parity” now depends on the the CRS and so, even a non-uniform guy might have trouble knowing which way the bias goes (if it goes a different direction for each value of CRS, on average there is no bias).

    Jon –

    Thanks for providing a blog where I can waste time conversing with my advisor when I should be working on TCC papers. Perhaps this blog is a good first step in reducing # of publications in crypto….

    Daniel W.

  4. Yevgeniy – I assume you mean “pseudorandomness is easier to break than unpredictability”.

    Daniel – Interesting idea. But given a construction G in the CRS model, you get a construction G’ in the plain model via G'(crs, s) = (crs, G_{crs}(s)).

    …and I’m glad I can provide a forum where you can converse with your advisor instead of speaking to him in person!

  5. Jon-
    But the point is that G’ has a very long key and so you (might) get security 2^{-m/2} where m = |crs| + |s|. It’d be great if G (which has a much shorter key) had such high security, even with n-bit key. Of course, it cannot be better than 2^{-n}, but maybe, in CRS model, it could be better than 2^{-n/2}, if the CRS is long enough. In other words, public randomness might provide added security, getting us to the trivial 2^{-n} bound, without needing more private randomness.

  6. Yevgeniy: That’s a nice proof! thanks!

    anonymous (a.k.a Vinod)

Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )


Connecting to %s


%d bloggers like this: