This question is a follow up to the question I asked here. Basically, the protocol I described has a flaw (as pointed out in this answer), and I am trying to figure out how to address it. The setup is:

  • Alice has a secret value $a$ to which she's publicly committed by sharing $A=a∗G+X_a$, where $X_a$ is her public key
  • She calculates a new value $a' = a - c$
  • And then publicly commits to $C = c *G$ and to $A′=a'∗G+X_a$

An independent observer can check that the math was done correctly by verifying that $A=A′+C$. However, this doesn't quite work because Alice can underflow $a$ and the verification would still pass.

One way to address it that I can think of is for Alice to prove that $a > c$ (or that $a' < a)$, but I'm not sure how this can be done without revealing $a$ or $c$.

Edit2: removed a potential approach because it doesn't seem to work.


Statement $a > c$ could be proved as $a - c - 1 = b_1^2 + b_2^2 + b_3^2 + b_4^2$. According to Lagrange theorem, a 4-tuple of integers exists for any non-negative integer such that it equals to the sum of squares. This kind of proof was suggested by Helger Lipmaa (On diophantine complexity and statistical zero-knowledge arguments. ASIACRYPT 2003). Proving statements about integers (not finite field elements) committed with Okamoto-Fujisaki commitment scheme, is doable with a group of order hidden from Prover.

Scenario described previously looks somewhat like a Zcash JoinSplit (section 1.2 High-level Overview).

| improve this answer | |
  • $\begingroup$ Would you mind and edit links to the mentioned ressources (JoinSplit, Stadler-Camenisch,...) into your answer? $\endgroup$ – SEJPM Jun 18 '18 at 20:03
  • 1
    $\begingroup$ Does Okamoto-Fujisaki commitment scheme imply trusted setup? After going through the paper it seems like it, but also my ability to understand scientific literature is pretty limited. So, I might be wrong. $\endgroup$ – irakliy Jun 20 '18 at 21:52
  • $\begingroup$ @irakliy Setup is trusted in a sense that Prover must not know modulus factorization, and modulus itself must be properly generated. $\endgroup$ – Vadym Fedyukovych Jun 21 '18 at 22:02

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.