I learned about probabilistic polynomial time adversary, but I have some doubt.
- Is probabilistic polynomial time adversary referred to those who attack in polynomial time with the form of probabilistic?
$\begingroup$
$\endgroup$
3
-
$\begingroup$ Possible duplicate of What does it mean for an adversary to run in PPT? $\endgroup$– DanielOct 9, 2018 at 8:44
-
$\begingroup$ @Daniel I agree that the title of that other question suggests that it is a dupe. I'll try and fix the title (later) though, because the rest of the question seems to focus on the probabilistic part of the term while this question seems to focus on the polynomial time component. The answers are also pretty different from each other for that reason. $\endgroup$– Maarten Bodewes ♦Oct 9, 2018 at 14:00
-
$\begingroup$ @MaartenBodewes Ok! Thanks for taking a look at it :) $\endgroup$– DanielOct 10, 2018 at 12:40
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
3
Yes, but note as below, the probability is not biased.
From the Lindell, Katz book;
An algorithm $A$ is said to run in polynomial time if there exists a polynomial $p(\cdot)$ such that for every input $x \in \{0,1\}^*$, the computation of $A(x)$ terminates within at most $p(|x|)$ steps.
A probabilistic algorithm is one that has the capability of "tossing coins", i.e. the algorithm has access to a random source of randomness that yields unbiased random bits that are independently equal to 1 with $1/2$ probability and to 0 with $1/2$ probability.
Probabilistic Polynomial-time adversary means; An adversary runs in probabilistic polynomial time algorithm.
Different formulation (due to a comment of SEJPM):
- A probabilistic polynomial-time algorithm is a probabilistic algorithm that may only perform a polynomial amount of operations including at most a polynomial number of coin-flips.
- A probabilistic polynomial-time adversary is then any probabilistic polynomial-time algorithm.
-
3$\begingroup$ Different formulation: A probabilistic polynomial-time algorithm is a probabilistic algorithm that may only perform a polynomial amount of operations including at most a polynomial number of coin-flips. A probabilistic polynomial-time adversary is then any probabilistic polynomial-time algorithm. $\endgroup$– SEJPMOct 9, 2018 at 6:49
-
3$\begingroup$ You should mention that it's a polynomial in the length of the algorithms input. Otherwise the bound on the number of steps is ill defined. $\endgroup$– MaeherOct 9, 2018 at 7:10
-
1$\begingroup$ @SEJPM The difference is immaterial, though. Even if you allow an unbounded number of coin tosses, this does not give the adversary more power because it cannot "use" more than a polynomial number of them. $\endgroup$– fkraiemOct 9, 2018 at 12:27