Can anyone help me understand this: How do we say that one cryptographic primitive is stronger than another?
$\begingroup$
$\endgroup$
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
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.
