Some Reductions Will Always Be Lossy

One of the last sessions at yesterday’s Eurocrypt was an excellent talk by Tibor Jager, who presented his paper On The Impossibility of Tight Cryptographic Reductions, which is joint work with Christoph Bader, Yong Li and Sven Schäge.

Recall that we often prove the security of a public key primitive by constructing an algorithm, called a reduction, that is able to violate some complexity assumption $A$ (like CDH or DDH) if it has access to an adversary that breaks the primitive. So if $A$ is true, then such an adversary cannot exist.

In the setting where there are $n$ users, it is often the case that the probability of the reduction breaking $A$ is $\frac{1}{n}$ times the probability that the adversary breaks the primitive. This is what we mean when we say that the reduction is not “tight”: it is essentially $n$ times easier for an adversary to break the primitive than for the reduction to violate $A$. If $n$ is very large, then we must choose very large parameters to be sure that the primitive is unbreakable with these parameters (assuming $A$ is true). So tight reductions are highly desirable in practice.

The paper presented yesterday shows that there are many public key primitives for which no tight reductions can exist. We will illustrate this here with the example of an encryption scheme, but the result easily generalises to other primitives.

Consider the following multi-user security game $G$ for an encryption scheme: the adversary is given $n$ public keys $pk_1, \dots, pk_n$, outputs an index $i$ between 1 and $n$, receives the secret keys $sk_j$ for $j \in \{1, \dots, n\} \setminus \{ i \}$, and wins the game if it outputs a valid secret key for $pk_i$.

This looks like an odd game and it corresponds to a very weak notion of security, but showing that no tight reduction exists for $G$ implies that no tight reduction exists for a more natural game: $n$-key IND-CPA where the adversary can adaptively corrupt up to $n-1$ secret keys and query its test oracle using a single uncorrupted key.

We will suppose that a reduction from $G$ to an assumption $A$ exists, and use the reduction itself to violate $A$ directly, without accessing an adversary against $G$. Instead, our meta-reduction will simulate an ideal adversary against $G$ and violate $A$ using the reduction's output from interacting with the simulated adversary. To do the simulation, we essentially replay the reduction $n$ times, supplying a different index $i$ each time and storing the secret keys returned by the reduction, provided that they are actually valid for the public keys. Then it is trivial to “win” $G$ by simply outputting one of these stored secret keys, so our meta-reduction behaves like a very powerful adversary against $G$.

One of two things can happen: either the reduction answers honestly for exactly one index $i$, in which case our rewinding strategy won’t work but the reduction isn’t tight; or our meta-reduction perfectly simulates an ideal adversary, so we violate $A$. So either the reduction isn’t tight, or $A$ is false.

Many of the technical details are omitted here, but it’s worth pointing out one of the conditions that is necessary for this argument to go through. Simply forwarding valid secret keys provided by the reduction doesn’t quite simulate an ideal adversary, since these secret keys could be “non-uniform” in some way. So there must be an efficient algorithm that takes a public key $pk$ and a valid secret key $sk$ and uniformly samples from all the valid secret keys for $pk$. The easiest way to achieve this is if there is exactly one valid secret key for each public key: the “resampling” algorithm just returns its input.

I find this result very neat. It represents the intersection of theoretical work and practical concerns; often the two are very different things.