# Privacy-Preserving Machine Learning with Fully Homomorphic Encryption for Deep Neural Network
- Paper: [link](https://eprint.iacr.org/2021/783.pdf)
- Model: ResNet-20 model for CIFAR-10 dataset
- Implements **RNS-CKKS** scheme
- ## Contributions:
- Implement ReLU function based on the composition of minimax approximate polynomials to encrypted data.
- **Softmax**: Implement the function from [[CKKS17]](https://eprint.iacr.org/2016/421.pdf)
- **Binary Tree Based Implementation of Polynomial Evaluation**:
- Modification of baby-step giant-step polynomial evalutaiotn algorithm using binary tree data structure
- Utilizes **Chebyshev Polynomials**: $T_{m+n}(x) - T_{m-n}(x0 = 2T_m(x)T_n(x)$
- Notes:
- $m = n \implies T_0(x) = 1$
- We set $m$ to be the *largest* power-of-two less than the degree
- Set $n$ to be the difference between the degree and $m$
- 

- **Strided Convolution:**
- Efficient convolution operation for the **packing structure in FHE schemes**
- 
- **Softmax Approximation**
- $f(x) = e^{x_i}/\sum_{j = 0}^{T - 1} e^{x_j}$
- **Exponential Function**
- Approximate the exponential function $e^x \in [-B, B]$
- Consider $(e^{x/B})^B$, then we can approximate $e^y \in [-1, 1]$ **least square method** where $y = x/B$ with a degree 12 polynomial.
- **Inverse Function**
- Goldschmidt division method
- $\frac{1 - x^{2^n}}{1-x} = \Pi^{n - 1}_{i = 0}(1+x^2)$
- For $|x| < 1$, the LHS converges to $1/(1-x)$.
- **Gumbel Softmax Funciton**
- For a somewhat large input value to the exponential function, $B$ could be very large
- Then, we use the Gumbel softmax technique:
- $\frac{e^{x_i/\lambda}}{\sum_{j=0}^{T-1}e^{x_j / \lambda}}$
- Range is reduced from $B$ to $B^{1/\lambda}$
- **Performance**
- Total Time (ResNet-20):
- After conv: **2.945 hours**
- After Relu: **6.895 hours**

# Approximate Homomorphic Encryption with Reduced Approximation Error
- Paper: [link](https://eprint.iacr.org/2020/1118.pdf)
- CKKS-RNS scheme that **removes the approximate scaling error** by computing level-specific scaling factors.
- ## Contributions
- Multiplication operation in CKKS is redefined as `ct_mult' = Mult'(ct1, ct2) = Mult(Rescale(ct_1, ∆), Rescale(ct_2, ∆))`
- Benefits of reordering rescaling and multiplication operations:
- Remove the (1) prior encoding approximation errors (2) LWE encryption error (3) addition and key switching approximation errors
- Implements **Reduced-Error** CKKS variant of RNS **(decreases output error)**
- **Eliminating the Scalor Factor Approximation Error in RNS CKKS**
- **Keeping Scaling Factor $\Delta$ Constant**: This involves choosing RNS moduli close to $\Delta$ and adjusting scaling factors after each rescaling operation to minimize errors. However, this method is complex and hard to optimize.
- **Using Different Scaling Factors for Each Level**: Instead of keeping $\Delta$ constant, adjusting scaling factors after each rescaling operation to integrate the error term $u_∆$. This eliminates the scaling factor error but introduces complexity in evaluating circuits.
- To mitigate the complexity, the approach suggests automating rescaling after each multiplication operation to maintain consistent scaling factors within the same level of ciphertexts. This ensures that all ciphertexts at the same level have the same scaling factors, reducing the potential for error accumulation. A table is provided to illustrate how scaling factors change during computations depending on the level of the ciphertext. The choice of the initial scaling factor is crucial and determined based on specific considerations not detailed in this excerpt.

# Optimized Privacy-Preserving CNN Inference With Fully Homomorphic Encryption
- Paper: [link](https://ieeexplore.ieee.org/stamp/stamp.jsp?tp=&arnumber=10089847)
- More **efficient way of evaluating convolutions with FHE**, where the cost remains **constant** regardless of the kernel size
- Results in a **12-46x** timing improvement on various kernel sizes.
- Achievements:
- *Concise* representation of convolution operations via arithmetic operations
- Input is packed into coefficeints of a polynomial of the ring $\mathcal{R} := \mathbb{Z}[X]/(X^N + 1)$
- Single convolution can be evaluated with ***single multiplication*** without any rotation.
- Extends to **batch convolutions** by packing s many convolution ouputs as possible into each output ciphertext.
- Evaluation of convolution layers: Bootstrapping procedure of FHE is modified so that convolutions are evaluated in teh coefficient domain while activation functiosn are evaluated in the slot dimension.
- **Single convolution** (multiplciation of two polynomials in $\mathcal{R}$):
- Let $I \in \mathbb{R}^{w \times w}$ be an input and $K \in \mathbb{R}^{k \times k}$ be a kernel
- 
- **Batch Convolution**:
- **Remove $DFT$ and $DFT^{-1}$** via novel packign methods of **input and kernel into co**

Implementations to benchmark:
- HEANN
- PALISADE

Strict Machine Learning Libraries to benchmark:
- https://github.com/NervanaSystems/he-transformer/tree/v0.2-benchmarks-2
- https://github.com/PaddlePaddle/Paddle
- https://github.com/alan-turing-institute/SHEEP
- https://github.com/tensorflow/ngraph-bridge

Papers to go through:

Logistic Regression
1. Bos J W, Lauter K, Naehrig M. Private Predictive Analysis On Encrypted Medical Data. Journal Of Biomedical Informatics, 2014, 50: 234-243.

Neural Networks
1. Boemer F, Lao Y, Cammarota R, et al. nGraph-HE: A Graph Compiler For Deep Learning On Homomorphically Encrypted Data. arXiv preprint arXiv:1810.10121, 2018.

2. Boemer F, Costache A, Cammarota R, et al. nGraph-HE2: A High-Throughput Framework for Neural Network Inference on Encrypted Data. Proceedings of the 7th ACM Workshop on Encrypted Computing & Applied Homomorphic Cryptography. ACM, 2019: 45-56.

3. Gilad-Bachrach R, Dowlin N, Laine K, et al. Cryptonets: Applying Neural Networks to Encrypted Data with High Throughput and Accuracy. International Conference on Machine Learning. 2016: 201-210.

Convolutional Neural Networks
1. Hesamifard E, Takabi H, Ghasemi M. CryptoDL: Deep Neural Networks over Encrypted Data. ArXiv preprint:1711.05189, 2017.

2. Hesamifard E, Takabi H, Ghasemi M. Deep Neural Networks Classification over Encrypted Data. Proceedings of the Ninth ACM Conference on Data and Application Security and Privacy. ACM, 2019: 97-108.

3. Brutzkus A, Elisha O, Gilad-Bachrach R. Low Latency Privacy Preserving Inference. ArXiv preprint arXiv:1812.10659, 2018.

4. Izabachène M, Sirdey R, Zuber M. Practical Fully Homomorphic Encryption for Fully Masked Neural Networks. International Conference on Cryptology and Network Security. Springer, Cham, 2019: 24-36.

5. Boddeti V N. Secure Face Matching Using Fully Homomorphic Encryption. IEEE 9th International Conference on Biometrics Theory, Applications and Systems (BTAS). IEEE, 2018: 1-10.

Model Training
————————————————————————————————

Logistic Regression
1. Kim A, Song Y, Kim M, et al. Logistic Regression Model Training Based On The Approximate Homomorphic Encryption. BMC medical genomics, 2018, 11(4): 83.

2. Han K, Hong S, Cheon J H, et al. Efficient Logistic Regression on Large Encrypted Data. IACR Cryptology ePrint Archive, 2018, 2018: 662.

3. Sim J J, Chan F M, Chen S, et al. Achieving GWAS with Homomorphic Encryption. ArXiv preprint:1902.04303, 2019.

4. Kim M, Song Y, Wang S, Xia Y, Jiang X. Secure Logistic Regression Based on Homomorphic Encryption: Design and Evaluation. JMIR Med Inform 2018.

Neural Networks
1. Lou Q, Feng B, Fox G C, et al. Glyph: Fast and Accurately Training Deep Neural Networks on Encrypted Data. Arxiv preprint:1911.07101, 2019.

2. Sirichotedumrong W, Maekawa T, Kinoshita Y, et al. Privacy-Preserving Deep Neural Networks with Pixel-based Image Encryption Considering Data Augmentation in the Encrypted Domain. Arxiv preprint:1905.01827, 2019.

3. Nandakumar K, Ratha N, Pankanti S, et al. Towards Deep Neural Network Training on Encrypted Data. Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition Workshops. 2019.

Convolutional Neural Networks
1. Xu R, Joshi J B D, Li C. CryptoNN: Training Neural Networks over Encrypted Data. ArXiv preprint arXiv:1904.07303, 2019.

[Securing Neural Networks with Knapsack Optimization](https://arxiv.org/html/2304.10442v2)

[Cheetah: Optimizing and Accelerating Homomorphic Encryption for Private Inference](https://scontent-lax3-1.xx.fbcdn.net/v/t39.8562-6/246804767_385235596578738_5432468749856569188_n.pdf?_nc_cat=109&ccb=1-7&_nc_sid=e280be&_nc_ohc=QeUciZTOm18AX8cdRNS&_nc_ht=scontent-lax3-1.xx&oh=00_AfDY-5ulVTjo3eXiJZCNDiLj54azKq4QbPIU4x_5DS3L5g&oe=65F2B75C)