Matrix FHE and Its Application in Optimizing Bootstrapping. (28th August 2018)

• Record Type: Journal Article
• Authors: Wang, Biao; Wang, Xueqing; Xue, Rui; Huang, Xinyi
• Editors: Liu, Joseph
• Is Part Of: Computer journal. Volume 61:Number 12(2018)
• Page Start: 1845
• Page End: 1861
• Publication Date: 2018-08-28
• Subjects: fully homomorphic encryption -- LWE -- matrix -- packing -- bootstrapping; Computers -- Periodicals; 005.1
• DOI: 10.1093/comjnl/bxy088
• Languages: English
• ISSNs: 0010-4620

Abstract

Abstract: We propose a fully homomorphic encryption (FHE) scheme that encrypts matrices. Our scheme supports homomorphic matrix addition, multiplication and Hadamard product. In PKC 2015, Hiromasa et al. constructed the only FHE scheme that encrypts matrices and supports homomorphic matrix addition and multiplication. Compared with their work, the advantages of our scheme are the following: (1) Small ciphertext size : For a plaintext matrix M ∈ {0, 1} r × r, the size of ciphertext matrix is r × ( n + r ), in contrast to ( n + r ) × ( n + r ) ⌈ log q ⌉ in their work. (2) Standard assumption : The security is based on LWE assumption merely, while the security of scheme in their work depends additionally on some special kind of circular security assumption. (3) Supporting homomorphic matrix Hadamard product. We show how to apply the proposed scheme to optimize the bootstrapping procedure of Alperin-Sheriff and Peikert, in a way similar to the work of Hiromasa, Abe and Okamoto. Due to smaller ciphertext matrices, the bootstrapping key of our optimized bootstrapping procedure is smaller than that in the work of Hiromasa, Abe and Okamoto by a factor of ( n / r + 1) ⌈ log q ⌉ .