Natural to-from Ring (AsNaturalNumber & AsRingElement)

[ycscaly]

I'd like to write a decrypt<T>(decryption_key: &T, encryption_key: &T, ciphetext: &T) -> T function that does Paillier decryption.

Paillier decryption first raises the ciphertext c to the power of the decryption key d modulo the sqaure of the encryption key n^2. For this, I would need a trait bound for T that allows me to exponentiate given a specific modulus.

Next, we switch to work over the integers to perform L which takes the above result and decrease one from it and divides by n. So I need a trait bound for T that satisfies division over the integers.

Now, we need to think of that result again as in a finite field but this time mod n and not n^2, and do modular multiplication with the inverse of the decryption key d^-1. So again, we need a trait bound that allows modular multiplication (and the modulus shouldn't be fixed).

I can and have written such code using crypto-bigint directly, but want to decouple myself and work over traits instead, and have crypto-bigint implement these traits e.g. for U4096.

I think that's possible, maybe the current traits aren't the ones to satisfy it tho.

let me know if this makes sense now, and I'll open an issue for this.

I'd like to write a decrypt<T>(decryption_key: &T, encryption_key: &T, ciphetext: &T) -> T function that does Paillier decryption.

Paillier decryption first raises the ciphertext c to the power of the decryption key d modulo the sqaure of the encryption key n^2. For this, I would need a trait bound for T that allows me to exponentiate given a specific modulus.

Next, we switch to work over the integers to perform L which takes the above result and decrease one from it and divides by n. So I need a trait bound for T that satisfies division over the integers.

Now, we need to think of that result again as in a finite field but this time mod n and not n^2, and do modular multiplication with the inverse of the decryption key d^-1. So again, we need a trait bound that allows modular multiplication (and the modulus shouldn't be fixed).

I can and have written such code using crypto-bigint directly, but want to decouple myself and work over traits instead, and have crypto-bigint implement these traits e.g. for U4096.

I think that's possible, maybe the current traits aren't the ones to satisfy it tho.

let me know if this makes sense now, and I'll open an issue for this.

Originally posted by @ycscaly in #70 (comment)
Following several discussions with @tarcieri, both in #70 and in #158, I decided to create this issue, and a corresponding PR #214 for this discussion.

My idea here is to have two types of "numbers" (i.e. num_traits::Num) that we can think of when we're thinking of a Uint; to think of it as a natural number (i.e.$x \in \N$) or as a ring element (i.e.$x \in \Z_n$) and I defined corresponding traits to switch between them.

This allows me to greatly simplify my code, and also to decouple it from the particular types (e.g. U2048) and instead work over generic types.

The implementation is uncomplete and I have encountered some problems when approaching it, esp. when trying to implement Num for DynamicResidue, primarily due to what appears to be the lack of rust-lang/rust#95174 being closed - so we can't have type safety for DynamicResidue meaning the modulus can't be specified in the type, so I can't implement e.g. Zero (see my TODO comments in the PR.)

Just for illustration purposes, what was previously written (Paillier encryption) like this:

fn encrypt(encryption_key: U2048, plaintext: U2048, randomness: U2048) -> U4096 {
    let N = encryption_key;
    let N2: U4096 = N.square();
    let N2_mod = DynResidueParams::new(&N2);

    let m = DynResidue::new(&U2048::ZERO.concat(&plaintext), N2_mod);
    let r = DynResidue::new(&U2048::ZERO.concat(&randomness), N2_mod);
    let N = DynResidue::new(&U2048::ZERO.concat(&N), N2_mod);
    let one = DynResidue::one(N2_mod);

    let mut ciphertext = ((m * N) + one); // $ (m*N + 1) $
    let N: U2048 = encryption_key;
    let N: U4096 = U2048::ZERO.concat(&N);
    ciphertext *= (r.pow(&N)); // $ * (r^N) $

    ciphertext.retrieve()
}

can now be written like this:

pub fn encrypt<N: num_traits::Num, F: num_traits::Num>(encryption_key: &N, plaintext: &N, randomness: &N) -> N
    where
        N: AsRingElement<F> + Clone,
        F: AsNaturalNumber<N> + num_traits::Pow<F, Output = F> + Clone
{
    let n: N = encryption_key.clone();
    let n2 = n.clone() * n; // wrapping mul (N should be < 2048, T should be U4096);
    let n = encryption_key.as_ring_element(&n2);
    let m = plaintext.as_ring_element(&n2);
    let r = randomness.as_ring_element(&n2);
    let one = N::one().as_ring_element(&n2);

    ((m * n.clone() + one) * (r.pow(n))).as_natural_number()
}

So there are great benefits here (and for the Paillier decryption case it has an even greater effect).

Please let me know about your thoughts, both of the general idea of implementing these traits and then the specific question I've raised when implementing.

[ycscaly]

Digging deeper, it seems that Num can’t be implemented for DynResidue. That is because the notion of reminder Rem<> is undefined within a (standard, not a division) ring. It is also because we can’t implement one() or zero() for they take no self from which the moduli can be determined.

Thereafter, I thought about implementing ff:Field. It actually would have been the perfect fit, alas it also has a const ZERO and const ONE members which we cannot determine for DynResidue by definition.

Therefore I see two options;

1. Define my own RingArithmetics trait which will basically involve addition, multiplication, subtraction, optional-inversion, and exponentiation. And then implement AsRingElement<DynResidue> for Uint.
2. Drop AsRingElement and AsNaturalNumber entirely, and instead rely on a single type BigInt = Num + AddPow<Self, Output = Self> + SubMod<Self, Output = Self> + NegMod<Self, Output = Self> + MulMod<Self, Output = Self> + PowMod<Self, Output = Self> + InvMod<Self, Output = (Self, CtChoice)> building on existing traits from crypto-bigint for modular operations (as there are no such traits, nor implementations, in num-traits Or num-bigint), amending MulMod as it currently takes p_inv which is unsuitable for DynResidue and adding the missing traits PowMod and InvMod. Then implementing all these traits, using AddMod, NegMod and SubMod as is, and the rest implementing via DynResidue transitions.

I assume the second option will be more desirable by crypto-bigint, and I am leaning towards this one, assuming this is something that is of interest. I can also drop the Num dependency here, and simply explicitly state the operations or use Integer instead.

@tarcieri thoughts on this?

[tarcieri]

Sounds like you should just use Integer at that point. That's what it's for.

[ycscaly]

Sounds like you should just use Integer at that point. That's what it's for.

But I'll be missing all the modular operations that I need.

[tarcieri]

We can potentially add bounds for the modular operations, but that's debatably a breaking change.

In the meantime you can just notate them in your bounds.

[ycscaly]

We can potentially add bounds for the modular operations, but that's debatably a breaking change.

In the meantime you can just notate them in your bounds.

It's more than that, as I said before, there are missing traits for modular operations: multiplication (current one isn't complete), exponentiation and inversion.

If you'd like that, I'll open two seperate PRs: one to add these bounds, and another implementing Num

[tarcieri]

Yes, go ahead and open separate PRs for each

[ycscaly]

Closing this issue as this task has been rethought