IACR News item: 30 October 2015
Mohammad Mahmoody; Ameer Mohammed; Soheil Nematihaji; Rafael Pass; Abhi Shelat
ePrint ReportWhether or not iO could be based on standard and well-studied hardness assumptions has remain an elusive open question.
In this work we prove \\emph{lower bounds} on the assumptions that imply iO in a black-box way, based on computational assumptions. Note that any lower bound for iO needs to somehow rely on computational assumptions, because if $\\P = \\NP$ then statistically secure iO does exist. Our results are twofold:
1. There is no fully black-box construction of iO from (exponentially secure) collision-resistant hash functions unless the polynomial hierarchy collapses. Our lower bound extends to (separate iO from) any primitive implied by a random oracle in a black-box way.
2. Let $\\cP$ be any primitive that exists relative to random trapdoor permutations, the generic group model for any finite abelian group, or degree-$O(1)$ graded encoding model for any finite ring. We show that achieving a black-box construction of iO from $\\cP$ is \\emph{as hard as} basing public-key cryptography on one-way functions.
In particular, for any such primitive $\\cP$ we present a constructive procedure that takes any black-box construction of iO from $\\cP$ and turns it into a a construction of semantically secure public-key encryption form any one-way functions.
Our separations hold even if the construction of iO from $\\cP$ is \\emph{semi-}black-box (Reingold, Trevisan, and Vadhan, TCC\'04) and the security reduction could access the adversary in a non-black-box way.
Additional news items may be found on the IACR news page.