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 add it to itself to get \(2a\):
Lattice Crypto (CKKS) - Homomorphic Add |
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 add it to itself to get \(2a\):
package main import ( "fmt" "github.com/ldsec/lattigo/ckks" "os" "strconv" ) func main() { var logN, logQ, levels, scale uint64 // Scheme params logN = 10 logQ = 30 levels = 8 scale = logQ sigma := 3.19 a:=6.0 argCount := len(os.Args[1:]) if (argCount>0) { a,_=strconv.ParseFloat(os.Args[1], 64) } // Context var ckkscontext *ckks.CkksContext ckkscontext, _ = ckks.NewCkksContext(logN, logQ, scale, levels, sigma) kgen := ckkscontext.NewKeyGenerator() // Keys var sk *ckks.SecretKey var pk *ckks.PublicKey sk, pk, _ = kgen.NewKeyPair() // Encryptor var encryptor *ckks.Encryptor encryptor, _ = ckkscontext.NewEncryptor(pk) // Decryptor var decryptor *ckks.Decryptor decryptor, _ = ckkscontext.NewDecryptor(sk) // Values to encrypt values := make([]complex128, 1<<(logN-1)) values[0] = complex(a, 0) fmt.Printf("HEAAN parameters : logN = %d, logQ = %d, levels = %d (%d bits), logPrecision = %d, logScale = %d, sigma = %f \n", logN, logQ, levels, 60+(levels-1)*logQ, ckkscontext.Precision(), scale, sigma) // Plaintext creation and encoding process plaintext := ckkscontext.NewPlaintext(levels-1, scale) plaintext.EncodeComplex(values) // Encryption process var ciphertext *ckks.Ciphertext ciphertext, _ = encryptor.EncryptNew(plaintext) evaluator := ckkscontext.NewEvaluator() evaluator.Add(ciphertext, ciphertext, ciphertext) // Decryption process plaintext, _ = decryptor.DecryptNew(ciphertext) // Decoding process valuesTest := plaintext.DecodeComplex() fmt.Printf("\nInput: %f", a) fmt.Printf("\nCipher: %v\n\nDecrypted: ", ciphertext) ch:=real(valuesTest[0]) fmt.Printf("%.2f", ch) }
A sample run is:
HEAAN parameters : logN = 10, logQ = 30, levels = 8 (270 bits), logPrecision = 13, logScale = 30, sigma = 3.190000 Input: 7.200000 Cipher: &{[0xc0001294c0 0xc0001294e0] 0xc0000942c0 30 0xc000129500 true false} Decrypted: 14.40