{"id":1064340,"date":"2024-08-02T00:29:34","date_gmt":"2024-08-02T07:29:34","guid":{"rendered":"https:\/\/www.microsoft.com\/en-us\/research\/?post_type=msr-research-item&p=1064340"},"modified":"2024-08-15T09:06:38","modified_gmt":"2024-08-15T16:06:38","slug":"securely-training-decision-trees-efficiently","status":"publish","type":"msr-research-item","link":"https:\/\/www.microsoft.com\/en-us\/research\/publication\/securely-training-decision-trees-efficiently\/","title":{"rendered":"Securely Training Decision Trees Efficiently"},"content":{"rendered":"

Decision trees are an important class of supervised learning algo<\/span>rithms. When multiple entities contribute data to train a decision <\/span>tree (e.g. for fraud detection in the financial sector), data privacy <\/span>concerns necessitate the use of a privacy-enhancing technology <\/span>such as secure multi-party computation (MPC) in order to secure the <\/span>underlying training data. Prior state-of-the-art (Hamada<\/span> et al.<\/span>) <\/span>construct an MPC protocol for decision tree training with a commu<\/span>nication of<\/span> O (<\/span>\u210e\ud835\udc5a\ud835\udc41<\/span> log<\/span> \ud835\udc41<\/span> )<\/span>, when building a decision tree of height <\/span>\u210e<\/span> for a training dataset of<\/span> \ud835\udc41<\/span> samples, each having<\/span> \ud835\udc5a<\/span> attributes.\u00a0<\/span><\/p>\n

In this work, we significantly reduce the communication com<\/span>plexity of secure decision tree training. We construct a protocol <\/span>with communication complexity<\/span> O (<\/span>\ud835\udc5a\ud835\udc41<\/span> log<\/span> \ud835\udc41<\/span> +<\/span> \u210e\ud835\udc5a\ud835\udc41<\/span> +<\/span> \u210e\ud835\udc41<\/span> log<\/span> \ud835\udc41<\/span> )<\/span>, <\/span>thereby achieving an improvement of<\/span> \u2248<\/span> min<\/span>(<\/span>\u210e, \ud835\udc5a,<\/span> log<\/span> \ud835\udc41<\/span> )<\/span> over Hamada et al<\/span>. <\/span>At the core of our technique is an improved protocol to regroup <\/span>sorted private elements further into additional groups (according <\/span>to a flag vector) while maintaining their relative ordering. We im<\/span>plement our protocol in the MP-SPDZ framework<\/span>\u00a0and show <\/span>that it requires<\/span> 10<\/span>\u00d7<\/span> lesser communication and is<\/span> 9<\/span>\u00d7<\/span> faster than Hamada et al.<\/span><\/p>\n","protected":false},"excerpt":{"rendered":"

Decision trees are an important class of supervised learning algorithms. When multiple entities contribute data to train a decision tree (e.g. for fraud detection in the financial sector), data privacy concerns necessitate the use of a privacy-enhancing technology such as secure multi-party computation (MPC) in order to secure the underlying training data. Prior state-of-the-art (Hamada […]<\/p>\n","protected":false},"featured_media":0,"template":"","meta":{"msr-url-field":"","msr-podcast-episode":"","msrModifiedDate":"","msrModifiedDateEnabled":false,"ep_exclude_from_search":false,"_classifai_error":"","msr-author-ordering":null,"msr_publishername":"","msr_publisher_other":"","msr_booktitle":"","msr_chapter":"","msr_edition":"","msr_editors":"","msr_how_published":"","msr_isbn":"","msr_issue":"","msr_journal":"","msr_number":"","msr_organization":"","msr_pages_string":"","msr_page_range_start":"","msr_page_range_end":"","msr_series":"","msr_volume":"","msr_copyright":"","msr_conference_name":"31st Annual Conference on Computer and Communications Security (ACM CCS 2024)","msr_doi":"","msr_arxiv_id":"","msr_s2_paper_id":"","msr_mag_id":"","msr_pubmed_id":"","msr_other_authors":"","msr_other_contributors":"","msr_speaker":"","msr_award":"","msr_affiliation":"","msr_institution":"","msr_host":"","msr_version":"","msr_duration":"","msr_original_fields_of_study":"","msr_release_tracker_id":"","msr_s2_match_type":"","msr_citation_count_updated":"","msr_published_date":"2024-8-1","msr_highlight_text":"","msr_notes":"","msr_longbiography":"","msr_publicationurl":"","msr_external_url":"","msr_secondary_video_url":"","msr_conference_url":"","msr_journal_url":"","msr_s2_pdf_url":"","msr_year":0,"msr_citation_count":0,"msr_influential_citations":0,"msr_reference_count":0,"msr_s2_match_confidence":0,"msr_microsoftintellectualproperty":true,"msr_s2_open_access":false,"msr_s2_author_ids":[],"msr_pub_ids":[],"msr_hide_image_in_river":0,"footnotes":""},"msr-research-highlight":[],"research-area":[13558],"msr-publication-type":[193716],"msr-publisher":[],"msr-focus-area":[],"msr-locale":[268875],"msr-post-option":[],"msr-field-of-study":[246691],"msr-conference":[],"msr-journal":[],"msr-impact-theme":[],"msr-pillar":[],"class_list":["post-1064340","msr-research-item","type-msr-research-item","status-publish","hentry","msr-research-area-security-privacy-cryptography","msr-locale-en_us","msr-field-of-study-computer-science"],"msr_publishername":"","msr_edition":"","msr_affiliation":"","msr_published_date":"2024-8-1","msr_host":"","msr_duration":"","msr_version":"","msr_speaker":"","msr_other_contributors":"","msr_booktitle":"","msr_pages_string":"","msr_chapter":"","msr_isbn":"","msr_journal":"","msr_volume":"","msr_number":"","msr_editors":"","msr_series":"","msr_issue":"","msr_organization":"","msr_how_published":"","msr_notes":"","msr_highlight_text":"","msr_release_tracker_id":"","msr_original_fields_of_study":"","msr_download_urls":"","msr_external_url":"","msr_secondary_video_url":"","msr_longbiography":"","msr_microsoftintellectualproperty":1,"msr_main_download":"","msr_publicationurl":"","msr_doi":"","msr_publication_uploader":[{"type":"url","viewUrl":"false","id":"false","title":"https:\/\/eprint.iacr.org\/2024\/1077","label_id":"243109","label":0}],"msr_related_uploader":[{"type":"url","viewUrl":"false","id":"false","title":"https:\/\/eprint.iacr.org\/2024\/1077.pdf","label_id":"243112","label":0}],"msr_citation_count":0,"msr_citation_count_updated":"","msr_s2_paper_id":"","msr_influential_citations":0,"msr_reference_count":0,"msr_arxiv_id":"","msr_s2_author_ids":[],"msr_s2_open_access":false,"msr_s2_pdf_url":null,"msr_attachments":[],"msr-author-ordering":[{"type":"text","value":"Divyanshu Bhardwaj","user_id":0,"rest_url":false},{"type":"text","value":"Sandhya Saravanan","user_id":0,"rest_url":false},{"type":"user_nicename","value":"Nishanth Chandran","user_id":33084,"rest_url":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/microsoft-research\/v1\/researchers?person=Nishanth Chandran"},{"type":"user_nicename","value":"Divya Gupta","user_id":37766,"rest_url":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/microsoft-research\/v1\/researchers?person=Divya Gupta"}],"msr_impact_theme":[],"msr_research_lab":[],"msr_event":[],"msr_group":[],"msr_project":[507611],"publication":[],"video":[],"msr-tool":[],"msr_publication_type":"inproceedings","related_content":{"projects":[{"ID":507611,"post_title":"EzPC (Easy Secure Multi-party Computation)","post_name":"ezpc-easy-secure-multi-party-computation","post_type":"msr-project","post_date":"2018-10-10 01:30:32","post_modified":"2025-01-15 20:59:33","post_status":"publish","permalink":"https:\/\/www.microsoft.com\/en-us\/research\/project\/ezpc-easy-secure-multi-party-computation\/","post_excerpt":"Consider the following scenario: Two hospitals, each having sensitive patient data, must compute statistical information about their joint data. Or, one of the hospitals has a pre-trained ML model based on sensitive patient data and another hospital either wants to learn inference results for its sensitive patient data or the accuracy of the model for its sensitive patient data. In all cases, privacy regulations forbid them from sharing the data and\/or the model in the…","_links":{"self":[{"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/msr-project\/507611"}]}}]},"_links":{"self":[{"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/msr-research-item\/1064340","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/msr-research-item"}],"about":[{"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/types\/msr-research-item"}],"version-history":[{"count":3,"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/msr-research-item\/1064340\/revisions"}],"predecessor-version":[{"id":1075773,"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/msr-research-item\/1064340\/revisions\/1075773"}],"wp:attachment":[{"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/media?parent=1064340"}],"wp:term":[{"taxonomy":"msr-research-highlight","embeddable":true,"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/msr-research-highlight?post=1064340"},{"taxonomy":"msr-research-area","embeddable":true,"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/research-area?post=1064340"},{"taxonomy":"msr-publication-type","embeddable":true,"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/msr-publication-type?post=1064340"},{"taxonomy":"msr-publisher","embeddable":true,"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/msr-publisher?post=1064340"},{"taxonomy":"msr-focus-area","embeddable":true,"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/msr-focus-area?post=1064340"},{"taxonomy":"msr-locale","embeddable":true,"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/msr-locale?post=1064340"},{"taxonomy":"msr-post-option","embeddable":true,"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/msr-post-option?post=1064340"},{"taxonomy":"msr-field-of-study","embeddable":true,"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/msr-field-of-study?post=1064340"},{"taxonomy":"msr-conference","embeddable":true,"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/msr-conference?post=1064340"},{"taxonomy":"msr-journal","embeddable":true,"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/msr-journal?post=1064340"},{"taxonomy":"msr-impact-theme","embeddable":true,"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/msr-impact-theme?post=1064340"},{"taxonomy":"msr-pillar","embeddable":true,"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/msr-pillar?post=1064340"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}