1
$\begingroup$

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

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

we have $r∈Zn$ 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_2∗r_2....+a_n∗r_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

$\endgroup$
2
  • $\begingroup$ You're using the notation $< a, b >$. What does that signify? Dot product? $\endgroup$
    – poncho
    Sep 1 '20 at 20:25
  • $\begingroup$ yes, you can see it in $R3$ example $\endgroup$
    – Abdo T
    Sep 1 '20 at 20:38
3
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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