18
$\begingroup$

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?

Improve this question
$\endgroup$
5
  • 4
    $\begingroup$ How about an interactive SZK proof of knowledge for a number's factorization? citeseerx.ist.psu.edu/viewdoc/… $\endgroup$
    – Daniel Apon
    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$
    – Daniel Apon
    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

0

Reset to default

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.