Cryptography
zero-knowledge-proofs
Updated Wed, 25 May 2022 08:37:44 GMT

is this range proof i made sound?


so to prouve a value $v$ is in range $[0,2n1]$ we convince the verifier that $v$ is represented by a binary vector $a\{0,1\}^n$ so that $<a,2n>=v$

$//$ $2nZn$ is the vector of powers of $2$ satch that $2n={2^0,2^1,2^2,,,,,2^n}$

we have $rZn$ a random vector for blinding

we also have $G$ an eleptice curve generator and $A,R1,R2,R3,R4,V$ are eliptice curve points such that :

$A=<a,1>G,R1=<r,1>G,R2=<2n,r>G,R3=<a,r>G,R4=<r,r>G $ and $V=vG$

// for an example $R3$ equals : $R3=(a_1*r_1+a_2r_2....+a_nr_n)G$

the prouve goes like this:

$-$ the prouver send $A,R1,R2,R3,R4$ to the verifier

$-$ the verifier send back a challenge : $x$

$-$the prouver compute and send:

$fx=xa+r$

$-$ the verifier verify:

$<fx,1>G=?=xA+R1$ $//$ check that $fx$ was constructed corectly

$<fx,fx>G=?=x^2A+xR3+R4$ $//$ check that $a$ is a binary vector because a binary vector is the only vector where $<a,a>=<a,1>$

$<fx,2n>G=?=xV+R2$ $//$ check that $<a,2n>=v$

is this prouve sound? i'm a beginner so probably not

thanks and let me know if anything is unclear




Solution

If you're using the syntax $<a, b>$ to mean dot-product, then the assumption that you make:

a binary vector is the only vector where $<a,a>=<a,1>$

is incorrect. It is correct in the ring $\mathbb{Z}$, however we're not in the integers, we're in a finite field.

Counterexamples in finite fields are easy to find; for example, in $GF(11)$ (picked solely because it's large enough to be nontrivial, but small enough for the computation to be easy), we find that for $a = \{ 2, 5 \}$, we have:

$$<a, a> = 2 \cdot 2 + 5 \cdot 5 = 4 + 3 = 7$$

$$<a, 1> = 2 \cdot 1 + 5 \cdot 1 = 2 + 5 = 7$$