# How do we say that one cryptographic primitive is stronger than another?

Can anyone help me understand this: How do we say that one cryptographic primitive is stronger than another?

A cryptographic primitive $$Q$$ is stronger than another cryptographic primitive $$P$$ if $$Q$$ implies $$P$$ but the converse is not true. For concreteness, think of $$P$$ as one-way functions and $$Q$$ as public-key encryption.

The conventional way to show that $$Q$$ implies $$P$$ is via a black-box reduction of $$P$$ to $$Q$$: i.e.,

• first show an efficient construction $$C^{(\cdot)}$$ that, given black-box access to every instance (not necessarily efficient) $$\mathsf{Q}$$ of $$Q$$, yields an instance $$\mathsf{P}=C^{\mathsf{Q}}$$ of $$P$$; and
• then show an efficient security reduction $$\mathsf{R}^{(\cdot)}$$ that, given black-box access to every adversary (not necessarily efficient) $$\mathsf{A}_P$$ that breaks $$\mathsf{P}$$, yields an adversary $$\mathsf{A}_Q$$ that breaks $$\mathsf{Q}$$.

To see that a public-key encryption $$(\mathsf{G},\mathsf{E},\mathsf{D})$$ implies one-way functions, (for instance) set its key-generation algorithm as the one-way function, i.e., $$\mathsf{F}(1^n,r):=pk$$, where $$(pk,sk):=\mathsf{G}(1^n;r)$$.

On the other hand, to show that $$P$$ does not imply $$Q$$ one has to rule out all reductions of $$Q$$ to $$P$$, i.e., show a separation. For example, to show that $$P$$ does not imply $$Q$$ via black-box reductions, it suffices to describe an oracle $$\mathcal{O}$$ such that the primitive $$P$$ exists relative to $$\mathcal{O}$$, but all instances of $$Q$$ are broken. Since black-box reductions relativise, such reductions cannot exist. It was shown in [IR] that one-way functions do not imply public-key encryption via black-box reductions (this is highly non-trivial).

You can read more about the various flavours of reductions and separations in [RTV].

[IR]: Impagliazzo and Rudich, Limits on the Provable Consequences of One-way Permutations, STOC'89.

[RTV]: Reingold, Trevisan and Vadhan, Notions of Reducibility between Cryptographic Primitives, TCC'04.