HEAAN

HEAANDeveloper(s)| Cryptography LAB in Seoul National University

|

Initial release| May 15, 2016; 9 years ago (2016-05-15)
Written in| C++
Type| Homomorphic encryption
License| CC BY-NC 3.0

HEAAN (Homomorphic Encryption for Arithmetic of Approximate Numbers) is an open source homomorphic encryption (HE) library which implements an approximate HE scheme proposed by Cheon, Kim, Kim and Song (CKKS).[1] The first version of HEAAN was published on GitHub[2] on 15 May 2016, and later a new version of HEAAN with a bootstrapping algorithm[3] was released. Currently, the latest regular version is version 1.1[4] and the latest pre-release version is 2.1.[5]

## Contents

* 1 CKKS plaintext space
* 1.1 Encoding method
* 1.2 Decoding method
* 2 Algorithms
* 2.1 Key generation
* 2.2 Encryption
* 2.3 Decryption
* 2.4 Homomorphic addition
* 2.5 Homomorphic multiplication
* 2.6 Rescaling
* 3 Security
* 4 Library
* 5 References

## CKKS plaintext space

Unlike other HE schemes, the CKKS scheme supports approximate arithmetics over complex numbers (hence, real numbers). More precisely, the plaintext space of the CKKS scheme is ℂn/2 for some power-of-two integer n. To deal with the complex plaintext vector efficiently, Cheon et al. proposed plaintext encoding/decoding methods which exploits a ring isomorphism ϕ:ℝ[X]/(Xn+1)->ℂn/2.

### Encoding method

With a plaintext vector z→=(z1,z2,...,zn/2)∈ℂn/2 and a scaling factor Δ>1, the plaintext vector is encoded as a polynomial m(X)∈R:=ℤ[X]/(Xn+1) by computing m(X)=⌊Δ⋅ϕ−1(z→)⌉∈R where ⌊⋅⌉ denotes the coefficient-wise rounding function.

### Decoding method

Given a message polynomial m(X)∈R and a scaling factor Δ>1, the message polynomial is decoded to a complex vector z→∈ℂn/2 by computing z→=Δ−1⋅ϕ(m(X))∈ℂn/2.

Here the scaling factor Δ>1 enables us to control the encoding/decoding error which is occurred by the rounding process. Namely, one can obtain the approximate equation Dcd(Ecd(z→;Δ);Δ)≈z→ by controlling Δ where Ecd and Dcd denote the encoding and decoding algorithm, respectively.

From the ring-isomorphic property of the mapping ϕ:ℝ[X]/(Xn+1)->ℂn/2, for m1=Ecd(z→1;Δ) and m2=Ecd(z→2;Δ), the following hold:

* Dcd(m1+m2;Δ)≈z→1+z→2,
* Dcd(m1⋅m2;Δ)≈z→1∘z→2,

where ∘ denotes the Hadamard product of the same-length vectors. These properties guarantee the approximate correctness of the computations in the encoded state when the scaling factor Δ is chosen appropriately.

## Algorithms

The CKKS scheme basically consists of those algorithms: key Generation, encryption, decryption, homomorphic addition and multiplication, and rescaling. For a positive integer q, let Rq:=R/qR be the quotient ring of R modulo q. Let χs, χr and χe be distributions over R which output polynomials with small coefficients. These distributions, the initial modulus Q, and the ring dimension n are predetermined before the key generation phase.

### Key generation

The key generation algorithm is following:

* Sample a secret polynomial s<-χs.
* Sample a (resp. a′) uniform randomly from RQ (resp. RPQ), and e,e′<-χe.
* Output a secret key sk<-(1,s)∈RQ2, a public key pk<-(b=−a⋅s+e,a)∈RQ2, and an evaluation key evk<-(b′=−a′⋅s+e′+P⋅s2,a′)∈RPQ2.

### Encryption

The encryption algorithm is following:

* Sample an ephemeral secret polynomial r<-χr.
* For a given message polynomial m∈R, output a ciphertext ct<-(c0=r⋅b+e0+m,c1=r⋅a+e1)∈RQ2.

### Decryption

The decryption algorithm is following:

* For a given ciphertext ct∈Rq2, output a message m′<-⟨ct,sk⟩ (mod q).

The decryption outputs an approximate value of the original message, i.e., Dec(sk,Enc(pk,m))≈m, and the approximation error is determined by the choice of distributions χs,χe,χr. When considering homomorphic operations, the evaluation errors are also included in the approximation error. Basic homomorphic operations, addition and multiplication, are done as follows.

### Homomorphic addition

The homomorphic addition algorithm is following:

* Given two ciphertexts ct and ct′ in Rq2, output ctadd<-ct+ct′∈Rq2.

The correctness holds as Dec(sk,ctadd)≈Dec(sk,ct)+Dec(sk,ct′).

### Homomorphic multiplication

The homomorphic multiplication algorithm is following:

* Given two ciphertext ct=(c0,c1) and ct′=(c0′,c1′) in Rq2, compute (d0,d1,d2)=(c0c0′,c0c1′+c1c0′,c1c1′) (mod q). Output ctmult<-(d0,d1)+⌊P−1⋅d2⋅evk⌉∈Rq2.

The correctness holds as Dec(sk,ctmult)≈Dec(sk,ct)⋅Dec(sk,ct′).

Note that the approximation error (on the message) exponentially grows up on the number of homomorphic multiplications. To overcome this problem, most of HE schemes usually use a modulus-switching technique which was introduced by Brakerski, Gentry and Vaikuntanathan.[6] In case of HEAAN, the modulus-switching procedure is called rescaling. The Rescaling algorithm is very simple compared to Brakerski-Gentry-Vaikuntanathan's original algorithm. Applying the rescaling algorithm after a homomomorphic multiplication, the approximation error grows linearly, not exponentially.

### Rescaling

The rescaling algorithm is following:

* Given a ciphertext ct∈Rq2 and a new modulus q′<q, output a rescaled ciphertext ctrs<-⌊(q′/q)⋅ct⌉∈Rq′2.

The total procedure of the CKKS scheme is as following: Each plaintext vector z→ which consists of complex (or real) numbers is firstly encoded as a polynomial m(X)∈R by the encoding method, and then encrypted as a ciphertext ct∈Rq2. After several homomorphic operations, the resulting ciphertext is decrypted as a polynomial m′(X)∈R and then decoded as a plaintext vector z→′ which is the final output.

## Security

The IND-CPA security of the CKKS scheme is based on the hardness assumption of the ring learning with errors (RLWE) problem, the ring variant of very promising lattice-based hard problem Learning with errors (LWE). Currently the best known attacks for RLWE over a power-of-two cyclotomic ring are general LWE attacks such as dual attack and primal attack. The bit security of the CKKS scheme based on known attacks was estimated by Albrecht's LWE estimator.[7]

## Library

Version 1.0, 1.1 and 2.1 have been released so far. Version 1.0 is the first implementation of the CKKS scheme without bootstrapping. In the second version, the bootstrapping algorithm was attached so that users are able to address large-scale homomorphic computations. In Version 2.1, currently the latest version, the multiplication of ring elements in Rq was accelerated by utilizing fast Fourier transform (FFT)-optimized number theoretic transform (NTT) implementation.

## References

1. ↑ Cheon, Jung Hee; Kim, Andrey; Kim, Miran; Song, Yongsoo (2017). "Homomorphic encryption for arithmetic of approximate numbers". ASIACRYPT 2017. Springer, Cham. pp. 409–437. doi:10.1007/978-3-319-70694-8_15.
2. ↑ Andrey Kim; Kyoohyung Han. "An approximate HE library HEAAN". https://github.com/snucrypto/HEAAN. Retrieved 15 May 2016.
3. ↑ Jung Hee Cheon, Kyoohyung Han, Andrey Kim, Miran Kim and Yongsoo Song. Bootstrapping for Approximate Homomorphic Encryption. In EUROCRYPT 2018(springer).
4. ↑ "Release HEAAN with BOOTSTRAPPING · snucrypto/HEAAN" (in en). https://github.com/snucrypto/HEAAN/releases/tag/1.1.
5. ↑ Release HEAAN with Faster Multiplication · snucrypto/HEAAN, Cryptography LAB in Seoul National University, Sep 5, 2018, https://github.com/snucrypto/HEAAN/releases/tag/2.1, retrieved 2024-12-10
6. ↑ Z. Brakerski, C. Gentry, and V. Vaikuntanathan. Fully Homomorphic Encryption without Bootstrapping. In ITCS 2012
7. ↑ Martin Albrecht. Security Estimates for the Learning with Errors Problem, https://bitbucket.org/malb/lwe-estimator

0.00

(0 votes)

Original source: https://en.wikipedia.org/wiki/HEAAN. Read more

|

Retrieved from "https://handwiki.org/wiki/index.php?title=Software:HEAAN&oldid=4158112"