# Times of nested algorithms in proofs of security

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").

• It is not the case that $A'$ terminates when $A$ terminates. $A'$ may require some more computations to transform the output of $A$ into a solution to the respective problem $A'$ is required to solve. Mar 27, 2014 at 19:00
• @DrLecter Yes I've supposed that $A'$ doesn't need more computations at the end so as to show what is the problem. Mar 27, 2014 at 19:04
• Even if $A'$ makes more computation after having obtained the output from $A$ this does not explain why there is a "pause" (in the elapsed time for $A$) when $A$ is waiting for the response to a query ! Mar 27, 2014 at 19:05
• Thanks DrLecter. An oracle call requires (or doesn't require ?) unit time ? What is referred to the simulation of an oracle call ? I don't understand what this means. Mar 27, 2014 at 19:15
• When I say that I don't understand why "there is a "pause" (in the elapsed time for A) when A is waiting for the response to a query", I'm speaking about a simulated oracle since this is $A'$ which responds to $A$. Mar 27, 2014 at 19:19

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$).

• Thank you for your efforts to explain me. Why you say that the "subalgorithms" of A simulate the challenger and the oracles ? This is not $A'$ (t.i.t.s. the reduction) which simulates the environment of $A$ ? Mar 28, 2014 at 18:26
• @Dingo13 The reduction $A'$ is an algorithm were you put a problem in and get the solution out. But internally $A'$ simulates the challenger and oracles for $A$. Thus I wrote "subalgorithms" of $A'$ for the parts of $A'$ that do these tasks. Anyways thats only one "big" algorithm $A'$ when viewed from the outside. Hope that helps. Mar 28, 2014 at 18:32
• Sorry I've read "subalgorithms" of $A$ in your answer. In fact I've already understood your comments. There is only small details that are a problem for me. You say that oracle queries costs $1$ unit of time. Why they don't appear in the times of proofs by reduction ? It seems to me that if we have $q$ oracle calls, we should take into account the amount of time $q$, not ? Mar 28, 2014 at 18:40
• @Dingo13 thats already counted in the operations $A'$ makes, since the oracles are simulated by $A'$. Mar 28, 2014 at 19:05
• I make the distinction between simulated oracle and "real" oracle. I thought in your explanation that "real" oracle queries costs $1$ whereas "simulated" oracle costs the time to make the needed computations. Mar 28, 2014 at 19:33

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.

• Thanks tylo, I've already understood these things but this does not respond to my misunderstanding. My problem is the following: I don't understand why we can deduct something like that about $t$ since $t$ and $t'$ seem tightly related. When $A'$ performs a computation to respond to a query from $A$, time goes by the same for both. It seems to me that $A$ and $A′$ terminate at virtually the same time ($A′$ uses the output from A almost immediately). Mar 27, 2014 at 17:52
• Maybe it's preferable to give an example ? I'm going to give a concrete example in my post ! :-) Mar 27, 2014 at 17:55
• If we write $t' - n \cdot t_c \leq t$, this means that the computations are free (they take $0$ unit of time). Maybe you will say me that this is normal since we are looking for an upper bound... But this strange anyway (computations are not free) Mar 27, 2014 at 18:08
• That is a wrong conclusion. The computations are bound by $n\cdot t_c \geq t' - t$. But if $A'$ has to do any computations after it $A$ terminated and gave the results, they do not end at the same time. Even in your simple example, the attack $A$ alone does 2 steps of time ($A$ is a standalone algorithm), while $A$ requires to wait for $A$ for 2 units and do 2 computations of its own, so overall $4$ (if you assume the time slots to be equal, and no parallel execution).
– tylo
Mar 27, 2014 at 18:33
• Thanks tylo, I've not understood your last comment because of mistakes when writing... And this is not clear because when $A$ waits for the responses from $A'$, time is always elapsing. Even is $A$ is a standalone algorithm, each waiting takes time... Mar 27, 2014 at 18:46