摘要
由于简单、安全且便于高效实现,R-LWE上FHE方案成为目前FHE方案设计的主流。R-LWE上FHE方案基于剩余类环R=Z[x]/(f(x))的多项式扩张因子大小对密文同态操作时的噪声膨胀速度有重要影响。基于对无穷范数意义下多项式环R的扩张因子的研究,给出了几个特殊多项式所对应的具体扩张因子值。证明了系数为零的单项式越多的多项式,其对应的扩张因子越小,系数为0的单项式的幂次越高,其对应的扩张因子越小。该结果可为R-LWE上高效同态密码算法的设计提供理论指导。
Because of the simplicity,security and efficiency R-LWE-based FHE schemes become the mainstream design of FHE.The value of polynomial expansion factor of R-LWE-based FHE for quotient ring R = Z[x]/(f(x)) has an important influence on the noise expansion speed for homomorphic operation of ciphertexts. Based on the expansion factor of ∞ norm for different polynomials,the values of expansion factors of ∞ norm over ring R for some special polynomials f(x) are obtained. It proves that the larger numbers of monomials with coefficient being zero for polynomials f(x), the smaller the corresponding expansion factors is. The higher the power of a monomial with a coefficient of 0, the smaller the corresponding expansion factor. The results can provide theoretical guidance for the design of efficient R-LWE-based FHE schemes.
引文
[1]RIVEST R L,ADLEMAN L,DERTOUZOS M L. On data banks and privacy homomorphisms[J]. Foundations of Secure Computation,1978:169-179.
[2]MITTAL D,KAUR D,AGGARWAL A. Secure data mining in cloud using homomorphic encryption[C]//IEEE International Conference on Cloud Computing in Emerging M arkets.[S. l]IEEE,2014:1-7.
[3]PASUPULETI S K,RAMALINGAM S,BUYYA R. An efficient and secure privacy-preserving approach for outsourced data of resource constrained mobile devices in cloud computing[J]. Journal of Netw ork&Computer Applications,2016,64(C):12-22.
[4] JAIN R,MADAN S,GARG B. Homomorphic framework to ensure data security in cloud environment[C]//International Conference on Innovation and Challenges in Cyber Security.[S. l]IEEE,2016:177-181.
[5]GENTRY C. Fully homomorphic encryption using ideal lattices[J]. Stoc,2009,9(4):169-178.
[6]REGEV O. On lattices,learning with errors,random linear codes,and cryptography[C]//Acm Symposium on Theory of Computing. ACM,2005:84-93.
[7]BRAKERSKI Z,VAIKUNTANATHAN V. Efficient fully homomorphic encryption from(standard)LWE[C]//Foundations of Computer Science. IEEE,2011:97-106.
[8]BRAKERSKI Z,VAIKUNTANATHAN V. Fully homomorphic encryption from ring-LWE and security for key dependent messages[C]//Cryptology Conference. Berlin:Springer,2011:505-524.
[9] BRAKERSKI Z,GENTRY C,VAIKUNTANATHAN V.(Leveled)Fully homomorphic encryption without bootstrapping[J]. Acm Transactions on Computation Theory,2014,6(3):1-36.
[10]BRAKERSKI Z. Fully homomorphic encryption without modulus switching from classical GapSVP[C]//Cryptology Conference on Advances in Cryptology-CRYPTO. New York:Springer-Verlag,2012:868-886.
[11]GENTRY C,HALEVI S,PEIKERT C,et al. Ring switching in BGV-style homomorphic encryption[C]//International Conference on Security and Cryptography for Netw orks. Berlin:Springer,2012:19-37.
[12]ALPERIN-SHERIFF J,PEIKERT C. Practical bootstrapping in quasilinear time[M]//Advances in Cryptology—CRYPTO2013. Berlin:Springer,2013:1-20.
[13]GENTRy C,SAHAI A,WATERS B. Homomorphic encryption from learning with errors:conceptually-simpler,asymptotically-faster,attribute-based[M]//Advances in Cryptology—CRYPTO 2013. Berlin:Springer,2013:75-92.
[14]ALPERIN-SHERIFF J,PEIKERT C. Faster bootstrapping with polynomial error[M]//Advances in Cryptology—CRYPTO2014. Berlin:Springer,2014:297-314.
[15]DUCAS L,MICCIANCIO D. FHEW:Bootstrapping homomorphic encryption in less than a second[M]//Advances in Cryptology-EUROCRYPT 2015. Berlin:Springer,2015:617-640.
[16]COSTACHE A,SMART N P. Which Ring based somewhat homomorphic encryption scheme is best?[C]//CryptographersTrack at the RSA Conference. Cham:Springer,2016:325-340.