{"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":"","footnotes":""},"msr-content-type":[3],"msr-research-highlight":[],"research-area":[13558],"msr-publication-type":[193716],"msr-product-type":[],"msr-focus-area":[],"msr-platform":[],"msr-download-source":[],"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_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":[],"download":[],"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":"2023-09-07 08:59:53","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. Privacy regulations forbid them from sharing data in the clear with any entity. So, can they compute this information while keeping their private data encrypted (or \u201chidden\u201d) from each other? Cryptography and specifically, the primitive Secure Multi-Party Computation (MPC), provides an answer to this seemingly impossible task using sophisticated mathematical protocols. However, two big challenges remain:…","_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"}],"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-content-type","embeddable":true,"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/msr-content-type?post=1064340"},{"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-product-type","embeddable":true,"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/msr-product-type?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-platform","embeddable":true,"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/msr-platform?post=1064340"},{"taxonomy":"msr-download-source","embeddable":true,"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/msr-download-source?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}]}}