2
$\begingroup$

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.

$\endgroup$

1 Answer 1

1
$\begingroup$

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).

$\endgroup$
3
  • $\begingroup$ Would you mind and edit links to the mentioned ressources (JoinSplit, Stadler-Camenisch,...) into your answer? $\endgroup$
    – SEJPM
    Jun 18, 2018 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, 2018 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$ Jun 21, 2018 at 22:02

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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