# Is there an interactive proof system for factoring with the perfect zero knowledge property?

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.

-

## 1 Answer

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.

-
To clarify, I was thinking along the lines of the second question, where one would ask "does this number have k prime factors". –  Alexander Kalinowski Jul 15 '10 at 0:27
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 –  Peter Shor Jul 17 '10 at 13:24
I'll check that out, thank you! –  Alexander Kalinowski Jul 19 '10 at 3:40