Key Reduction in Multi-Key and Threshold Multi-Key Homomorphic Encryptions by Reusing Error

Abstract

As cloud computing and AI as a Service are provided, it is increasingly necessary to deal with privacy sensitive data. To deal with the sensitive data, there are two cases of outsourcing process: i) many clients participate dynamically ii) many clients are pre-determined. The solutions for protecting sensitive data in both cases are the multi-key homomorphic encryption (MKHE) scheme and the threshold multi-key homomorphic encryption (TMKHE) scheme. However, these schemes may be difficult for clients with limited resources to perform MKHE and TMKHE. In addition, due to the large size of the evaluation keys, in particular multiplication and rotation keys, the communication between the clients and server that provide outsourcing service increases. Also, the size of the evaluation keys that the server must hold is tremendous, in particular, for the multiplication and rotation keys, which are essential for bootstrapping operation. In this paper, we propose a variant of MKHE and TMKHE with reduced evaluation keys. To reduce the size of the evaluation keys, we propose a variant of ring learning with errors (RLWE), called RLWE reusing errors (ReRLWE). ReRLWE generates other components by reusing the error that is used when generating an RLWE sample. We prove that RLWE can be reduced to ReRLWE and propose modified evaluation keys under the ReRLWE assumption, which are the modified multiplication and rotation keys. For MKHE, multiplication and rotation keys are reduced by 66% and 25%, respectively. For TMKHE, a multiplication and rotation keys are reduced by 50% and 25%, respectively.

Keywords

• Homomorphic encryption (HE)
• multi-key homomorphic encryption (MKHE)
• ring learning with error (RLWE)
• threshold multi-key homomorphic encryption (TMKHE)