<p>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? </p>

CC BY-SA 3.0
2016-03-05T00:58:42.483Z
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
CC BY-SA 3.0
2016-03-07T18:00:32.433Z
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
CC BY-SA 3.0
2016-03-07T18:51:32.083Z
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
CC BY-SA 3.0
2016-03-09T01:27:06.883Z
@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
<cr.crypto-security><nt.number-theory><factoring><zero-knowledge>
Does Factoring have a Statistical Zero Knowledge Proof?
Henry Yuen
# Does Factoring have a Statistical Zero Knowledge Proof?

(Asked by: username_0 on 2016-03-04)

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?

**Tags:** cr.crypto-security, nt.number-theory, factoring, zero-knowledge

> **Comments:**
> **username_1**: 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  
> **username_2**: 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.  
> **username_0**: 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!  
> **username_1**: @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.)  

---

## 0 answers

