| 引用本文： |
-
刘钦菊,路献辉,王鲲鹏,毕蕾.紧致编码下可编程自举方案[J].信息安全学报,已采用 [点击复制]
- LIU Qinju,LU Xianhui,WANG Kunpeng,BI Lei.Programmable Bootstrapping via Compact Isomorphic Mapping[J].Journal of Cyber Security,Accept [点击复制]
|
|
| 摘要: |
| 全同态加密 (Fully Homomorphic Encryption，FHE) 能够对加密的数据进行操作，是数据隐私保护领域强有力的技术手段之一。自举 (Bootstrapping) 是目前实现全同态加密的唯一技术途径，也是全同态加密计算效率的主要瓶颈。目前，在降低噪声的同时，利用自举过程执行有效的函数计算是提高自举效率的一个很有前景的方向，即可编程自举 (Programmable Bootstrapping，PBS)。同态映射的构造是实现可编程自举方案的核心。在现有的可编程自举方案中，基于其同构映射设计的编码方式是稀疏的，导致自举密钥的尺寸较大。此外，同构映射与模数存在耦合关系，因此在自举过程中只能计算负循环函数。本文构造了一种新的同构映射，并基于此提出了一种紧致的编码方式，从而解开了现有方案与模数之间的耦合关系。在该编码方式的基础上，将函数查找表嵌入到自举算法中，设计了同态的功能性相等测试算法，即在加密的情况下判断元素是否相等并执行函数计算，从而完成了可编程自举方案的设计与分析。与其他可编程自举方案相比，一方面，本文给出的可编程自举方案可计算的函数不再局限于负循环函数而是任意可计算函数；另一方面，对于高精度的密文，本文给出的可编程自举方案所需的自举密钥尺寸较小。 |
| 关键词: 全同态加密 紧致编码 功能性相等测试 可编程自举 |
| DOI： |
| 投稿时间：2021-10-09修订日期：2021-12-08 |
| 基金项目:(Y610112103)资助。 |
|
| Programmable Bootstrapping via Compact Isomorphic Mapping |
|
LIU Qinju, LU Xianhui, WANG Kunpeng, BI Lei
|
| (State Key Laboratory of Information Security,Institute of Information Engineering,CAS) |
| Abstract: |
| Fully homomorphic encryption (FHE) can perform operations on encrypted data, which has become one of the powerful tools in the field of data privacy protection. As most of us know, bootstrapping is the only way to realize fully homomorphic encryption at present, and it is also the main bottleneck in the computation efficiency of fully homomorphic encryption. Currently, a promising direction towards improving concrete efficiency is to exploit the bootstrapping process to perform useful computation while reducing the noise at the same time, which is called programmable bootstrapping (PBS), also known as functional bootstrapping. The construction of isomorphic mapping is the core of the programmable bootstrapping scheme. In the existing programmable bootstrapping scheme, the coding method based on its isomorphic mapping design is sparse, resulting in a larger size of the bootstrapping key. In addition, the isomorphic mapping has a coupling relationship with the modulus, so that only negacyclic functions can be evaluated during the bootstrapping process. In this paper, a new isomorphic mapping is constructed, and a compact coding method is proposed based on this isomorphic mapping, thereby unraveling the coupling relationship between the existing scheme and the modulus. On the basis of the coding method, the function lookup table is embedded in the bootstrapping scheme, the homomorphic functional equality test algorithm is designed, that is, to judge whether the elements are equal under encryption and perform function evaluations, and the design and analysis of the programmable bootstrapping scheme are completed. Compared with other programmable bootstrapping schemes, on the one hand, the computable function of the programmable bootstrapping scheme given in this paper is no longer limited to the negacyclic function, but arbitrary computable functions; on the other hand, for the high-precision ciphertext, the size of the bootstrapping key required by the programmable bootstrapping scheme given in this paper is relatively small. |
| Key words: Fully homomorphic encryption compact isomorphic mapping functional equality test programmable bootstrapping |
