HEAAN (Homomorphic Encryption for Arithmetic of Approximate Numbers) defines an homomorphic encryption (HE) library proposed by Cheon, Kim, Kim and Song (CKKS). The CKKS uses approximate arithmetics over complex numbers. We will basically get an input of \(a\) and \(b\) and then encrypt them, and then add, subtract and multiply the encrypted values:
Lattice Crypto (CKKS) - Homomorphic Add, Subtract and Multiply |
Theory
Homomorphic encryption can either be partially homomorphic, somewhat homomorphic, leveled fully homomorphic, or fully homomorphic encryption. For security, the best case is full homomorphic encryption. HEAAN (Homomorphic Encryption for Arithmetic of Approximate Numbers) is a homomorphic encryption (HE) method proposed by Cheon, Kim, Kim and Song (CKKS) [paper]. Overall it is a leveled approach, and which involves the evaluation of arbitrary circuits of bounded (pre-determined) depth. These circuits can include ADD (X-OR) and Multiply (AND). HEAAN uses a rescaling procedure for the size of the plaintext. It then produces an approximate rounding due to the truncation of the ciphertext into a smaller modulus. The method is especially useful in that it can be applied to carry-out encryption computations in parallel. Unfortunately, the ciphertext modulus can become too small, and where it is not possible to carry out any more operations. The HEAAN (CKK) method uses approximate arithmetic over complex numbers (\(\mathbb{C}\)), and is based on Ring Learning With Errors (RLWE). It focuses on defining an encryption error within the computational error that will happen within approximate computations. We initially take a message (\(M\)) and convert to a cipher message (\(ct\)) using a secret key \(sk\). To decrypt (\([\langle ct,sk \rangle ]_q\)), we produce an approximate value along with a small error (\(e\)).
The main parameters are:
- logN. Number of slots of plaintext values. This must be less than logP.
- logQ. The ciphertext modulus.
- logP. The scaling factor. The larger this is, the more accurace the answer will be.
To determine \(n\) we just calculate \(n = 2^{logn}\) and simply use a bit shift (given a value of \(logn\)):
n = 1 << logn
Ring Learning With Errors
With RLWE [here] use the coefficients of polynomials and which can be added and multiplied within a finite field (\(\textbf{F}_q\)) [theory] and where all the coefficients will be less than \(q\). Initially Alice and Bob agree on a complexity value of \(n\), and which is the highest co-efficient power to be used. They then generate \(q\) which is \(2^n-1\). All the polynomial operations will then be conducted with a modulus of \(q\) and where the largest coefficient value will be \(q-1\). She then creates \(a_i(x)\) which is a set of polynomial values:
\(\textbf{A} = a_{n-1} x^{n-1} + ... + a_1 x + a_1 x^2 + a_0 \)
Next Alice will divide by \(\Phi (x)\), which is \(x^n+1\):
\(\textbf{A} = (a_{n-1} x^{n-1} + ... + a_1 x + a_1 x^2 + a_0) \div (x^n+1) \)
In Python this is achieved with:
xN_1 = [1] + [0] * (n-1) + [1] A = np.floor(p.polydiv(A,xN_1)[1])
Code
Here is the code (based on code [here]). We will basically get an input of \(a\) and encrypt it. We will then multiply this encrypted value by \(b\) and then decrypt to get \(ab\):
package main import ( "fmt" "github.com/ldsec/lattigo/ckks" "os" "strconv" ) var sk *ckks.SecretKey // Secret key for decrypting results var pk *ckks.PublicKey // Public key used to encrypt data var encryptor ckks.Encryptor // This is used to encrypt with public var decryptor ckks.Decryptor // This is used to decrypt with secret key var encoder ckks.Encoder var evaluator ckks.Evaluator // we need logQP = 600 and greater for 128-bit security // var params = ckks.DefaultParams[ckks.PN12QP109] // logQP = 109 var params = ckks.DefaultParams[ckks.PN13QP218] // // logQP = 218 // var params = ckks.DefaultParams[ckks.PN14QP438] // logQP = 438 // var params = ckks.DefaultParams[ckks.PN15QP880] // logQP = 880 const slots=1 // Number of homomorphic operations func enc_value(values1 []complex128) *ckks.Ciphertext{ // encrypt with pk : ciphertext = [pk[0]*u + m + e_0, pk[1]*u + e_1] // encrypt with sk : ciphertext = [-a*sk + m + e, a] plaintext := encoder.EncodeNew(values1, slots) ciphertext1:=encryptor.EncryptNew(plaintext) return ciphertext1 } func dec_val(ciphertext *ckks.Ciphertext) []float64 { valuesTest :=encoder.Decode(decryptor.DecryptNew(ciphertext), slots) realval := make([]float64, slots) for i:=0;i<int(slots);i++ { realval[i]=real(valuesTest[i]) } return (realval) } func main() { fmt.Printf("CKKS parameters: logN = %d, logQ = %d, levels = %d, scale= %f, sigma = %f \n", params.LogN, params.LogQP(), params.MaxLevel()+1, params.Scale, params.Sigma) argCount := len(os.Args[1:]) a1:=10.0 b1:=2.0 if (argCount≥0) {a1,_= strconv.ParseFloat(os.Args[1],16)} if (argCount≥1) {b1,_= strconv.ParseFloat(os.Args[2],2)} fmt.Printf("\na=%.1f, b=%.1f\n",a1,b1) encoder = ckks.NewEncoder(params) kgen := ckks.NewKeyGenerator(params) sk, pk := kgen.GenKeyPair() decryptor = ckks.NewDecryptor(params, sk) encryptor = ckks.NewEncryptorFromPk(params, pk) evaluator = ckks.NewEvaluator(params) values1 := make([]complex128, slots) values1[0] =complex(a1, 0) values2 := make([]complex128, slots) values2[0] =complex(b1, 0) ciphertext1:=enc_value(values1) ciphertext2:=enc_value(values2) // Example of reloading ciphertext ciphertext1 = new(ckks.Ciphertext) ciphertext1.UnmarshalBinary(obj) fmt.Printf("Bytes in cipher: %d [%s...] %d...\n", len(obj),str[0:20],obj[0:20]) // 4+ 8*N*ModPQ*(degree+1) ciphertextres:=enc_value(values1) evaluator.Sub(ciphertext1, ciphertext2, ciphertextres) res:= dec_val(ciphertextres) fmt.Printf("\n %.1f-%.1f=%.1f\n", a1,b1,res[0]) evaluator.Add(ciphertext1, ciphertext2, ciphertextres) res= dec_val(ciphertextres) fmt.Printf("\n %.1f+%.1f=%.1f\n", a1,b1,res[0]) evaluator.MultByConst(ciphertext1, complex(b1, 0), ciphertextres) res= dec_val(ciphertextres) fmt.Printf("\n %.1f*%.1f=%.1f\n", a1,b1,res[0]) }
A sample run is:
CKKS parameters: logN = 12, logQ = 108, levels = 2, scale= 4294967296.000000, sigma = 3.200000 a=3.200, b=7.300 Ciphertext: Degree=1, Level =1, Scale=4294967296.0000 Bytes in cipher: 131087 [AgAAAAAAAPBBAAEMAgAA...] [2 0 0 0 0 0 0 240 65 0 1 12 2 0 0 0 5 101 127 6]... 3.200-7.300=-4.100 3.200+7.300=10.500 3.200*7.300=-8.640