5
$\begingroup$

Suppose I have a secret value $a$ which maps to a public point on an elliptic curve $A = a \cdot G$, where $G$ is a generator of the elliptic curve of primer order $q$.

Can I prove to someone that the least significant bit of $a$ is $0$ using a non-interactive proof that does not expose the value of $a$? If I can, what would be the most efficient (in terms of proof size) way to do it?


Edit: this can probably be done using bit commitments (something similar to Confidential Transactions), but in this case, proof sizes are likely to be close to 10KB. Is there a way to do this more efficiently? Maybe somehow relying on the fact that $a$ is even?


Edit2: I've been reading a bit about Division Polynomials and I'm wondering if it is possible to use them somehow to prove that $a$ is even.

$\endgroup$

This question has an open bounty worth +100 reputation from irakliy ending in 3 days.

This question has not received enough attention.

I'm looking for a proof that is less than 1KB in size.

  • $\begingroup$ I assume $A$ is public? You can certainly do this using standard generic zero-knowledge proofs, since this is an NP statement. There might be a much more efficient way for this specific example, though. $\endgroup$ – Noah Stephens-Davidowitz Jan 11 at 7:42
  • $\begingroup$ Yes - $A$ is public. I updated the question with this and one other clarification. $\endgroup$ – irakliy Jan 11 at 8:12
  • $\begingroup$ How are considering to do this with CT? $\endgroup$ – Youssef El Housni Jan 15 at 10:09
2
$\begingroup$

Maybe this works. Let $A=aG$ and $a=a_0+a_12+a_22^2+\dots+a_{k-1}2^{k-1}$. You want to prove that $a_0=0$. If it is true, then $A=2P$ with $P$ some point on the curve, otherwise $A=G+2P'$ with $P'$ some other point in the curve. So for the proof you just give the point $P$ and the verifier checks that $A-2P=\mathcal{O}$. You get the $P$ point when computing $A$ using double-and-add algorithm.

$\endgroup$
  • 2
    $\begingroup$ If $a_0=1$ then there is still a point $P$ s.t. $A-2P=\mathcal{O}$. You just have to compute $P=\frac{a}{2}*G$ with $\frac{a}{2}=a*2^{-1} \mod q$ $\endgroup$ – Ruggero Jan 15 at 11:40
  • $\begingroup$ This doesn't quite work. Here is an example. For $q=11$, $a = 5$, and $p = 8$, we still get $A-2 \cdot P=\mathcal{O}$ because $(5 - 2 \cdot 8) \bmod 11 = 0$. $\endgroup$ – irakliy Jan 15 at 17:11
  • $\begingroup$ @irakliy $P$ is a point not the base field modulus $p$. Anyway, it is not working. $\endgroup$ – Youssef El Housni Jan 15 at 17:14

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

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