This thesis is published by Craig Gentry, Amit Sahai and Brent Waters: a 3rd generation fully homomorphic encryption scheme. They present a more effective and simple (leveled)FHE scheme based learning with error. In this work, a method called approximate eigenvector is used to construct a asymptotically faster FHE scheme with matrix addition and multiplication. A new technique called flatten is used to slow down the expansion of errors generated by homomorphic multiplication.
Background
Essentially, this cryptosystem is partly motivated by BGV’s FHE scheme, because in BGV’s encryption scheme after every arithmetic level especially multiplication the size of ciphertexts will expand with dimension $Theta (n^2)$ and for the reason of compactness we need to relinearize the ciphertexts which is generalized as a key switching’’ procedure in BGV’s scheme. However, key switching is an expensive step as every time to compress a processed ciphertext into a normal-sized n-dimension ciphertext the long ciphertext vector must multiply with a special $ntimes Theta (n^2)$ matrix which I introduced in the last summary: $tau_{s_1rightarrow s_2}=(text{powersof2}(textbf{s}_1)||textbf{A})$. This is a expensive step for both calculating and storage.
Observing the flaws of the FHE scheme described by Brakerski, etc. they use a approximate eigenvector method for both encryption end encryption to support matrix addition and multiplication as well as $texttt{Flatten}$ technique can keep the ciphertexts the same size after homomorphic calculations but with small coefficients. So that the key switching procedure can be eliminated and compare to the complexity of relinearization matrices with complexity $Omega (n^3)$ the complexity of matrices multipication is $n^{2.3727}$ thus the FHE scheme will be faster. And natural operation of ciphertexts allow us to do homomorphic operations without evaluation key namely, the evaluator can do homomorphic operations without knowing the user’s public key at all. This proposition can be used to construct identity-based FHE scheme as well as a recent attribute-based FHE scheme.
Decrypt by approximate eigenvector
As we mentioned above in this FHE scheme homomorphic operation is matrix addition and matrix multiplication, this works because a message ${muinmathbb{Z}_p }$ is encrypted as a $N times N$ matrix ciphertext over $mathbb{Z}_p$. In order to decrypt such a matrix ciphertext, a trick in linear algebra is used: if we set secret key $stackrel{rightarrow}{v}$ of the encryption scheme the approximate eigenvector of matrix $C $then we can say $C$ encrypts $mu$ when $Ccdotstackrel{rightarrow}{v}=mucdotstackrel{rightarrow}{v}+stackrel{rightarrow}{e}$ and compute $x=< C_i,stackrel{rightarrow}{v}>=mucdot v_i+e_i$ to decrypt for $mu=leftlfloor x/v_irightrceil$.
Thus, it is easy to see that matrix addtion just double the errors for $C^+cdot stackrel{rightarrow}{v}=(mu_1+mu_2)cdot stackrel{rightarrow}{v}+(stackrel{rightarrow}{e}_1+stackrel{rightarrow}{e}_2)$ and for matrix multiplication we have $$C^timescdot stackrel{rightarrow}{v}= C_1cdot(mu_2cdot stackrel{rightarrow}{v}+stackrel{rightarrow}{e}_2)=mu_1cdotmu_2cdotstackrel{rightarrow}{v}+mu_2cdotstackrel{rightarrow}{e}_1+C_1cdotstackrel{rightarrow}{e}_2$$
Errors from matrix multiplication come from the part $mu_2cdotstackrel{rightarrow}{e}_1+C_1cdotstackrel{rightarrow}{e}_2$ and it is actually a large error vector because $C_1$ is a $Ntimes N$ matrix in $mathbb{Z}_q$ the coefficient of $stackrel{rightarrow}{e}_2$ will be $Ncdot q$ at most. In short, in order to construct a FHE scheme we short to dcrease the magnitude of the error vector’s coefficients. However, the error vector is necessary, because the security of the scheme base on LWE problem.
Flattening Ciphertexts
As we see above $C_1$ contribute the most factor of error, to obtain a leveled FHE scheme the coefficients of the ciphertext $C$ must have a small magnitude thus ensuring better bounds on the growth of the error. A B-strongly-bounded cipher text is sufficient, namely, the associated message $mu$ and coefficients of $C$ have magnitude at most 1, while the coefficients of the error $stackrel{rightarrow}{e}$ has at most $B$. Then after evaluating a circuit of depth $L $ the error of ciphertext has magnitude at most $(N+1)^LB$ In order to keep ciphertext strongly bounded a operation called flattening is described. It also has several subroutines like what we described in the last summary abot key switching, we recall them here:
From these three subroutines, it’s not difficult to see that the most direct way to make the coefficients of a vector or matrix small is to run $texttt{Bitdecomp}$ so that all coefficients are in ${0,1}$ and then the ciphertext is B-strongly bounded indeed. However, the final aim of ciphertexts’ B-strongly bound is to decrease the magnitude of error produced by homomorphic multiplication the procedure of $texttt{BitDecomp}$ will expand the dimension of vectors by a factor of $leftlfloor log_qrightrfloor+1$ as well as procedure $texttt{Powersoft2}$.
This disadvantage will lead to the expansion of the error and it also increases the need for storage. Thus, in order to meet the need of restricting the increase of errors we should keep the dimension of vectors unchanged. Observed that $texttt{BitDecomp_{-1}}$ decrease the dimension as same as the increase by $texttt{BitDecomp}$, the technique $text{Flatten}(stackrel{rightarrow}{a}’)=texttt{BitDecomp}(texttt{BitDecomp}_{-1}(stackrel{rightarrow}{a}’)) $ make coefficients of vectors in ${0,1}$ with its dimension unchanged. The decryption of ciphertext is ensured by the good property of $texttt{Flatten}$ that for any vector $stackrel{rightarrow}{a}’$, $langlestackrel{rightarrow}{a}’,texttt{Powersof2}(stackrel{rightarrow}{b}) rangle=langletexttt{Flatten}(stackrel{rightarrow}{a}’), texttt{Powersof2}(stackrel{rightarrow}{b})rangle$.
Construction
In this scheme, we will only consider NAND gate: $C_3=I_N-C_1cdot C_2$, because NAND gate is the most universal gate and can be used to build any other gates. And we usually consider the message space ${0,1}$ so that the error increase $(N+1)B$ and a NAND-based Boolean circuit could be used for further computations. Then we get the leveled FHE scheme:
Setup$(1^lambda,1^L)$: $L$ is the multiplicative depth, $n=(lambda,L)$, error distribution $chi=chi(lambda,L)$ appropriately for LWE that achieves at least $2^lambda$security against known attacks. $m=m(lambda,L)=O(nlog_q)$
SecretKeyGen: Sample $stackrel{rightarrow}{t}leftarrowmathbb{Z}_q$. Output $sk=stackrel{rightarrow}{s}=(1,-stackrel{rightarrow}{t})inmathbb{Z}_q^{n+1}$.Let $stackrel{rightarrow}{v}=text{Powersof2}(stackrel{rightarrow}{s})$.
PublicKeyGen: The public key $pk$=$textbf{A}in R_q^{mtimes {(n+1)}}$, $textbf{A}=(stackrel{rightarrow}{b}||textbf{B})$ in which $textbf{B}leftarrow R_q^{mtimes n}$ and set $stackrel{rightarrow}{b}:=textbf{B}stackrel{rightarrow}{t}+textbf{e}$($textbf{e}leftarrow chi^m$).
Encrypt: Message space is $muin {0,1}$, sample $Rleftarrow {0,1}^{Ntimes m}$ and output the ciphertext $C$,
$$C=text{Flatten}(mucdot I_N+text{BitDecomp}(Rcdot A))inmathbb{Z}_q^{Ntimes N}$$
Decrypt: Let $v_i=2^iinleft(q/4,q/2right]$ and $C_i$ the i-th row of $C$. Then $x_ileftarrow langle C_i,stackrel{rightarrow}{v} rangle$. Output $mu’=leftlfloor x_i/v_irightrceil$
NAND $(C_1,C_2)$: $C^{NAND}=text{flatten}(I_N-C_1cdot C_2)$ and $$C^{NAND}cdot stackrel{rightarrow}{v}=(I_N-C_1cdot C_2)cdotstackrel{rightarrow}{v}=(1-mu_1cdotmu_2)cdotstackrel{rightarrow}{v}-mu_2cdotstackrel{rightarrow}{e}_1-C_1cdotstackrel{rightarrow}{e}_2$$
Since $mu_2in{0,1}$, the error is increased by a factor of at most $N+1$ and the final ciphertext’s error will be bounded by $(N+1)^Lcdot B$.
Security
The security argument is surprisingly simple. Consider $C’=texttt{BitDecomp}^{-1}(C)$. Because $C$ is already the output of $texttt{Flatten}$ it reveals nothing more than $C’$. Unpacking $C’$ to $texttt{BitDecomp}^{-1}(mu cdot I_N) + Rcdot A$, note that $Rtimes A $ is statistically uniform by the leftover hash lemma for uniform $A$. Finally, $A$ is indistinguishable from a uniform by the decisional LWE assumption.
Note
This leveled FHE scheme without evaluate key make it possible for constructing an identity-based FHE scheme which is an open problem mentioned in previous works. And I think the message to take home of this scheme is that they find a proper method to decrease the coefficients of matrix without change it’s dimension. In BGV’s FHE scheme they change the dimension of key space with key switching and modulus switching to come to the aim of decreasing noise and in this scheme the change of ciphertext space make it possible to do a much natural homomorphic calculation without increasing the error sharply.
Reference
近期评论