Zero-knowledge integer comparison 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 &gt; c$ (or that $a' &lt; 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 &gt; 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).