1
$\begingroup$

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."

$\endgroup$
3
  • $\begingroup$ what is the range of the hash value $u$ ? $\endgroup$
    – user27950
    Jul 10, 2018 at 4:09
  • $\begingroup$ I'm not sure if it matters (I'm guessing bigger value makes it more secure - but I don't know how much more secure). Assuming $g$ and $g'$ are 256-bit curves, I'm thinking $u$ could be the same order as $q$. But this is actually related to another question I've asked here. $\endgroup$
    – irakliy
    Jul 10, 2018 at 4:53
  • $\begingroup$ Range proof about an integer suggests a group of a hidden order, rather than an elliptic curve points group of some (by default) known prime order. $\endgroup$ Jul 11, 2018 at 11:53

2 Answers 2

5
$\begingroup$

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

$\endgroup$
8
  • 1
    $\begingroup$ Thank you for the answer! I clarified the question. Does it make more sense now? $\endgroup$
    – irakliy
    Jul 9, 2018 at 2:19
  • 1
    $\begingroup$ No; it doesn't - it is still a trivial statement. In any case, I would prefer that you add any modifications at the end of the question so that my answer can benefit others as well. $\endgroup$ Jul 9, 2018 at 2:24
  • 1
    $\begingroup$ I updated the question again and added a part at the bottom to make sure your answer stays in context. Does the question make more sense now? $\endgroup$
    – irakliy
    Jul 9, 2018 at 2:52
  • 1
    $\begingroup$ Getting there, but still not quite! Now there is a public $A=a\cdot G$ and we can ask if you what the range is. However, you defined the range to be less than $q$ where $q$ is the order. This is trivial since such an $a$ always exists. $\endgroup$ Jul 9, 2018 at 11:56
  • 1
    $\begingroup$ I was trying to make sure $a < q$ and not just $ a \bmod q < q$ (which is trivial indeed) but I think I see the issue. I'm wondering if what I'm trying to describe is not actually a range proof but rather a commitment function. Basically, if you have a value $a$, I want you to commit to $a$ in such a way that I know that $a < q$. $\endgroup$
    – irakliy
    Jul 9, 2018 at 16:43
0
$\begingroup$

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$

$\endgroup$
10
  • $\begingroup$ Maybe I'm missing something, but if $v=r+a⋅u$, then $\frac{v}{u}=\frac{r}{u}+a$, and the only way $\frac{r}{u}+a < q$ is when $a < q$. Or did I misunderstand something? $\endgroup$
    – irakliy
    Jul 10, 2018 at 6:39
  • $\begingroup$ You are mixing up working modulo $qq'$ with working in $Z$. Your equation is defined modulo $qq'$ but your inequality is defined in $Z$. $\endgroup$
    – user27950
    Jul 10, 2018 at 6:43
  • $\begingroup$ Aren't $a$, $u$, $r$, and $v$ defined in $Z$? The equation $v=r+a⋅u$ is in $Z$ (it would work for any integers $a$, $u$, $r$, and $v$). $\endgroup$
    – irakliy
    Jul 10, 2018 at 6:49
  • $\begingroup$ Thinking about it more, I still don't understand why you think the equation is defined modulo $qq′$. Using your assumptions, the only constraints for the equation are that $a$ and $r$ are in $Z$ and $u < q'$. This implies that $r+a⋅u$ is defined in $Z$. Am I missing something? $\endgroup$
    – irakliy
    Jul 10, 2018 at 16:28
  • $\begingroup$ because in a cyclic group with order q and generator G one has $a \cdot G = b \cdot G \iff a = b \mod q$ $\endgroup$
    – user27950
    Jul 10, 2018 at 17:05

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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