Worse than that, even if 3 exact squares are found, one of the three square roots is likely to turn out to be very small (fewer than 32 bits). None of the roots are blinded for the proofs to work; they have to be the actual commitments. Then either the prover has to generate a new random number and run large-integer factoring again (and again...), or the attacker will know that one of the 3 committed values is cheap to break. Then the smallest square might as well be in plaintext and save the 50% overhead anyway. To solve that problem, [38] suggests using a probabilistic ECC system instead of a deterministic one, which doubles the cost of all commitments (though there are probably some new methods to push some of the cost back down), introduces the need for additional explicit equality proofs and other complexities.

It does have many solutions, as there are many more integers close (up to ∆) to sums of squares than there are integers that are actually sums of squares. There are also many more sums of squares than there are squares. Easy way to think about it is to set ∆=1, and see how sums of squares can work with it (4+9+1=14, 9+16+1=26, 4+16+1=21, 16+25+1=42, 4+25+1=30, ...), and that this is only bounded by the modulus of the system.

A proof of exactly how well [sum_of_two_squares, sum_of_two_squares + n] covers the integers would be good to include in the paper (it might also help to calibrate a better upper limit for ∆), but difficult to come up with.

I think solving your point 4 is sufficient.