# 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. – DrLecter Mar 27 '14 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. – Dingo13 Mar 27 '14 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 ! – Dingo13 Mar 27 '14 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. – Dingo13 Mar 27 '14 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$. – Dingo13 Mar 27 '14 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$ ? – Dingo13 Mar 28 '14 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. – DrLecter Mar 28 '14 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 ? – Dingo13 Mar 28 '14 at 18:40
• @Dingo13 thats already counted in the operations $A'$ makes, since the oracles are simulated by $A'$. – DrLecter Mar 28 '14 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. – Dingo13 Mar 28 '14 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). – Dingo13 Mar 27 '14 at 17:52
• Maybe it's preferable to give an example ? I'm going to give a concrete example in my post ! :-) – Dingo13 Mar 27 '14 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) – Dingo13 Mar 27 '14 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 '14 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... – Dingo13 Mar 27 '14 at 18:46