Genes have great significance for the prevention and treatment of some diseases. A vital consideration is the need to find a way to locate pathogenic genes by analyzing the genetic data obtained from different medical institutions while protecting the privacy of patients’ genetic data. In this paper, we present a secure scheme for locating disease-causing genes based on Multi-Key Homomorphic Encryption (MKHE), which reduces the risk of leaking genetic data. First, we combine MKHE with a frequency-based pathogenic gene location function. The medical institutions use MKHE to encrypt their genetic data. The cloud then homomorphically evaluates specific gene-locating circuits on the encrypted genetic data. Second, whereas most location circuits are designed only for locating monogenic diseases, we propose two location circuits (TH-intersection and Top-q) that can locate the disease-causing genes of polygenic diseases. Third, we construct a directed decryption protocol in which the users involved in the homomorphic evaluation can appoint a target user who can obtain the final decryption result. Our experimental results show that compared to the JWB+17 scheme published in the journal Science, our scheme can be used to diagnose polygenic diseases, and the participants only need to upload their encrypted genetic data once, which reduces the communication traffic by a few hundred-fold.

The Multi-Key Fully Homomorphic Encryption (MKFHE) based on the NTRU cryptosystem is an important alternative to the post-quantum cryptography due to its simple scheme form, high efficiency, and fewer ciphertexts and keys. In 2012, López-Alt et al. proposed the first NTRU-type MKFHE scheme, the LTV12 scheme, using the key-switching and modulus-reduction techniques, whose security relies on two assumptions: the Ring Learning With Error (RLWE) assumption and the Decisional Small Polynomial Ratio (DSPR) assumption. However, the LTV12 and subsequent NTRU-type schemes are restricted to the family of power-of-2 cyclotomic rings, which may affect the security in the case of subfield attacks. Moreover, the key-switching technique of the LTV12 scheme requires a circular application of evaluation keys, which causes rapid growth of the error and thus affects the circuit depth. In this paper, an NTRU-type MKFHE scheme over prime cyclotomic rings without key-switching is proposed, which has the potential to resist the subfield attack and decrease the error exponentially during the homomorphic evaluating process. First, based on the RLWE and DSPR assumptions over the prime cyclotomic rings, a detailed analysis of the factors affecting the error during the homomorphic evaluations in the LTV12 scheme is provided. Next, a Low Bit Discarded & Dimension Expansion of Ciphertexts (LBD&DEC) technique is proposed, and the inherent homomorphic multiplication decryption structure of the NTRU is proposed, which can eliminate the key-switching operation in the LTV12 scheme. Finally, a leveled NTRU-type MKFHE scheme is developed using the LBD&DEC and modulus-reduction techniques. The analysis shows that the proposed scheme compared to the LTV12 scheme can decrease the magnitude of the error exponentially and minimize the dimension of ciphertexts.