Homomorphic Encryption (HE) is a cryptosytem that allows us to perform an arbitrary computation on encrypted data. The standard HE, however, has a disadvantage in that the authority is concentrated in the secret key owner since computations can only be performed on ciphertexts encrypted under the same secret key. To resolve this issue, research is underway on Multi-Key Homomorphic Encryption (MKHE), which is a variant of HE supporting computations on ciphertexts possibly encrypted under different keys. Despite its ability to provide privacy for multiple parties, existing MKHE schemes suffer from poor performance due to the cost of multiplication which grows at least quadratically with the number of keys involved.

The Tate pairing computation consists of two parts: Miller step and final exponentiation step. In this paper, we investigate the structure of the final exponentiation step. Consider an orderrsubgroup of an elliptic curve defined over Fqwith embedding degreek. The final exponentiation in the Tate pairing is an exponentiation of an element in Fqkby (qk-1)/r. The hardest part of this computation is to raise to the power λ:=Φk(q)/r, where Φk(·) denotes thekth cyclotomic polynomial. Write it as λ = λ0+λ1q+⋯+λφ(k)-1qφ(k)-1in theq-ary representation. The final exponentiation cost mostly depends on κ(λ), the size of the maximum of |λi|. In many parameterized pairing-friendly curves, the value κ is about (1-1/ρφ(k))log2qwhere ρ = log2q/log2r, while random curves will have κ ≈ log2q. We investigate how this small κ is obtained for parameterized pairing-friendly elliptic curves, and show that (1-1/ρφ(k))log2qis the lower bound for all known construction methods of parameterized pairing-friendly curves. In the second part of our paper, we propose a method to obtain a modified Tate pairing with small κ for any pairing-friendly elliptic curves including those not belonging to parameterized families. More precisely, our method finds an integermusing the lattice basis reduction such that κ(mλ)=(1-1/ρφ(k))log2q. Using this modified Tate pairing, we can reduce the number of squarings in the final exponentiation by a factor of (1-1/ρφ(k)) from the usual Tate pairing. We apply our method to several known pairing-friendly curves to verify the expected speedup.