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

Github: https://github.com/nucypher/DarkIntegers.jl
Docs: https://nucypher.github.io/DarkIntegers.jl/latest/

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 https://nucypher.github.io/DarkIntegers.jl/latest/manual.html):

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, https://github.com/nucypher/DarkCurves.jl , 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

Cool, I was about to say you should plug it into my FHE library (https://github.com/JuliaComputing/ToyFHE.jl) and win some FHE speed contests, but I see you have your own CKKS implementation already at https://github.com/nucypher/HEAAN.jl. 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

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.

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

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