0
$\begingroup$

Let us take an known example for the zero-knowledge proof like the Graphisomorphism (NP). I know there are different versions how to formulate an zero knowledge example for this problem but for this question it doens't matter.

I would like to know why it does make sense from a theoretical point of view to choose such a problem and ask somebody of whom I know already he can solve it if he can? As I read on wikipedia the prover in an interactive proofing system is in a higher complexity class than the problem (all mighty is atleat EXPSpace) then we know before trying to let the prover prove something that he will succeed.

So why is the prover chosen to be all mighty? Shouldn't it be possible that the result of the interaction reveals the complexity class of the prover (or atleast makes considerably assumptions possible, nobody knows if graph isomorphism has a P algorithm and because the problem isn't complete it would follow no collapsing of NP to P) like if the prover is able to solve an NP complete problem the prover is atleast in NP?

$\endgroup$

1 Answer 1

Reset to default
1
$\begingroup$

For the sake of these types of problems, we don't need to know anything about the other agent. Instead, the agent is attempting to prove that they know specific information, such as whether graphs are isomorphic, without necessarily revealing that information to third parties.

So the verifier does not know what knowledge the other party has. We formulate the problem as: assuming the other party has this knowledge, how can they prove that to the verifier?

It's certainly possible that if the other party is able to accurately solve every isntance, then we could believe they have an oracle for that complexity class.

$\endgroup$
3
  • $\begingroup$ You are right, thank you didn't thought about it... $\endgroup$
    – baxbear
    Jun 28, 2018 at 21:36
  • $\begingroup$ Can I ask you an additional question: What would happen for a Problem that is atleast in NP (like graph isomorphism) if the number of questions which can be asked by the verifier aren't limited by deterministic polynomial time but still the verification has to be possible in deterministic polynomial time. Is it possible for the prover to answer still with an NP algorithm but some how cut into slices? (Or would this kind of solution lead to a P?NP answer?) $\endgroup$
    – baxbear
    Jun 28, 2018 at 21:43
  • 1
    $\begingroup$ Well, if we assume that receiving an answer takes some time, then a verifier in polynomial time must ask only polynomially many questions. Else, we'd allow them to ask a very large number of questions. I'm not certain we'd see any differences since ultimately the verifier would have to process those questions in polynomial time anyway. I guess I don't know the answer for you there, but my intuition is that it won't change anything. $\endgroup$
    – Jason Carr
    Jun 29, 2018 at 2:05

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.