Accelerated Multi-Key Homomorphic Encryption via Automorphism-Based Circuit Bootstrapping

In FHEW-like bootstrapping, blind rotation is based on the CMUX Gate (The CMux gate is a controlled selector gate that uses a control input to choose between two data inputs for the output), and blind rotation based on automorphism (A bijective transformation that maps a mathematical structure onto itself while preserving its original structure) supports arbitrary key distributions, uses smaller keys, and, compared to the CMUX gate-based blind rotation, has smaller noise growth without considering key distribution. It is noteworthy that the feature of supporting arbitrary key distributions makes it applicable to multi-key homomorphic encryption schemes. Multi-key homomorphic encryption (MKHE) allows computations to be performed on ciphertexts encrypted with different keys, thus expanding the application scenarios of homomorphic encryption to more fields. We improved the automorphism-based blind rotation by using the hybrid product, making it suitable for the multi-key schemes. However, previous multi-key schemes were limited to gate bootstrapping after a single NAND gate computation. Our scheme implements a multi-key circuit bootstrapping method based on automorphism-based blind rotation. In leveled homomorphic encryption mode, the ciphertext needs to go through computational circuits that include leveled operations. Due to the asymmetric nature of the input and output ciphertext types required for the computational circuit (with input being RGSW ciphertext and output being RLWE ciphertext), the circuit bootstrapping input and output ciphertext types are also asymmetric, with its output being low-noise RGSW ciphertext. To the best of our knowledge, this is the first attempt in the literature to implement multi-key circuit bootstrapping.