Luận án phát triển giao thức tính tổng bảo mật hiệu quả - Nghiên cứu của Vũ Duy Hiến

MINISTRY OF EDUCATION VIETNAM ACADEMY OF SCIENCE AND TRAINING AND TECHNOLOGY GRADUATE UNIVERSITY OF SCIENCE AND TECHNOLOGY Vu Duy Hien DEVELOPING EFFICIENT AND SECURE MULTI-PARTY SUM COMPUTATION PROTOCOLS AND THEIR APPLICATIONS DISSERTATION ON INFORMATION SYSTEM Hanoi – 2024 BỘ GIÁO DỤC VIỆN HÀN LÂM KHOA HỌC VÀ ĐÀO TẠO VÀ CÔNG NGHỆ VIỆT NAM HỌC VIỆN KHOA HỌC VÀ CÔNG NGHỆ Vũ Duy Hiến NGHIÊN CỨU PHÁT TRIỂN MỘT SỐ GIAO THỨC TÍNH TỔNG BẢO MẬT HIỆU QUẢ TRONG MÔ HÌNH DỮ LIỆU PHÂN TÁN ĐẦY ĐỦ VÀ ỨNG DỤNG LUẬN ÁN TIẾN SĨ NGÀNH HỆ THỐNG THÔNG TIN Hà Nội – 2024 BỘ GIÁO DỤC VIỆN HÀN LÂM KHOA HỌC VÀ ĐÀO TẠO VÀ CÔNG NGHỆ VIỆT NAM HỌC VIỆN KHOA HỌC VÀ CÔNG NGHỆ Vũ Duy Hiến NGHIÊN CỨU PHÁT TRIỂN MỘT SỐ GIAO THỨC TÍNH TỔNG BẢO MẬT HIỆU QUẢ TRONG MÔ HÌNH DỮ LIỆU PHÂN TÁN ĐẦY ĐỦ VÀ ỨNG DỤNG LUẬN ÁN TIẾN SĨ NGÀNH HỆ THỐNG THÔNG TIN Mã số: 9 48 01 04 Xác nhận của Học viện Người hướng dẫn 1 Người hướng dẫn 2 Khoa học và Công nghệ (Ký, ghi rõ họ tên) (Ký, ghi rõ họ tên) GS. Hồ Tú Bảo PGS. Lương Thế Dũng Hà Nội - 2024 i PLEDGE I promise that the thesis: ”Developing efficient and secure multi-party sum computation protocols and their applications” is my original research work under the guidance of the academic supervisors. All contents of the thesis were written based on papers and articles published in distinguished international conferences and journals published by the reputed publishers.

The source of the references in this thesis are explitly cited. My research results were published jointly with other authors and were agreed upon by the co-authors when included in the thesis. New results and discussions presented in the thesis are perfectly honest and they have not yet published by any other authors beyond my publications. This thesis has been finished during the time I work as a PhD student at Graduate University of Science and Technology, Vietnam Academy of Science and Technology.

Hanoi, 2024 PhD student Vu Duy Hien ii ACKNOWLEDGEMENTS Scientific research is an interesting journey where the thesis is one of the first results that researchers have reached. On that journey, I have met many kind people who have supported for me to finish this thesis. First of all, I would like to thank my great supervisors Prof. Ho Tu Bao and Assoc.

Luong The Dung who have provided valuable advice to me. Without their support and guidance, I would not able to complete my thesis. I have learned a lot of things from my supervisors. I am thankful to Graduate University of Science and Technology, colleagues at Banking Academy of Vietnam, friends, and collaborators who always encour- age me along my research journey.

I also thank the CAMEL cafe (No.104/1 Viet Hung street, Long Bien dis- trict, Ha Noi) where my publications and thesis had been born in. Finally, I want to send the most special thank to my big family, my wife, and our children who always have my back. Hanoi, 2024 PhD student Vu Duy Hien iii CONTENTS INTRODUCTION. 1 1 OVERVIEW OF SECURE MULTI-PARTY SUM COMPUTATION 7 1.1 Background of secure multi-party computation .3 Definition of security .2 Secure multi-party sum computation problem.

35 2 PROPOSING EFFICIENT SECURE MULTI-PARTY SUM COMPUTA- TION PROTOCOLS 36 2.1 Analysis of typical secure multi-party sum computation protocols .1 Simple secure multi-party sum computation protocol .2 Secure multi-party sum computation protocol of Urabe et al.3 Secure multi-party sum computation protocol of Hao et al., 2010 in an electronic voting system .4 Privacy-preserving frequency computation protocol of Yang et al.2 Proposed secure multi-party sum computation protocols .1 Privacy-preserving frequency computation protocol based on elliptic curve ElGamal cryptosystem .2 An efficient approach for secure multi-party sum computation without pre-establishing secure/authenticated channels .3 Secure multi-sum computation protocol. 91 3 DEVELOPING NEW SOLUTIONS BASED ON SECURE MULTI-PARTY SUM COMPUTATION PROTOCOLS FOR PRACTICAL PROBLEMS 93 3.1 An efficient solution for the secure electronic voting scheme without pre-establishing authenticated channel .4 A secure end-to-end electronic voting scheme .2 An efficient and practical solution for privacy-preserving Naive Bayes classification in the horizontal data setting .4 New privacy-preserving Naive Bayes classifier for the hori- zontal partition data setting. 140 v LIST OF ABBREVIATIONS BoW. Bag-of-Words CDH.

Computational Diffie-Hellman DDH. Decisional Diffie-Hellman DD-PKE. Public-key encryption with a double-decryption algorithm DNA. Deoxyribonucleic acid DRE.

Direct-recording electronic DSS. Digital signature standard E2E. End-to-end LWE. Learn with error NSC.

National university of Singapore short text messages corpus PPFC. Privacy-preserving frequency computation PPML. Privacy-preserving machine learning PPNBC. Privacy-preserving Naive Bayes classification PSI.

Private set intersection RAM. Random Access Machines SMC. Secure multi-party computation SMS. Secure multi-party sum SSC.

Secure sum computation TF-IDF. Term frequency – inverse document frequency UK. United Kingdom ZKP. Zero knowledge proof vi LIST OF TABLES 2.1 The brief comparisons of the computational complexity among three typical SMS protocols .2 The computational complexity comparisons among the proposed pro- tocol and the typical protocols.3 The communication cost comparisons among the typical PPFC protocols.4 The stored data volume of the miner comparisons among the typical PPFC protocols (in megabytes).5 The comparisons of each user’s computational complexity among the proposed protocol and the typical protocols.6 The miner’s computational complexity comparisons among the pro- posed protocol and the typical protocols.7 The comparisons of each user’s communication cost among the pro- posed protocol and the typical protocols.8 The comparisons of the miner’s communication cost among the pro- posed protocol and the typical protocols.9 The stored data volume of the miner comparisons among the pro- posed protocol and the typical protocols (in megabytes).10 The computational complexity comparisons among the new proposal and the typical solutions.11 The communication cost comparison among the new proposal and the typical solutions.12 The running time for the miner to compute the sum values compar- isons among the compared solutions (in seconds).13 The stored data volume of the miner comparisons among the com- pared solutions (in megabytes).1 Spam short-messages dataset information .2 The running time comparisons among the new proposal and the typi- cal PPNBC solutions on the real dataset (in seconds).

119 viii LIST OF FIGURES 1.1 The distributed computing model in a secure manner .2 An example of the authentication method without knowing user’s password .3 An example of monitoring user’s passwords .4 An example of the DNA pattern-matching problem .5 The secure electronic sealed-bid auction model .6 The real and ideal models in distributed computing field .7 The computational model of the secure multi-party sum computation problem .8 The single-candidate end to end decentralized e-voting model .9 An example of the privacy-preserving frequent itemset mining problem 23 2.1 The computational model of the simple secure multi-party sum com- putation protocol .2 The running time of each user comparisons among the typical PPFC protocols.3 The time for the miner/the server computing the public keys compar- isons among the typical PPFC protocols.4 The time for the miner/the server computing the frequency value com- parisons among the typical PPFC protocols.5 The running time of each user comparisons among the proposed pro- tocol and the typical protocols.6 The time of the pre-computation phase comparisons among the pro- posed protocol and the typical protocols.7 The time of the user authentication phase comparisons among the proposed protocol and the typical protocols.8 The time of the secure n-parties sum phase comparisons among the proposed protocol and the typical protocols.9 The number of private keys comparisons among the compared solutions.10 The total running time of each user comparisons among the compared solutions.11 The running time for the miner to compute the public keys compar- isons among the compared solutions.1 The single-candidate E2E decentralized electronic voting model.2 The total running time of each voter comparisons between the new solution and Hao’s scheme.3 The voting server’s total running time comparisons between the new solution and Hao’s scheme.4 The horizontally distributed computing model.5 An example of data transformation. Motivation Nowadays, the development of information technology and communication, especially the birth of web applications or information systems has created a large amount of data owned by organizations or individuals. This has spurred the devel- opment of the distributed computing field where the data owners perform together computational tasks based on their cooperative data [1, 2]. Basically, the distributed computing field has brought a lot of substantial benefits to organizations and individ- uals, such asreducing significantly costs, understanding comprehensively customers, and making good business decisions.

However, in fact, because of privacy policy or business secrets, participants of distributed computing systems often wish to ob- tain cooperative tasks’ correct output without revealing their input data. For instance, some banks cooperate together to improve machine learning-based credit scoring tool using their customers’ data, but they are not ready to share their customers’ data for anyone. Similarly, although there are some hospitals who want to jointly develop dis- ease diagnosis methods based on a large united database, however they do not want to provide their patients’ data to others. These challenges had motivated the birth of SECURE MULTI-PARTY COMPUTATION area (SMC, for short) that has been considered as a subfield of modern cryptography.

In essence, Secure Multi-party Computation refers distributed computing methods in security concerns [1, 3]. Particularly, in a secure multi-party computation model, there are several parties, in which each participant owns a private input. These participants wish to obtain the result of the specific function f over all private inputs while each party reveals nothing about his/her input but the output result. Unlike traditional cryptography field, the adversary of SMC problems in general and the SMS problem in particular can be inside the system of participants.

The attacks of the ad- versary may be to learn the honest participants’ private input or to cause the outputs to be incorrect [1]. As a result, the ”secure” term here means: (1) the output’s cor- 2 rectness is guaranteed, and (2) each party’s input is privately kept by himself/herself. Nowadays, SMC has become an interesting topic that has attracted more and more attention from research community. A variety of SMC problems have been for- mulated and their solutions have been proposed into SMC protocols, such as secure comparison protocols [4,5], secure multi-party sum computation protocols [6–8], and secure dot product protocols [6,9–11].

Furthermore, such SMC protocols have been ap- plied to various practical problems, such as secure online auction [14], secure e-voting systems [12,13], privacy-preserving queries system [15], privacy-preserving financial data analytic [16], privacy-preserving online advertising [17], and privacy-preserving machine learning/data mining [18–20]. This thesis has investigated one of the most important and popular SMC prob- lems [6] that is the secure multi-party sum computation one (SMS, for short). In the SMS problem, it is assumed that where there are some parties, in which each party owns a private value as his/her input, and the parties wish to obtain the sum of all inputs but they reveal nothing about their inputs beyond the sum value. Similarly to SMC problems in general, the birth of SMS one has been based on the security requirements of specific distributed computing problems.

Currently, a lot of proto- cols have been propounded for the SMS problem, and they have a wide applicability in various practical computing tasks, such as privacy-preserving recommendation sys- tem [21], privacy-preserving multi-party data analytics [22], secure electronic voting system [12, 13], privacy-preserving association rule mining [6, 7], privacy-preserving classification [23], secure data collection for the smart grid [24], and secure auc- tion [25, 26]. For SMC problems in general, and SMS one in particular, the protocols must be secure (mainly including the preservation of the privacy of the participants’ local inputs and the correctness of the honest parties’ outputs [3]) enough to prevent the adversary’s harmful behaviors. Besides, SMS protocols should be good performance (i.