Tell me more ×
Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It's 100% free, no registration required.
up vote 1 down vote favorite

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

share|improve this question
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

Know someone who can answer? Share a link to this question via email, Google+, Twitter, or Facebook.

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.