@inproceedings{oai:ipsj.ixsq.nii.ac.jp:00228772,
 author = {高寺, 俊喜 and 定兼, 邦彦 and 戸澤, 一成 and Toshiki, Takatera and Kunihiko, Sadakane and Kazunari, Tozawa},
 book = {コンピュータセキュリティシンポジウム2023論文集},
 month = {Oct},
 note = {秘匿決定木評価を実現する2者間Function Secret SharingプロトコルがBoyleら(ACM CCS 2016)によって提案されている．提案されているプロトコルでは，決定木は鍵とよばれる暗号文のまま扱われるため，各パーティは決定木のトポロジーさえ知っていれば結果のパスを隠したまま決定木を評価することができ，疑似乱数生成器の呼び出し回数は木の頂点数$N$に対して線形に抑えられている．だが，鍵長，鍵の生成及び関数の評価の最悪時間計算量は O(N2) であった．本論文では，このプロトコルの鍵長及び計算量を改善する以下の三つの手法を提案する：1)決定木を計算結果の等しい異なる木に変更，2)内部で使われているDistributed Point Functionの変更，3)疑似乱数生成器に条件を追加．また，決定木のFunction Secret Sharingの合成手法を提案し，これによって鍵生成の並列化が可能であることを示す．, 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.},
 pages = {1165--1172},
 publisher = {情報処理学会},
 title = {決定木評価のFunction Secret Sharingプロトコルの計算量の改善および並列化},
 year = {2023}
}