Abstract: As the development of the emerging areas of network services such as big data and cloud computing, data element has played an increasingly critical role in the fields of intelligent e-health and scientific research. Gene sequencing technology is widely used in many fields to determine the cause and category of a patient’s disease, by processing the patient’s gene sequence. Due to constrained storage and computing resources, local users often need to rent resource-abundant cloud servers, unfortunately always working in untrusted environments, to fulfill the computationally-intensive task of large-scale gene sequencing function evaluation. To guarantee users’ data privacy and the correctness of computing results, most of the state-of-the-art methods exploit the techniques of public key fully homomorphic encryption and secure multiparty computation to achieve data privacy, and the technique of Yao’s garbled circuit or bilinear paring to achieve correctness verification. Owing to the fact that huge computational overhead and communication overhead are required in the cryptographic primitives mentioned above, they are inappropriate for efficiency needs of the resource-constrained local users in gene sequence analysis. To address this challenging issue, in this paper, a lightweight verifiable privacy-preserving gene sequence analysis scheme in the multi-user setting is proposed. Firstly, we design an efficient verifiable multi-key homomorphic data encapsulation mechanism VMK-HDEM. The proposed VMK-HDEM enables batch outsourced function evaluation on L different input instances over the encrypted domain. The usage time complexity of public key encryption on each user S en_i ’s end is O(L), independent of the dataset size n_i , which significantly decreases the computational cost of local users. For verification, the size of the proof is O(deg_F) where deg_F denotes the degree of the function, independent to the size of user’s dataset n_i . Furthermore, based on our constructed cryptographic primitive VMK-HDEM, a lightweight and efficient verifiable privacy-preserving gene sequence analysis scheme LWPPGS is proposed. It not only can preserve the privacy of both users’ gene datasets and the results of gene sequence analysis, but also efficiently verify the correctness of the outcome. Finally, formal security proof and experimental simulation results show the security and practicability of our proposed VMK-HDEM and LWPPGS.