MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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.

share|cite|improve this question
up vote 5 down vote accepted

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.

share|cite|improve this answer
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. – Peter Shor Jul 17 '10 at 13:24
I'll check that out, thank you! – Alexander Kalinowski Jul 19 '10 at 3:40

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.