num-traits support (optional)

[tarcieri]

Currently num-traits is only in dev-dependencies.

As originally suggested here it would be useful to have some support for traits for abstracting across bignum libraries, which would make it possible for e.g. the rsa crate to use either crypto-bigint or num-bigint-dig.

Though num-traits probably lacks all of the requisite functionality to do that, it would get us quite a bit of the way there.

[ycscaly]

Currently num-traits is only in dev-dependencies.

As originally suggested here it would be useful to have some support for traits for abstracting across bignum libraries, which would make it possible for e.g. the rsa crate to use either crypto-bigint or num-bigint-dig.

Though num-traits probably lacks all of the requisite functionality to do that, it would get us quite a bit of the way there.

Is the absence of num-traits the reason for not using crypto-bigint in rsa, k256 etc.?

I am now compiling a list of all dependencies for the MPC project I am building, and obviously a bigint library is a prerequisite for many higher-level primitives (like the actual group code, for both Paillier and the elliptic curves k256, ed25519 etc. that I need).

I am very careful in my analysis, as for me it is important to know exactly the building blocks both theory and implementation wise. It is important for me to not have duplication, so e.g. relying on both crypto-bigint and num-bigint is something I'd go a long way to avoid. There is enough attack surface as it is, I don't want to be exposed to double the attack surface.

Now, regarding choosing which bigint library to use, crypto-bigint seemed the obvious choice for me:

• because it is constant-time (num-bigint is not, afaik)
• it is no-std pure-rust (which is important for me for WASM, but num-bigint seems to offer it)
• it is developed by RustCrypto, which means the same developers of many other building blocks I plan to use anyway (like k256, and the hash functions, and maybe other tools).

But finding out crypto-bigint isn't even used internally within RustCrypto made me wonder how production-ready it is, and what was the reasons behind you choosing to work with num-bigint (is it purely for historical reasons? num-bigint was ready before crypto-bigint was, and you need to do the switch now? will supporting num-traits allow that transition?)

Thanks

[tarcieri]

Is the absence of num-traits the reason for not using crypto-bigint in rsa, k256 etc.?

k256 uses it via the elliptic-curve crate, at least using Uint for the internal Scalar implementation. The base field implementations in k256 use unsaturated limbs, so retrofitting it into the existing arithmetic is somewhat problematic.

All of the other elliptic curve libraries we maintain (e.g. p256, p384) use it for both the scalar and field implementations, although that's generally leveraging purpose-dedicated field arithmetic on saturated limbs, either implemented specific to a particular modulus or synthesized via fiat-crypto. Support for Montgomery form in crypto-bigint (i.e. Residue) is relatively new, shipping in v0.5.0 about a month ago, and we haven't attempted migrating yet.

crypto-bigint has 10 million downloads largely due to its use in the elliptic-curve crate and all of its downstream consumers.

The reason rsa (and dsa) don't use it is lack of heap-backed integers, which are needed to accommodate the widely varying key sizes used by these algorithms (as opposed to monomorphizing for multiple key sizes, or only monomorphizing for the largest supported key size and bailing out for slower ones).

It's something we plan to add but just haven't had time for.

It would be nice to be able to use traits to abstract between stack and heap-based big integers, so RSA and DSA can be implemented generically and the stack-based big integers used on heapless platforms.

[ycscaly]

Is the absence of num-traits the reason for not using crypto-bigint in rsa, k256 etc.?

k256 uses it via the elliptic-curve crate, at least using Uint for the internal Scalar implementation. The base field implementations in k256 use unsaturated limbs, so retrofitting it into the existing arithmetic is somewhat problematic.

All of the other elliptic curve libraries we maintain (e.g. p256, p384) use it for both the scalar and field implementations, although that's generally leveraging purpose-dedicated field arithmetic on saturated limbs, either implemented specific to a particular modulus or synthesized via fiat-crypto. Support for Montgomery form in crypto-bigint (i.e. Residue) is relatively new, shipping in v0.5.0 about a month ago, and we haven't attempted migrating yet.

crypto-bigint has 10 million downloads largely due to its use in the elliptic-curve crate and all of its downstream consumers.

The reason rsa (and dsa) don't use it is lack of heap-backed integers, which are needed to accommodate the widely varying key sizes used by these algorithms (as opposed to monomorphizing for multiple key sizes, or only monomorphizing for the largest supported key size and bailing out for slower ones).

It's something we plan to add but just haven't had time for.

It would be nice to be able to use traits to abstract between stack and heap-based big integers, so RSA and DSA can be implemented generically and the stack-based big integers used on heapless platforms.

Thanks for the detailed reply, however I was left even more confused because an apparent lack of knowledge on my side, I'd love if you'll clarify:

• what are saturated and unsaturated limbs?
• what do you mean by monomorphizing for a key size?
• with Montgomery support in crypto-bigint, what can change?
• which code is now generated via fiat-crypto?
• and how do you imagine num-traits support in crypto-bigint? Is that for the generic BigInt object, or also for U256 etc.?

Thank you very much

[tarcieri]

what are saturated and unsaturated limbs?

Some bigint libraries do not use all of the bits of a limb. This is an unsaturated representation. There are a few different reasons for this: sometimes the unsaturated implementation can be more efficient, especially when leveraging e.g. special properties of the field modulus.

However, one of the most common reasons was better carry handling. Unsaturated representations could use part of a limb represent carry bits. The need for this has largely been obviated by using machine instructions which provide access to the carry bit, like add-and-carry (ADC), subtraction-with-borrow (SBB), and multiply-and-carry (MAC), all of which are emitted by crypto-bigint on x86/x86_64 when using a saturated representation.

what do you mean by monomorphizing for a key size?

The size of a Uint is a const generic parameter, and thus determined at compile time.

With RSA, it'd be nice to use a 2048-bit Uint for 2048-bit keys, and a 4096-bit Uint for 4096-bit keys. In other words: to pick the number of limbs on the fly at runtime to match the key size.

Without a heap, the best you could do is having an enum over a U2048, U4096, and possibly others. This monomorphizes the arithmetic implementations specific to each size. Great for efficiency, less so for code bloat.

Heap-backed integers would allow dynamic sizes, reusing the same code regardless of the size, at the cost of efficiency.

with Montgomery support in crypto-bigint, what can change?

We could potentially use Residue as the internal type of various field elements, replacing various modulus-specific arithmetic implementations.

which code is now generated via fiat-crypto?

The arithmetic operations on the base and scalar fields for p224, p384, and p521 are all generated via fiat-crypto. We'll likely extend that to p192, bp256, and bp384 at some point too.

and how do you imagine num-traits support in crypto-bigint? Is that for the generic BigInt object, or also for U256 etc.?

Hopefully a generic implementation would work for all Uint regardless of the size.

[ycscaly]

what are saturated and unsaturated limbs?

Some bigint libraries do not use all of the bits of a limb. This is an unsaturated representation. There are a few different reasons for this: sometimes the unsaturated implementation can be more efficient, especially when leveraging e.g. special properties of the field modulus.

However, one of the most common reasons was better carry handling. Unsaturated representations could use part of a limb represent carry bits. The need for this has largely been obviated by using machine instructions which provide access to the carry bit, like add-and-carry (ADC), subtraction-with-borrow (SBB), and multiply-and-carry (MAC), all of which are emitted by crypto-bigint on x86/x86_64 when using a saturated representation.

what do you mean by monomorphizing for a key size?

The size of a Uint is a const generic parameter, and thus determined at compile time.

With RSA, it'd be nice to use a 2048-bit Uint for 2048-bit keys, and a 4096-bit Uint for 4096-bit keys. In other words: to pick the number of limbs on the fly at runtime to match the key size.

Without a heap, the best you could do is having an enum over a U2048, U4096, and possibly others. This monomorphizes the arithmetic implementations specific to each size. Great for efficiency, less so for code bloat.

Heap-backed integers would allow dynamic sizes, reusing the same code regardless of the size, at the cost of efficiency.

with Montgomery support in crypto-bigint, what can change?

We could potentially use Residue as the internal type of various field elements, replacing various modulus-specific arithmetic implementations.

which code is now generated via fiat-crypto?

The arithmetic operations on the base and scalar fields for p224, p384, and p521 are all generated via fiat-crypto. We'll likely extend that to p192, bp256, and bp384 at some point too.

and how do you imagine num-traits support in crypto-bigint? Is that for the generic BigInt object, or also for U256 etc.?

Hopefully a generic implementation would work for all Uint regardless of the size.

Wow, that's an amazing answer.

I'll take a deeper look at Residue and num-traits with these new understandings.

One thing however, why use fiat-crypto in several libraries and not others?

Is there no way of generating generic big-num (or at least for a specific modulus size) code using fiat-crypto?

[tarcieri]

One thing however, why use fiat-crypto in several libraries and not others?

The libraries that don't use fiat-crypto have handwritten field arithmetic implementations which outperform the fiat-crypto synthesized code, namely k256 and p256.

k256 in particular supports lazy normalization which helps performance significantly. To my knowledge this is only supported in fiat-crypto for fields modulo Solinas primes.

Is there no way of generating generic big-num (or at least for a specific modulus size) code using fiat-crypto?

What would it be generic around? The modulus? (like Residue?)

fiat-crypto takes the field modulus as input, and generates code specific to that modulus. It doesn't have support for generic parameters in the synthesized implementations.

[ycscaly]

One thing however, why use fiat-crypto in several libraries and not others?

The libraries that don't use fiat-crypto have handwritten field arithmetic implementations which outperform the fiat-crypto synthesized code, namely k256 and p256.

k256 in particular supports lazy normalization which helps performance significantly. To my knowledge this is only supported in fiat-crypto for fields modulo Solinas primes.

Is there no way of generating generic big-num (or at least for a specific modulus size) code using fiat-crypto?

What would it be generic around? The modulus? (like Residue?)

fiat-crypto takes the field modulus as input, and generates code specific to that modulus. It doesn't have support for generic parameters in the synthesized implementations.

Sorry that was a problem in my wording. What I meant by generic is that it is not special-purpose for e.g. a specific curve but just a standard 128,256,2024,2048,4096 etc. bits long.

I guess that won't suffice for elliptic curves because they are not really using u256 but a ~256-bit (prime sometimes) modulos right?

Also, from your questions there seems to be a tradeoff between performance and security here? if you want the formal security grantees of fiat-crypto, you lose a little on performance?

[tarcieri]

fiat-crypto synthesizes field arithmetic, so it's all specialized to the properties of a particular field modulus.

There is a formal verification versus performance tradeoff, yes. We opt for better performance because that seems to interest our users more than formal verification.

Hopefully in the future fiat-crypto will improve performance and add features like lazy normalization.

[ycscaly]

fiat-crypto synthesizes field arithmetic, so it's all specialized to the properties of a particular field modulus.

There is a formal verification versus performance tradeoff, yes. We opt for better performance because that seems to interest our users more than formal verification.

Hopefully in the future fiat-crypto will improve performance and add features like lazy normalization.

I definitely am on the other side, and if formal verification is possible it is worth performance penalties. Esp when performance optimizations in these fields tend to be a factor under 2, at least from what I've seen so far.

However, from a brief look on fiat-crypto it seems that the Rust generated code isn't formally verified (no proof).

Also, I'm not sure what are the guarantees fiat-crypto formally proves: is it purely correctness, or also side-channel resistance (e.g. constant-time)

So I'd have to dig deeper, read the fiat-crypto papers before I decide the path to go.

Assuming that I end up deciding to go with fiat-crypto, what would be the best way to assure all my cryptographic building blocks rely on it?

My thoughts (although I need to take a deeper look into num-traits) are to rely on num-traits, and to adapt the fiat-crypto generated code to it later upon instantiation.

My question to you is - could we in the future rely on num-traits for elliptic-curve and k256? just asking if it's a possibility, not whether you are willing to do it ( I might decide to contribute it myself if I find it necessary, for now I just want to know if it's a valid option)?

[tarcieri]

Most of our downstream users would disagree I think, especially about k256.

The most common requests we get on k256 are for improved performance, particularly from prospective users who are using the C implementation.

We try to improve the performance with each release. The last release shipped variable-time inversions for verification, and the next will hopefully ship wNAF.

Another option is to provide both, ala curve25519-dalek which has a fiat backend, though that would also be a lot of work.

I'm honestly not sure about using num-traits as an abstraction for the purposes of the @RustCrypto crates. crypto-bigint already has its own traits which e.g. elliptic-curve uses.

For dsa and rsa, I'd probably rather add a heap-allocated equivalent of Uint like DynUint, which could implement the crypto-bigint internal traits. That would let us take advantage of other work being done within the crypto-bigint ecosystem, like crypto-primes.

[ycscaly]

fiat-crypto synthesizes field arithmetic, so it's all specialized to the properties of a particular field modulus.

There is a formal verification versus performance tradeoff, yes. We opt for better performance because that seems to interest our users more than formal verification.

Hopefully in the future fiat-crypto will improve performance and add features like lazy normalization.

I ran some benchmarking, and was really surprised at the results. I published the code so you can see that I haven't made any mistakes.

But results are (full trace is found in the readme file of the repo):

• fiat-crypto field arithmetic is faster (add: 3.6ns vs 5.2ns, mul: 22ns vs 28ns) than k256
• crypto-bigint::Residue arithmetic faster (add: 3.8ns vs 5.2ns, mul: 27ns vs 28ns) than k256 (but slower than fiat-crypto

How can this be explained? perhaps there's some error on my side?

[tarcieri]

Perhaps open an issue on https://github.com/rustcrypto/elliptic-curves

[ycscaly]

@tarcieri getting back to the subject of this issue, is this feature something we are planning on delivering? specifically, I care about implementing Num forDynResidue, so I can support multiple backend implementations when writing my code (as I'm doing Paillier, I need a dynamic modulus and the arithmetic operations defined for it.)

[tarcieri]

I think a num-traits impl would be great, but per the issue title I think it should be an optional rather than hard dependency

[ycscaly]

I think a num-traits impl would be great, but per the issue title I think it should be an optional rather than hard dependency

Optional as in a crate feature? that works for me. If so, I'll write my code assuming it and might contribute this feature later on.

[tarcieri]

Yep

[ycscaly]

Started to develop my code based on num-traits, but found an obstacle that I cannot overcome; the Num trait offers basic arithmetic operation over some field, probably meant to be over \Z. Whilst I do need that functionality, in order to perform Paillier operations we also need to sometime think of those numbers as over \Z_{N^2} or \Z_N.

My original thinking was to implement Num for DynResidue, which I think could work:

specifically, I care about implementing Num forDynResidue, so I can support multiple backend implementations when writing my code (as I'm doing Paillier, I need a dynamic modulus and the arithmetic operations defined for it.)

But not only that this won't work in-tandem with normal (over $\Z) Uint operations, I'm not even sure how to implement Num for Uint: for example, Mul expects to output Self, which is not the case for Uint which outputs Self::Concat which is the "next-size" type (so we'd have U128 outputting U256, which makes sense but does not comply with the Num interface.)

So:

1. I'm not sure what was your original intention with implementing num-traits.
2. I believe the no num-traits interface could supply me with the operations I need for Paillier.

An interface that does, however, comply with what I need for Paillier is curv::BasicOps + curv::Modulo.

However, this trait has the same restriction as Num - it operates on the same type for both input and output of arithmetic operations so that I believe that it can't be implemented for Uint.

Would love to hear your thoughts on this @tarcieri

[tarcieri]

You should be able to implement Mul for e.g. Wrapping<Uint<LIMBS>>.

crypto-bigint deviates from core in that all operations are explicitly wide, wrapping, or checked, and there is no "checked at debug time, wrapping at compile time" behavior.

[ycscaly]

You should be able to implement Mul for e.g. Wrapping<Uint<LIMBS>>.

crypto-bigint deviates from core in that all operations are explicitly wide, wrapping, or checked, and there is no "checked at debug time, wrapping at compile time" behavior.

I see, so your suggestion is to actually use the output size (i.e. the largest integer I'll work with, e.g. the size of $N^2$ for Paillier which is 4096-bit) to represent all numbers and do operations there, so instead of multiplying two smaller numbers (e.g. the size of $P, Q$ so 1024-bit long) and getting their output size (e.g. the size of $N$ which is 2048-bit) I'll treat them all as numbers in $Z$ so-long that no operation overflows (and in my example, multiplying $P*Q$ where both P and Q take 1024-bit but are stored in a U4096, there will be no overflow -- will it also be as efficient as in wide-multiplication of U1024 by U1024 though?)

I believe this approach works, but still the num-traits traits are missing modular arithmetics so that will not be of use to me. The curv traits could work, but this issue is not about support curv traits nor do I think there is wide interest in that.

Therefore, I believe the best approach for me is to use the crypto_bigint::Integer traits with corresponding MulMod etc. traits, and if I'd need to implement them for different libraries in the future (e.g. for benchmarking) I'll adapt them to the crypto-bigint traits and not vise-versa as was intended by this issue.

Thank you in any-case; if you agree with my reasoning, I guess I wouldn't be requiring this feature anymore.

[tarcieri]

num-traits is now a hard dependency. #433 added quite a few trait impls.

It would be nice to impl Num, and there are a few PRs open to do that, but to really do that properly I think we need to finish up #246 and/or #247.

I'm going to close this and suggest #218 as a place to follow up on Num support for now.