決定木評価のFunction Secret Sharingプロトコルの計算量の改善および並列化

• Item type: Symposium(1)
• 公開日: 2023-10-23
• タイトル: 決定木評価のFunction Secret Sharingプロトコルの計算量の改善および並列化
• タイトル / 言語: en
• タイトル: Improvement of time complexity and parallel performance of Function Secret Sharing for Decision Tree
• 言語: jpn
• キーワード / 主題Scheme: Other
• キーワード / 主題: 秘密分散,Function Secret Sharing,決定⽊
• 資源タイプ / 資源タイプ識別子: http://purl.org/coar/resource_type/c_5794
• 資源タイプ: conference paper
• 著者所属: 東京⼤学⼤学院情報理⼯学系研究科数理情報学専攻
• 著者所属: 東京⼤学⼤学院情報理⼯学系研究科数理情報学専攻
• 著者所属: 東京⼤学⼤学院情報理⼯学系研究科数理情報学専攻
• 著者所属(英): en
• 著者所属(英): Graduate School of Information Science and Technology Mathematical Informatics The University of Tokyo
• 著者所属(英): en
• 著者所属(英): Graduate School of Information Science and Technology Mathematical Informatics The University of Tokyo
• 著者所属(英): en
• 著者所属(英): Graduate School of Information Science and Technology Mathematical Informatics The University of Tokyo
• 著者名: 高寺, 俊喜; 定兼, 邦彦; 戸澤, 一成
• 著者名(英): Toshiki, Takatera; Kunihiko, Sadakane; Kazunari, Tozawa
• 論文抄録 / 内容記述タイプ: Other
• 論文抄録 / 内容記述: 秘匿決定木評価を実現する2者間Function Secret SharingプロトコルがBoyleら(ACM CCS 2016)によって提案されている．提案されているプロトコルでは，決定木は鍵とよばれる暗号文のまま扱われるため，各パーティは決定木のトポロジーさえ知っていれば結果のパスを隠したまま決定木を評価することができ，疑似乱数生成器の呼び出し回数は木の頂点数$N$に対して線形に抑えられている．だが，鍵長，鍵の生成及び関数の評価の最悪時間計算量は O(N2) であった．本論文では，このプロトコルの鍵長及び計算量を改善する以下の三つの手法を提案する：1)決定木を計算結果の等しい異なる木に変更，2)内部で使われているDistributed Point Functionの変更，3)疑似乱数生成器に条件を追加．また，決定木のFunction Secret Sharingの合成手法を提案し，これによって鍵生成の並列化が可能であることを示す．
• 論文抄録(英) / 内容記述タイプ: Other
• 論文抄録(英) / 内容記述: Boyle et al. (ACM CCS 2016) introduced 2-party Function Secret Sharing (FSS) for decision trees, which allows private decision tree evaluation. In this scheme, a decision tree is processed as encrypted data called a key, so that the parties can evaluate the decision tree while hiding the resulting path, knowing only the tree's topology. The number of pseudo-random generator calls is linearly proportional to the number N of vertices in the tree. However, it is not scalable because the key size and worst-case complexity of the key generation and private evaluation algorithms are O(N2). This work shows that these costs of the FSS scheme can be improved by 1) binarizing the decision tree, 2) changing the distributed point function scheme used internally, and 3) using an appropriate pseudo-random generator. We also propose a method of composing two FSSs for decision trees and demonstrate parallelization of the key generation algorithm.
• 書誌情報: コンピュータセキュリティシンポジウム2023論文集; p. 1165-1172, 発行日 2023-10-23
• 出版者 / 言語: ja
• 出版者: 情報処理学会