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?
Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It only takes a minute to sign up.
Sign up to join this communityI learned about probabilistic polynomial time adversary, but I have some doubt.
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):