7
$\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 prime 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.

Improve this question
$\endgroup$
3
  • $\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, 2019 at 7:42
  • $\begingroup$ Yes - $A$ is public. I updated the question with this and one other clarification. $\endgroup$
    – irakliy
    Jan 11, 2019 at 8:12
  • $\begingroup$ How are considering to do this with CT? $\endgroup$
    – Youssef El Housni
    Jan 15, 2019 at 10:09

1 Answer 1

Reset to default
2
+100
$\begingroup$

Take a look at SNARGs, e.g. Bulletproofs (which are range proofs). The proof may be slightly too large though.

Assuming that $a \in \{0, \ldots, q-1\}$ is your representative, you want to prove is that you know a bit decomposition of $a$ with $a = a_1 d_1 + a_2 d_2 + ... + a_k d_k$ where all $d_i$ are even and $\sum d_i = p-1$. E.g. $d_i = 2^i$ but $d_k < 2^k$ otherwise you can get wraparound. This trick is found in some range-proof paper(s). Without this, it may be possible to find, for odd $a$, a bit decomposition $a_i$ with $a' = \sum a_i d_i$, and $a'$ even (due to wraparound, $a = a' \mod q$). Hence you don't get a proof for "(representative of) a is even".

One question though: Why is the last bit zero? If you just want to split the exponents into two groups, using squares and non-squares is more efficient w.r.t. ZK. It's simple and efficient to prove that $a = b^2$ (with standard sigma protocols).

It seems hard to somehow express "is divisible by 2" efficiently, because all calculations happen over finite fields, hence every (non-zero) element is invertible. So there is no such thing as "even and odd". (Also: $1$ is odd, $1 + p$ is even, but $1 + q \equiv 1 (q)$.) But: Polynomials make sense, e.g. squares $f(x, y) = x^2 - y$ or bits $f(b) = b (b-1)$. The vanishing/zero sets of polynomials are "algebraic", which helps in the group setting.

Improve this answer
$\endgroup$
3
  • $\begingroup$ Using bit decomposition will work - but I was trying to see if there is a more efficient way to do it somehow (it appears there might not be). The reason I wanted to do this is: if $a$ is divisible by 2, then $a/2 < q / 2$. This makes commitment to $a$ additively homomorphic. Meaning, I can check that $A + B = C$ and not worry about overflows and underflows as long as each of these points is backed by values that is less than $q/2$. $\endgroup$
    – irakliy
    Jan 21, 2019 at 7:58
  • $\begingroup$ What do you think of this approach: crypto.stackexchange.com/questions/66656/… ? $\endgroup$
    – irakliy
    Jan 21, 2019 at 18:21
  • $\begingroup$ As I said in the last paragraph, unless you can make "divisible by 2" an algebraic property (over finite fields you're working on) somehow, I do not expect such approaches to work. $\endgroup$
    – mk.
    Jan 23, 2019 at 17:53

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.