Times of nested algorithms in proofs of security

Question

Proofs of security may be constructed such that an adversary $A$ is used to construct an adversary $A'$. The reduction/algorithm which uses $A$ has to perform a number of computations in order to simulate the environnement of $A$ (t.i.t.s to intercept/answer to queries from $A$).

I've noticed that we evaluate the time $t'$ taken by $A'$ such that $t'=t+n \cdot t_c$ where $t$ is the time taken by $A$, $n$ is the number of computations made by the reduction and $t_c$ the time to perform one computation.

I don't understand why we generally conclude that $t \ge t' - n \cdot t_c$. I don't understand why we remove the quantity $n \cdot t_c$. It seems to me that $A$ and $A'$ terminate at virtually the same time ($A'$ uses the output from $A$ almost immediately).

An example: Assume that a computation needs $1$ unit of time. An algorithm $A'$ uses $A$ as follows:

• $A$ makes a query (the elapsed time for $A$ and $A'$ is $1$)

• $A'$ makes a computation and responds to $A$ (the overall elapsed time for $A$ and $A'$ is 2)

• $A$ makes a query (the overall elapsed time for $A$ and $A'$ is $3$)

• $A'$ makes a computation and responds to $A$ (the overall elapsed time for $A$ and $A'$ is 4)

• etc ...

• when $A$ terminates and gives the result to $A'$, we assume there is not need for more computations. It seems that $A$ and $A'$ terminate at the same time.

We see in this example that it's strange for $A$ to remove the time of computations (unless these computations are considered as "free").

Answer 1

You always need to have in mind that $A$ is a hypothetical algorithm, since our goal in the reduction is to contradict the existence of such an efficient $A$.

Now to your concrete security framework: Here, you are not satisfied by the fact that a hypothetical poly-time $A$ implies a poly-time reduction $A'$, but your aim is that the reduction does not take significantly more time than $A$ and you want to quantify that difference. So you want to relate the running time $t$ of such an hypothetical $A$ to the runtime $t'$ of the reduction $A'$ where $A'$ simulates the environment of the real attack game for $A$ such that $A$ cannot distinguish the real game from the simulated game in the reduction.

What you already observed in your question is the runtime of $A'$ is $t'=t+n \cdot t_c$, where $t$ is the time taken by $A$, $n$ is the number of computations made by the reduction and $t_c$ the time to perform one computation (such as an exponentiation of a group element). The term $n\cdot t_c$ typically includes all the overhead that $A'$ has to make, transformations required to the problem instance that $A'$ receives in order to "give" it to $A$ as part of some parameters or as answers to oracle queries and transforming the output of $A$ to a solution to the instance of the input problem if necessary. Furthermore, the operations that are required the answer the oracle calls that $A$ makes to the oracles that are simulated by $A'$. Often you will also encounter in such concrete reductions that the number of oracle queries and the associated costs are made more explicit. Anyways, observe that the runtime of $A$ does not include the time the oracles require to answer since this is counted in the $n\cdot t_c$ term (this is work done by $A'$, since it simulates the oracles for $A$).

Actually, I think there is a bug in your question, since I think you mean that $t'\leq t+n \cdot t_c$ which is simply since your constructed reduction $A'$ gives an upper bound on the runtime (there may be more efficient reductions $A''$, which you did not figure out, but you have one and it can only get better. Hence the $\leq$).

Answer 2

The equation $t'=t+n\cdot t_c$ is an estimation to put an upper limit on $t'$. It might be possible that an attacker $A'$ can use a different, more efficient algorithm. But since the attack will work with using $A$, there exists an attacker $A'$ with at most $t'$. This means it's actually not an equation, but an inequality $t' \leq t + n \cdot t_c$. And then the next step is just a standard transformation to get $t' - n \cdot t_c \leq t$.

Edit: Actually, this assumes that $A'$ only has to run $A$ once. There are also reductions which run $A$ multiple times. If you are only looking for asymptotical complexity, it doesn't change much, tho. Running a polynomial time algorithm polynomial many times is still polynomial overall.

Edit2: Concerning your example, there are a couple of misunderstandings of of the these times. First, in a reduction we use $A$ mostly as a blackbox. We can observe the queries (e.g. if we assume an oracle for that, which can be accessed by both $A$ and $A'$). But we make no assumptions about these times. Saying that $A'$ takes 1 unit of time for a calculation and $A$ needing 1 unit of time for a query (and possibly some internal computations) is an assumption about their correlation we should not make.

And then there is the question what we actually use from the attacker $A$. Usually we do not only use their queries, but their results. And that happens at the time $A$ is finished, which is $t$. Then $A'$ can do its final transformation of results or do some more complex computations, which is not necessarily instant (e.g. solving a large linear system or doing $k$ exponentiations, etc.). If you assume this to be instant, then $t=t'$ for exactly this attack. But that doesn't mean that this is the fastest attack (if you assume $A'$ to be the "best" attacker, $t'$ might be lower), or if those computations are not instant, then $t'$ might be greater.