Probabilistic polynomial-time

B then receives an encrypted message M with a revoked set 7Z. It has to guess whether M = M or M = Rm where Rm is a random message of similar length. We say that a revocation scheme is secure if for any (probabilistic polynomial time) adversary B as above, the probability that B distinguishes between the two cases is negligible. 

Feasible computations are usually expressed by probabilistic polynomial-time algorithms. For concreteness, Turing machines are used as the model of computation. ... 

The running time of a probabilistic polynomial-time algorithm is deterministically polynomial, i.e., there is a polynomial Q such that the algorithm never needs more than Q k) steps on an input of binary length k. Of course, the random tape does not count as an input. 

Probabilistic polynomial-time computations Computational security... 

Computational security. For computational security, the quantifier over the attacker strategies is restricted toAe PPA n Attacker class(Scheme, Req), where PPA denotes the class of probabilistic polynomial-time interactive algorithms. In this case, one can at most allow other system parameters to grow polynomially with the security parameters under consideration, and one usually requires superpolynomially small error probabilities only. 

A and B are probabilistic polynomial-time interactive algorithms with two input and output ports each one pair is called 2-party ports and the other... 

Definition 7.11. A standard fail-stop signature scheme is secure for risk bearers iff for all probabilistic polynomial-time interactive algorithms Aj and non-interactive A2 (the two parts of the attacker strategy) and all polynomials Qsig, Qn (determining the growth of a and N as functions of k) ... 

In a scheme with several risk bearers, all but one risk bearer may be attacking. Hence a protocol Gen j g Q is executed, where O is a probabilistic polynomial-time interactive algorithm. The outcome is (pub, sk, ouxq). ... 

Proof. Let F, and in the case of several risk bearers O, be given, and let B and par be defined accordingly. As F and O are probabilistic polynomial-time, a signer who tries to break the security for risk bearers can use these algorithms as subroutines in the following way ... 

P, the prover s algorithm, is a probabilistic polynomial-time interactive algorithm with one input-output port. Its initial input is a triple (par, K, aux) with par as above and (K, aux) e [gen(par ), and it does not produce a final output. 

For all probabilistic polynomial-time interactive algorithms V (the cheating verifier),... 

The Jacobi symbol is interesting because it can be computed efficiently for any pair of numbers, by use of the so-called law of quadratic reciprocity. Actually, one would often be more interested in deciding quadratic residuosity, but no probabilistic polynomial-time algorithm for that is known, unless the prime factors of n are additional inputs. (A cryptologic assumption that deciding quadratic residuosity is infeasible has been used several times in the literature, e.g., in the... 

A probabilistic polynomial-time algorithm gen, the group-generation algorithm, that, on input 1 with k e IN (the security parameter), outputs a prime q and a value desc (representing the description of a group Hq desc of order q). 

A probabilistic polynomial-time algorithm choose that chooses a random... 

Theorem 8.41 (Collision-intractability of poly(ll)-tnple exponentiation in groups of prime order). Let a family of groups of prime order be given where the discrete logarithm is hard. For every probabilistic polynomial-time algorithm A (that tries to compute collisions) and every polynomial Qmu (determining the growth of /i as a function of k) ... 

D. Collision-intractability (8.29d). Assume that there were a probabilistic polynomial-time algorithm A that computed collisions better than permitted in Definition 8.29d, i.e., there is a polynomial Qtau and a constant c> 0 such that /k 3k >k 3t [Pg.264]

A probabilistic polynomial-time algorithm choose that selects a random extended value for a given secret xj merely chooses X2 in with uniform distribution and outputs (xj, X2). 

---