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:
- Pick a large random value $r$ and map it to both curves as $R = r ⋅ G$ and $R' = r ⋅ G'$
- Compute $u = H(G, G', A, A', R, R')$, where $H$ is a hash function
- Compute $v = r + a ⋅ u$ such that $\frac{v}{u} < q$. This could require iterating through several values of $r$
- 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:
- Compute the value of $u$
- Check that $\frac{v}{u} < q$
- Check that $v ⋅ G = R + u ⋅ A$ and $v ⋅ G' = R' + u ⋅ A'$
Some limitations of this approach are:
- To be secure, $a$ must be large (over 224 bits) high-entropy value
- 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."