Intel Paillier Cryptosystem Library: An ISO-compliant Implementation Accelerated with Intel AVX512/IFMA

Authors: Sejun Kim (sejun.kim@intel.com), Jingyi Jin (jingyi.jin@intel.com), with contribution from Bin Wang, Xiaoran Fang, Pengfei Zhao, Fillipe D.M. de Souza, Anil Goteti, and Flavio Bergamaschi
Edited by Evan Peregrine

Introduction

Paillier Cryptosystem [1] is a form of partial Homomorphic Encryption (HE) that allows additive operation in homomorphically encrypted data. Invented by Pascal Paillier in 1999, it is one of few HE schemes that has been standardized (ISO/IEC 18033-6) [2]. For that reason, Paillier Cryptosystem is widely used, primarily for privacy-preserving Federated Learning (FL) and secure aggregation. Nevertheless, despite the popularity of Paillier Cryptosystem, there has been a lack of an efficient, well-maintained, and most importantly, an ISO-compliant software library that implements the scheme.

In order to meet the need of an efficient and standardized Paillier scheme, we developed Intel Paillier Cryptosystem Library (IPCL) [3] , the first open source, ISO-compliant Paillier Cryptosystem software implementation that is optimized for performance on the latest 3rd Generation Intel® Xeon® Scalable Processors.

IPCL is being integrated into one of the most used federated learning software platforms: Federated AI Technology Enabler (FATE), to expedite its deployment by the community. DEKRA, an ISO 19790 accredited laboratory, certifies that each Paillier functionality implemented in IPCL is ISO-18033 compliant.

Paillier Cryptosystem Scheme

Paillier Cryptosystem is a type of an asymmetric keypair-based encryption scheme, similar to RSA. However, unlike many other asymmetric schemes, Paillier Cryptosystem also provides linear homomorphism, which means encrypted ciphertexts can be added or multiplied, and the decrypted results will be equal to non-encrypted addition or multiplication results.

The public-private key pair is generated by, given the key length \(n_{length}\), two random prime numbers \(p\) and \(q\), such that \(n=p∙q\) and \(bitsize(n)==n_{length}\), where \(n\) is the public key and \(p,q\) is the private key.

The encryption and decryption are performed in the following steps:

1. Encryption
   Given plaintext \(m<n\), select random integer \(r<n\) and \(g∈ \mathbb{Z}^*_{n^2}\)
   Ciphertext \(c=g^m r^n \bmod {n^2}\)
2. Decryption
   Set \(g=n+1, λ=lcm(p-1,q-1)\)
   Given ciphertext \(c<n^27\)
   Plaintext \(m= \frac {L(c^λ \bmod n^2 )}{L(g^λ \bmod n^2)}\)

The homomorphic addition and multiplication are calculated by the following formulas: 

• Addition (Ciphertext + Ciphertext): \(c_1∙c_2 \bmod n^2=m_1+m_2 \bmod n\)
• Addition (Ciphertext + Plaintext): \(c_1∙(n∙m_2+1 mod n^2 ) mod n^2=m_1+m_2 mod n \)
• Multiplication (Ciphertext * Plaintext): \(c_1^{m_2} mod n^2=m_1 m_2 mod n\)

Intel Paillier Cryptosystem Library with Intel® Integrated Performance Primitives Cryptography

Commonly used implementations of the modular exponentiation are from OpenSSL [4] and GNU Multiple Precision Arithmetic Library (GMP) [5], which many cryptographic libraries are based on. As an alternative to those libraries, Intel® Integrated Performance Primitives Cryptography (Intel® IPP Cryptography) [6] is an open source library that offers similar mathematical functionalities as the OpenSSL and GNU libraries, but is optimized for large number computation on Intel systems, alongside cryptographic operations. Especially for systems with Intel® Advanced Vector Extensions 512 (Intel® AVX512) and Integer Fused Multiply Accumulate (IFMA) enabled, Intel IPP Cryptography can concurrently support eight (8) modular exponentiation operations through the multi-buffer function \(mbx\_exp\_mb8()\), as shown in Figure 2. On supported systems, the Intel IPP Cryptography multi-buffered modular exponentiation can provide various degrees of speed-up compared to GMP. For more details, please refer to our previous blog [7]. 

Intel Paillier Cryptosystem Library is developed on C++ by solely depending on Intel IPP Cryptography for both large number representation (Intel IPP Cryptography BigNumber) and mathematical operations. We have also built IPCL Python [9] to facilitate and expedite potential integration to additional software frameworks.

Conclusion and Future Plans / Use

We introduced and released IPCL, the first open source, ISO-compliant implementation of Paillier Cryptosystem, optimized for Intel Xeon processors. IPCL provides accelerated primitives of the Paillier cryptographic scheme— encryption, decryption, addition, and multiplication—with optimization techniques including: 

• Utilizing the Intel IPP Cryptography library’s multi-buffer feature, built based on the Intel AVX-512/IFMA instruction sets, to accelerate the calculation of modular exponentiation.
• Applying algorithmic optimizations such as Chinese Remainder Theorem (CRT) and Damgard-Jurik-Nielsen (DJN) scheme.

 We will be continuously improving the IPCL with code optimization in the future. 

Bibliography

1. P. Paillier, "Public-key cryptosystems based on composite degree residuosity classes," in International conference on the theory and applications of cryptographic techniques, Berlin, Heidelberg, Springer, 1999, pp. 223-238.
2. "ISO/IEC 18033-6:2019 IT Security techniques - Encryption algorithms - Part 6: Homomorphic encryption," International Organization for Standardization, [Online]. Available: https://www.iso.org/standard/67740.html.
3. "Intel Paillier Cryptosystem Library," Intel Corp, [Online]. Available: https://github.com/intel/pailliercryptolib.
4. FedAI, "Federated AI Technology Enabler (FATE)," Mar 2022. [Online]. Available: https://github.com/FederatedAI/FATE.
5. "OpenSSL: Cryptography and SSL/TLS Toolkit," 2022. [Online]. Available: https://www.openssl.org/.
6. "The GNU Multiple Precision Arithmetic Library," 14 11 2020. [Online]. Available: https://gmplib.org.
7. Intel, "Integrated Performance Primitives Cryptography," 2022. [Online]. Available: https://github.com/intel/ipp-crypto.
8. Intel, "Accelerating Secure Compute for the FATE Framework," Intel, 1 Mar 2022. [Online]. Available: https://www.intel.com/content/www/us/en/developer/articles/technical/homomorphic-encryption/accelerating-secure-compute-for-fate-framework.html.
9. "Intel Paillier Cryptosystem Library Python," Intel Corp., [Online]. Available: https://github.com/intel/pailliercryptolib_python.
10. K. Bonawitz, V. Ivanov, B. Kreuter, A. Marcedone, H. B. McMahan, S. Patel, D. Ramage, A. Segal and K. Seth, "Practical Secure Aggregation for Privacy-Preserving Machine Learning," in proceedings of the ACM SIGSAC Conference on Computer and Communications Security, 2017.