Identity-Based Matrix (Level) Fully Homomorphic Encryption Scheme

doi:10.3778/j.issn.1673-9418.1910061

Abstract

Abstract:

With the development of quantum theory, traditional encryption algorithms are facing enormous challenges. Once quantum computers are available, existing encryption systems will no longer be secure. The lattice cipher is proven by theory to be a new type of encryption scheme, which can resist quantum algorithm. It has the property of fast computing speed and small space occupation, hence, it has become a hot issue in today??s research. The identity-based encryption scheme can improve the utilization of storage space and facilitate user public key management. Consequently, this paper based on the hard problem of learning with errors (LWE), constructs an identity-based matrix encryption scheme at first, then applies the improved key switching technology to reduce the dimension of homomorphic ciphertext to normal, and uses the mode conversion technique to reduce noise, realizing matrix homo-morphic operation, and getting an identity-based matrix (level) fully homomorphic encryption scheme. The scheme uses matrices as the storage structure, which has greatly improved the processing capability compared to other single-bit schemes. The scheme not only satisfies the addition and Hadamard product of the matrix, but also supports matrix dot multiplication. The experimental results show that compared with other methods, the improved key switching technology in this paper inputs less noise. Through the difficulty of the LWE problem, it is proven that the scheme satisfies IND-sID-CPA (indistinguishability-selective identity-chosen plaintext attack).

Key words: lattice cipher, learning with errors (LWE), identity-based encryption, fully homomorphic encryption

摘要：

随着量子理论的发展，传统的加密算法面临着巨大的挑战，一旦量子计算机问世，现有的加密体制将不再安全。格密码是被理论证明能抵抗量子算法的新型加密方案，它具有运算速度快，占用空间小等特点，因此成为了当今研究的热点问题。身份基加密方案，能提高对存储空间的利用率，方便用户进行公钥管理。基于格上误差学习（LWE）困难问题，首先构造一个基于身份的矩阵加密方案，然后采用改进密钥转换技术将同态运算密文的维度缩减到正常值，并使用模转换技术减小噪声，实现矩阵同态运算，得到一个基于身份的矩阵层级全同态加密方案。方案以矩阵为存储结构，较其他单比特方案，在处理能力上有了大幅提高。方案不仅满足矩阵的加法与哈达玛积，还支持矩阵点乘运算。实验结果表明，该改进密钥转换技术较其他方法引入的噪声更小。最后，通过LWE问题的困难性，证明了该方案安全性满足IND-sID-CPA。

关键词: 格密码, 格上误差学习（LWE）, 身份基加密, 全同态加密

CHEN Hong, HUANG Jie, CHEN Honglin, WANG Runting, XIAO Chenglong, GUO Pengfei, JIN Haibo. Identity-Based Matrix (Level) Fully Homomorphic Encryption Scheme[J]. Journal of Frontiers of Computer Science and Technology, 2020, 14(10): 1702-1711.

陈虹，黄洁，陈红霖，王闰婷，肖成龙，郭鹏飞，金海波. 身份基矩阵层级全同态加密方案[J]. 计算机科学与探索, 2020, 14(10): 1702-1711.

References

[1] Ajtai M. Generating hard instances of lattice problems[C]//Proceedings of the 28th Annual ACM Symposium on the Theory of Computing, Philadelphia, May 22-24, 1996. New York: ACM, 1996: 99-108.
[2] Ajtai M, Dwork C. A public-key cryptosystem with worst-case/average-case equivalence[C]//Proceedings of the 29th Annual ACM Symposium on the Theory of Computing, El Paso, May 4-6, 1997. New York: ACM, 1997: 284-293.
[3] Regev O. On lattices, learning with errors, random linear codes, and cryptography[C]//Proceedings of the 37th Annual ACM Symposium on Theory of Computing, Baltimore, May 22-24, 2005. New York: ACM, 2005: 84-93.
[4] Gentry C, Peikert C, Vaikuntanathan V. Trapdoors for hard lattices and new cryptographic constructions[C]//Proceedings of the 40th Annual ACM Symposium on Theory of Com-puting, Victoria, May 17-20, 2008. New York: ACM, 2008: 197-206.
[5] Kawachi A, Tanaka K, Xagawa K. Multi-bit cryptosystems based on lattice problems[C]//LNCS 4450: Proceedings of the 10th International Conference on Practice and Theory in Public-Key Cryptography, Beijing, Apr 16-20, 2007. Berlin, Heidelberg: Springer, 2007: 315-329.
[6] Peikert C, Vaikuntanathan V, Waters B. A framework for efficient and composable oblivious transfer[C]//LNCS 5157: Proceedings of the 28th Annual International Cryptology Conference on Advances in Cryptology, Santa Barbara, Aug 12-17, 2008. Berlin, Heidelberg: Springer, 2008: 554-571.
[7] Li Z P, Ma C G, Zhang L, et al. Two types LWE-based multi-bit lattice-based encryption schemes[J]. Netinfo Security, 2017, 17(10): 1-7.
[8] Li M X, Wang H T. Identity-based matrix encryption scheme based on lattices[J]. Netinfo Security, 2019, 19(1): 34-41. 李明祥, 王洪涛. 基于格的身份基矩阵加密方案[J]. 信息网络安全, 2019, 19(1): 34-41.
[9] Chen H, Han K. Homomorphic lower digits removal and im-proved FHE bootstrapping[C]//LNCS 10820: Proceedings of the 37th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Tel Aviv, Apr 29-May 3, 2018. Berlin, Heidelberg: Springer, 2018: 315-337.
[10] Ducas L, Micciancio D. FHEW: bootstrapping homomorphic encryption in less than a second[C]//LNCS 9056: Procee-dings of the 34th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Sofia, Apr 26-30, 2015. Berlin, Heidelberg: Springer, 2015: 617-640.
[11] Brakerski Z, Gentry C, Vaikuntanathan V. (leveled) fully homomorphic encryption without bootstrapping[J]. ACM Transactions on Computation Theory, 2014, 6(3): 13.
[12] Tu G S, Yang X Y, Zhou T P. Efficient identity-based multi-identity fully homomorphic encryption scheme[J]. Journal of Computer Applications, 2019, 39(3): 750-755. 涂广升, 杨晓元, 周潭平. 高效的身份基多用户全同态加密方案[J]. 计算机应用, 2019, 39(3): 750-755.
[13] Yang X Y, Tu G S, Kong Y J, et al. Multi-identity fully ho-momorphic encryption scheme supporting threshold decryp-tion[J]. Advanced Engineering Sciences, 2019, 51(4): 133-139. 杨晓元, 涂广升, 孔咏骏, 等. 支持门限解密的多身份全同态加密方案[J]. 工程科学与技术, 2019, 51(4): 133-139.
[14] Shen T C, Wang F Q, Chen K F, et al. Efficient leveled (multi) identity-based fully homomorphic encryption sche-mes[J]. IEEE Access, 2019, 7: 79299-79310.
[15] Hiromasa R, Abe M, Okamoto T. Packing messages and optimizing bootstrapping in GSW-FHE[J]. IEICE Transactions on Fundamentals of Electronics, Communications and Com-puter Sciences, 2016(1): 73-82.
[16] Wang B, Wang X Q, Xue R, et al. Matrix FHE and its application in optimizing Bootstrapping[J]. The Computer Journal, 2018, 61(12): 1845-1861.
[17] Cash D, Hofheinz D, Kiltz E, et al. Bonsai trees, or how to delegate a lattice basis[J]. Journal of Cryptology, 2012, 25(4): 601-639.
[18] Brakerski Z. Fully homomorphic encryption without mo-dulus switching from classical GapSVP[C]//LNCS 7417: Proceedings of the 32nd Annual Cryptology Conference Advances in Cryptology，Santa Barbara, Aug 19-23, 2012. Berlin, Heidelberg: Springer, 2012: 868-886.
[19] Micciancio D, Peikert C. Trapdoors for lattices: simpler, tighter, faster, smaller[C]//LNCS 7237: Proceedings of the 31st Annual International Conference on the Theory and Applications of Cryptographic Techniques, Cambridge, Apr 15-19, 2012. Berlin, Heidelberg: Springer, 2012: 700-718.
[20] Gentry C, Sahai A, Waters B. Homomorphic encryption from learning with errors: conceptually-simpler, asymptotically-faster, attribute-based[C]//LNCS 8042: Proceedings of the 33rd Annual Cryptology Conference, Santa Barbara, Aug 18-22, 2013. Berlin, Heidelberg: Springer, 2013: 75-92.