3
$\begingroup$

This would be the opposite of a rangeproof.

For example, I wanted to prove that my number was not between 0 and 200 in zero knowledge?

On a separate note: how would I prove that I hold a number, but it is not a specific number x ?

$\endgroup$
3
$\begingroup$

You can achieve that by combining two range proof with an OR proof.

Specifically, given a commitment $c$ to a secret number $x$, you would prove the statement: ($x > 200$) OR ($x < 0$). Each of the two statements can be proven using any standard $\Sigma$-protocol for range proofs (see e.g. my answers here and here), and there are standard methods to construct a $\Sigma$-protocol for the OR of two statements given a $\Sigma$-protocol for each of the statements. You can find simple explanations about how this works by reading Section 3.5.1.2 of my PhD thesis.

For your second question, the usual strategy is as follows: you have a homomorphic commitment (e.g. a Pedersen commitment) to a value $v$ over $\mathbb{Z}_p$, where $p$ is a prime, and you want to prove that it is not equal to $x$. To do so, compute $m = (v-x)^{-1} \bmod p$ and commit to it. Note that $v-x$ has an inverse modulo $p$ if and only if $v \neq x$. Then, prove that the committed value $m$ was correctly constructed by proving that $m\cdot (v-x) = 1$, using any standard $\Sigma$-protocol for proving multiplicative relations between committed values.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.