## Cryptology ePrint Archive: Report 2018/1054

Efficient Multi-key FHE with short extended ciphertexts and less public parameters

Tanping Zhou and Ningbo Li and Xiaoyuan Yang and Yiliang Han and Wenchao Liu

Abstract: Multi-Key Full Homomorphic Encryption scheme (MKFHE) can perform arbitrary operation on encrypted data under different public keys (users), and the final ciphertext can be jointly decrypted. Therefore, MKFHE has natural advantages and application value in security multi-party computation (MPC). For BGV-type MKFHE scheme, the amount of ciphertexts and keys are relatively large, and the process of generating evaluation keys is complicated. In this paper, we presented an efficient BGV-type MKFHE scheme with short extended ciphertexts and less public parameters. Firstly, we construct a nested ciphertext extension for BGV and separable ciphertext extension for GSW, which can reduce the amount of the extended ciphertext. Secondly, we construct a hybrid homomorphic multiplication between RBGV ciphertext and RGSW ciphertext, which can reduce the size of input ciphertext and improve the computational efficiency. Finally, the coefficient of user’s secret key is limited to $\{-1,0,1\}$, which can reduce the ciphertext size in key switching process. Comparing to CZW17 proposed in TCC17, analysis shows that the our scheme reduces the amount of ciphertext from $2k$ to $(k + 1)$, and the evaluation key generation materials are reduced from $\sum\nolimits_{l = 0}^L {24\beta _l^2}$ to $\sum\nolimits_{l = 0}^L {4{\beta _B} + 4{\beta _l}}$, and the amount of evaluation keys are reduced from $4{k^2}\beta _l^{}$ to ${(k + 1)^2}{\beta _B}$, where $k$ is the number of users participating in the homomorphic evaluations, $L$ is a bound on the circuit depth, ${\beta _l}$ and ${\beta _B}$ relatively denotes the bit length of modulus $q_l$ and the noise bound $B$. The reduction in the amount of data may lead to improvement in computational efficiency. Further more, the separable ciphertext extension for GSW can also be used in GSW-type MKFHE scheme such as CM15 to reduce the amount of ciphertext and improve the efficiency of homomorphic operations.

Category / Keywords: public-key cryptography / Multi-key FHE, BGV scheme, ciphertext extension, public parameter, evaluation key, hybrid homomorphic multiplication.