Type of Talk: Colloquia

Speaker Name/Affil

iation: Charanjit S. Jutla/IBM T. J. Watson Research Ctr.

Date/Time

: Thursday August 16 2007 11:00 a.m. - 12:15 p.m.

Location: AC

ES 2.402

Host: David Zuckerman

Talk Title: Average Case Com

plexity Good Codes and SHA

Talk Abstract:
We show a search probl

em which is similar to inverting SHA on uniform distribution over its outpu

ts to be average case hard for distributional search-NP. On the other hand

we believe showing a problem to be one-way even based on average case NP-ha

rdness seems unlikely. To this end we define novel complexity classes Avg-

NP and Avg-AM (not to be confused
with distributional-NP and AM) and w

e show (following Akavia et al) that for pre-image size-verifiable function

s f if there is an oblivious randomized Turing
reduction from average

case inverting f to average case NP hard problem then distribution NP is i

n Avg-co-AM (a hardness assumption).

The second part of the talk wi

ll focus on why collision finding is easier than inversion problem. We char

acterize local-collision strategies and prove that complexity of a general
class of recent attacks strategies is related to the minimum weight of a l

inear code given as sum of two low density parity codes. We describe novel

techniques to
lower bound minimum weight of such low density parity cod

es and argue that it leads to a good (computational) bound on finding low

weight codeword in the sum of the two codes.

Joint work with Anindya
Patthak.