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


1 Answer 1


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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.