17
$\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?

$\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 '16 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 '16 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 '16 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 '16 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 '16 at 18:46

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.