Abstract: The application of full homomorphic encryption in cloud computing effectively meets the user’s demand for “available but invisible” data over the cloud server. Aiming at the problems that the efficiency of multikey fully homomorphic encryption scheme needs to be optimized and the working mode applied to cloud computing is not reasonable, an efficient dynamic multikey fully homomorphic encryption scheme is proposed. On the one hand, the ciphertext extension algorithm of multikey homomorphic encryption scheme is optimized by introducing a pair of public keys and constructing new auxiliary ciphertexts. On the other hand, using a single user and the cloud server to complete the ciphertext extension operation, a new working mode of fully homomorphic encryption applied to cloud computing is proposed. Compared with the scheme of ICPADS meeting in 2023, our scheme reduces the computation overhead from O(n44) to O(n3k22), nk and noise expansion from O(m4γ) to O(mγ), making our scheme with smaller public parameters and more efficient. At the same time, the new working mode not only reduces the user’s high dependence on the server, but also reduces the computing overhead that the user needs to bear, and is more in line with the practical application. The scheme is proved to be INDCPA security and the difficulty can be reduced to the learning with error problem.

Key words: fully homomorphic encryption, multikey, learning with errors, cloud computing, ciphertext extension

摘要： 全同态加密在云计算中的应用有效满足了用户对云端服务器数据“可用不可见”的需求.针对多密钥全同态加密方案计算开销较大、应用于云计算的工作模式不合理等问题，提出了一个高效的动态多密钥全同态加密方案.一方面，通过引入公钥对构造新的辅助密文的方法，对多密钥全同态加密方案密文扩展算法进行优化；另一方面，采用单个用户和服务器交互的方式完成密文扩展操作，提出了一种全同态加密应用于云计算中的新工作模式.与2023年ICPADS会议的方案对比，该方案将计算开销从O(n44)降至O(n3k22)，nk，噪声扩张率从O(m4γ)降低至O(mγ).使得方案的公开参数更小、效率更高.同时，新工作模式不仅减少了用户对服务器的高度依赖，也降低了用户需要承担的计算开销，更加符合实际应用.该方案被证明为INDCPA安全，困难性可归约到误差学习问题.

关键词: 全同态加密, 多密钥, 误差学习问题, 云计算, 密文扩展