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?

  • 4
    $\begingroup$ How about an interactive SZK proof of knowledge for a number's factorization? citeseerx.ist.psu.edu/viewdoc/… $\endgroup$ Mar 5, 2016 at 0:58
  • 1
    $\begingroup$ 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. $\endgroup$
    – Joe Bebel
    Mar 7, 2016 at 18:00
  • $\begingroup$ 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! $\endgroup$
    – Henry Yuen
    Mar 7, 2016 at 18:51
  • $\begingroup$ @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.) $\endgroup$ Mar 9, 2016 at 1:27
  • $\begingroup$ No, I believe that the following implication is open: Factoring is Hard => SZK is non-trivial (not in BPP). $\endgroup$
    – user40751
    Jul 11, 2016 at 18:46


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.