DarkIntegers, a pure Julia library for modulo integer and polynomial arithmetic

Package Announcements
,
1

Github: GitHub - nucypher/DarkIntegers.jl: A modulo arithmetic toolbox for integers and polynomials
Docs: Home · DarkIntegers.jl

This is a side project developed for prototyping of various cryptographic schemes at my job in NuCypher. The interface may be a bit rough at the moment, and there may be gaps in functionality - the features were essentially implemented as I needed them. Naturally, issues are welcome, including complaints about the API :slight_smile: It is not really production quality, but perhaps it may be interesting for someone.

The other goal of this library was to see how fast I can make Julia code - that’s why there is some type system magic (like modulus as a part of the type), and the usage of fixed-size multi-limb integers.

The operations are not constant-time currently, although it wouldn’t be much of a problem to implement constant-time algorithms. The question is, is there a guarantee that Julia compiler will produce constant-time code out of them? If anyone has any advice on that, I’d be glad to hear it.

Quick usage example (more at Manual · DarkIntegers.jl):

julia> using DarkIntegers

julia> modulus = convert(MLUInt{4, UInt64}, big(2)^256 - 2^32 - 2^9 - 2^8 - 2^7 - 2^6 - 2^4 - 1)
{(0xfffffffefffffc2f, 0xffffffffffffffff, 0xffffffffffffffff, 0xffffffffffffffff)}

julia> modulo_type = ModUInt{MLUInt{4, UInt64}, modulus}
ModUInt{MLUInt{4,UInt64},{(0xfffffffefffffc2f, 0xffffffffffffffff, 0xffffffffffffffff, 0xffffffffffffffff)}}

julia> a = convert(modulo_type, 1234)
{(0x00000000000004d2, 0x0000000000000000, 0x0000000000000000, 0x0000000000000000)}RR

julia> inv(a)
{(0x1098afeb5f38d509, 0xea027d4d969cd618, 0xb0564d2c653cfdec, 0xb65a7358604262bf)}RR

julia> a * inv(a)
{(0x0000000000000001, 0x0000000000000000, 0x0000000000000000, 0x0000000000000000)}RR

The polynomial part supports fixed-size polynomials (with coefficients of any type supporting arithmetic operations), with Karatsuba, NTT and Nussbaumer multiplications implemented.

There is also a draft DarkIntegers-based ECC library, GitHub - nucypher/DarkCurves.jl: A DarkIntegers-based library for working with elliptic curves , that already has some fast point-scalar multiplication algorithms (wNAF and endomorphism based, albeit only for one type of endomorphism). Polynomial algorithms may be similarly extracted into their own package in the future.

3 Likes
2

Cool, I was about to say you should plug it into my FHE library (GitHub - JuliaCrypto/ToyFHE.jl: Toy implementation of FHE algorithms) and win some FHE speed contests, but I see you have your own CKKS implementation already at GitHub - nucypher/HEAAN.jl: Implementation of HEAAN in Julia. This does make me think whether we shouldn’t put together an AbstractFHE.jl package that defined common methods for encrypt, decrypt, etc.

1 Like
3

Yep, prototyping FHE schemes were exactly what it was created as a basis for (there’s also TFHE, Shuhong Gao’s FHE scheme and Discrete Log proofs in other repos). I’m aware of ToyFHE too, cool stuff.

Not sure whether it is possible to make a good generic FHE API though, they have different limitations, different plaintext types, different ways of applying bootstrapping/relinearization/etc and so on. But it would be interesting to try.

Edit: actually, I didn’t realize ToyFHE has a CKKS implementation too. Which variant is it, with 2^n plaintext modulus, or the newer full-RNS one? I had problems with bootstrapping in mine, I may need to see how it is handled in your implementation.

4

I’ve been thinking about this for similar reasons. At the Julia level, this isn’t too hard to achieve with a Cassette-like pass, but unfortunately there’s no guarantee LLVM won’t just undo those transformations. Of course C/C++ implementations have exactly the same problem, so all the crypto libraries that are claiming to have constant time algorithms are probably lying unless they’re 100% assembly. There have been discussions in the LLVM community in the past for adding some attribute or other support that would force LLVM to preserve some sort of constant-time-ness property, but as far as I’m aware nobody has done any work on this.

1 Like
5

It’s full RNS with CRT-decomposition based keyswitch. I’m not entirely convinced I did it correctly though. The noise growth properties are a bit worse than what I would have expected from the literature. I just did this as a side project, so I never got around to spending too much time thinking about it.

1 Like