# McEliece Public Key Encryption

The definition of Public Key Encryption(PKE) say that:

A PKE scheme is a triple of probabilistic polynomial time algorithm (PPT) (Gen,Enc,Dec).

The definition of PPT say:

In complexity theory, PP is the class of decision problems solvable by a probabilistic Turing machine in polynomial time, with an error probability of less than 1/2 for all instances.

Let "Find a pair key $(pk,sk)$ (public and private key)" be the problem related with the first algorithm (Gen). In the McEliece scheme, what is a example of error of any instance of the algorithm Gen? Which will be a response "No" and What is a difference between the response "No" and the error response of the algorithm Gen?

-
Zero is also an acceptable error probability. –  CodesInChaos Nov 4 '13 at 8:33

As K.G. already noted, it does not make much sense to speak here in terms of decision problems. It makes more sense to consider probabilistic polynomial time algorithms in the setting of search problems. Basically, the $Gen$ algorithm is required to produce output that satisfies a certain relation, but may fail to do so (think for instance of RSA key generation, then the key generation algorithm is required to produce two primes of certain size, but can fail to do so depending on the probabilistic primality test used). –  DrLecter Nov 3 '13 at 18:59