# Does Factoring have a Statistical Zero Knowledge Proof?

The title should be pretty self-explanatory, but to be more precise, consider the decision version of factoring, which is given input $(x,k)$, where $x$ and $k$ are binary encodings of integers, to determine whether $x$ has a prime factor less than $k$. Does this decision problem have a statistical zero knowledge proof?

• How about an interactive SZK proof of knowledge for a number's factorization? citeseerx.ist.psu.edu/viewdoc/… Mar 5 '16 at 0:58
• is it obvious if it's possible to covert this into the decision version? For example, someone may know one factor but not the rest. Mar 7 '16 at 18:00
• Daniel: My question was pretty open ended. I guess this means that we don't know of an SZK protocol for Factoring? It would be cool if there was. I'm happy to accept your answer, though! Mar 7 '16 at 18:51
• @JoeBebel That's a good part of the question I hadn't considered: when the witness $w$ is any (not necessarily prime) factor of $x = p_1p_2p_3...$ of size less than $k.$ I don't know the answer off-hand. (I suspect that it's known, and been known for a while.) Mar 9 '16 at 1:27
• No, I believe that the following implication is open: Factoring is Hard => SZK is non-trivial (not in BPP).
– user40751
Jul 11 '16 at 18:46