4
$\begingroup$

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?

$\endgroup$
2
$\begingroup$

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.

$\endgroup$
  • $\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 '18 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$ – Geoffroy Couteau May 22 '18 at 14:41

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.