IACR News item: 06 November 2015
Sanjam Garg, Omkant Pandey, Akshayaram Srinivasan
ePrint ReportBitansky, 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 *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} public key functional encryption and one-way permutations. Our results further demonstrate the power of polynomially hard public key functional encryption which is believed to be weaker than indistinguishability obfuscation.
Additional news items may be found on the IACR news page.