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. In this paper, we revisit the work of Chen et al. (ACM CCS 2019) on MKHE schemes from CKKS and BFV and significantly improve their performance. Specifically, we redesign the multi-key multiplication algorithm and achieve an asymptotically optimal complexity that grows linearly with the number of keys. Our construction relies on a new notion of gadget decomposition, which we call homomorphic gadget decomposition, where arithmetic operations can be performed over the decomposed vectors with guarantee of its functionality. Finally, we implement our MKHE schemes and demonstrate their benchmarks. For example, our multi-key CKKS multiplication takes only 0.5, 1.0, and 1.9 seconds compared to 1.6, 5.9, and 23.0 seconds of the previous work when 8, 16, and 32 keys are involved, respectively.
Bootstrapping is currently the only known method for constructing fully homomorphic encryptions. In the BFV scheme specifically, bootstrapping aims to reduce the error of a ciphertext while preserving the encrypted plaintext. The existing BFV bootstrapping methods follow the same pipeline, relying on the evaluation of a digit extraction polynomial to annihilate the error located in the least significant digits. However, due to its strong dependence on performance, bootstrapping could only utilize a limited form of plaintext modulus, such as a power of a small prime number. In this paper, we present a novel approach to instantiate BFV bootstrapping, distinct from the previous digit extraction-based method. The core idea of our bootstrapping is to utilize CKKS bootstrapping as a subroutine, so the performance of our method mainly depends on the underlying CKKS bootstrapping rather than the plaintext modulus. We implement our method at a proof-of-concept level to provide concrete benchmark results. When performing the bootstrapping operation for a 51-bits plaintext modulus, our method improves the previous digit extraction-based method by a factor of 37.9 in latency and 29.4 in throughput. Additionally, we achieve viable bootstrapping performance for large plaintext moduli, such as 144-bits and 234-bits, which has never been measured before.
Fully Homomorphic Encryption over the Torus (TFHE) is a homomorphic encryption scheme which supports efficient Boolean operations over encrypted bits. TFHE has a unique feature in that the evaluation of each binary gate is followed by a bootstrapping procedure to refresh the noise of a ciphertext. In particular, this gate bootstrapping involves two algorithms called the blind rotation and key-switching. In this work, we introduce several optimization techniques for the TFHE bootstrapping. We first define a new key distribution, called the block binary distribution, where the secret key can be expressed as a concatenation of several vectors of Hamming weight at most one. We analyze the hardness of (Ring) LWE with a block binary secret and provide candidate parameter sets which are secure against the best-known attacks. Then, we use the block key structure to simplify the inner working of blind rotation and reduce its complexity. We also modify the RLWE key generation and the gadget decomposition method to improve the performance of the key-switching algorithm in terms of complexity and noise growth. Finally, we use the TFHE library to implement our algorithms and demonstrate their benchmarks. Our experimentation shows that the execution time of TFHE bootstrapping is reduced from 10.5ms down to 6.4ms under the same security level, and the size of the bootstrapping key decreases from 109MB to 60MB.
12 May 2023 in IEEE Transactions on Dependable and Secure Computing
Statistical analysis of largescale data is useful as it enables the extraction of a large amount of information, despite its simplicity. Therefore, fusing and analyzing data from different security domains is an attractive and promising approach, unless it jeopardizes the privacy of the data in any security domain. In this study, we proposed the HEaaN-STAT toolkit that can efficiently fuse data from different domains to enable largescale statistical analysis while protecting data privacy. Moreover, we proposed an efficient inverse operation and a table lookup function for Cheon-Kim-Kim-Song (CKKS) encrypted data, as well as a data encoding method for counting encrypted data. Based on this, we proposed a method for generating a contingency table with a large number of cases and k-percentile for largescale data that is hundreds to thousands of times faster than the method proposed by Lu et al. in NDSS' 17. The validity of the proposed toolkit was verified through practical use for business applications using real-world data.