No fully-black-box reduction from PPAD hardness + OWF to KE

Unconditional · against fully-black-box reductions · RSS17

Statement

There is no fully-black-box construction of a key-agreement protocol from a one-way function together with average-case PPAD hardness, a hard-on-average distribution of End-of-Line instances, nor even from a one-way function together with a hard-on-average distribution of instances of the sink-of-verifiable-line problem (SVL) — RSS17. A hard-on-average SVL distribution gives a hard-on-average End-of-Line distribution by a black-box construction — BPR15, RSS17 — so the separation with SVL hardness implies the one with PPAD hardness.

Notes

• Without the one-way function, SVL hardness does not even give a one-way function by a fully-black-box construction: No fully-black-box reduction from PPAD hardness to OWF — RSS17.
• A CPA-secure PKE scheme gives two-message key agreement by a fully-black-box construction (PKE ⇒ KE) — folklore — so PKE has no fully-black-box construction from these hypotheses either — standard.