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?

  • 1
    $\begingroup$ Zero is also an acceptable error probability. $\endgroup$ – CodesInChaos Nov 4 '13 at 8:33

A decision problem is to decide if something is true or not (typically phrased in terms of membership of a language). In complexity theory, decision problems are useful for understanding, and most problems can be reduced to a decision problem of some form.

However, in everyday life we are usually not trying to solve decision problems. The algorithms in a public key cryptosystem aren't trying to solve decision problems, so you cannot use the language of decision problems. It just doesn't make sense, as you have discovered.

The notion of polynomial time still makes sense, though.

  • $\begingroup$ 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). $\endgroup$ – DrLecter Nov 3 '13 at 18:59
  • $\begingroup$ I don't know anything about complexity theory, but it doesn't seem productive to me to consider key generation in terms of search problems. Also, while we do use implementations that may fail to generate a proper RSA key, we never care about such issues because the prime search won't fail. $\endgroup$ – K.G. Nov 3 '13 at 19:13
  • $\begingroup$ Right, in practice it wont fail. But as you already said, looking at this from the perspective of decision problems does very likely not make any sense at all. $\endgroup$ – DrLecter Nov 3 '13 at 19:31
  • $\begingroup$ In the case of McEliece, I had seeing here [1], that GEN algorithm fail for example when with certain parameters can't get rearrange the G matrix in the systematic form? But in the case of Enc algorithm Why that is a PPT? What will be a example of Enc fail when Gen had generated a correct pair (sk,pk)? [1] cdc.informatik.tu-darmstadt.de/reports/reports/… $\endgroup$ – juaninf Nov 13 '13 at 18:10

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.