{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,1,17]],"date-time":"2024-01-17T00:37:47Z","timestamp":1705451867549},"reference-count":56,"publisher":"MDPI AG","issue":"1","license":[{"start":{"date-parts":[[2024,1,11]],"date-time":"2024-01-11T00:00:00Z","timestamp":1704931200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"funder":[{"DOI":"10.13039\/501100000038","name":"Natural Sciences and Engineering Research Council","doi-asserted-by":"publisher","award":["RGPIN-04127-2022"],"id":[{"id":"10.13039\/501100000038","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Information"],"abstract":"Fully homomorphic encryption (FHE) cryptographic systems enable limitless computations over encrypted data, providing solutions to many of today\u2019s data security problems. While effective FHE platforms can address modern data security concerns in unsecure environments, the extended execution time for these platforms hinders their broader application. This project aims to enhance FHE systems through an efficient parallel framework, specifically building upon the existing torus FHE (TFHE) system chillotti2016faster. The TFHE system was chosen for its superior bootstrapping computations and precise results for countless Boolean gate evaluations, such as AND and XOR. Our first approach was to expand upon the gate operations within the current system, shifting towards algebraic circuits, and using graphics processing units (GPUs) to manage cryptographic operations in parallel. Then, we implemented this GPU-parallel FHE framework into a needed genomic data operation, specifically string search. We utilized popular string distance metrics (hamming distance, edit distance, set maximal matches) to ascertain the disparities between multiple genomic sequences in a secure context with all data and operations occurring under encryption. Our experimental data revealed that our GPU implementation vastly outperforms the former method, providing a 20-fold speedup for any 32-bit Boolean operation and a 14.5-fold increase for multiplications.This paper introduces unique enhancements to existing FHE cryptographic systems using GPUs and additional algorithms to quicken fundamental computations. Looking ahead, the presented framework can be further developed to accommodate more complex, real-world applications.<\/jats:p>","DOI":"10.3390\/info15010040","type":"journal-article","created":{"date-parts":[[2024,1,11]],"date-time":"2024-01-11T17:56:33Z","timestamp":1704995793000},"page":"40","source":"Crossref","is-referenced-by-count":0,"title":["Secure Genomic String Search with Parallel Homomorphic Encryption"],"prefix":"10.3390","volume":"15","author":[{"ORCID":"http:\/\/orcid.org\/0000-0001-6161-8275","authenticated-orcid":false,"given":"Md Momin Al","family":"Aziz","sequence":"first","affiliation":[{"name":"Department of Computer Science, University of Manitoba, Winnipeg , MB R3T 5V6, Canada"}]},{"given":"Md Toufique Morshed","family":"Tamal","sequence":"additional","affiliation":[{"name":"Department of Computer Science, University of Manitoba, Winnipeg , MB R3T 5V6, Canada"}]},{"ORCID":"http:\/\/orcid.org\/0000-0001-8547-9951","authenticated-orcid":false,"given":"Noman","family":"Mohammed","sequence":"additional","affiliation":[{"name":"Department of Computer Science, University of Manitoba, Winnipeg , MB R3T 5V6, Canada"}]}],"member":"1968","published-online":{"date-parts":[[2024,1,11]]},"reference":[{"key":"ref_1","unstructured":"Gentry, C. (31\u20132, January 31). Fully homomorphic encryption using ideal lattices. Proceedings of the STOC, Bethesda, MD, USA."},{"key":"ref_2","doi-asserted-by":"crossref","unstructured":"Pham, A., Dacosta, I., Endignoux, G., Pastoriza, J.R.T., Huguenin, K., and Hubaux, J.P. (2017, January 16\u201318). ORide: A Privacy-Preserving yet Accountable Ride-Hailing Service. Proceedings of the 26th USENIX Security Symposium (USENIX Security 17), Vancouver, BC, Canada.","DOI":"10.1515\/popets-2017-0015"},{"key":"ref_3","doi-asserted-by":"crossref","unstructured":"Kim, M., Song, Y., and Cheon, J.H. (2017). Secure searching of biomarkers through hybrid homomorphic encryption scheme. BMC Med. Genom., 10.","DOI":"10.1186\/s12920-017-0280-3"},{"key":"ref_4","doi-asserted-by":"crossref","unstructured":"Chen, H., Gilad-Bachrach, R., Han, K., Huang, Z., Jalali, A., Laine, K., and Lauter, K. (2018). Logistic regression over encrypted data from fully homomorphic encryption. BMC Med. Genom., 11.","DOI":"10.1186\/s12920-018-0397-z"},{"key":"ref_5","doi-asserted-by":"crossref","unstructured":"Morshed, T., Alhadidi, D., and Mohammed, N. (2018, January 28\u201330). Parallel Linear Regression on Encrypted Data. Proceedings of the 16th Annual Conference on Privacy, Security and Trust (PST), Belfast, Ireland.","DOI":"10.1109\/PST.2018.8514158"},{"key":"ref_6","doi-asserted-by":"crossref","first-page":"6","DOI":"10.1145\/2767007","article-title":"Privacy in the genomic era","volume":"48","author":"Naveed","year":"2015","journal-title":"ACM Comput. Surv. (CSUR)"},{"key":"ref_7","doi-asserted-by":"crossref","first-page":"887","DOI":"10.1093\/bib\/bbx139","article-title":"Privacy-preserving techniques of genomic data: A survey","volume":"20","author":"Aziz","year":"2017","journal-title":"Briefings Bioinform."},{"key":"ref_8","unstructured":"23AndMe.com (2020, November 20). Our Health + Ancestry DNA Service\u201423AndMe Canada. Available online: https:\/\/www.23andme.com\/en-ca\/dna-health-ancestry."},{"key":"ref_9","doi-asserted-by":"crossref","unstructured":"Wang, X.S., Huang, Y., Zhao, Y., Tang, H., Wang, X., and Bu, D. (2015, January 12\u201316). Efficient genome-wide, privacy-preserving similar patient query based on private edit distance. Proceedings of the 22Nd ACM SIGSAC Conference on Computer and Communications Security, Denver, CO, USA.","DOI":"10.1145\/2810103.2813725"},{"key":"ref_10","doi-asserted-by":"crossref","unstructured":"Al Aziz, M.M., Alhadidi, D., and Mohammed, N. (2017). Secure approximation of edit distance on genomic data. BMC Med. Genom., 10.","DOI":"10.1186\/s12920-017-0279-9"},{"key":"ref_11","doi-asserted-by":"crossref","unstructured":"Guerrini, C.J., Robinson, J.O., Petersen, D., and McGuire, A.L. (2018). Should police have access to genetic genealogy databases? Capturing the Golden State Killer and other criminals using a controversial new forensic technique. PLoS Biol., 16.","DOI":"10.1371\/journal.pbio.2006906"},{"key":"ref_12","doi-asserted-by":"crossref","unstructured":"Chillotti, I., Gama, N., Georgieva, M., and Izabach\u00e8ne, M. (2016, January 4\u20138). Faster fully homomorphic encryption: Bootstrapping in less than 0.1 seconds. Proceedings of the Advances in Cryptology\u2014ASIACRYPT 2016: 22nd International Conference on the Theory and Application of Cryptology and Information Security, Hanoi, Vietnam.","DOI":"10.1007\/978-3-662-53887-6_1"},{"key":"ref_13","unstructured":"(2023, December 15). CUDA-Accelerated Fully Homomorphic Encryption Library. Available online: https:\/\/github.com\/vernamlab\/cuFHE."},{"key":"ref_14","unstructured":"(2023, December 15). NuFHE, a GPU-Powered Torus FHE Implementation. Available online: https:\/\/github.com\/nucypher\/nufhe."},{"key":"ref_15","unstructured":"(2023, December 15). Cingulata. Available online: https:\/\/github.com\/CEA-LIST\/Cingulata."},{"key":"ref_16","doi-asserted-by":"crossref","unstructured":"Cheon, J.H., Kim, M., and Lauter, K. (2015, January 26\u201330). Homomorphic computation of edit distance. Proceedings of the International Conference on Financial Cryptography and Data Security, San Juan, Puerto Rico.","DOI":"10.1007\/978-3-662-48051-9_15"},{"key":"ref_17","doi-asserted-by":"crossref","unstructured":"Chillotti, I., Gama, N., Georgieva, M., and Izabach\u00e8ne, M. (2017, January 3\u20137). Faster packed homomorphic operations and efficient circuit bootstrapping for TFHE. Proceedings of the International Conference on the Theory and Application of Cryptology and Information Security, Hong Kong, China.","DOI":"10.1007\/978-3-319-70694-8_14"},{"key":"ref_18","doi-asserted-by":"crossref","unstructured":"Morshed, T., Aziz, M., and Mohammed, N. (2020, January 7\u201311). CPU and GPU Accelerated Fully Homomorphic Encryption. Proceedings of the 2020 IEEE International Symposium on Hardware Oriented Security and Trust (HOST), Los Alamitos, CA, USA.","DOI":"10.1109\/HOST45689.2020.9300288"},{"key":"ref_19","doi-asserted-by":"crossref","first-page":"34","DOI":"10.1145\/1568318.1568324","article-title":"On lattices, learning with errors, random linear codes, and cryptography","volume":"56","author":"Regev","year":"2009","journal-title":"J. ACM"},{"key":"ref_20","unstructured":"Cheon, J.H., Han, K., Kim, A., Kim, M., and Song, Y. (May, January 29). Bootstrapping for approximate homomorphic encryption. Proceedings of the Annual International Conference on the Theory and Applications of Cryptographic Techniques, Tel Aviv, Israel."},{"key":"ref_21","first-page":"758","article-title":"Chimera: A Unified Framework for B\/FV, TFHE and HEAAN Fully Homomorphic Encryption and Predictions for Deep Learning","volume":"2018","author":"Boura","year":"2018","journal-title":"IACR Cryptol. ePrint Arch."},{"key":"ref_22","unstructured":"Lomont, C. (2023, December 16). Introduction to Intel Advanced Vector Extensions. Intel White Paper 2011, pp. 1\u201321, Available online: https:\/\/hpc.llnl.gov\/sites\/default\/files\/intelAVXintro.pdf."},{"key":"ref_23","unstructured":"Frigo, M., and Johnson, S.G. (1998, January 12\u201315). FFTW: An adaptive software architecture for the FFT. Proceedings of the 1998 IEEE International Conference on Acoustics, Speech and Signal Processing, ICASSP\u201998 (Cat. No. 98CH36181), Seattle, WA, USA."},{"key":"ref_24","unstructured":"Brakerski, Z., Gentry, C., and Halevi, S. (March, January 26). Packed ciphertexts in LWE-based homomorphic encryption. Proceedings of the International Workshop on Public Key Cryptography, Nara, Japan."},{"key":"ref_25","unstructured":"Ducas, L., and Micciancio, D. (2023, December 20). FHEW: Bootstrapping Homomorphic Encryption in Less Than a Second. Cryptology ePrint Archive, Report 2014\/816, 2014. Available online: https:\/\/eprint.iacr.org\/2014\/816."},{"key":"ref_26","first-page":"144","article-title":"Somewhat Practical Fully Homomorphic Encryption","volume":"2012","author":"Fan","year":"2012","journal-title":"IACR Cryptol. Eprint Arch."},{"key":"ref_27","doi-asserted-by":"crossref","first-page":"867","DOI":"10.1080\/00029890.1993.11990504","article-title":"Parallel Addition","volume":"100","author":"McGeoch","year":"1993","journal-title":"Am. Math. Mon."},{"key":"ref_28","first-page":"293","article-title":"Multiplication of many-digital numbers by automatic computers","volume":"Volume 145","author":"Karatsuba","year":"1962","journal-title":"Proceedings of the Doklady Akademii Nauk"},{"key":"ref_29","unstructured":"Chandra, R., Dagum, L., Kohr, D., Menon, R., Maydan, D., and McDonald, J. (2001). Parallel Programming in OpenMP, Morgan Kaufmann."},{"key":"ref_30","unstructured":"NVIDIA (2023, December 20). GeForce GTX 1080 Graphics Cards from NVIDIA GeForce. Available online: https:\/\/www.nvidia.com\/en-us\/geforce\/products\/10series\/geforce-gtx-1080\/."},{"key":"ref_31","doi-asserted-by":"crossref","first-page":"175","DOI":"10.1093\/nar\/12.1Part1.175","article-title":"Fast optimal alignment","volume":"12","author":"Fickett","year":"1984","journal-title":"Nucleic Acids Res."},{"key":"ref_32","doi-asserted-by":"crossref","unstructured":"Sotiraki, K., Ghosh, E., and Chen, H. (2020). Privately computing set-maximal matches in genomic data. BMC Med. Genom., 13.","DOI":"10.1186\/s12920-020-0718-x"},{"key":"ref_33","doi-asserted-by":"crossref","first-page":"1652","DOI":"10.1093\/bioinformatics\/btw050","article-title":"Efficient Privacy-Preserving String Search and an Application in Genomics","volume":"32","author":"Shimizu","year":"2016","journal-title":"Bioinformatics"},{"key":"ref_34","doi-asserted-by":"crossref","first-page":"1266","DOI":"10.1093\/bioinformatics\/btu014","article-title":"Efficient haplotype matching and storage using the positional Burrows\u2013Wheeler transform (PBWT)","volume":"30","author":"Durbin","year":"2014","journal-title":"Bioinformatics"},{"key":"ref_35","unstructured":"Xie, P., Bilenko, M., Finley, T., Gilad-Bachrach, R., Lauter, K., and Naehrig, M. (2014). Crypto-nets: Neural networks over encrypted data. arXiv."},{"key":"ref_36","unstructured":"Takabi, H., Hesamifard, E., and Ghasemi, M. (2016, January 5\u201310). Privacy preserving multi-party machine learning with homomorphic encryption. Proceedings of the 29th Annual Conference on Neural Information Processing Systems (NIPS), Barcelona, Spain."},{"key":"ref_37","unstructured":"Chillotti, I., Gama, N., Georgieva, M., and Izabach\u00e8ne, M. (2023, December 20). TFHE: Fast Fully Homomorphic Encryption Library. Available online: https:\/\/tfhe.github.io\/tfhe\/."},{"key":"ref_38","doi-asserted-by":"crossref","first-page":"120","DOI":"10.1145\/359340.359342","article-title":"A method for obtaining digital signatures and public-key cryptosystems","volume":"21","author":"Rivest","year":"1978","journal-title":"Commun. ACM"},{"key":"ref_39","unstructured":"Paillier, P. (1999, January 2\u20136). Public-key cryptosystems based on composite degree residuosity classes. Proceedings of the Advances in cryptology, EUROCRYPT, Prague, Czech Republic."},{"key":"ref_40","unstructured":"(2023, December 20). Microsoft SEAL (Release 3.2). 2019. Microsoft Research, Redmond, WA. Available online: https:\/\/github.com\/Microsoft\/SEAL."},{"key":"ref_41","unstructured":"Gentry, C., Sahai, A., and Waters, B. (2013). Advances in Cryptology\u2013CRYPTO 2013, Springer."},{"key":"ref_42","doi-asserted-by":"crossref","first-page":"831","DOI":"10.1137\/120868669","article-title":"Efficient fully homomorphic encryption from (standard) LWE","volume":"43","author":"Brakerski","year":"2014","journal-title":"SIAM J. Comput."},{"key":"ref_43","doi-asserted-by":"crossref","first-page":"13","DOI":"10.1145\/2633600","article-title":"(Leveled) fully homomorphic encryption without bootstrapping","volume":"6","author":"Brakerski","year":"2014","journal-title":"ACM Trans. Comput. Theory"},{"key":"ref_44","doi-asserted-by":"crossref","unstructured":"Cheon, J.H., Kim, A., Kim, M., and Song, Y. (2017, January 3\u20137). Homomorphic encryption for arithmetic of approximate numbers. Proceedings of the International Conference on the Theory and Application of Cryptology and Information Security, Hong Kong, China.","DOI":"10.1007\/978-3-319-70694-8_15"},{"key":"ref_45","doi-asserted-by":"crossref","first-page":"948","DOI":"10.1109\/TC.1972.5009071","article-title":"Some computer organizations and their effectiveness","volume":"100","author":"Flynn","year":"1972","journal-title":"IEEE Trans. Comput."},{"key":"ref_46","doi-asserted-by":"crossref","unstructured":"Halevi, S., and Shoup, V. (2014, January 17\u201321). Algorithms in helib. Proceedings of the Annual Cryptology Conference, Santa Barbara, CA, USA.","DOI":"10.1007\/978-3-662-44371-2_31"},{"key":"ref_47","doi-asserted-by":"crossref","unstructured":"Dor\u00f6z, Y., \u00d6zt\u00fcrk, E., Sava\u015f, E., and Sunar, B. (2015, January 13\u201316). Accelerating LTV based homomorphic encryption in reconfigurable hardware. Proceedings of the International Workshop on Cryptographic Hardware and Embedded Systems, Saint-Malo, France.","DOI":"10.1007\/978-3-662-48324-4_10"},{"key":"ref_48","doi-asserted-by":"crossref","unstructured":"L\u00f3pez-Alt, A., Tromer, E., and Vaikuntanathan, V. (2012, January 20\u201322). On-the-fly multiparty computation on the cloud via multikey fully homomorphic encryption. Proceedings of the forty-fourth annual ACM symposium on Theory of computing, New York, NY, USA.","DOI":"10.1145\/2213977.2214086"},{"key":"ref_49","doi-asserted-by":"crossref","unstructured":"Dai, W., and Sunar, B. (2015, January 3\u20134). cuHE: A homomorphic encryption accelerator library. Proceedings of the International Conference on Cryptography and Information Security in the Balkans, Koper, Slovenia.","DOI":"10.1007\/978-3-319-29172-7_11"},{"key":"ref_50","doi-asserted-by":"crossref","unstructured":"Dai, W., Dor\u00f6z, Y., and Sunar, B. (2015, January 26\u201330). Accelerating swhe based pirs using gpus. Proceedings of the International Conference on Financial Cryptography and Data Security, San Juan, Puerto Rico.","DOI":"10.1007\/978-3-662-48051-9_12"},{"key":"ref_51","doi-asserted-by":"crossref","unstructured":"Lei, X., Guo, R., Zhang, F., Wang, L., Xu, R., and Qu, G. (2019, January 10\u201312). Accelerating Homomorphic Full Adder based on FHEW Using Multicore CPU and GPUs. Proceedings of the 2019 IEEE 21st International Conference on High Performance Computing and Communications; IEEE 17th International Conference on Smart City; IEEE 5th International Conference on Data Science and Systems (HPCC\/SmartCity\/DSS), Zhangjiajie, China.","DOI":"10.1109\/HPCC\/SmartCity\/DSS.2019.00351"},{"key":"ref_52","doi-asserted-by":"crossref","unstructured":"Yang, H., Yao, W., Liu, W., and Wei, B. (2019, January 27\u201329). Efficiency Analysis of TFHE Fully Homomorphic Encryption Software Library Based on GPU. Proceedings of the Workshops of the International Conference on Advanced Information Networking and Applications, Matsue, Japan.","DOI":"10.1007\/978-3-030-15035-8_9"},{"key":"ref_53","doi-asserted-by":"crossref","first-page":"49868","DOI":"10.1109\/ACCESS.2018.2867655","article-title":"Faster bootstrapping with multiple addends","volume":"6","author":"Zhou","year":"2018","journal-title":"IEEE Access"},{"key":"ref_54","unstructured":"(2023, December 20). Zama. Available online: https:\/\/github.com\/zama-ai\/concrete."},{"key":"ref_55","doi-asserted-by":"crossref","unstructured":"Jha, S., Kruger, L., and Shmatikov, V. (2008, January 18\u201321). Towards practical privacy for genomic computation. Proceedings of the 2008 IEEE Symposium on Security and Privacy (sp 2008), Oakland, CA, USA.","DOI":"10.1109\/SP.2008.34"},{"key":"ref_56","unstructured":"NVidia, F. (2009). Nvidia\u2019s Next Generation Cuda Compute Architecture, NVidia."}],"container-title":["Information"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.mdpi.com\/2078-2489\/15\/1\/40\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,1,16]],"date-time":"2024-01-16T05:10:52Z","timestamp":1705381852000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.mdpi.com\/2078-2489\/15\/1\/40"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,1,11]]},"references-count":56,"journal-issue":{"issue":"1","published-online":{"date-parts":[[2024,1]]}},"alternative-id":["info15010040"],"URL":"https:\/\/doi.org\/10.3390\/info15010040","relation":{},"ISSN":["2078-2489"],"issn-type":[{"value":"2078-2489","type":"electronic"}],"subject":[],"published":{"date-parts":[[2024,1,11]]}}}