Lattice Crypto (CKKS)[Lattice Home][Home]
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.
|
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]):
package main import ( "fmt" "github.com/ldsec/lattigo/ckks" "math" "os" ) func main() { var logN, logQ, levels, scale uint64 // Scheme params logN = 10 logQ = 30 levels = 8 scale = logQ sigma := 3.19 str:="abc" argCount := len(os.Args[1:]) if (argCount>0) {str= string(os.Args[1])} // 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)) for i := 0; i < len(str); i++ { val := float64(int(str[i])) values[i] = complex(val, val) } 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) // Decryption process plaintext, _ = decryptor.DecryptNew(ciphertext) // Decoding process valuesTest := plaintext.DecodeComplex() fmt.Printf("\nInput: %s", str) fmt.Printf("\nCipher: %v\n\nDecrypted: ", ciphertext) for i := 0; i < len(str); i++ { ch:=int(math.Round(real(valuesTest[i]))) fmt.Printf("%s", string(ch)) } }
A sample run is:
HEAAN parameters : logN = 10, logQ = 30, levels = 8 (270 bits), logPrecision = 13, logScale = 30, sigma = 3.190000 Input: qwerty Cipher: &{[0xc00012b4c0 0xc00012b4e0] 0xc0000962c0 30 0xc00012b500 true false} qwerty