Optimization methods for encrypted machine learning algorithms
Advisor: Ms. Gehlot
Internship Location: Intel
Onsite Mentor: Dr. Raghavan Kumar, Intel Labs
Machine Learning has become extremely prevalent in the age of computing. Data collection and analysis is instrumental to many organizations. However collecting lots of data comes with the inherent risk of people being able to steal extremely valuable information. Encrypted machine learning would ensure user privacy as data would not be decrypted. However, for many common encryption algorithms like RSA(Rivest–Shamir–Adleman) and AES(Advanced Encryption Standard), the ciphertext is not amenable to computation and thus cannot be used. To address this problem we can use Fully Homomorphic Encryption(FHE). Homomorphic encryption allows mathematical operations to be conducted on ciphertext without compromising the security of data. Data remains encrypted throughout its life cycle including computation. Homomorphic computation allows polynomial mathematics to be computed on ciphertext.
In this work we focus on adapting various optimization techniques such as gradient descent, coordinate descent, Nelder-Mead, and other algorithms for machine learning algorithms such as linear regression, logistic regression, KNN(K nearest neighbours), K-means, and basic neural networks. Almost all machine learning algorithms rely on computing the minimum value of a cost function. Therefore we can test many optimization algorithms, replacing addition, multiplication, and subtraction with the homomorphic versions to run these optimization algorithms on ciphertext. For each algorithm, we will replace operations not amenable to homomorphic encryption such as division and exponentiation with polynomial approximations.
There are many different homomorphic schemes which all rely on differing branches of mathematics such as learning with error or the torus. This project will discuss the use of different schemes such as CKKS(Cheon–Kim–Kim–Song), BGV(Brakerski-Gentry-Vaikuntanathan), TFHE(Fast Fully Homomorphic Encryption over the Torus), and others. All these algorithms have advantages and disadvantages. CKKS can work on floating point numbers, but is approximate and doesn’t support less than/equal to operations. BGV and TFHE only work on integers, but both are much faster. I expect to be able to use homomorphic encryption to develop secure machine learning algorithms that are able to work on ciphertext and determine which encryption algorithms and optimization algorithms are the strongest and most compatible with machine learning.
Project Blog
Week 1: Introduction to Homomorphic encryption
Welcome to my blog!
I will be using these blog posts to introduce the idea of homomorphic encryption and its role in machine learning. My first posts will be a general introduction into homomorphic encryption and optimization methods introducing the mathematics behind all these algorithms. Next I will discuss different machine learning algorithms and how I can use these encrypted optimization to create "secure machine learning algorithms"(nothing is ever truly secure). I will compare the results of each homomorphic encryption scheme using both accuracy and the time to determine the best optimization algorithm and encryption scheme for that particular machine learning model. I hope to get through logistical regression, K-means, KNN, and a basic neural network which I will explain in future blog posts.
I will define terms that will be used throughout the rest of my blog posts. Plaintext is the unencrypted readable version of data, while ciphertext is the unreadable encrypted version of the data. Ciphertext is what plaintext turns into when plaintext is encrypted and plaintext is decrypted ciphertext. Cipher's or encryption algorithms are the algorithms used to turn the ciphertext into plaintext and vice-versa. For almost all encryption algorithms the ciphertext is unusable and random. Therefore it seems feasibly impossible to create an algorithm that can run on ciphertext.
However there are encryption algorithms that are homomorphic. This means that the sum of two ciphertexts will give a ciphertext that when its decrypted will be the sum of the two plaintexts. For a simple example consider the numbers 1 and 2 and their ciphertexts, 14 and 34. If I were to sum 14 and 34 and get a result of 78(note we don't get 14+34 = 48, addition on ciphertext is not the same as addition on plaintext). If I were to decrypt 78 using the same key, I would end up getting 1+2=3. Fully Homomorphic Encryption allows us to run polynomial operations on ciphertext. Consequently, division, logarithms, and fractional exponents are impossible using homomorphic encryption. For the sake of brevity, I will write Fully Homomorphic Encryption as FHE or Homomorphic Encryption and an Fully Homomorphic Encryption algorithm as a scheme
Now we can return to our original question, the study of encrypted optimization methods. Optimization algorithms are used in almost all machine learning algorithms are a core component of them. To show this consider a simple example of linear regression whose goal is to find the line of best fit for a set of data points. The algorithm works by defining a cost function which finds the average of the residuals squared. A residual is how far the actual point is from the predicted point. To find the line of best fit we simply want to find the line such minimized or optimizes the cost function. This pattern shows up in nearly all machine learning algorithms where we need to minimize a cost function.
Linear Regression is a relatively simple example as the cost function itself is a polynomial, so we can calculate its derivatives analytically and use a simple gradient descent algorithm to minimize the cost function. However for other algorithms the cost function often contains e, fractions, and fractional exponents(square roots) which are impossible to calculate using homomorphic encryption. Therefore I will have to resort to different strategies and optimization algorithms.
However why is this important? Homomorphic encryption is already far more computationally intensive than running machine learning algorithms on plaintext. If needed we can just decrypt the data before running the algorithms. However, homomorphic encryption solves two major security flaws: Man-in-the-Middle attacks and cloud computing[1]. Man-in-the-Middle attacks(MITMs) allow they attacker to "eavesdrop" on a conversations between two parties. In our case if we use homomorphic encryption the attacker will only find the ciphertext and not be able to decrypt it where as If we ran the algorithm on plaintext, the attacker would be able to view all the sensitive data. Cloud computing services help many business as it provides cheaper and scalable computing services. However data privacy has always been a risk when using the cloud. Homomorphic encryption allows data privacy on the cloud something needed for smaller businesses.
However homomorphic encryption isn't perfect. Researchers have found ways to use side channel attacks[2] to gain information on the plaintext even if it is never revealed. Homomorphic encryption is also slower and less efficient than plaintext calculations. On average it takes homomorphic encryption processing 1000 times longer than plaintext processing. However despite these downsides I still think the advantages it provides are far greater and is worth studying especially as the number of ransomware and cyberattacks increase.
Through this project I hope to develop encrypted optimization algorithms that are compatible with machine learning algorithms and explain to you all the potential homomorphic encryption has. My next blog post will dive deeper into the mathematics behind homomorphic encryption specifically the algorithms CKKS(Cheon-Kim-Kim-Song), BGV(Brakerski-Gentry-Vaikuntanathan), and GSW(Gentry-Sahai-Waters). I will discuss how these algorithms encrypt, decrypt, add, multiply, and any other special operations that they can do.
Thanks for reading,
Pranav Bodapati
Sources
[1]“Homomorphic Encryption: What Is It, and Why Does It Matter?,” Internet Society, Mar. 09, 2023. https://www.internetsociety.org/resources/doc/2023/homomorphic-encryption/
[2] F. Aydin and Aydin Aysu, “Leaking Secrets in Homomorphic Encryption with Side-Channel Attacks,” Cryptology ePrint Archive, 2023. https://eprint.iacr.org/2023/1128
Week 2: CKKS and the mathematics behind it part 1
Welcome back to my blog post! This will be an extremely long and dense post discussing the mathematics behind homomorphic encryption schemes. I will first discuss some mathematics that will be needed to understand the blog post. If you don't understand the math, I will provide a summary of the important takeaways, but I think it is important to see how Homomorphic Encryption works.
Math Interlude
First lets define what a cyclotomic polynomial is. It is an irreducible(non factorable in the integers) polynomial that is divisible by x^k-1 but not any lower degree polynomial of that form. Their roots are all primitive roots of unity something that is very important. Now we will define polynomial rings. The ring Z[X]/f(x) is a ring of integer polynomials. where everything is reduced with the condition f(x) = 0. For example if f(x) = x^4+1 we have that x^5 = -x, x^4 = -1.... And we can restrict this further by taking Z_q which is all numbers that are from 0 to q-1. The notation (Z_q)* is all numbers that are relatively prime to q in Z_q(gcd is 1). The cardinality of this set is phi(q). Finally the Vandermonde matrix is a square matrix of geometric series as its rows. It is used to find the polynomial such that f(x) valued at specific values is equal to specific vector.
CKKS(Cheon-Kim-Kim-Song)
The CKKS encryption scheme is one of the few encryption schemes that works on floating point numbers. CKKS does mathematics on polynomials rather than vectors due to polynomial arithmetic being faster. First lets discuss the encoder. The encoder is different from the encryption algorithm. The job of the encoder is to turn a vector into a polynomial as mathematics is faster on the polynomial. Then the polynomial will be encrypted.
First we will consider a simple case encoding a vector z of of length N into a polynomial m(x) in C[x]/(x^N+1) where N is a power of 2. To do this we evaluate our polynomial on the vector (xi,xi^3,xi^5 ... xi^(2N-1)) where xi = e^(i*pi)/N. We want to find the polynomial m such that (m(xi), m(xi^3) .. m(xi^(2N-1)) is equivalent to our vector z. However we can see that we can construct the Vandermonde matrix A for (xi,xi^3 ... xi^(2N-1)) and now we are just looking to solve the equation A*a = z where a is the vector of coefficients for m. Therefore we get a = A^{-1}*z. This is commonly written as sigma^-1(z) where sigma is the canonical embedding between complex polynomials and complex vectors. However we can't use this since a will have complex coefficients and to utilize the properties of integer polynomial rings. Note that even if our data is made of a integers a will still have complex coefficients.
Lets consider the embedding sigma on R = Z[x]/(x^N+1). One think we can notice is that the values that we are evaluating our function on are actually complex conjugates of each other. Therefore m(xi^j) = \overline{m(xi^-j)} = m(\overline(xi^-j)). Therefore sigma(R) turns a polynomial into a N/2 length complex vector. Therefore for any
Define H = {(z_j )j∈(Z_M)* : z_j = overline(z_-j) , ∀j ∈ (Z_M)*} ⊆ C^phi(M). This is simply the set of phi(M) length vectors that are "symmetric".(The complex conjugate of the jth element is the same as the phi(M) - j + 1th) element. Now we define the operator pi (z_j)j∈(Z_M)*→ (z_j )j∈T . Where T is a multiplicative subgroup of (Z_m)* such that (Z_m)*/T = {+1,-1}. If this makes no sense that's ok. All this does is create the operator pi that takes an element from H and turns it to an element of C^(N/2) by taking (1+3i 4-3i,1-3i,4+3i) to (1+3i, 4-3i). Therefore we want an algorithm that finds a polynomial m for pi^-1() * sigma^-1(z) and provides an isomorphism from C^n/2 and H.
However we have a small problem because the operator sigma defines an isomorphism from R to sigma(R) but not all elements of H are in sigma(R). Therefore we need to find a way to project pi^-1(z) on sigma(R). To do this we will use a technique called coordinate wise rounding.
R has an basis for (1.. X^N-1) and therefore sigma(R) has an basis of (sigma(1).. sigma(X^{N-1}). Therefore we simply project an element z as sum(z_i*sigma(x^i)) for all i from 0 to n-1 where z_i = <z,sigma(x^i)_i>/||sigma(x^i)||^2 where <> denotes a hermitian product(x_i*overline{y_i}). Once we found z_i we round them randomly. Since rounding might destroy significant values we multiply by a scaling factor delta.
I will quickly go through the example used in the paper to give a clear understanding of how this works. Let N = 4 and M=8 and delta = 64. Lets encode (3+4i,2-i). The polynomial 1/4 * (10+4root2 * X + 10X^2 + 2root2 * X^3) has these values at xi and xi^3 respectively. The encoding algorithm will round this to 160+91X+160X^2+45X^3. Decoding gives us (3.0082 + 4.0026i, 1.9918 − 0.9974i) which is extremely close to the correct value[1].
Now that we have our encoding we need to explain the encryption algorithm
Encryption
CKKS is a public key encryption scheme which relies on the Ring Learning With error problem. The problem involved adding noise to pairs. To do this we first discuss learning with error a simpler version of the problem. We will consider the pair (a_i,b_i) = (a_i, <a_i,s_i> + e_i) from random pairs. Notice without e, the problem becomes a trivial gaussian elimination system and the error term provides enough complexity that it can't even be cracked by quantum computers. The e_i s are usually extremely small numbers that are gaussians that create the worst case lattice problems. If we write this in matrix form we have (-a*s+e,a) as our public key. To encode we take a message mu by adding (mu,0) to the public key to get (mu-a*s+e,a) as (c1,c2). To decrypt we just take (c_1+c_2*s) = mu-a*s+e+a = mu+e which approximates the message
We take polynomials a,s,e. s is the secret private key polynomial, a is a random polynomial uniformly sampled, and e is a small error polynomial. We give our public key as (-a.s+e,a). The negative isnt really important here. To encrypt a random message mu, we return (mu -a.s+e, a) and to decrypt it we simply just add (mu -a.s + e) + a.s = mu. As we are multiplying polynomials we can use the discrete Fourier transform to compute it faster. This is one of the main reasons we encode our vectors as polynomials and ring learning with error are much better than regular learning with error.
Multiplication and Addition.
If we have two messaged mu and mu' that are encrypted as (mu-a.s+e,a) + (mu'-a.s+e,a) = (mu+mu' - 2a.s+2e,2a) which is decrypted as mu+mu' + 2e which can be approximated as mu+mu' so addition is homomorphic. Multiplication is slightly more complicated. First we discuss multiplication with a ciphertext and a plaintext. If we have mu encrypted as (mu-a.s+e,a) = (c_0,c_1) and multiply iy by mu' a plaintext we get (mu'*c_0, mu'*c1) which if we decrypt we get mu'*c_0 + mu'*c_1 = mu'*(mu+e) = mu'*mu + mu*e which is approximately mu'*mu.
Using these tools described above we can easily describe the last 2 encryption algorithms aswell as ciphertext to ciphertext multiplication something I will do for in my next blog post.
Sources
[1] J. Cheon, A. Kim, M. Kim, and Y. Song, “Homomorphic Encryption for Arithmetic of Approximate Numbers.” Available: https://eprint.iacr.org/2016/421.pdf
Week 3: Multiplication, Linearization, and Rescaling
Picking up where we left off on our last blog post its time to discuss ciphertext-ciphertext multiplication.
Ciphertext to Ciphertext multiplication
We want to find an operation such that decrypt(f(c,c'),s) = decrypt(c,s)*decrypt(c',s). Remember that for key (c0,c1) decrypt is c0+c1s. Simplifying we get c0*c'0 + (c0c'1 + c1c'0)*s + c1*c1's^2 which we can rewrite as d0+d1s+d2s^2. If we consider this as a polynomial in s, we have the operation f(c,c') = (d0,d1,d2) = (c0*c'0,c0c'1+c1c'0,c1c'1). and write this as a polynomial in s. Our problem however is that we have expanded into 3 variables. To solve this problem we look for two polynomials d0' and d1' such that f(c,c') = d0'+d1's. We will introduce an evaluation key. evk = (-a0*s+e0+s^2,a0) where a0 is chosen from R_q ,e0 are chosen randomly. If we decrypt evk with s we get s^2+e0 which is approximately s^2. However if we try and multiply this by d2 we end up with the term d2*e0 which is too large for an error to ignore. The trick is rather than multiplying the entire -a0*s+e0+s^2 by a polynomial d2 we change it to (-a0*s+e0+p*s^2) mod pq where a0 is randomly chosen from R_pq and p is a large prime. The purpose here is to decrease the error provided by d2*e0 by dividing it by a large prime p. So to relinearize (d0,d1,d2,evk) we turn it to (d0,d1)+floor(p^{-1} * d2*evk) which will give us our answer.
Rescaling is the final step for CKKS
The more multiplication operations you get the nosier your ciphertext becomes due to all the error polynomials. To solve this problem CKKS using rescaling and bootstrapping. Bootstrapping is well beyond the scope of this senior project although I might discuss it later. It works as a self decrypting algorithm, finding a less nosy ciphertext that contains the same value. The more we try to ensure security by increasing the polynomial degree, the more time consuming the process becomes showcasing the tradeoff between the security, accuracy, and speed of an operation something that we will discuss further.
As we have seen from multiplication, multiplying two ciphertexts adds some large error. In fact if we multiply two ciphertexts together we get (z*z'*delta^2). Note delta is the scaling factor used to incentive precision and z/z' is the encoding of our vectors. Therefore if we want to do L multiplications we need to make sure we remember how much scaling we need. We can keep track of this by multiplying q_L = delta^L*q_0. So we just divide by this amount. This also decreases our error term because the error is being divided by this amount. We do have a problem for extremely large numbers. If delta is 2^30(ensures 30 bits of precesion) than q_l = 2^340. This is an extremely large number. To solve this problem we can use the chinese remainder theorem and modular arithmetic to reduce the number of operations. The rescaling part was brief however the major takeaway is that rescaling is time-expensive we will need to balance accuracy and time when using homomorphic encryption.
Sources
[1] J. Cheon, A. Kim, M. Kim, and Y. Song, “Homomorphic Encryption for Arithmetic of Approximate Numbers.” Available: https://eprint.iacr.org/2016/421.pdf [2] D. Huynh, “CKKS explained, Part 5: Rescaling - OpenMined,” OpenMined, Nov. 19, 2020. https://openmined.org/blog/ckks-explained-part-5-rescaling/ (accessed Mar. 08, 2025).
Week 4: Finally applying homomorphic encryption to machine learning
Welcome to my blog post. We will continue outside of FHE into the machine learning aspect of the research.
Logistic and Linear Regression
logistic and linear regression are extremely common machine learning algorithms that have an extremely wide impact. Linear Regression as its name suggests finds the line of best fit through a series of calculations called gradient descent. Logistic regression works in a similar way where it takes an input and gives a binary answer(usually yes or no). It does this by using the sigmoid function which I will denote as sigma(z) = 1/(1+e^-z). However z isn't actually the input(lets say an image) it is usually in the form of W*x + B. This makes sense intuitively if z is a large positive number e^-z becomes extremely small and sigma(z) = 1. If z is a large negative number e^-(-z) becomes a large positive number and 1/(a large numbers) becomes approximately 0. So we have our simple classification algorithm. Run a function on some data point usually linear trained such that positive numbers mean yes and negative numbers mean no and train it on the sigmoid function. I will point out that logistic regression isn't optimal usually(tanh is preferred), but we will stick with our definition of sigma(z) for now.
Gradient descent
Gradient descent is a very common optimization algorithm something that we will discuss in future blog posts. However it is probably the most well known and extremely simple and fast to implement. It works rather intuitively. Consider a parabolic simple curve. At the minimum point, we know that the derivative is equal to 0(the line tangent to it is flat). If you don't know calculus the derivative is simple the slope of the tangent line and it makes sense that at the minimum will be a point where there is nothing below it so the line is flat. Now df/dx is the estimated slope at the point and can be used to estimate values of the function. Using the defintion of the derivative gives the approximation f(x+h) ~ f(x) + h * df/dx. However we don't know the sign of h. To this we make an observation. If the derivative of a function is positive it means the function is increasing and we want to go into the opposite direction. A similar observation can be made for h being negative giving us the following f_new(x) = f(x) - alpha*df/dx where alpha is a fixed value.
Although I said previously derivatives can't be calculated easily for linear regression its extremely simple as the function is a polynomial and the derivative of a polynomial is also a polynomial and polynomials can be calculated easily. Therefore we can easily use the common technique as backpropagation as well as the provided vectorization by CKKS(I can multiply a 1 dim vector with a 5 dim vector to get a 5 dim vector) and write the derivatives as polynomials.
However for logistic regression we can't do this as the function is 1/(1+e^-z) and the cost function is -(x*log(z) + (1-x)*log(1-z)). The logic behind this cost function is let x be the correct value. if the correct value is 0 we want we end up with log(1-z). If z is close to 0 we dont add anything to the cost since log(1) is 0. However log(0.000007) is a large negative number increasing our cost. However neither of these are polynomials and therefore we need to find a different way of doing this. Many strong mathematicians may point to the Taylor series a way of turning log(x) into a polynomial series that approximates it. However this approximates the value not the entire function(i will explain this in a later blog post using graphs). Therefore the derivatives are inaccurate.
Therefore we cant use taylor series to approximate the entire function and instead we use a technique called the least squares method to approximate the function as a degree 3 polynomial and test CKKS and potentially other algorithms.
Thanks for reading. If anyone can find a good approximation curve feel free to comment it I will give my answer in the next blog post
Week 5: The finishing touches for logistic regression
Welcome back to my blog post. Here we will finally start the actual coding of the first algorithm logistic regression. If you remember from my last blog post our goal is to find a function f(x) that closely matches the sigmoid function sigma(x) = 1/(1+e^-x).
Possible Approximations
Since homomorphic encryption is time consuming and many multiplications increases the need for rescaling and bootstrapping our goal is to minimize the number of ciphertext-ciphertext and ciphertext-plaintext multiplications. Therefore we will stick to small degree(3) approximations. The first option I and many papers considered was the taylor series, I way of approximating functions. However comparing the graphs of the Taylor series to the function on such an interval doesn't yield such results. To see this graph the functions sigmoid(x) and 0.5+x/4-x^3/48 the taylor series approximation for sigmoid(x). As you can see at the point (0,0.5) it has perfect accuracy, but is vastly different at all other points. This is because the taylor series approximates the function at the point, not the entire function. We want to look at possible approximations across wider ranges. The reason for this is our function is optimized using the parameters M and B such that sigmoid(Mx+B) provides a yes(1) or no(0) result. Therefore we want Mx+B to have a much wider range. Therefore we consider the "least squares fitting method"
This method is extremely similar to gradient descent except now rather than having mx+b, we have g(x) = a0+a1x+a2x^2+a3x^3 where x,x^2,x^3 can be treated as their own parameters that need optimizing. Then we use the least squares cost function sum[(g(x)-sigmoid(x))^2]. We don't need to use homomorphic encryption to optimize this function since we aren't actually using any data we are just trying to find a curve that fits the sigmoid function enough. However we need to pick the points (x,sigmoid(x)) that we want our cost function to be calculated on. Choosing all numbers from -8 to 8 with one decimal place gives us an approximate line 0.5 + 0.15x − 0.0015x^3.
Although this curve is good we can still try another method called the Remez algorithm. It works in a similar way but finds an approximation only using n+2 points for an n degree polynomial. The way these points are chosen is beyond the scope of this blog post however when these 5 points are chosen. The Linear system a0+a1x_i+a2x_i^2+a3x_i^3 + (-1)^i*E for all 5 x_is. The algorithm works by setting these up as linear equations. There is a faster algorithm to solve the system in O(n^2), but since we are only looking for a degree 3 polynomial we can use this algorithm to get 0.5 + 0.197x −0.004x^3. Now with these new approximations we can start coding!
Sources
https://eprint.iacr.org/2018/462.pdf
Week 6: Optimization algorithms: the final piece
As we discussed in previous blog posts our goal in machine learning algorithms involve optimizing certain cost functions. As we discussed previously these cost functions are often functions in terms of the function we are optimizing. For example if we are optimizing a line y = mx+b, our cost function will be in terms of m and b. Similarly if our curve is ax^3+bx+c, we optimize a function f(a,b,c). We will discuss the most prominent optimization algorithms and later test their viability with homomorphic encryption. We will first discuss gradient descent the most common optimization algorithm.
Gradient Descent
Gradient Descent uses the derivative of a function at a point to determine what direction and by how much should we adjust both inputs. The derivation is extremely simple as all we do is update each function with alpha*partial derivatives where alpha is the learning rate. However gradient descent is commonly ran using the back propagation method and requires lots of multiplications of ciphertexts and plaintext-ciphertext multiplications. As we recall from discussions around CKKS, multiplication increases the error often forcing rescaling and bootstrapping the most time consuming operations. Therefore we run a few extra optimizations to gradient descent that will boost its speed at the cost of some accuracy we hope is minor. Through our tests, we will determine how beneficial these optimizations are. One example is mini-batch gradient descent which runs the algorithms on smaller randomly chosen values at each step. There is also another method involving momentum and velocity whose math we will discuss later.
Coordinate Descent
While Gradient Descent updates all values at the same coordinate descent keeps n-1 parameters constant and focuses on updating one value at a time. While it can still use the same method as gradient descent by calculating derivatives, it doesn't decreases the number of operations. Here we use a newer method called Line Search. Where I take two points and keep comparing them, decreasing the higher value using a predetermined formula. As long as the two points chosen are on opposite sides we will always get to the output. This reduces lots of multiplications however does introduce comparisons.
Nelder-Mead
The final algorithm we will discuss is the Nelder-Mead algorithm. This algorithm is also a line search algorithm, but rather than searching for a specific point, it searches for the area of a function that has a lower value, by comparing it to other regions. It uses a series of fixed steps called "expansions" and "contractions" that we will discuss later. This algorithm contains no ciphertext-ciphertext multiplications and only ciphertext-plaintext multiplications.
Week 7: Problems and advancements
A Few Problems
Welcome back to my blog post. As discussed in previous blog posts we are working on both KNN and logistic regression. However we have found a few small problems. Most homomorphic encryption libraries are written in c or c++, however for this project I want to use python as it is most commonly used for machine learning. However all python libraries don't support bootstrapping. Bootstrapping is the process of creating a noiseless ciphertext that operations can be done on. However if there is too much noise which arises from multiplication operations then we must bootstrap. To solve the problem of bootstrapping not being viable, I am forced to decrypt and encrypt again which increases the time considerably and is also not secure as we are decrypting it, but I think for the final result we will simply replace it with the step of bootstrapping. Another problem involves setting the hyperparameters for the cipher. If we recall previous blog posts, all ciphers involve a ring of a certain modulus and a set number of primes. Choosing these values increases the number of multiplication operations that can be done. However even with this adjustment it takes over two hours to run one loop. However on a better computer with the ability to use bootstrapping and other optimizations that the openfhe library has we can decrease this time to 30 minutes in total.
Despite these problems we are still making considerably progress, finishing the gradient descent and half of coordinate descent. In our next blog post, I will hopefully have the results for logistic regression done and later the results for KNN and K means and we can finally move on to neural networks. The mathematics of the project is almost complete(minus the discussion of inverse square roots) and we are almost able to focus completely on the coding aspect.
Week 8: A major setback Week 8
Welcome back to my senior project blog.
Continuing our plan from our past blog post I am currently coding our logistic and KNN algorithms in homomorphic encryption. To set up a cipher for the python library TenSEAL, we need to first set up the hyperparameters for our cipher. This is because TenSEAL doesn't contain the bootstrapping operation. To further understand this we need to turn to the word "boostrapping". Bootstrapping is a self decrypting process in homomorphic encryption that finds an equivalent ciphertext with less noise to the one that is currently in use. As we do many calculations in gradient descent, the error contained in our ciphertext rises rendering them useless for computation any further. However my goal throughout the entire project was to avoid bootstrapping(which is why I chose TenSEAL) because it often takes 10 minutes to compute a bootstrapping operation and if I have to do it for each iteration the encrypted version is so time intensive that their is no reason to actually do it.
However there is a way to solve this problem. The hyperparameters for our cipher involve determining the scaling factor, modulus, and bit sizes for polynomials. The larger the scaling factor the result will be more accurate, but might take a longer scaling time. Modulus size increases security, but as the degrees get larger the computation scales at a much higher rate than normal. However the most important hyperparameter is the bit size. These numbers determine the possible primes that can be used and are directly related to both the modulus and the scaling factor. the bitsizes are listed in an array [a,b,b,b,....,b,b,a] where b is the scaling factor and the sum of all the bits needs to at least a specific number(determined by TenSEAL to match the modulus's security level). Therefore to allow the number of computations needed for gradient descent. To do this I tested many different combinations until I came to one that could at least compute 10 iterations of gradient descent. I ended up using a modulus of 8192(2**13) and bit sizes [21,22(8 times),21]. However if this doesn't provide accurate results, I will be forced to simulate bootstrapping and add an extra 10 minutes to my time anaylsis
Week 9: Reaching the finish line Week 9
Welcome back to my blog!
After discussing the hyperparameters I have decided to simulate bootstrapping 3 times and compare the accuracy of (0 bootstrapping,1,2, and 3). Now I can finally start my discuss my work on the neural network. Most neural networks end with a final step using a sigmoid function so I can just use my work in logistic regression. However before neural networks use activation functions. The most common activation function is RELU(0 for negative numbers x for positive numbers) however its derivative will need me to decrypt certain values like I needed to do for KNNs. This again poses risks as you don't want to be sending any plaintext when using homomorphic encryption. Another possible activation function is the tanH function. similar to the sigmoid function it gives positive values 1 and negative values -1.
One might think that we can do a least squares approximation like we did for tanh like we did for sigmoid As they look extremely similar. The tanh function is (e^x-e^(-x))/(e^x+e^(-x)). Just like the sigmoid function we will reach a point where we need to bound the interval and I decided to stick with [-4,4] and using similar method reached a degree 5 polynomail 0.7642x−0.0732x^3+0.0027x^5. I tried to find a degree 3 polynomial but testing without the CKKS approximation was already giving very inaccurate results. I suspect that it won't be worth using this approximation for tanh and we will unfortunately have to stick with using the RELU function instead as although it will be much faster will also be less secure. A final option could be using a different type of activation function.
The job of an activation function is to introduce non linearity. This is the main reason why we use the RELU function or exponentiation. If none of these prove fruitful, I will look at polynomial activation functions.
Week 10: A new activation function Week 10
In our last blog post we discussed the idea of two activations functions RELU and tanh. RELU the more commonly used function written as max(x,0) would be possible to code in homomorphic encryption. However to calculate the derivative we need to check whether the value of max(x,0) == 0. Equality is impossible in homomorphic encryption, therefore we would have to decrypt the value of max(x,0) which itself makes calculating max(x,0) pointless and puts too much security risk. To be precise, we want to avoid running any decryption operations in loops. However calculating the RELU function will be done in a loop and provide massive security risk. Calculating the max itself is quite computationally intensive making the RELU activation function difficult to use.
The next option we discussed was tanh. However tanh has two problems. It is used less often than RELU due to its derivatives approximating 0 leading to less change in the values. However our approximate function is degree 5(already too big to be normally used) and lacks the same structure as the regular tanh function having certain negative values with a derivative of the wrong sign. This will cause a massive amount of problem and led to an extremely inaccurate and time-consuming process as expected.
This leads us to consider the point of an activation function in the first place(to introduce non-linearity to our system). If our activation function was just mx+b we would just be doing linear regression. Therefore one option is to try activation functions in the form of polynomials. the square activation function had been used briefly and is worth a try here. Although one might say that this is just polynomial regression, using a polynomial approximation for tanh accomplishes the same thing expect with bounded derivatives. In our final blog post I will discuss my finding with this new activation function,
Week 11: The end for now
Welcome to my final blog post. Here I will discuss the results of my project and further exploration of the topic. Logistic regression proved to be the simplest to work with and the most secure/accurate. This is due to the sigmoid function easily being approximated as a 3rd degree polynomial and a simple standardization allowing the data to stay in the [-4,4] range. Since the sigmoid function is a polynomial we can calculate its derivatives easily. This allows us to use gradient descent and back propagation easily. Running the encrypted sigmoid function and randomly generated data showed that it gave a similar accuracy to the plaintext version while being 2 minutes slower per iteration. However I believe that this is the most successful of all algorithms.
The next algorithm we got results for was KNN. KNN is quite a simple algorithm to code as the distances itself are just the sum of squares of the differences between the data points. However I was unable to find a suitable way to compare the encrypted distances to find the K smallest. The only successful comparison I was able to do was between two relatively different numbers. With multiple distances I was unable to find the K smallest and was therefore forces to decrypt the data to find the K smallest. I personally don't think the 75 seconds time it took was necessary when we inevitable have to decrypt the final distances although some will argue that decrypting it doesn't give any unnecessary information.
The neural network provided to be the most interesting. The square activation function provided interesting results sometimes up to par with the RELU function but other times 10% less accurate. However comparing the encrypted neural network to other square activation functions on plaintext would always provide the same results as expected. It took around 5 minutes for one iteration to run. I personally consider this a strong success even getting a 76% accuracy on one iteration and one hidden layer. Future work in my opinion involves understanding the RELU function more and using the definition of the derivative and coordinate descent to calculate the optimal point. I would write RELU(x) = f(x) = max(x,0) = (|x|+x)/2 = (x+sqrt(x^2))/2 = (x+x^2*1/sqrt(x^2))*0.5. And the inverse square can be calculated using newtons method for x^2 = 1/a^2. However this does require more study and analysis to see whether its viable.
Thank you so much for reading my blog posts. Hope you learned a lot about homomorphic encryption.