Yilei Chen: Fiat-Shamir and Correlation Intractability from Strong KDM-Secure Encyrption

We construct simple functions that suffice for realizing the Fiat Shamir paradigm when applied to any interactive proof. More generally, our functions are correlation intractable w.r.t. all relations.

 

Our construction relies on the existence of encryption schemes where polytime key-dependent-message attacks succeed only with exponentially small probability. We then provide parameter settings where the El-Gamal and Regev encryption schemes plausibly enjoy such level of security. Our analysis closely follows that of Kalai, Rothblum and Rothblum (Crypto 17), who obtain similar results based on strong variants of program obfuscation. Thus, our main contribution is removing the use of obfuscation from their construction.

 

We also extend the notion of correlation intractability so as to capture the properties required from hash functions used for proof-of-work (as in Bitcoin). We discuss the applicability of our constructions and analyses in that regime.