No fully-black-box reduction from iO + OWP to CRHF

Unconditional · against fully-black-box reductions · AS15

Statement

There is no fully-black-box construction of a collision-resistant hash function family from iO and a one-way permutation, even when the construction obfuscates circuits that call the permutation — AS15. Allowing such oracle-aided circuits covers the non-black-box use of the underlying primitives in punctured programming, with the obfuscator itself used as a black box; every such construction has an exponential security loss, so sub-exponential security assumptions do not help.

Notes

• The proof extends Simon’s collision-finding oracle to oracles that also answer obfuscation queries — Sim98, AS15.
• The same framework shows that every fully-black-box construction of key agreement with perfect completeness from private-key functional encryption for oracle-aided circuits has an exponential security loss — AS15.