18

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?

Henry Yuen
  • 3,798
  • 1
  • 21
  • 33
  • 4
    How about an interactive SZK proof of knowledge for a number's factorization? http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.46.3300&rep=rep1&type=pdf – Daniel Apon Mar 05 '16 at 00:58
  • 1
    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. – Joe Bebel Mar 07 '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! – Henry Yuen Mar 07 '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.) – Daniel Apon Mar 09 '16 at 01:27
  • No, I believe that the following implication is open: Factoring is Hard => SZK is non-trivial (not in BPP). –  Jul 11 '16 at 18:46

0 Answers0