{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,20]],"date-time":"2026-01-20T10:05:14Z","timestamp":1768903514922,"version":"3.49.0"},"reference-count":29,"publisher":"MDPI AG","issue":"9","license":[{"start":{"date-parts":[[2022,9,18]],"date-time":"2022-09-18T00:00:00Z","timestamp":1663459200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"funder":[{"DOI":"10.13039\/501100001348","name":"A*STAR under its RIE2020 Advanced Manufacturing and Engineering (AME) Programmatic Programme","doi-asserted-by":"publisher","award":["A19E3b0099"],"award-info":[{"award-number":["A19E3b0099"]}],"id":[{"id":"10.13039\/501100001348","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Algorithms"],"abstract":"<jats:p>Machine learning classification algorithms, such as decision trees and random forests, are commonly used in many applications. Clients who want to classify their data send them to a server that performs their inference using a trained model. The client must trust the server and provide the data in plaintext. Moreover, if the classification is done at a third-party cloud service, the model owner also needs to trust the cloud service. In this paper, we propose a protocol for privately evaluating decision trees. The protocol uses a novel private comparison function based on fully homomorphic encryption over the torus (TFHE) scheme and a programmable bootstrapping technique. Our comparison function for 32-bit and 64-bit integers is 26% faster than the naive TFHE implementation. The protocol is designed to be non-interactive and is less complex than the existing interactive protocols. Our experiment results show that our technique scales linearly with the depth of the decision tree and efficiently evaluates large decision trees on real datasets. Compared with the state of the art, ours is the only non-interactive protocol to evaluate a decision tree with high precision on encrypted parameters. The final download bandwidth is also 50% lower than the state of the art.<\/jats:p>","DOI":"10.3390\/a15090333","type":"journal-article","created":{"date-parts":[[2022,9,18]],"date-time":"2022-09-18T22:12:43Z","timestamp":1663539163000},"page":"333","update-policy":"https:\/\/doi.org\/10.3390\/mdpi_crossmark_policy","source":"Crossref","is-referenced-by-count":5,"title":["Non-Interactive Decision Trees and Applications with Multi-Bit TFHE"],"prefix":"10.3390","volume":"15","author":[{"ORCID":"https:\/\/orcid.org\/0000-0001-8998-6598","authenticated-orcid":false,"given":"Jestine","family":"Paul","sequence":"first","affiliation":[{"name":"Institute for Infocomm Research, A*STAR, Connexis North, Singapore 138632, Singapore"},{"name":"Department of Electrical and Computer Engineering, National University of Singapore, Singapore 117583, Singapore"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-8629-9052","authenticated-orcid":false,"given":"Benjamin Hong Meng","family":"Tan","sequence":"additional","affiliation":[{"name":"Institute for Infocomm Research, A*STAR, Connexis North, Singapore 138632, Singapore"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-9000-1813","authenticated-orcid":false,"given":"Bharadwaj","family":"Veeravalli","sequence":"additional","affiliation":[{"name":"Department of Electrical and Computer Engineering, National University of Singapore, Singapore 117583, Singapore"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-5652-3455","authenticated-orcid":false,"given":"Khin Mi Mi","family":"Aung","sequence":"additional","affiliation":[{"name":"Institute for Infocomm Research, A*STAR, Connexis North, Singapore 138632, Singapore"}]}],"member":"1968","published-online":{"date-parts":[[2022,9,18]]},"reference":[{"key":"ref_1","doi-asserted-by":"crossref","unstructured":"Fredrikson, M., Jha, S., and Ristenpart, T. (2015, January 12\u201316). Model inversion attacks that exploit confidence information and basic countermeasures. Proceedings of the 22nd ACM SIGSAC Conference on Computer and Communications Security, Denver, CO, USA.","DOI":"10.1145\/2810103.2813677"},{"key":"ref_2","unstructured":"Gentry, C. (2, January 31). Fully homomorphic encryption using ideal lattices. Proceedings of the Forty-First Annual ACM Symposium on Theory of Computing, Bethesda, MD, USA."},{"key":"ref_3","doi-asserted-by":"crossref","first-page":"34","DOI":"10.1007\/s00145-019-09319-x","article-title":"TFHE: Fast fully homomorphic encryption over the torus","volume":"33","author":"Chillotti","year":"2020","journal-title":"J. Cryptol."},{"key":"ref_4","doi-asserted-by":"crossref","unstructured":"Chillotti, I., Joye, M., and Paillier, P. (2021, January 8\u20139). Programmable bootstrapping enables efficient homomorphic inference of deep neural networks. Proceedings of the International Symposium on Cyber Security Cryptography and Machine Learning, Be\u2019er Sheva, Israel.","DOI":"10.1007\/978-3-030-78086-9_1"},{"key":"ref_5","unstructured":"Dua, D., and Graff, C. (2017). UCI Machine Learning Repository, University of California."},{"key":"ref_6","doi-asserted-by":"crossref","unstructured":"Lu, W.J., Zhou, J.J., and Sakuma, J. (2018, January 4\u20138). Non-interactive and output expressive private comparison from homomorphic encryption. Proceedings of the 2018 on Asia Conference on Computer and Communications Security, Incheon, Korea.","DOI":"10.1145\/3196494.3196503"},{"key":"ref_7","doi-asserted-by":"crossref","first-page":"246","DOI":"10.2478\/popets-2021-0046","article-title":"Faster homomorphic comparison operations for BGV and BFV","volume":"2021","author":"Iliashenko","year":"2021","journal-title":"Proc. Priv. Enhancing Technol."},{"key":"ref_8","doi-asserted-by":"crossref","unstructured":"Agrawal, R., and Srikant, R. (2000, January 16\u201318). Privacy-preserving data mining. Proceedings of the 2000 ACM SIGMOD International Conference on Management of Data, Dallas, TX, USA.","DOI":"10.1145\/342009.335438"},{"key":"ref_9","unstructured":"Du, W., and Zhan, Z. (2002). Building Decision Tree Classifier on Private Data, Syracuse University."},{"key":"ref_10","doi-asserted-by":"crossref","unstructured":"Yao, A.C. (1982, January 3\u20135). Protocols for secure computations. Proceedings of the 23rd Annual Symposium on Foundations of Computer Science (SFCS 1982), Chicago, IL, USA.","DOI":"10.1109\/SFCS.1982.38"},{"key":"ref_11","doi-asserted-by":"crossref","unstructured":"Brickell, J., Porter, D.E., Shmatikov, V., and Witchel, E. (2007, January 28\u201331). Privacy-preserving remote diagnostics. Proceedings of the 14th ACM Conference on Computer and Communications Security, Alexandria, VA, USA.","DOI":"10.1145\/1315245.1315307"},{"key":"ref_12","doi-asserted-by":"crossref","unstructured":"Barni, M., Failla, P., Kolesnikov, V., Lazzeretti, R., Sadeghi, A.R., and Schneider, T. (2009, January 21\u201323). Secure evaluation of private linear branching programs with medical applications. Proceedings of the European Symposium on Research in Computer Security, Saint-Malo, France.","DOI":"10.1007\/978-3-642-04444-1_26"},{"key":"ref_13","doi-asserted-by":"crossref","unstructured":"Agrawal, R., Kiernan, J., Srikant, R., and Xu, Y. (2004, January 13\u201318). Order preserving encryption for numeric data. Proceedings of the 2004 ACM SIGMOD International Conference on Management of Data, Paris, France.","DOI":"10.1145\/1007568.1007632"},{"key":"ref_14","doi-asserted-by":"crossref","unstructured":"Boneh, D., Lewi, K., Raykova, M., Sahai, A., Zhandry, M., and Zimmerman, J. (2015, January 26\u201330). Semantically secure order-revealing encryption: Multi-input functional encryption without obfuscation. Proceedings of the Annual International Conference on the Theory and Applications of Cryptographic Techniques, Sofia, Bulgaria.","DOI":"10.1007\/978-3-662-46803-6_19"},{"key":"ref_15","doi-asserted-by":"crossref","unstructured":"Naveed, M., Kamara, S., and Wright, C.V. (2015, January 12\u201316). Inference attacks on property-preserving encrypted databases. Proceedings of the 22nd ACM SIGSAC Conference on Computer and Communications Security, Denver, CO, USA.","DOI":"10.1145\/2810103.2813651"},{"key":"ref_16","unstructured":"Damg\u00e5rd, I., Geisler, M., and Kr\u00f8igaard, M. (2007, January 2\u20134). Efficient and secure comparison for on-line auctions. Proceedings of the Australasian conference on Information Security and Privacy, Townsville, Australia."},{"key":"ref_17","first-page":"321","article-title":"A correction to \u201cEfficient and Secure Comparison for On-Line Auctions\u201d","volume":"2008","author":"Geisler","year":"2008","journal-title":"Cryptol. ePrint Arch."},{"key":"ref_18","doi-asserted-by":"crossref","unstructured":"Veugen, T. (2012, January 2\u20135). Improving the DGK comparison protocol. Proceedings of the 2012 IEEE International Workshop on Information Forensics and Security (WIFS), Tenerife, Spain.","DOI":"10.1109\/WIFS.2012.6412624"},{"key":"ref_19","first-page":"331","article-title":"Machine learning classification over encrypted data","volume":"2014","author":"Bost","year":"2014","journal-title":"Cryptol. ePrint Arch."},{"key":"ref_20","doi-asserted-by":"crossref","first-page":"1170","DOI":"10.1145\/7902.7903","article-title":"Data parallel algorithms","volume":"29","author":"Hillis","year":"1986","journal-title":"Commun. ACM"},{"key":"ref_21","doi-asserted-by":"crossref","unstructured":"Tai, R.K., Ma, J.P., Zhao, Y., and Chow, S.S. (2017, January 11\u201315). Privacy-preserving decision trees evaluation via linear functions. Proceedings of the European Symposium on Research in Computer Security, Oslo, Norway.","DOI":"10.1007\/978-3-319-66399-9_27"},{"key":"ref_22","doi-asserted-by":"crossref","first-page":"335","DOI":"10.1515\/popets-2016-0043","article-title":"Privately Evaluating Decision Trees and Random Forests","volume":"4","author":"Wu","year":"2016","journal-title":"Proc. Priv. Enhancing Technol."},{"key":"ref_23","unstructured":"Chillotti, I., Joye, M., Ligier, D., Orfila, J.B., and Tap, S. (2020, January 15). CONCRETE: Concrete operates on ciphertexts rapidly by extending TfhE. Proceedings of the WAHC 2020\u20138th Workshop on Encrypted Computing & Applied Homomorphic Cryptography, Virtual Event."},{"key":"ref_24","doi-asserted-by":"crossref","first-page":"169","DOI":"10.1515\/jmc-2015-0016","article-title":"On the concrete hardness of learning with errors","volume":"9","author":"Albrecht","year":"2015","journal-title":"J. Math. Cryptol."},{"key":"ref_25","first-page":"1481","article-title":"Design and implementation of HElib: A homomorphic encryption library","volume":"2020","author":"Halevi","year":"2020","journal-title":"Cryptol. ePrint Arch."},{"key":"ref_26","doi-asserted-by":"crossref","unstructured":"Ishimaki, Y., and Yamana, H. (2018, January 9\u201312). Non-interactive and fully output expressive private comparison. Proceedings of the International Conference on Cryptology in India, New Delhi, India.","DOI":"10.1007\/978-3-030-05378-9_19"},{"key":"ref_27","first-page":"2825","article-title":"Scikit-learn: Machine Learning in Python","volume":"12","author":"Pedregosa","year":"2011","journal-title":"J. Mach. Learn. Res."},{"key":"ref_28","doi-asserted-by":"crossref","unstructured":"Chen, H., Dai, W., Kim, M., and Song, Y. (2019, January 11\u201315). Efficient multi-key homomorphic encryption with packed ciphertexts with application to oblivious neural network inference. Proceedings of the 2019 ACM SIGSAC Conference on Computer and Communications Security, London, UK.","DOI":"10.1145\/3319535.3363207"},{"key":"ref_29","doi-asserted-by":"crossref","unstructured":"Chen, H., Chillotti, I., and Song, Y. (2019, January 8\u201312). Multi-key homomorphic encryption from TFHE. Proceedings of the International Conference on the Theory and Application of Cryptology and Information Security, Kobe, Japan.","DOI":"10.1007\/978-3-030-34621-8_16"}],"container-title":["Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.mdpi.com\/1999-4893\/15\/9\/333\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,10,11]],"date-time":"2025-10-11T00:33:55Z","timestamp":1760142835000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.mdpi.com\/1999-4893\/15\/9\/333"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,9,18]]},"references-count":29,"journal-issue":{"issue":"9","published-online":{"date-parts":[[2022,9]]}},"alternative-id":["a15090333"],"URL":"https:\/\/doi.org\/10.3390\/a15090333","relation":{},"ISSN":["1999-4893"],"issn-type":[{"value":"1999-4893","type":"electronic"}],"subject":[],"published":{"date-parts":[[2022,9,18]]}}}