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!

[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).