Every RLWE implementation I know uses unsigned integers even when it needs to represent signed values. Why?
$\begingroup$
$\endgroup$
5
-
1$\begingroup$ There exist implemented papers claiming benefits to using signed operations, so I don't know if the choice of unsigned arithmetic is for some fundamental reason. $\endgroup$– Mark Schultz-Wu ♦Commented Nov 5 at 6:08
-
1$\begingroup$ Wild guess: when short vectors are sampled, they're converted to NTT domain, so all working variables have non-negative coefficients. $\endgroup$– DannyNiuCommented Nov 5 at 11:03
-
$\begingroup$ @DannyNiu: Are you sure that the NTT domain requires non-negative coefficients? See for example Efficient Word Size Modular Multiplication over Signed Integers. $\endgroup$– garfunkelCommented Nov 6 at 13:41
-
$\begingroup$ I'd say that it's mentally easier to think of multiplying positive numbers when looking what happens on bit-level. Also checking only if a number is smaller than the modulus (positivity is practically for free thanks to the negative flag of most CPUs) is easier than checking if an absolute value is bounded, at least if you are working on a low-level implementation. Only after understanding the easier case of unsigned integer completely, I'd tackle the same problem for signed values. $\endgroup$– garfunkelCommented Nov 6 at 13:44
-
$\begingroup$ Note that many ops are identical for signed (two-complement) and unsigned integers. Not sure if that plays a part here though. $\endgroup$– Maarten Bodewes ♦Commented Nov 6 at 23:33
Add a comment
|