2
$\begingroup$

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?

Improve this question
$\endgroup$
1
  • 2
    $\begingroup$ Zero is also an acceptable error probability. $\endgroup$
    – CodesInChaos
    Commented Nov 4, 2013 at 8:33

1 Answer 1

Reset to default
1
$\begingroup$

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.

Improve this answer
$\endgroup$
4
  • $\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
    Commented Nov 3, 2013 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.
    Commented Nov 3, 2013 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
    Commented Nov 3, 2013 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
    Commented Nov 13, 2013 at 18:10

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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