1
$\begingroup$

The common definition of security (for some cryptographic primitive) is to be secure against any PPT adversary (any probabilistic algorithm which runs in polynomial time). At the same time, we assume that underlying problem in this primitive is NP problem (the set of decision problems solvable in polynomial time by a theoretical non-deterministic Turing machine, link).

Is PPT algorithms are the same as non-deterministic polynomial? If yes then I am probably missing something, but for me it looks like any NP problem is solvable by some PPT algorithm (by definition of NP class), and so - what is the point of defining security against PPT? I understand this statement is false, but can't find out what exactly I am mising.

$\endgroup$
  • $\begingroup$ The class P describes problems solvable in polynomial time. NP is only verifiable in polynomial time, the solving requires the non-deterministic magic to come up with a candidate. This is what PPT cannot. $\endgroup$ – eckes Jun 6 '17 at 8:30
  • $\begingroup$ If PPT is probabilistic, why it can't use this non-deterministic magic? I just can't see the formal difference between PPT and non deterministic polynomial. $\endgroup$ – zma Jun 6 '17 at 8:39
  • $\begingroup$ Ah, Hopefully somebody knows better, my naive model is It can use randomness. It can then polynomial decide if it was right, if not it has to retry and therefore it needs exponential time. $\endgroup$ – eckes Jun 6 '17 at 8:53
  • $\begingroup$ PPT algorithms belong to the class BPP, and NP is belived not to be contained in BPP. See here. $\endgroup$ – Occams_Trimmer Jun 6 '17 at 10:08
  • $\begingroup$ "At the same time, we assume that underlying problem in this primitive is NP problem" No, we don't. $\endgroup$ – fkraiem Jun 6 '17 at 14:08
0
$\begingroup$

I think you are misunderstanding what "solve" means in the NP class.

The definition of Complexity Zoo is more accurate: A problem is in NP if there is a non-deterministic Turing Machine $M$ such that

  1. In yes-instances, at least one computation path of $M$ accepts.

  2. In no-instances, all computation paths of $M$ reject.

For instance, the subset sum problem is in NP because $M$ can just randomly select (non-deterministically construct) a subset of the given integers, add them, and then accept if it results in zero or reject otherwise. In yes-instances, at least one of the random selected subset will sum up to zero. And in no-instances, there is no such subset.

But now, how can you use a PPT algorithm to solve this problem? You can create a random subset, but you have no guaranties that it will be a solution.

$\endgroup$

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.