SKE ⇒ OWF

Fully-black-box reduction · standard model · IL89 · security loss: polynomial

Statement

If a symmetric-key encryption scheme is secure for messages longer than its key — in particular, if it is CPA-secure — then a one-way function exists — IL89.

Sketch

If no one-way function exists, every efficiently computable function can be distributionally inverted: some efficient algorithm maps $f(x)$, for uniform $x$, to a preimage whose distribution is $1/\mathrm{poly}$-close to uniform among the preimages — IL89. Apply this to $f(s,m,r):=(m,\mathsf{Enc}(k,m;r))$ with $k:=\mathsf{KeyGen}(1^{\lambda };s)$ and $|m|>|k|$. The adversary submits uniform $m_0,m_1$, inverts $(m_0,c)$ on its challenge $c$ to obtain coins $s^{\prime }$, and outputs $0$ iff $\mathsf{Dec}(\mathsf{KeyGen}(1^{\lambda };s^{\prime }),c)=m_0$: when $c$ encrypts $m_0$, the pair $(m_0,c)$ is distributed as $f$‘s output and the test passes except with small probability, while a ciphertext of $m_1$ decrypts under the at most $2^{|k|}$ keys to at most $2^{|k|}$ messages, which contain the independent $m_0$ with probability at most $2^{|k|-|m|}\le 1/2$.

Notes

• The bound $|m|>|k|$ is necessary for one-time security: the one-time pad encrypts messages as long as its key with perfect secrecy and no assumption — folklore.
• The same distributional-inversion argument shows that commitment schemes and identification schemes require one-way functions — IL89.