Generally, in cryptography, the security of a scheme/protocol $\Pi$ relying on a hard problem $P$ is demonstrated by constructing a reduction $\mathcal{B}$ that takes as input an instance of the problem $P$ and then interacts in a black-box manner with an adversary $\mathcal{A}$ that can "break" the security of $\Pi$ to solve the given instance.

Usually, $\mathcal{B}$ has to properly simulate a "challenger" for $\mathcal{A}$ to ensure that $\mathcal{A}$'s strategy is consistent with the strategy that it typically uses to "break" $\Pi$. Properly simulating here generally means that the $\mathcal{A}$'s view (requests and responses) when it interacts with a challenger running $\Pi$ is indistinguishable from its view when it interacts with $\mathcal{B}$.

However, it seems the times it takes for the challenger to answer $\mathcal{A}$'s requests are omitted from $\mathcal{A}$'s view, and I was wondering if, in practice, that can help $\mathcal{A}$'s distinguish its typical challenger from $\mathcal{B}$. For instance, if $\mathcal{A}$'s challenger takes $O(n)$ time to answer $\mathcal{A}$'s request, and it takes $\mathcal{B}$ $O(n^3)$ time to answer $\mathcal{A}$'s request because $\mathcal{B}$ does not have access to trapdoor information that can help $\mathcal{A}$'s challenger to quickly form its response, can $\mathcal{A}$ use that time difference to know whether it is interacting with its typical challenger or with $\mathcal{B}$? Or can we leap and argue that realistically it will be hard for $\mathcal{A}$ to differentiate them because of hardware and network reasons?


1 Answer 1


I think you're missing the main point of reductions, which I would describe as the following

Any adversary $A$ that breaks the cryptographic algorithm can also be used to break the hardness assumption.

The reduction then describes a formula for how to convert $A$ into a new adversary $A'$ that is not much slower for the hardness assumption.

In particular, we don't view the adversary $A$ as being some actual person, constantly monitoring things. Instead, they are just code (say a PPT turing machine). We can execute them in a VM, and pause execution of the VM while we wait for the $O(n^3)$ reduction (or whatever). This is to say that we get all control over the computational environment they are in, so they can only "detect" something is different

  1. if the simulation is bad, or
  2. if we want them to.

This idea is also the justification for "rewinding" techniques. You cannot rewind some person wearing a fedora in a dark room (or whatever). But you can take a snapshot of the state of a VM, and restore it later.

  • $\begingroup$ This is correct insofar as our model of computation doesn't allow the adversary to notice the passage of time. This is because Turing-Machines have no notion of time beyond #steps. That this relates in any way to the real world is an assumption. It's true that, if an adversary has access to even an approximation of wall-clock time most rewinding strategies fail. The impossibility result in ia.cr/2019/253 e.g. essentially uses access to a blockchain to approximate the passage of time. Something the reduction can't simulate without breaking the supposed security of the blockchain. $\endgroup$
    – Maeher
    Jan 18 at 7:37

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.