# Efficient zero knowledge proof of least significant bits either RSA or Rabin?

I need to reveal the log(n) least significant bits of $x^2 mod\ N$ or $x^3 mod\ N$ without revealing x.

So far the best I have involves a Boudot range proof and is not a very nice construction

-
What exactly would the ZKP actually prove? That you know a value $x$ with $(x^2 \bmod N) \bmod 2^k = value$, for some modest $k$ which you list as $\log(n)$, for some $n$? Or, in other words, how would the verifier know that the value of $x$ involved is the secret $x$ you're thinking of? – poncho Jul 13 '12 at 15:31
The full proof would have other predicates about x in it. So you might prove,for example, that you know the factorization of x and then show the least significant bits of the rsa encryption of x. – imichaelmiers Jul 13 '12 at 15:58