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