Internal, Fast "from scratch" Re-build of Paillier

[iamtrask]

Description: We are currently wrapping a Python implementation of the Paillier cryptosystem. While it is a great implementation, we want to be able to integrate one into our project a bit more closely. Furthermore, we would like to leverage lower level libraries for C, BLAS, and/or GPU integration when available. As such, this project endeavors to rebuild Paillier from scratch in a way that is more performant than the current (while also leaning on (ISSUE 12) for fixed point precision instead of having it deeply coupled to the encryption algorithm (as in python-paillier).

Acceptance Criteria:

1. The new implementation supports the major homomorphic operations (with unit tests demonstrating) a. Public / Private Key Generation, Serialization, and Deserialization b. Encryption and Decryption c. Addition Between Encrypted Numbers d. Multiplication of an Encrypted Number by a Decrypted Scalar e. Leverages vector "packing" for increased performance (thus, the base data structure is a vector, not a scalar)
2. The new implementation by default calls a highly performant runtime at least as fast as THIS
3. The new implementation can support BLAS if available (and if BLAS is faster than (2))
4. The new implementation can support CUDA and/or OpenCL GPU if available on a machine.
5. This implementation is constructed in a new library called PyPaillier (OpenMined/PyPaillier) and integrated into Syft proper.
6. Benchmarking suite documents the performance across a range of key sizes and backends.

[iamtrask]

@samsontmr this one could be split into sub-tasks too based on the underlying architecture (C, Blas, and CUDA tickets)

[mortendahl]

just a few inputs:

• the existing phe Python lib uses GMP underneath (when available: https://github.com/n1analytics/python-paillier/blob/master/phe/util.py#L50) so the performance is already quite good

• I am not too optimistic about how much boost we'd get from using GPUs; my best guess is that a gain will most likely only show when dealing with several ciphertexts in parallel (to eg encrypt vectors)

• a (Python) lib where the encoding is decoupled from encryption would indeed be useful; the overflow detection built in phe can sometimes get a bit in the way

based on this it would seem reasonable to me to go with phe for now, and give this re-implementation task a somewhat low priority

[iamtrask]

@mortendahl given your feedback I'm inclined to agree.

[iamtrask]

assigned it to Lithium milestone (our latest one yet laid out), and it'll be a low priority there as well :)

[iamtrask]

Rumor has it that the folks who built python-paillier are about to release a CUDA version