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.

Improve this question
$\endgroup$

1 Answer 1

Reset to default
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.

Improve this answer
$\endgroup$
3
  • $\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$ Commented 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$ Commented Jul 17, 2010 at 13:24
  • $\begingroup$ The link to springerlink.com in the previous comment is broken, but the article can be found at doi:10.1007/3-540-48910-x_8 (Zbl 0971.94009). $\endgroup$ Commented Aug 10 at 5:43

You must log in to answer this question.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.