Using two elliptic curves to do a range proof

Question

Suppose Alice holds a secret value $a$ to which she has publicly committed to using two elliptic curves of distinct order. The curves are $g$ and $g'$ of orders $q$ and $q'$ (with $q < q'$) and generator points $G$ and $G'$. The commitment would be $(A, A')$, where $A = a⋅G$ and $A' = a ⋅ G'$.

I'm wondering if Alice could use a variation on the method described here to prove to a verifier that $A$ and $A'$ are derived from the same $a$ AND that $a < q$. Specifically, I am thinking Alice could do the following:

1. Pick a large random value $r$ and map it to both curves as $R = r ⋅ G$ and $R' = r ⋅ G'$
2. Compute $u = H(G, G', A, A', R, R')$, where $H$ is a hash function
3. Compute $v = r + a ⋅ u$ such that $\frac{v}{u} < q$. This could require iterating through several values of $r$
4. The proof then is $(R, R', v)$ (the verifier already has $A$ and $A'$)

To check that $A$ and $A'$ are derived from the same $a$ and that $a < q$, the verifier could do the following:

1. Compute the value of $u$
2. Check that $\frac{v}{u} < q$
3. Check that $v ⋅ G = R + u ⋅ A$ and $v ⋅ G' = R' + u ⋅ A'$

---

Some limitations of this approach are:

1. To be secure, $a$ must be large (over 224 bits) high-entropy value
2. To be practical, $a$ would probably need to be smaller than $\frac{q}{2}$. Otherwise, picking $r$ that satisfies the constraints would be difficult

Are there any other limitations?

---

This answer from Yehuda Lindell refers to an earlier version of this question which started like:

"Suppose I wanted to prove that $0<a<q$ for some larger integer $a$ and a large prime $q$, without revealing the value of $a$. I'm wondering if I could use a variation on the method described here to do that."

Answer 1

I am going to write this as an answer rather than as a comment, since this type of mistake repeats itself multiple times on this forum.

First, specifically to this question: the question doesn't make sense. What are you trying to prove? That there exists an $a<q$; of course there does. That you know an $a<q$; of course you do. These range proofs make sense when you have a commitment to or encryption of $a$ and want to prove that $a<q$. I am not saying this to be critical but to address a mistake that is very common.

Now, to the more general issue, which is the important one. Zero-knowledge proofs only make sense when you have a well-defined statement that you are trying to prove. It is important to write down this statement clearly, and then see if it is trivial. For example, a statement that says "for all primes $q$ there exists an integer $a$ such that $a<q$" is trivial. That is; it always holds (for all primes $q$) and thus there is nothing to prove. Note that there are statements that look less obvious. For example, given a group of order $q$ with generator $g$ and a group element $h$, the statement "there exists a value $x\in\mathbb{Z}_q$ such that $h=g^x$" is also always true, and thus is trivial. This may seem confusing since this is exactly the statement of the Schnorr discrete log proof; I will explain below. Finally, any statement that can be verified in polynomial time does not make sense for zero knowledge (at least as we formulate it) since the verifier can check itself, making it trivial. In short, in order to talk about zero knowledge in a non-trivial way, there needs to be a well formulated NP statement (NP so that the prover can be polynomial time) that cannot always be verified in polynomial time without any additional information.

Having said the above, there is sometimes a need to prove that the prover knows something. For example, for every $g,h$ as above, there always exists some $x$ such that $g^x=h$ but it is not necessarily known (and cannot be found efficiently). Thus, a zero-knowledge proof of knowledge can be used in such circumstances. Another classic example is that I know the value inside a commitment or ciphertext (without revealing it). Here too there should be a clearly formulated NP statement and finding the witness should be something that cannot in general be done in polynomial time.

I hope that this helps...

Answer 2

This does not work.

For simplicity, lets assume that the values of the Hash function are in $q'$.

First note that by the Chinese Remainder Theorem, the equation $\nu = r + a \cdot u$ is defined modulo $q q'$. This means, $\nu, r$ and $a$ are in the range $\{0 \dots qq'- 1\}$.

Now chose an arbitrary $a > q$, $r$ randomly in $\{0 \dots q q' \}$ and calculate $R, R', A, A'$ and $u= Hash(G, G', A, A', R, R')$.

The Hash can be seen as a random mapping and so $u$ can be seen as a random value in $\{0 \dots q' \}$. Due to modular reduction, $\nu$ can be seen as a random value in $\{0 \dots qq' \}$.
Also not true in a strict sense, one can practically assume that $\nu$ and $u$ are independant random variables.

As $\nu$ and $u$ are random variables, approximately half of the values $\nu$ will be less than $qq' / 2$ and half of the values of $u$ will be greater than $q'/2$. That means, approximately 1/4 of pairs $\nu$ and $u$ will fulfill both conditions.

It follows that $\nu < qq'/2 < q u$ and therefore $ {\nu \over u} < q$