I'm trying to optimize the decryption process for Paillier Homomorphic Encryption (PHE) using the Chinese Remainder Theorem (CRT). However, I want to check if there's a different way of applying CRT to PHE apart from the traditional approach and still get the same result or a faster result since there's a simpler variant for the PHE as stated here in Wikipedia.
Recall that, 𝑚=𝐿(𝑐^𝜆 𝑚𝑜𝑑 𝑛^2 ). 𝜇 𝑚𝑜𝑑 𝑛, 𝑐= 𝑔^𝑚.𝑟^𝑛 𝑚𝑜𝑑 𝑛^2, 𝜆=𝜑(𝑛)=(𝑝−1)(𝑞−1) 𝜇=[(𝐿(𝑔^𝜆 𝑚𝑜𝑑𝑛^2 ))]^(−1)𝑚𝑜𝑑 𝑛, 𝜇=𝜑(𝑛)^(−1) 𝑚𝑜𝑑 𝑛 = [(𝑝−1)(𝑞−1)]^(−1) 𝑚𝑜𝑑 𝑛 𝑚=𝐿(𝑐^𝜆 𝑚𝑜𝑑 𝑛^2 ). 𝜇 𝑚𝑜𝑑 𝑛 𝑚=𝐿(𝑐^((𝑝−1)(𝑞−1)) 𝑚𝑜𝑑 𝑛^2 ). [[(𝑝−1)(𝑞−1)]^(−1) 𝑚𝑜𝑑 𝑛]𝑚𝑜𝑑 𝑛 𝑚𝑝= 𝐿𝑝 [(𝑐^((𝑝−1)) 𝑚𝑜𝑑 𝑝^2 ).(𝑝−1)^(−1) 𝑚𝑜𝑑 𝑝]𝑚𝑜𝑑 𝑝 𝑚𝑞= 𝐿𝑞 [(𝑐^((𝑞−1)) 𝑚𝑜𝑑 𝑞^2 ).(𝑞−1)^(−1) 𝑚𝑜𝑑 𝑞]𝑚𝑜𝑑 𝑞 Let 𝑘𝑝= (𝑝−1)^(−1) 𝑚𝑜𝑑 𝑝 and 𝑘𝑞= (𝑞−1)^(−1) 𝑚𝑜𝑑 𝑞 𝑚𝑝= 𝐿𝑝 [(𝑐^((𝑝−1)) 𝑚𝑜𝑑 𝑝^2 )] 𝑘𝑝 𝑚𝑜𝑑 𝑝 𝑚𝑞= 𝐿𝑞 [(𝑐^((𝑞−1)) 𝑚𝑜𝑑 𝑞^2 )] 𝑘𝑞 𝑚𝑜𝑑 𝑞 𝑚 = CRT(𝑚𝑝, 𝑚𝑞) 𝑚𝑜𝑑 𝑝𝑞 𝑚 = 𝐿𝑝 [(𝑐^(𝑝−1) 𝑚𝑜𝑑 𝑝^2 ) 𝑘𝑝 𝑚𝑜𝑑 𝑝] + 𝐿𝑞 [(𝑐^(𝑞−1) 𝑚𝑜𝑑 𝑞^2 ) 𝑘𝑞 𝑚𝑜𝑑 𝑞] 𝑚 = 𝐿(𝑐^𝜆 𝑚𝑜𝑑 𝑛^2 ). 𝜇 𝑚𝑜𝑑 𝑛
Implementing the above steps in python gave me an inconsistent decryption result.
Is this proof correct, and if not, can anyone please explain as to why it's not correct and how to make it correct?