@article{oai:ipsj.ixsq.nii.ac.jp:00095211,
 author = {千田, 浩司 and 五十嵐, 大 and 高橋, 克巳 and Koji, Chida and Dai, Ikarashi and Katsumi, Takahashi},
 issue = {9},
 journal = {情報処理学会論文誌},
 month = {Sep},
 note = {セキュアマルチパーティ計算(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の応用方式を提案する., Secure Multi-Party Computation (MPC) has attracted attention recently as a core technology for the privacy preserving data mining (PPDM), however, MPC remains a tremendous challenge to reduce the computation and communication complexities from a practical view point. As a potential solution to the challenge, there exists a cryptographic protocol called bit-decomposition protocol that converts an encrypted integer into each encrypted bit of the integer without leaking the integer. In this paper, we propose some bit-decomposition protocols in the semi-honest model for the ElGamal encryption with additive homomorphism, which is expected as a building block for efficient MPC, unlike that for the Paillier encryption proposed by Schoenmakers and Tuyls at Eurocrypt 2006. In particular, the proposed two-party bit-decomposition protocol with pre-computation is much more efficient than the Paillier-based method. We also propose some efficient MPC applications using the bit-decomposition protocol.},
 pages = {2137--2145},
 title = {加法準同型ElGamal暗号を用いたビット分解プロトコル},
 volume = {54},
 year = {2013}
}