Supporting Signed Integer Arithmetic

[erik-3milabs]

I'm interested in performing cryptographic arithmetic involving negative (signed) integers. As is made evident in #1, this crate does not yet provide support for this.

I'm exploring what writing the necessary code to support this would take. To progress my exploration, I'd like to learn what additions would be valued/accepted to this library. In particular, what would be considered a "minimal useful addition"? What functionality must be included? Adding support for all operations (right off the bat) might be beyond my current capacity.

Looking forward to your input!

Edit:
This discussion was superseded by #700

[tarcieri]

As I don't happen to work on cryptographic algorithms that require signed arithmetic (instead we use modular arithmetic where negative values wrap around a modulus, e.g. DSA, RSA, and elliptic curves) I can't answer these questions for you.

What cryptographic algorithm are you implementing and how does it leverage signed arithmetic?

[erik-3milabs]

I'm working on cryptography involving class groups. In these groups, each element can be represented as a tuple (a, b, c) with a, b, c \in \mathbb{Z} (called 'form representation'). Each tuple can be reduced to a representative with non-negative a and c. However, b can still be negative, and intermediate results involve negative coefficients too.

The most prevalent operations on these tuples are normalization, reduction, and composition. These operations use a combination of addition, subtraction, multiplication, and (floored)division on the tuple's elements.

Currently, I'm investigating whether it is "best" to make my 'math fit the code' or make the 'code fit the math'. Here, "best" is a trade-off between the code's development cost, understandability/modifiability, and execution time. It is quite a complex process ;-)

[burdges]

Just curious, do any class group protocols involve secrets or otherwise benefit from constant time arithmetic for other reasons? VDFs need pure speed, but afaik do not benefit from being constant time, but those are likely broken anyways. An accumulator or such does probably.

[erik-3milabs]

The Additive Homomorphic Encryption (AHE) scheme I'm building on top of Class Groups involves operations that I think should be constant time. Two examples:

1. encrypt(m, pk) -> ct involves (among other things) raising some predetermined group element f to the power m. An efficient method would be to do this through the repeated squaring (compose with self) of f. If the running time of this composition function is non-constant, one could potentially uncover (parts of) the bit pattern of m (which is supposed to be secret).
2. decrypt(ct, sk) -> m involves raising (part of) ct to the power -sk. Again, if the composition function isn't constant, information on sk could be leaked.

Perhaps there are other techniques to achieve this. If that is the case, I'd love to hear about them :)

[erik-3milabs]

This brings me back to my initial question: what are the requirements for a (partial) implementation of signed integer arithmetic to be accepted into this crate? If I get around to implementing (part of) it, I'd prefer to make something that has a high probability of being accepted :)

[erik-3milabs]

I noticed that there is a BoxInt62L implementation for the bernstein-yang gcd algorithm. I have two questions about this:

1. Would there be value in expanding that type to Int?
2. In the "Goals" section of the README, it reads

Constant-time by default. Variable-time functions are explicitly marked as such

I noticed that this crate's implementation of Bernstein-Yang's GCD (a function I'd like to use) is not marked as "variable time". Though, I noticed that it contains an if-statement, as well as a while-loop that are conditional on the input. I thought this was a big no-no for constant-time algorithms. What am I missing here?

[tarcieri]

Using a built-in public signed number implementation rather than the private vendored implementation used for Bernstein-Yang is a good observation for a potential improvement, but signedness is half the story. The other is the 62-bit unsaturated limb representation, where we'd need Uint to be generic around the inner limb type, which is a bit tricky right now because we also want to support const fn.

It's all potentially doable right now though, even on stable Rust.

I noticed that this crate's implementation of Bernstein-Yang's GCD (a function I'd like to use) is not marked as "variable time". Though, I noticed that it contains an if-statement, as well as a while-loop that are conditional on the input. I thought this was a big no-no for constant-time algorithms. What am I missing here?

That's definitely also another good observation, and it seems like it was probably a case of something more like PoC-quality code being committed due to lack of proper review (mea culpa), in the haste of trying to build out all the functionality that was needed for rsa.

The conditional negation is easy enough to fix. I believe the while loop can be replaced by always running in a worst-case number of iterations, similar to how inv_mod is implemented.

I'll make a separate tracking issue for that. Thanks.

Edit: opened #627

[erik-3milabs]

The other is the 62-bit unsaturated limb representation, where we'd need Uint to be generic around the inner limb type, which is a bit tricky right now because we also want to support const fn.

It's all potentially doable right now though, even on stable Rust.

Sounds like this is going to be a complex project. I'm in! Sounds like quite some planning/investigation will have to take place to do this right. I'm just getting the hang of Rust, so we'll have to collab to properly integrate this nicely into the crate. Do you have a preferred way of working in this regard?

[tarcieri]

@erik-3milabs I'd suggest starting by adding signed integer support.

Rather than my previous suggestion of trying to make Uint/BoxedUnit generic around the limb type, I'd investigate if it's possible to implement what are now called UnsatInt/BoxedUnsatInt as newtypes of the signed integer type, handling the 62-bit unsaturated form using the existing Limb types.

[ycscaly]

@tarcieri just mentioning that I'm working with Erik and will be helping, it is valuable for us to have constant-time signed integers.

[erik-3milabs]

@tarcieri IIUC, you're essentially proposing to investigate whether it is possible to replace

pub(super) struct UnsatInt<const LIMBS: usize>(pub [u64; LIMBS]);

with

pub(super) struct UnsatInt<const LIMBS: usize>(pub Int<LIMBS>);

where Int<LIMBS> would be the yet-to-be-implemented signed integer struct that depends on [Limb; LIMBS].

The first step - moving from u64 to Limb - should not be too much work (famous last words). As for the second step - making it a newtype of Int<LIMBS>: I don't know whether that makes sense. Let me try to explain.

Idealistic perspective

Making UnsatInt a newtype of Int<LIMBS> would suggest the following 'dependency tree':

This suggests that UnsatInt is a special case of Int. I would argue, however, that UnsatInt and Int are both cases of a (non-existing) SaturationInt<LIMBS, SAT_LVL>, where

• Int<LIMBS> = SaturationInt<LIMBS, 64>
• UnsatInt<LIMBS> = SaturationInt<LIMBS, 62>.

Extrapolating this would yield the following dependency tree:

i.e., from an idealistic perspective, one should first split on saturation level, and only then on signedness.

Realistic perspective

Ok, let's come back down to earth. I don't think there is demand for a UnsatUint struct. Moreover, this split would make Uint unnecessarily complicated to understand. Also, Uint would most likely get a performance hit because of the added genericity, while it is (probably) used much more often than UnsatInt. In other words, not worth the effort.

Instead, I think we should stick with the structure we have right now:

and provide proper support to switch from Int to UnsatInt and back.
Then, in the future, if there were to be demand for

1. UnsatUint, or
2. UnsatInt<SAT_LVL>,

the library could be made generic to include those as follows:

TL;DR:

From a structural perspective, I think it is best to leave UnsatInt`BoxedUnsatInt` be.

I'd love to hear your take on this.

[erik-3milabs]

As for implementing an Int module: how about I get started introducing

• add
• cmp
• concat
• div
• from
• mul
• neg
• rand
• resize
• split
• sub
  ?

[tarcieri]

As for implementing an Int module: how about I get started introducing...

Sure, that sounds fine

The first step - moving from u64 to Limb - should not be too much work (famous last words).

One complication is that Limb is a newtype for either u32 or u64 (i.e. Word) depending on the target, and the current Bernstein-Yang implementation is specialized to 62-bit limbs and always uses a u64.

So if you really want to support Limb over u64 it will also be necessary to add a 32-bit implementation of Bernstein-Yang. The paper briefly discusses this (see also #380) although I wasn't able to get it to work or find a working 32-bit (30-bit?) implementation to use as a reference.

Also, as it were, the implementation the current B-Y UnsatInt type uses was originally const generic around the number of bits, like you propose.

[lleoha]

@tarcieri

As I don't happen to work on cryptographic algorithms that require signed arithmetic (instead we use modular arithmetic where negative values wrap around a modulus, e.g. DSA, RSA, and elliptic curves)

Even for RSA you might want to have signed integers. Imagine the "scalar"/"exponent" of the elements of multiplicative group modulo N, which you don't know the factorization of (exactly like RSA public key). Then you cannot negate this scalar by doing negation mod phi(N), because you don't know the order of the group (unless you have secret key of RSA).

[erik-3milabs]

@tarcieri development has commenced! I decided to start with the checked and wrapping functionality for the add, sub, mul, and div operations.

Given your experience, have you, perchance, stumbled across a reference guide on implementing (fast) signed integer arithmetic (but never gotten around to implementing it yourself)? That could save me the arduous search for one.

[lleoha]

reference guide on implementing (fast) signed integer arithmetic (but never gotten around to implementing it yourself)? That could save me the arduous search for one.

Waiting on @tarcieri response, I'll let myself to add my $0.02 here as I have some experience implementing big ints.
IMO there are really only two possible options here:

• store extra sign bit along with digits/limbs (potential issues: zero has two representation as 0 and -0), I've come across this approach in virtually any unbound big int implementation (e.g. Go's big.Int, rust's num_bigint and so on),
• store the sign in the MSB of most significant digit/limb. So the limbs/digits are basically two's complement representation. The advantage of that is that most of the operations would be exactly the same as for unsigned digits/limbs and it's just a matter of how to interpret the limbs (the most significant limb being "signed").

I don't know which approach would be better here, provided it has to be constant time and crypto safe.
For my C++ implementation (not public unfortunately) of bound big signed integers (by bound I mean compile time size is known, as is it with this project) I went with the latter option. It performs a little worse that the former would in mul/div but is consistent with unsigned ints and easier to do const-time.

[erik-3milabs]

@lleoha thanks for your input! Three quick questions:

store extra sign bit along with digits/limbs (potential issues: zero has two representation as 0 and -0),

1. I.e. sign-magnitude (except storing the sign separately)?

store the sign in the MSB of most significant digit/limb. So the limbs/digits are basically two's complement representation.

2. This description does not sound like twos' complement, but more like sign-magnitude?

3. I find your proposal rather interesting, as my first idea would be to use twos' complement. Do you know of one/more reason(s) why this would not work / be slower than the others?

[lleoha]

@erik-3milabs

2. This description does not sound like twos' complement, but more like sign-magnitude?

This is exactly two's complement, the MSB is sign but the remaining bits are not interpreted as absolute value of unsigned int (e.g. -1 being all bits set to 1, sign included), with that addition, subtraction etc. work the same for signed and unsigned integers or mix thereof.

With sign magnitude the sign bit is usually stored seperately, so you can compute sign seperately and work on absolute values stored in limbs.

3. I find your proposal rather interesting, as my first idea would be to use twos' complement. Do you know of one/more reason(s) why this would not work / be slower than the others?

Well, it kind of depends on the implementation, but the naive method would require to sign extend when casting to bigger domain, probably not a problem with fixed length integers, but this is something that is not needed in "sign magnitude" approach, where extension is just filling with zeros.
Or in more generic context if you have a negative number any more significant limb that is not stored is implicitly all one's for negative numbers or all zero for non negative ones, which you have to take into account when doing widening mul, in the sign magnitude these would be zero so you can skip these in widening mul. But again this is when implementing school book multiplication naive way.

If I were to make a choice I would give it a go with twos complement for fixed sized int (as in this project).
You can take a look at num_bigint which is not fixed sized and took "sign magnitude" approach, which IMO is more suitable for dynamic sized integers mostly due to trivial sign extension in multiplication.

[tarcieri]

A few quick points:

This library supports both fixed-width and variable-width big integers, and ideally we could share algorithmic implementations between the two forms (see #667).

Generally I’d say the stack allocated form is the more important priority.

If one of the goals is to replace the bespoke signed integer implementation in the Bernstein-Yang / safegcd implementation, then note that algorithm is specified using two’s complement.

[tarcieri]

If you do end up going with a sign bit, it should probably be represented as a subtle::Choice.

Sidechannels involving sign bits have been a source of key recovery attacks: https://eprint.iacr.org/2015/1141.pdf

[erik-3milabs]

@tarcieri first draft PR is up: #694. Would love your feedback & input.

[lleoha]

@erik-3milabs left a bunch of comments, but general one I would still prefer to use U2 and not sign + abs (at least for fixed sized Int).

[erik-3milabs]

Superseeded by feature tracking ticket #700