According to Camenisch et al. in Efficient Protocols for Set Membership and Range Proofs (see Section 1.2), the range proofs devised by Boudot in Effcient Proofs that a Committed Number Lies in an Interval are based on representing a number as the sum of four squares.

Based on this, Camenisch et al. claim that the complexity of Boudot's scheme is governed by the cost of finding these squares (see Section 4.4 of the paper by Camenisch et al.)

However, studying Boudot's schemes, I do not see any reference to this issue. Rather, Boudot defines the squares involved in the proof as $\tilde{x}^2_1,\bar{x}^2_1$, where $\tilde{x_1} = \lfloor\sqrt{x-a}\rfloor$ and $\bar{x_1} = \lfloor\sqrt{b-x}\rfloor$, where the value being proved, $x$, belongs in $[a,b]$. So the computation of these squares seems quite straight forward.

What am I missing?


1 Answer 1


Boudot's protocol is not based on the four-square decomposition - in fact, he was the first to come up with this idea of using a decomposition in four squares, but this was only mentioned orally in the talk he gave on this paper (as I was told by people who saw it - I do not think there is any written record). The first written record on this four squares idea is Lipmaa's Asiacrypt'03 paper (where you'll find additional discussion on the cost of finding these four squares). Boudot's original protocol has other efficiency shortcoming, though, but they are related to the communication required for the protocol, not to the cost of finding the decomposition.

  • $\begingroup$ Good, thanks. So the comparison done by Camenisch et al. is either wrong or they mistakenly cite Boudot's system. $\endgroup$
    – Ginswich
    May 22, 2018 at 14:19
  • $\begingroup$ Or they refer to the system mentioned in his talk (that's not so uncommon to do so), but in any case they do not seem to discuss the actual system which is described in Boudot's paper, as far as I can see. $\endgroup$ May 22, 2018 at 14:41

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.