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 $$=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=G,R1=G,R2=<2n,r>G,R3=G,R4=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:

$$G=?=xA+R1$$ $$//$$ check that $$fx$$ was constructed corectly

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

$$G=?=xV+R2$$ $$//$$ check that $$=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 $$$$ to mean dot-product, then the assumption that you make:

a binary vector is the only vector where $$=$$

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:

$$ = 2 \cdot 2 + 5 \cdot 5 = 4 + 3 = 7$$

$$ = 2 \cdot 1 + 5 \cdot 1 = 2 + 5 = 7$$