You are looking at a specific version 20181102:011033 of this paper. See the latest version.

Paper 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.

Metadata
Available format(s)
PDF
Category
Public-key cryptography
Publication info
Preprint. MINOR revision.
Keywords
Multi-key FHEBGV schemeciphertext extensionpublic parameterevaluation keyhybrid homomorphic multiplication.
Contact author(s)
850301775 @ qq com
History
2019-06-25: revised
2018-11-02: received
See all versions
Short URL
https://ia.cr/2018/1054
License
Creative Commons Attribution
CC BY
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.