著者

千田 浩司 五十嵐 大 高橋 克巳

雑誌

情報処理学会論文誌 (ISSN:18827764)

巻号頁・発行日

vol.54, no.9, pp.2137-2145, 2013-09-15

---

セキュアマルチパーティ計算(MPC: Secure Multi-Party Computation)はPrivacy Preserving Data Mining(PPDM)の主要技術の1つとして近年注目されているが,通常の計算と比べ膨大な処理をともなうことが実用の障壁となっている.MPCの処理を軽減させる手法の1つに,数値からビット列への変換を暗号化したまま行う「ビット分解プロトコル」がある.SchoenmakersとTuylsはEurocrypt 2006でPaillier暗号を用いたビット分解プロトコルを提案しているが,MPCの高速処理に適した暗号として期待される加法準同型ElGamal暗号を用いた方式は我々が知る限り実現できていない.本論文では,従来のビット分解プロトコルでは加法準同型ElGamal暗号への適用が困難であることを述べ,従来とはまったく異なるアプローチにより,semi-honestモデルにおける,加法準同型ElGamal暗号を用いたビット分解プロトコルをいくつか構成する.特に事前処理を許す2パーティ限定の提案方式は,従来と比べ大きく処理削減できることを示す.またビット分解プロトコルが特に有効となるいくつかの具体的なMPCの応用方式を提案する.