UTCS Colloquium: Charanjit S. Jutla IBM T. J. Watson Research Center Average Case Complexity Good Codes and SHA ACES 2.402 Thursday August 16 2007 at 11:00 a.m.
iation: Charanjit S. Jutla/IBM T. J. Watson Research Ctr.
: Thursday August 16 2007 11:00 a.m. - 12:15 p.m.
Host: David Zuckerman
Talk Title: Average Case Com
plexity Good Codes and SHA
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
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
- Awards & Honors
- About Us
- Student Engagement and Support
- Masters Program
- Ph.D. Program
- Financial Information
- Prospective Students
- Incoming Students
- Current Students
- Portfolio Program in Robotics
- Curricular Practical Training
- Grad Student Talks
- UTCS Direct