2
$\begingroup$

Given the decision version of the factoring problem, is there an interactive proof system with the perfect zero knowledge property? I know there is for just the zero knowledge property, but is there without the assumption of one way functions?

perfect zero knowledge property: Let P and V be randomized algorithms of an interactive proof system for the decision problem L. This proof system has the perfect zero knowledge property if for every polynomial time randomized algorithm V' that can replace V, there is a randomized algorithm A with polynomially bounded worst case expected runtime that for each $x\in L$ produces what is communicated between P and V' with the same probabilities.

$\endgroup$

1 Answer 1

5
$\begingroup$

If by the decision version of the factoring problem you mean: does this number have a non-trivial factorization (i.e. is this number prime?), that's primality testing, which is in P so it's automatically in PZK.

Otherwise, I think "the decision version of the factoring problem" is ambiguous. You could mean questions like: "is the 10th digit of the largest factor 7?" or questions like "does this number have exactly k prime factors." I wouldn't be surprised if there were a PZK protocol for the second question, but I would be very surprised if there was one for the first.

$\endgroup$
2
  • $\begingroup$ To clarify, I was thinking along the lines of the second question, where one would ask "does this number have k prime factors". $\endgroup$ Jul 15, 2010 at 0:27
  • $\begingroup$ There's a paper that does something similar (in statistical zero knowledge): Camenisch and Michels: Proving in Zero-Knowledge that a Number is the Product of Two Safe Primes. springerlink.com/content/blqm17fy9wr5n1xx $\endgroup$
    – Peter Shor
    Jul 17, 2010 at 13:24

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.