# 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

-

1
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
{"extraction_info": {"found_math": true, "script_math_tex": 0, "script_math_asciimath": 0, "math_annotations": 0, "math_alttext": 0, "mathml": 0, "mathjax_tag": 0, "mathjax_inline_tex": 9, "mathjax_display_tex": 0, "mathjax_asciimath": 0, "img_math": 0, "codecogs_latex": 0, "wp_latex": 0, "mimetex.cgi": 0, "/images/math/codecogs": 0, "mathtex.cgi": 0}, "config": {"markdown_headings": true, "markdown_code": true, "boilerplate_config": {"ratio_threshold": 0.18, "absolute_threshold": 10, "end_threshold": 15, "enable": false}, "remove_buttons": true, "remove_image_figures": true, "remove_link_clusters": true, "table_config": {"min_rows": 2, "min_cols": 3, "format": "github"}, "remove_chinese": true, "remove_edit_buttons": true, "extract_latex": true}, "english_confidence": 0.9460448026657104, "perplexity_flag": "middle"}