Multikey homomorphic encryption(MKHE)supports arbitrary homomorphic evaluation on the ciphertext of different users and thus can be applied to scenarios involving multiusers(e.g.,cloud computing and artificial intelligence)to protect user privacy.CDKS19 is the current most efficient MKHE scheme,and its relinearization process consumes most of the time of homomorphic evaluation.In this study,an optimized relinearization algorithm of CDKS19 is proposed.This algorithm reorganizes the evaluation key during the key generation process,decreases the complexity of relinearization,and reduces the error growth rate during homomorphic evaluation.First,we reduce the scale of the evaluation key by increasing its modulus instead of using a gadget vector to decompose the user's public key and extend the ciphertext of homomorphic multiplication.Second,we use rescaling technology to optimize the relinearization algorithm;thus,the error bound of the ciphertext is reduced,and the homomorphic operation efficiency is improved.Lastly,the average-case error estimation on the variances of polynomial coefficients and the upper bound of the canonical embedding map are provided.Results show that our scheme reduces the scale of the evaluation key,the error variance,and the computational cost of the relinearization process.Our scheme can effectively perform the homomorphic multiplication of ciphertexts.

Xiaoyuan Yang;Shangwen Zheng;Tanping Zhou;Yao Liu;Xiaoliang Che

College of Cryptographic Engineering,Engineering University of PAP,Xi'an 710086,China

清华大学学报自然科学版（英文版）

[1]Xiaoyuan Yang;Shangwen Zheng;Tanping Zhou;Yao Liu;Xiaoliang Che-.Optimized Relinearization Algorithm of the Multikey Homomorphic Encryption Scheme)[J].清华大学学报自然科学版（英文版）,2022(03):642-652

Relinearization,Multikey,MKHE,multiusers,CDKS19,relinearization,reorganizes,rescaling

Optimized,Algorithm,Homomorphic,Encryption,Scheme,homomorphic,encryption,supports,arbitrary,evaluation,different,thus,applied,scenarios,involving,cloud,computing,artificial,intelligence,protect,privacy,current,most,scheme,its,process,consumes,In,this,study,optimized,algorithm,proposed,This,during,generation,decreases,complexity,reduces,error,growth,rate,First,we,scale,by,increasing,modulus,instead,using,gadget,vector,decompose,public,extend,multiplication,Second,technology,bound,reduced,operation,efficiency,improved,Lastly,average,case,estimation,variances,polynomial,coefficients,upper,canonical,embedding,map,are,provided,Results,show,that,our,computational,cost,Our,effectively,perform,ciphertexts

0.444626