Speaker: Charanjit Jutla
IBM Watson
Monday, May 14
2:30 pm - 3:30 pm
EBU3b 4217

ABSTRACT
We show a problem with uniform distribution to be hard for flat-NP, where flat-NP is defined to be distributional NP problems (dist-NP) with distributions smooth w.r.t. uniform. We show that this problem models the inversion problem of cryptographic hash function SHA-1, but with uniform distribution on the output.

On the other hand, we show that basing oneway-ness even on hardness of flat-NP seems unlikely. To this end, we define new complexity classes Avg-NP (not to be confused with dist-NP), and Avg-AM. Extending a result of Akavia et al., we show that for size-verifiable functions f, there is no oblivious reduction from flat-NP hard languages to average case inverting f, unless flat-NP is in Avg-coAM. A similar result holds for dist-NP. We mention that flat-NP includes the discrete log problem over finite fields.