Bitansky, Paneth, and Rosen [FOCS 2015] prove the hardness of \ppad\ assuming the existence of quasi-polynomially hard indistinguishability obfuscation and sub-exponentially hard one-way functions. This leaves open the possibility of basing \ppad\ hardness on simpler, polynomially hard, computational assumptions.
We make further progress in this direction and reduce \ppad\ hardness directly to polynomially hard assumptions. Our first result proves hardness of \ppad\ assuming the existence of {\em polynomially hard} indistinguishability obfuscation (\io) and one-way permutations. While this improves upon Bitansky et al.'s work, it does not give us a reduction to simpler, polynomially hard computational assumption because constructions of \io\ inherently seems to require assumptions with sub-exponential hardness. In contrast, {\em public key functional encryption} is a much simpler primitive and does not suffer from this drawback. Our second result shows that $\ppad$ hardness can be based on {\em polynomially hard} compact public key functional encryption and one-way permutations. Our results further demonstrate the power of polynomially hard compact public key functional encryption which is believed to be weaker than indistinguishability obfuscation. Our techniques are general and we expect them to have various applications.
Category / Keywords: Original Publication (with minor differences): IACR-CRYPTO-2016 Date: received 5 Nov 2015, last revised 3 Jun 2016 Contact author: sanjamg at berkeley edu,omkant@gmail com,akshayaram@berkeley edu Available format(s): PDF | BibTeX Citation Version: 20160604:044836 (All versions of this report) Short URL: ia.cr/2015/1078 Discussion forum: Show discussion | Start new discussion