# What does it mean in layman's term when it states that - "An algorithm running for polynomial time can break the scheme with probability p"?

For example - let's say an adversary algorithm runs for $n^{3}$ time and can break the scheme with probability 0.001. Does that mean, even after running the algorithm for $n^{3}$ time, it will only succeed in 1 out of 1000 times? So, if my understanding is correct, then the adversary algorithm need to be executed for at most 1000 * $n^{3}$ times to be successfully able to break the scheme.

• don't forget that on average it will break the scheme in 1 of 1000 cases.
– SEJPM
Feb 2 '17 at 17:17

The statement

An adversary algorithm runs for $n^3$ time and can break the scheme with probability 0.001

can't be much simplified while keeping its meaning; nor can it be used to derive something useful for what happens after the algorithm is run 1000 times, beyond that this breaks the scheme with probability at least $1/1000$.

This statement is shorthand for: There exists some deterministic algorithm, designated/modeling an adversary, which when run with inputs(s) varying uniformly randomly across experiments, after running for $n^3$ time in each experiment, will break the scheme for a proportion at least $1/1000$ of the possible input combinations (in practice, if the number of input combinations is huge, for a proportion not significantly lower than $1/1000$ of experiments when enough experiments are run that the algorithm succeeds a significant number of times). Importantly: the varying inputs(s) of the algorithm might be from the problem to solve, or/and from a random source used by a randomized algorithm turned deterministic by moving its source of randomness as an input; that's left unstated.

It is not possible to conclude that $1000$ executions of the algorithm will break the scheme with odds better than $1/1000$; much less with certainty.

If the algorithm is purely deterministic, that is succeeds or fails depending only on inputs part of the problem to solve, repeating the experiment with the same inputs won't help at all, and odds of success are the same for 1 or 1000 runs: (at least) $1/1000$.

If the algorithm succeeds or fails according to inputs that are made to vary randomly across experiments concerning the same problem to solve, but independently of inputs defining the problem to solve, we can state that the scheme is broken with odds at least $1-(1-1/1000)^{1000}\approx1-1/e\approx63\%$ after 1000 experiments (raising to $\approx99.3\%$ after 5000 experiments).

Illustration: the goal is to break RSA by factoring the public modulus $N$ with $n^{5.8}<N<n^{5.9}$, which can trivially be done by trial division of $N$ in time $n^3$. Consider these two algorithms:

• Algorithm $\mathcal A_0$ accepts as input $N$; it factors $N$ by trial division, and outputs the result only if $N\bmod997=42$
• Algorithm $\mathcal A_1$ accepts as input $N$ and a large value $R$ randomizing the algorithm; it factors $N$ by trial division, and outputs the result only if $R\bmod997=42$

Both algorithms satisfy the stated condition. Repeating $\mathcal A_0$ 1000 times for the same random $N$ succeeds with odds just above $1/1000$; while repeating $\mathcal A_1$ 1000 times for the same random $N$ and fresh random $R$ at each run succeeds with odds just above $63\%$.

Note: if we run $\mathcal A_1$ 1000 times with incremental rather than random $R$, then success is certain.

Your example means that executing the adversary algorithm once takes time $n^3$ and the probability that it successfully breaks the scheme in this single execution is $0.001$.

Your conclusion about the repetition is, however, flawed: First of all, the running time has nothing to do with the number of repetitions you have to do, and even after that many repetitions, the adversary is not guaranteed to succeed. Hence, a better, but still incorrect, conclusion would be: "Running the adversary algorithm $1000$ times will break the scheme with good probability, where the total time needed is $1000 \cdot n^3$." The problem with this conclusion is that the probability of a successful attack usually includes randomness used for key generation, encryption, etc. (depending on the scheme and the security definition). For example, if the adversary is always successful for $1$ in $1000$ keys and never succeeds for other keys, one would say that the success probability is $0.001$. In this case, repeatedly running the adversary on the same instance with the same key does not increase the success probability and is thus pointless.