Prove integer is within the interval [a,b]

Question

I am trying to find a schema to ensure that a secret integer lies in the interval [a, b], where a and b are not power of 2.

I took a look at hash chains as described in this paper and at 'range proof' with ring signature as described here.

Unfortunately, I don't think those systems meets my requirements. Do you know any other schema which could help me?

I can already tell that my numbers lies in the range [0, 100]. Thanks!

Answer 1

As I mentioned in a comment, you are looking for a range proof, see my previous answer to a related question.

You specifically ask for a solution not limited to powers of two, and for numbers known to be between 0 and 100. Let $0 \leq a < b \leq 100$ be the interval you consider. Let $m$ be your secret integer. The simplest solution I can think of works as follows:

• Commit to $m$, using the Pedersen commitment scheme over a prime-order group $\mathbb{G}$ of order $p$. That is, let $\mathbb{G}$ be a prime-order group (e.g. an appropriate elliptic curve where the discrete log is hard), and let $g$, $h$ be generators of $\mathbb{G}$. To commit to $m$, pick $r$ at random from $\mathbb{Z}_p$ and send $c\gets g^mh^r$.
• Commit to the bits $b_6, b_5, \cdots, b_0$ of $m-a$, using again the Pedersen scheme and $7$ random coins $r_6, r_5, \cdots, r_0$ from $\mathbb{Z}_p$, chosen uniformly at random subject to the following constraint: $\sum_i 2^i r_i = r$. For $i=0$ to $6$, let $c_i \gets g^{m_i}h^{r_i}$. Note that $m-a \leq m \leq 100 < 2^7$ so seven bits are sufficient.
• Prove for each $c_i$, using a zero-knowledge proof, that it commits to a bit. As the verifier can check herself that $\prod_i c_i^{2^i} = c\cdot g^{-a}$ (because $\sum_i b_i\cdot 2^i = m-a$, and the random coins $r_i$ have been chosen to ensure that this relation will hold), if she is convinced that the $b_i$ are bits, they indeed form the bit decomposition of $m-a$, which proves that $m \geq a$ (otherwise, $m-a$ would be considerably larger than seven bits, due to the modulo reduction with $p$).
• Repeat the two steps above, but using the bit decomposition of $b-m$ instead of $m-a$ this time. This will prove that $b-m \geq 0$, hence that $m \leq b$.

The only missing ingredient is a proof that a Pedersen commitment $C$ commits to a bit. There are two natural way to implement a $\Sigma$-protocol for this task.

The first possibility that comes to mind is to use an OR proof, showing that $C$ commits to $0$ OR $C$ commits to $1$. See for example the answer to this question.

The second possibility for such a ZK proof is quite simple: prove that you know $(x, s, s')$ such that $C = g^x h^s$ and $C = C^xh^{s'}$. This shows that you know an opening of $C$ to both $x$ and $x^2$; by the binding property of the commitment scheme, this ensures that $x = x^2$, hence that $x$ is a bit.