3
$\begingroup$

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!

$\endgroup$
  • $\begingroup$ I don't get what you mean with that last sentence, could you explain? $\endgroup$ – Maarten - reinstate Monica Dec 17 '17 at 0:57
  • $\begingroup$ What I mean is that I will have to give the proof for integer which are greater than 0 and less than 100. $\endgroup$ – fraccaman Dec 17 '17 at 5:37
  • $\begingroup$ You're looking for a range proof, see my answer to this question for example. $\endgroup$ – Geoffroy Couteau Dec 17 '17 at 13:37
  • $\begingroup$ @GeoffroyCouteau thank you for your answer and great post! About it, more specifically at: "The most natural method is the naive method that you mentioned: commit to the bits (mi)i≤logq/2(mi)i≤log⁡q/2 of the plaintext mm, prove that ∑mi2i=m∑mi2i=m and that mi(1−mi)=0mi(1−mi)=0 for every ii (id est, each mimi is a bit).", do you have any other paper / essay which explain a little bit deeper how to achieve this kind of proof? Im not really a mathematician/ cryptographer, so I'm struggling to understand how to implement this scheme. P.s: I don't need the proof to be efficient, I need it to work $\endgroup$ – fraccaman Dec 17 '17 at 14:18
  • $\begingroup$ I added an answer to your question, I hope it clarifies it. $\endgroup$ – Geoffroy Couteau Dec 18 '17 at 10:36
2
$\begingroup$

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.

$\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.