ID Privacy-Preserving Data Mining Lindell 20) 1),30) 1 3 semi-honest malicious 3 n t < n/2 15) semi-honest malicious semi-honest malicious mali

情報処理学会論文誌

エラー検出可能な軽量

3

パーティ秘匿関数計算の

提案と実装評価

1

千

田

浩

司

†1

五 十 嵐

大

†1

濱

田

浩

気

†1

高

橋

克

巳

†1 本稿では 3 主体の協調計算により入力値を秘匿しつつ算術演算や論理演算を実行 できる 3 パーティ秘匿関数計算プロトコルを提案し，その実装評価を行った結果を示 す．提案プロトコルは主体間の結託はないと仮定したとき，semi-honest モデルにお いて入力値の秘匿性が保証され，malicious モデルにおいて演算結果の改竄（エラー） を従来よりも効率良く検出できるという特徴を持つ．実装評価は CPU：Intel Core2 Quad 3.0 GHz，RAM：4 GB の 1 台マシン環境で測定し，32 ビット乗算 1 回を約 1.6µ 秒で処理できることを確認した．また 3 パーティ秘匿関数計算プロトコルの応 用として，個人に関する情報を安全に利活用できる技術として注目されているプライ バシ保護データマイニング（Privacy-Preserving Data Mining）への適用について 考察を行う．

A Lightweight Three-party Secure Function Evaluation

with Error Detection and Its Experimental Result

Koji Chida,

†1

Dai Ikarashi,

†1

Koki Hamada

†1

and Katsumi Takahashi

†1

We propose a three-party secure function evaluation protocol with lightweight error detection and show the experimental result. Assuming that there ex-ists honest majority, the proposed protocol obtains the outcome of arithmetic and/or logic operations from three-shared values without disclosing the origi-nal value in the semi-honest model and can detect the error if the outcome is manipulated by a malicious party faster than the existing schemes. The im-plementation system, which consists of a PC with Intel Core2 Quad 3.0 GHz and 4 GB RAM, can compute the multiplication of two 32 bits integers about 1.6 microseconds. Moreover we consider Privacy-Preserving Data Mining as an application of the three-party secure function evaluation protocol.

1. は じ め に

顧客情報や経営情報等，いわゆる機密情報の管理・運用は，組織における管理情報の多様化 やクラウドコンピューティング等の情報処理基盤の変化にともない，セキュリティ対策やプ ライバシへの配慮がいっそう重要な課題となっている．その中で最近では情報を複数個所に 分散させて情報漏洩を防ぐ秘密分散技術26)の実用化が国内においても進みつつある37)–39)． さらに分散された情報を復元することなく意中の演算結果を導く暗号プロトコル3),5)につ いても実用化を見据えた開発プロジェクトの動きが見られる11),25),28),31)．特定のデータを 秘匿しつつ意中の演算結果を導く技術は秘匿計算（Secure Computation）や秘匿関数計算 （Secure Function Evaluation）と呼ばれ，2章で述べるように様々な手法が提案されている．

秘密分散技術は情報の保管時のセキュリティ対策としては有効だが，利用時は一般に復元 する必要があるため漏洩リスクが高まる．これに対し文献3)，5)に代表される秘密分散に 基づく秘匿関数計算は，本来の入力値の代わりに分散された情報を計算の入力とすることが でき，計算過程においても本来の入力値がいっさい復元されないため，秘密分散技術の機能 を利用時も維持したより高度なセキュリティ技術といえる．しかし分散データを保有する複 数の主体が通常よりも膨大な計算を必要とし，主体間で大量のデータ通信をともなう場合も あるため，現時点での実利用は限定的といえる． 一方，個人情報保護やプライバシの観点から，国内外において法制度・ガイドラインや標 準化の整備とともに，個人に関する情報を安全に利活用するための技術的対策が検討されて いる10),14),34)–36)．現在検討されている主な技術的対策は，いわゆる広義の匿名化である． すなわち，個人に関する情報が個人と結び付くことのないように情報を加工する手段全般で ある．しかし一般に匿名化による対策は，情報の利用が限定的になることに加え，個人に関 する情報が個人と結び付かないことの保証が容易ではない．その理由の1つとして，個人に 関する情報と個人の結び付けが，あらかじめ備えている知識や情報に大きく左右されること があげられる．たとえば，氏名，住所，年齢，性別，職業，購買履歴（日時，店舗名，商品名） からなるデータをマーケティング用途に氏名，住所をID番号に置き換えて第三者提供や一般 公開を行った場合，年齢，性別，職業，および一部の購買履歴からID番号に対応する個人を †1 NTT 情報流通プラットフォーム研究所

NTT Information Sharing Platform Laboratories

エラー検出可能な軽量 3 パーティ秘匿関数計算 特定できる者がいないとも限らず，そのID番号から特定の個人の購買履歴がすべて紐付い てしまう可能性があり，これはプライバシの観点から望ましくない．このように，個人に関 する情報をどの程度まで開示可能かという問題は，情報の利活用と保護の両方の観点から慎 重に考える必要があるといえる．そして当該開示問題の有力な解決手段として，秘匿関数計 算が近年注目されている．特に情報を保護しつつデータマイニングを行う技術の総称である プライバシ保護データマイニング（Privacy-Preserving Data Mining）は，Lindellらによ る研究成果20)を端緒に秘匿関数計算を利用した手法が数多く提案されている1),30)．しかし ながら秘匿関数計算は前述のとおり，一般に通常の演算と比べ処理時間が著しく増加し，特 にデータマイニングは入力データ数や計算量が膨大となる場合があるため，秘匿関数計算を 利用する場合は処理時間の軽減が特に大きな課題となる．なお本稿では，情報を保護しつつ 統計処理を行うための技術も合わせてプライバシ保護データマイニングと呼ぶことにする1． 上述の状況をふまえ，本稿では，軽量かつ汎用の秘匿関数計算を提案し，実装評価により その有用性を検証する．対象とする演算を限定して処理軽減を図る方式は数多く提案され ているものの，代表的な演算への適用にとどまっているのが現状である．提案方式は，3主 体の協調計算により入力値を秘匿しつつ各種演算を効率良く実行し，主体間の結託はない と仮定したとき，semi-honestモデルにおいて入力値を秘匿でき，maliciousモデルにおい て演算結果の改竄（エラー）を従来よりも効率良く検出できるという特徴を持つ．これに よりウィルス感染や操作ミス，内部不正等の早期発見および対策に有効と考えられる．秘 密分散を拡張した秘匿関数計算，すなわち情報理論的安全性に基づく秘匿関数計算は少な くとも3以上の主体を必要とし，主体数をnとしたとき閾値t（< n/2）以下の結託に耐 性を持つよう設計される15)．攻撃者はsemi-honestおよびmaliciousのモデルに分類され， semi-honestモデルでは，攻撃者は正しくプロトコルを実行した主体の閾値以下のログから 入力値を得ようとし，maliciousモデルでは，攻撃者は閾値以下の主体を自由に操作して入 力値の取得や演算結果の改竄（エラー）といった不正を試みる．既存技術として，より強い 攻撃モデルであるmalicious攻撃の対策がいくつか知られている．文献3)ではn≥ 4のと き一般化Reed-Solomon符号を用いた対策が述べられている．文献12)では任意のn（≥ 3） についてゼロ知識証明技術を用いて不正の有無を検証する方式が提案されている．しかしゼ ロ知識証明技術は一般に計算量・通信量が大きく，大規模や複雑な計算には適用が難しい．

1 最近ではより広範の技術を指す，プライバシ保護データ分析（Privacy-Preserving Data Analysis）やプライ

バシ保護データ活用（Privacy-Preserving Data Utilization）といった用語も見受けられる．

提案方式は，情報理論的安全性に基づく秘匿関数計算において一般に処理時間の最小化が期 待できるn = 3に特化して，主体間の結託はないと仮定したとき，maliciousモデルにおい て従来のゼロ知識証明技術を用いずに軽量にエラー検出を可能とし，semi-honestモデルに おいて入力値の秘匿性を保証する汎用の秘匿関数計算である． 以降，2章で関連研究を紹介し，3章で提案方式について説明する．提案方式の安全性お よび実装評価をそれぞれ4，5章で示し，6章では3パーティ秘匿関数計算プロトコルの応 用として，プライバシ保護データマイニングへの適用について考察を行う．最後に7章で 本稿をまとめる．

2. 関 連 研 究

秘匿関数計算は一般に，意中の演算の入力値を秘匿処理したうえで提供する主体と，そ の入力値を復元することなく処理する主体の少なくとも2主体が関与し，秘匿方法は暗号 化や秘密分散が代表的である．その概念および具体的な実現方法はYaoによって提案され た32),33). Yaoの手法は，論理回路演算を実行可能な状態のまま秘匿する主体と，その秘匿 された論理回路演算を実行する主体によって構成され，実行には複数主体の協調計算が必 要なことからマルチパーティプロトコルとも呼ばれる（2主体に特化した方式は区別して2 パーティプロトコルと呼ぶ場合が多い）．論理回路演算を実行するマルチパーティプロトコ ルとして，紛失通信（Oblivious Transfer）を利用した方式17)や，MIX-netを利用した方 式19)等が提案されている．なお論理回路演算の実行を可能とする秘匿関数計算は秘匿回路 計算（Secure Circuit Evaluation）と呼ばれる．特に最近では秘匿回路計算の実行を単独で 行うことを可能とする準同型暗号が注目を集めている13)．またYaoの手法に基づく2パー ティプロトコル22)や，それを計算委託型に変形した2パーティプロトコル29)等の実装報 告もみられるようになり，実用に向けた動きが加速しつつある．ここで計算委託型とは，入 力提供主体と計算主体が異なる主体構成を指し，文献29)では計算主体が2主体となる． 一方，環Z/mZ（mは適当な整数）上の算術演算を可能とする秘匿関数計算も提案され ており，1章で述べた秘密分散に基づく方式3),5)や準同型暗号に基づく方式8),23)が知られ ている．なお秘匿回路計算は一般に処理効率が悪いため，秘匿関数計算を論理回路演算と算 術演算に分けて全体の処理効率を上げる手法も提案されている2),9),21),24)． 以下では，提案方式同様に加法的な秘密分散に基づく既存の秘匿関数計算4)について説明 する．これはSharemindと呼ばれるシステム28)の要素技術であり，提案方式同様に3主 体による処理を基本とするが，semi-honestモデルを仮定している．文献4)の手法は，環

エラー検出可能な軽量 3 パーティ秘匿関数計算 Z/mZ上で加法的に分散したデータ（シェア）について，復元することなく加算，定数倍お よび乗算結果のシェアを求める．そしてこれらの基本演算を組み合わせて型変換（2進数と 整数の相互変換）や大小比較等の演算を構成している．mは文献3)，5)と異なり任意の値と してよく，計算効率を考慮してm = 232としている．主体をPi（i = 0, . . . , n− 1），入力を a∈ Z/mZとしたとき，Piが受信するaのシェアはa =



n−1 i=0 aiを満たすai∈ Z/mZ，た だしa₀, . . . , an−1の任意のn− 1個の元はZ/mZ上の互いに独立な乱数とする．加算はPi が持つa, b∈ Z/mZのシェアai, biからdi= ai+ biを計算すればよく，



n−1 i=0 di= a + b かつd0, . . . , dn−1の任意のn− 1個の元はZ/mZ上の互いに独立な乱数と見なせるため， diはa + bのPiのシェアとなっていることが分かる．定数倍については入力をaのシェア および定数cとしたとき，Piのacのシェアはcaiとすればよい． 次に，文献4)における乗算について説明する．加算および定数倍は各主体が通信すること なくシェアを計算できるが，乗算は通信をともなう．文献4)では，Piの入力をa =



n−1 i=0 ai, b =



n−1_i=0 biのシェアai, bi∈ Z/mZとしたとき， ab = n−1



i=0 aibi+



j=k ajbk (1) となり，特に任意のα, β∈ Z/mZについて ajbk=−(aj+ α)(bk+ β) + aj(bk+ β) + (aj+ α)bk+ αβ を満たすことを利用する．たとえばn = 3としたとき，式(1)の項a0b1を次のように分散 する．なお以降Piの入力または出力がxであることをPi(x)で表し，Piが持つxのシェ アを[x]iで表す． P₀, P₁が持つ値の乗算結果をP₀, P₁, P₂に分散





入力：P0(a0), P1(b1)

出力：P₀([a₀b₁]₀), P₁([a₀b₁]₁), P₂([a₀b₁]₂)

( 1 ) P₂はα, β∈ Z/mZをランダムに選択してそれぞれP₀, P₁に送信し， [a0b1]2:= αβを計算する． ( 2 ) P0, P1はそれぞれa0+ α, b1+ βを計算してP1, P0に送信する． ( 3 ) P₀, P₁はそれぞれ[a₀b₁]₀:=−(a₀+ α)(b₁+ β) + a₀(b₁+ β), [a0b1]1:= (a0+ α)b1を計算する．





上記同様の手続きを式(1)の



_j=kajbk のすべての項について行い，Pi は[ab]i = aibi+



j=k[ajbk]iを得る．

3. 提 案 方 式

提案方式は前述のとおりn = 3に特化した方式であり，主体間の結託はないと仮定したと き，maliciousモデルにおいて従来のゼロ知識証明技術を用いずに軽量にエラー検出を可能 とし，semi-honestモデルにおいて入力値の秘匿性を保証する汎用の秘匿関数計算である． 本章ではまずsemi-honestモデルにおける秘密分散・復元，加減算・定数倍，乗算，論理回 路演算の順に提案方式を説明する．次にmaliciousモデルにおけるエラー検出手続きを与え る．なお本手続きは従来のゼロ知識証明技術と異なり，エラーを起こした主体を特定するこ とはできない．したがっていずれかの主体が（事実にかかわらず）エラー検出を主張した時 点でプロトコルは途中終了する．最後に，文献9)で提案された手法に基づき，エラー検出 可能な型変換の手続きを与える．これらの安全性評価は4章で論じる． 3.1 秘密分散・復元 入力a∈ Z/mZの秘密分散は，Piが持つシェアを[a]i = (ai, ai+1)とする．なお記述 の簡略化のため，i± 1は3で割った余りと見なす．すなわち，たとえばi = 2であれば ai+1= a0である．いまaを入力としてPiが[a]iを得る手続きをShareとしたとき，Share は任意の主体が実行してよく，Piのいずれかでもよいし，それ以外の外部の主体でもよい． 具体的な手続きは次のようになる． Share：2-out-of-3秘密分散





入力：a∈ Z/mZ 出力：Pi([a]i) ( 1 ) a₀, a₁∈ Z/mZをランダムに選択する． ( 2 ) a2:= a− a0− a1を計算する． ( 3 ) i = 0, 1, 2について，[a]i:= (ai, ai+1)としてPiに送信する．





a = a₀+ a₁+ a₂より，任意の異なる2つの[a]iからaを復元できる．また明らかに任 意の[a]iからaは復元できない，すなわち2-out-of-3秘密分散の性質を有している．なお 復元処理は各主体が持つシェアの冗長性によりエラー検出が可能である．具体的には次の手 続きDecのようにすればよい．

エラー検出可能な軽量 3 パーティ秘匿関数計算 Dec：2-out-of-3秘密分散のエラー検出を含む復元





入力：Pi([a]i) 出力：a or⊥ ( 1 ) Piは(αi, βi) := (ai, ai+1)を開示する． ( 2 ) i = 0, 1, 2についてβi= αi+1となるβi, αi+1が存在すれば，異常を示す⊥を 返して終了する． ( 3 ) a = α₀+ α₁+ α₂を計算する．





3.2 加減算・定数倍 加減算や定数倍演算はそれぞれ以下のAdd/Sub，CoMulにより実現される． Add/Sub：a, bのシェアからa± bのシェアを生成





入力：Pi([a]i, [b]i) 出力：Pi([a± b]i) • Piは[a± b]i:= (ai± bi, ai+1± bi+1)を計算する．





CoMul：aのシェアおよび定数cからacのシェアを生成





入力：Pi([a]i), c 出力：Pi([ca]i)

• Piは[ca]i:= (cai, cai+1)を計算する．





3.3 乗 算 乗算は文献3)，4)等と同様に各主体の協調計算が必要となる．手続きMulは次のように なる． Mul：a, bのシェアからabのシェアを生成





入力：Pi([a]i, [b]i) 出力：Pi([ab]i) ( 1 ) P₀はr₁, r₂, c₀∈ Z/mZをランダムに選択してから， c1:= (a0+ a1)(b0+ b1)− r1− r2− c0を計算してP1, P2にそれぞれ(r1, c1), (r2, c0)を送信し，[ab]0 := (c0, c1)とする． ( 2 ) P₁, P₂はそれぞれy := a₁b₂+ a₂b₁+ r₁, z := a₂b₀+ a₀b₂+ r₂を計算して P₂, P₁に送信する． ( 3 ) P1, P2はc2:= y + z + a2b2を計算してそれぞれ[ab]1:= (c1, c2), [ab]2:= (c2, c0)とする．





シェアの正当性について， c₀+ c₁+ c₂= (a₀+ a₁)(b₀+ b₁)− r₁− r₂+ y + z + a₂b₂ = (a0+ a1)(b0+ b1) + a1b2+ a2b1+ a2b0+ a0b2+ a2b2 = (a0+ a1+ a2)(b0+ b1+ b2) = ab となり，c₀, c₁, c₂の任意の2つの元はZ/mZ上の互いに独立な乱数と見なせるため，c₀, c1, c2は正しくabのシェアとなっていることが分かる． 3.4 論理回路演算 否定，論理積，論理和，および排他的論理和の論理回路演算について説明する．まず否定 は以下の手続きによる． Not：a∈ {0, 1}のシェアからaの否定¯a := 1− aのシェアを生成





入力：Pi([a]i) 出力：Pi([¯a]i) • P0は[¯a]0:= (1− a0,−a1)を計算する． • P1は[¯a]1:= (−a1,−a2)を計算する． • P2は[¯a]₂:= (−a₂, 1− a₀)を計算する．





論理積，論理和，および排他的論理和は，a, b∈ {0, 1}についてそれぞれ • a ∧ b = ab

エラー検出可能な軽量 3 パーティ秘匿関数計算 • a ∨ b = a + b − ab • a ⊕ b = a + b − 2ab となるから，a, b ∈ {0, 1}のシェアについて加減算Add/Sub，定数倍CoMul，および乗 算Mulを適用すればよい．具体的には以下のようになる．なお以降，xのシェアの組を [x] := ([x]₀, [x]₁, [x]₂)と表記する． • 論理積：And([a], [b]) := Mul([a], [b])

• 論理和：Or([a], [b]) := Sub(Add([a], [b]), Mul([a], [b]))

• 排他的論理和：Xor([a], [b]) := Sub(Add([a], [b]), CoMul(Mul([a], [b]), 2))

3.5 エラー検出 3.1∼3.4節で与えたsemi-honestモデルを仮定した方式は，Piのいずれかの主体が不正 値を他の主体に送信することでエラーを起こすことが可能となるだけでなく，不正値を受信 した主体が，その不正値に基づく何らかの計算結果を不正な主体に与えることで入力値の秘 匿性が損なわれる可能性がある．一方，3.1∼3.4節で与えた手続きのうち，各主体が不正値 を他の主体に送信する機会は秘密分散Share，および乗算Mul実行時のみとなる．以下では

maliciousモデルにおけるShareおよびMulのエラー検出について考える．

まずShareにおけるエラー検出手続きとして，複数の主体が共有しているシェアが一致し ているかどうか確認する手続きEqTestを与える． EqTest：複数の主体が共有しているシェアの一致性検証





入力：Pi([a]i) 出力：true/false

( 1 ) Piはαi+1:= ai+1をPi+1に送信する．

( 2 ) Piはαi= aiであれば1を，そうでなければ0を開示する．

( 3 ) すべてのPiから1が開示されればtrueを，そうでなければfalseを返す．





EqTestの( 2 )において，Piは偽の結果を開示する不正が考えられるが，これは結局，自 身が保持するシェアを書き換える操作に等しく，EqTestにおけるエラーとは見なさない．す なわち，たとえばEqTest実行後にDecを実行する場合，偽の結果を開示することでDec

実行時にエラー検出されるか，エラー検出されないようにDec実行前に正しいシェアに書 き直す必要があることは明らかである．

次にMulにおけるエラー検出手続きを与える．基本アイデアは，まずP1, P2は正しいと

仮定し，P₁, P₂のみが知る乱数を用いてP₀に特別な処理を行わせる．具体的には，乱数 をsとして[a], [b]から[ab]を得るとともに[sa], [b]から[sab]を求める手続きを行う．そ してP1, P2は，[ab], [sab]の復元結果がs倍の関係になっているかどうか，それらを復元 せずに検証し，sを知らないP0がそのような関係を保ちながらエラーを起こすことを困難 とする．ただしすでに述べたとおり提案方式はエラー検出のみを保証し，エラーを起こした 主体は特定できない． 以下同様の特別な処理をP1, P2それぞれにも行わせることで，すべての主体に対するエ ラー検出を行う．以下に一般性を失うことなく，P1, P2は正しいと仮定した場合のエラー 検出の手続きを与える． Verif：[c]← Mul([a], [b])におけるエラー検出





入力：Pi([a]i, [b]i, [c]i)ただしP0が正しければc = ab 出力：true/false ( 1 ) P1, P2はs∈ Z/mZをランダムに選択する．

( 2 ) P1, P2はそれぞれ(Share(sa1), Share(sa2)), Share(sa0)を実行し，Piは

(di, di+1) := ((sa0)i+ (sa1)i+ (sa2)i, (sa0)i+1+ (sa1)i+1+ (sa2)i+1)，すな わちd := saのシェアを得る．

( 3 ) Mul([d], [b])を実行し，Piはe := db = sabのシェア(ei, ei+1)を得る．

( 4 ) P1, P2はそれぞれf := sc1+ sc2− e1− e2, g := sc0− e0を計算して互いに送 信し，f + g = 0であればtrueを，そうでなければfalseを返す．





上記手続きVerifが正しく実行され，入力も正しければ，f + g = s(c0+ c1+ c2)− (e0+ e1+ e2) = sc− sab = 0より上記手続きはtrueを返し，P1, P2に対してg, fから秘匿性 を損ねることもない． ここでVerifの特徴および効率について，1章で触れたn = 3に適用可能なゼロ知識証明 技術12)と比較しながら簡単に考察を与える．Verifは乱数生成および単純な積和演算からな り，群位数mは適当な素数であればよく，5章で紹介する実装評価ではmを32ビットの 素数としている．一方，文献12)の方式は準同型暗号を用いた計算量仮定に基づく方式であ り，準同型暗号が安全となるような群上（たとえば群位数が1,024ビットとなるような群） でのべき乗演算をすべての主体が行い，演算結果の群要素を他の主体に送信する必要がある ため，Verifの方が計算効率および通信効率に優れると考えられる．ただし3章で述べたよ

エラー検出可能な軽量 3 パーティ秘匿関数計算 うに，文献12)の方式は各主体の不正の有無を検証できるのに対し，Verifはエラー検出の 機能のみである． 3.6 型 変 換 2章で述べたとおり，秘匿回路計算は一般に処理効率が悪いため，秘匿関数計算を論理回 路演算と算術演算に分けて全体の処理効率を上げる手法がいくつか提案されている．基本 的な方針は，a∈ Z/mZのシェアから，a = (ak−1· · · a0)2となるaiのシェア，およびその 逆をaを復元することなく求めることである．ここで前者の処理を2進変換，後者の処理 を整数変換，それらをまとめて型変換と呼び，(ak−1· · · a0)2はaの2進表記，すなわちk ビット整数aについてaiはaを2進表記したときの下位i + 1番目のビットを表すものと する．すると論理回路演算と算術演算は基本的に独立した処理であっても，型変換によりそ れらを組み合わせた秘匿関数計算が可能となる． 2進変換はmを素数とすれば文献9)で提案されている手法を適用できる．すなわち提 案方式に基づき2進変換を行う場合はmを素数とする必要がある．なお文献9)の手法は， どの主体も知りえないランダムなビットのシェアを生成する必要がある．提案方式に基づき 文献9)の手法を適用する場合は，以下に示す単純な方法でランダムビットのシェアを生成 してもよい． BitShare：ランダムなビットのシェアを生成





入力：なし 出力：Pi([b]i) or⊥ただしbはランダムなビット ( 1 ) Piはbi∈ {0, 1}, bi,0, bi,1∈ Z/mZをランダムに選択し，

bi,2:= bi− bi,0− bi,1を計算し，Pi+1, Pi−1にそれぞれ(bi,0, bi,1, bi,2),

(bi,i−1, bi,i)を送信する．

( 2 ) PiはPi−1から受信した(bi−1,0, bi−1,1, bi−1,2)について

bi−1,0+ bi−1,1+ bi−1,2∈ {0, 1}であれば異常を示す⊥を返して処理を中断さ せる．

( 3 ) Piが持つbj（0≤ j ≤ 2）のシェア[bj]i= (bj,i, bj,i+1)を入力としてEqTest を実行する． ( 4 ) Xor(Xor([b0], [b1]), [b2])を実行し，Piは実行結果を[b]iとする．





上記手続きBitShareについて，b₀, b₁, b₂はランダムなビットであり，b := b₀⊕ b₁⊕ b₂∈ {0, 1}となることから，すべての主体が正しく手続きを行えば，実行結果はランダムなビッ トのシェアとなる． 整数変換は文献9)にもあるように，a =



k−1_i=0 2iaiより

[a] = Add(· · · Add(Add([a0], CoMul([a1], 2)), CoMul([a2], 22))· · · , CoMul([ak−1], 2k−1)) の計算を行えばよい．

4. 安 全 性

4.1 準 備 攻撃者にとって秘密のデータの推定分布がある関数による開示データを見てもまったく変 化しないとき，その関数は完全秘匿性（perfect secrecy）を持つといい27)，以下によって 定義される． 定義4.1. 集合S上の確率変数Sと独立であるような，Sから集合Dへの確率的関数F が完全秘匿性を持つとは，任意の実際の秘密のデータs∈ Sと出力d∈ Dに対して， Pr(S = s|F (S) = d) = Pr(S = s) となることをいう． 上記でSが秘密のデータでありF (S)が開示されるデータである． 一方，マルチパーティプロトコルにおける完全秘匿性の定義を文献15)，16)に基づき以 下のように与える． 定義4.2. j番目の主体に関するデータが以下であるようなnパーティプロトコルを考える． • 入力：xj • 出力：fj(x1, . . . , xn) • 出力を除く受信データ：VIEWj(x1, . . . , xn) このプロトコルがsemi-honestモデルで完全秘匿性を持つとは，semi-honestモデルにおけ る攻撃者に対して以下のような確率的関数Sが存在することである． 任意の入力 −→x = {x1, . . . , xn}, I = {i1, . . . , i_|I|} ⊆ {1, . . . , n} に対して S(I, −→xI, fI(−→x ))とVIEWI(−→x )の確率分布は等しい．

ただし−→xI={xi1, . . . , xi|I|}, fI= (fi1, . . . , fi|I|), VIEWI = (VIEWi1, . . . , VIEWi|I|)で ある．

上記定義の中で主体の集合Iが2主体以上の集合の場合は当該主体が結託したことを表 現している．このため本定義の安全性は，主体どうしがどのように結託しようとも安全であ

エラー検出可能な軽量 3 パーティ秘匿関数計算 ることを保証する．そこで各主体は結託をしないことを仮定する提案方式においては，定 義4.2の条件を主体集合Iごとに分離した以下の定義をおく． 定義4.3. 定義4.2と同様のプロトコルを考え，I ={i1, . . . , it} ⊆ {1, . . . , N}とする．この プロトコルがsemi-honestモデルで主体集合Iに対して完全秘匿性を持つとは，semi-honest モデルにおける攻撃者に対して以下のような確率的関数Sが存在することである． 任意の入力−→x ={x₁, . . . , xN}に対してS(I, −→xI, fI(−→x ))とVIEWI(−→x )の確率分 布は等しい． 特に以下は本稿の証明で用いる，定義4.3の条件の十分条件である． 命題 4.1. 定義 4.2 と同様のプロトコルを考え，I ⊆ {1, . . . , n}とする．このとき， VIEWI(−→x )が一様乱数ならば，プロトコルはsemi-honest モデルで主体集合I に対し て完全秘匿性を持つ． Proof. 定義中，Sをつねに一様乱数を出力する関数とすればよい． 4.2 semi-honestモデル 提案方式は単一のプロトコルではなく，3章で与えた各手続きの複合からなるプロトコル の集合である．そのため，すべての複合したプロトコルが安全であることを示す必要があ る．特に3.1∼3.4節で与えたプロトコル，すなわちShare，Dec，Add/Sub，CoMul，Mul，

Not，And，Or，Xorはsemi-honestモデルを仮定している．以降，3.1∼3.4節で与えたプ ロトコル群を基本プロトコル，並列および直列の接続によりそれらを複合したプロトコルを 複合プロトコルと呼ぶ．すると本稿の示すべき命題は以下となる．

定理4.1. 3.1∼3.4節で与えたプロトコルShare，Dec，Add/Sub，CoMul，Mul，Not，And，

Or，Xorの任意の複合プロトコルは，主体間の結託を許さないsemi-honestモデルにおい て完全秘匿性を持つ．

Proof. P0, P1, P2の3パーティのVIEWに関しては，まず各基本プロトコルのVIEWを 考え，そこから帰納的にVIEWを定義する．基本プロトコルのうち，Add/Sub，CoMul，

Notはデータ送受信をともなわないため，VIEWは空である．Decの送受信データは明ら かに入出力データと等価であるため，やはりVIEWは空と見なすことができる．またAnd

はMulに等しく，Or，XorはAdd/Sub，CoMul，Mulから構成されるため複合プロトコル であると見なすことができる．これらから，結局Share，Mulのみが実際考慮する必要のあ る対象である．Share，MulのVIEWを表す確率的関数をそれぞれVσ_{, V}μ_{とすると，そ} れぞれ以下のようになる． Vσ:Z/mZ → [[(Z/mZ)2]]× [[(Z/mZ)2]]× [[(Z/mZ)2]] a → ((Rx, Ry), (Ry, a− Rx− Ry), (a− Rx− Ry, Rx)) Vμ: (Z/mZ)6 → {Ø} × [[(Z/mZ)3]]× [[(Z/mZ)3]] (a0, a1, a2, b0, b1, b2) → (Ø, (R₁, (a₀+ a₁)(b₀+ b₁)− R₁− R₂− R₀, (a− a₀− a₁)b₀+ a₀(b− b₀− b₁) + R₂), (R2, R0, a1(b− b0− b1) + (a− a0− a1)b1+ R1)) ただしRx, Ry, R0, R1, R2は互いに独立な一様乱数，Øは空データ，集合Ωに対して[[ Ω ]] はΩ上の確率変数の集合を表す．両者とも，関数値の第1成分から順にP₀, P₁, P₂のVIEW

である．これらを順にVIEW₀, VIEW₁, VIEW₂で表す．

命題4.1より複合プロトコルが一様乱数であることを示せばよいのだが，その前にまず Vσ, Vμが一様乱数であることを示す．

補題4.1. 任意のa, a₀, a₁, a₂, b₀, b₁, b₂∈ Z/mZに対して，Vσ

0 (a), V1σ(a), V2σ(a), V0μ(a0, a₁, a₂, b₀, b₁, b₂), V₁μ(a₀, a₁, a₂, b₀, b₁, b₂), V₂μ(a₀, a₁, a₂, b₀, b₁, b₂)は一様乱数である．た だしViσ, ViμはそれぞれV σ_{, V}μ_のVIEW iを表す． Proof.（補題） Rx, Ry, R0, R1, R2が互いに独立な一様乱数であることから，それぞれの一様乱数性を調 べればよい． Viσ ：Rx, Ryが一様乱数より一様乱数． V₀μ： 値域が一点集合より一様乱数． V_iμ：R₀, R₁, R₂が一様乱数より一様乱数． 補題により，ShareおよびMul単体が安全であることが示された．次にこれらが複合され た場合の一様乱数性について考える．複合プロトコルはある時点までのVIEWおよび定数 を入力としてさらに基本プロトコルを行うことで生成される．このときVIEWはその時点 のVIEWにそのまま次の処理のVIEWが直積として追加される．

まずP0のVIEWについて考える．P0のVIEWはShareに関するもののみであり，元 の入力aがk種類とすれば，複合プロトコルにおけるP₀のVIEWはShareのVIEWの直 積(Rx,1, Ry,1, . . . , Rx,k, Ry,k)である．各Rx,1, . . . , Ry,kは互いに独立な一様乱数であり， P0のVIEWも一様乱数であることが分かる．

エラー検出可能な軽量 3 パーティ秘匿関数計算 あることを示す． (1) Share実行後，すなわちP₁, P₂にaのシェアが入力された状態を初期状態とする．こ のときVIEW1, VIEW2は一様乱数である． (2)実行回数がi回以下の任意の複合プロトコルに対するVIEW1, VIEW2 が一様乱数で あると仮定する．実行回数がi + 1の複合プロトコルを考えると，実行回数i回のある複 合プロトコルが存在して，そのVIEWをVIEWi 1, VIEWi2 とおけば，両者は一様乱数で ある．また入力の確率変数をA，i回の実行および秘匿処理に使用された乱数をまとめて Rとおけば，乱数生成以外の処理は決定的であるから，ある決定的関数v1, v2が存在して v₁(A, R) = VIEWi 1, v2(A, R) = VIEWi2であり，i + 1回目の実行の入力に関しても同様に A，Rの決定的関数で表すことができる．よって実行後のVIEWをVIEWi+1

1 , VIEWi+12

とおけば，両者は次のように表される．

(I) i + 1回目が秘匿処理の場合 秘匿処理の入力をa(A, R)とおけば

VIEWi+1₁ = (v₁(A, R), V₁σ(a(A, R))) VIEWi+1₂ = (v2(A, R), V₂σ(a(A, R))) (II) i + 1回目が乗算処理の場合

乗算処理の入力をa₀(A, R), a₁(A, R), a₂(A, R), b₀(A, R), b₁(A, R), b₂(A, R)とおけば

VIEWi+1₁

= (v1(A, R), V₁μ(a0(A, R), a1(A, R), a2(A, R), b0(A, R), b1(A, R), b2(A, R))) VIEWi+1₂

= (v₂(A, R), V₂μ(a₀(A, R), a₁(A, R), a₂(A, R), b₀(A, R), b₁(A, R), b₂(A, R)))

次にVIEWi+1₁ = (v1(A, R), V₁σ(a(A, R)))が一様乱数であることを示す．その他の3つ の場合も同様に証明すればよい．

関数vY の値域集合をDvとおけば，任意のd1 ∈ Dv, d2 ∈ (Z/mZ)2に対して以下のよ

うにPr(VIEWi+1

1 = (d1, d2))が等しいことが分かり，一様乱数性が示される．

Pr(VIEWi+1₁ = (d₁, d₂)) = Pr((v(A, R), V₁σ(a(A, R))) = (d₁, d₂))

= Pr(v(A, R) = d₁)Pr(V₁σ(a(A, R)) = d₂|v(A, R) = d₁) = 1 |Dv| Pr(V₁σ(a(A, R)) = d2|(A, R) ∈ v−1({d1})) = 1 |Dv|



r∈v−1({d1}) Pr(V₁σ(a(A, R)) = d2|(A, R) = r) = 1 |Dv|



r∈v−1({d1}) Pr(V₁σ(a(r)) = d2) = 1 m2|Dv|

よって帰納法の仮定により，任意の有限回のShare，Mulの実行についてVIEW₁, VIEW₂

は一様乱数である． 4.3 エラー検出 3.5節で与えたエラー検出手続きVerif，BitShareについて以下がいえる． 定理4.2. mを素数とする．このとき，MulにおいてP₁, P₂は正しく処理を行い，P₀は P₁またはP₂にエラーを起こす不正値を送信した場合，Verifは(m− 1)/m以上の確率で falseを返す． Proof. P1, P2はf + g= 0のときエラー検出することから，P0は少なくとも s(˜c₀+ ˜c₁+ ˜c₂)≡ ˜e₀+ ˜e₁+ ˜e₂ (mod m) (2) を満たすci, ejの不正値c˜i, ˜ej（0 ≤ i, j ≤ 2）を生成しない限りエラーを起こすこと はできない．いま本来の値とエラーを起こす不正値の差分をΔc = c− (˜c0 + ˜c1+ ˜c2), Δe = sc− (˜e0+ ˜e1+ ˜e2)とおくと，式(2)は s(c− Δc) ≡ sc − Δe (mod m) sΔc≡ Δe (mod m) (3) とできる．するとmが素数であることから

Δc mod m = 0⇔ Δe mod m = 0

が成り立ち，Δc, Δeのいずれかが0となる場合はエラーを起こすことができない．一方 Δc mod m= 0の場合，P0がsを推定できないのは明らかなことから，Δeが式(3)を満 たす確率はたかだか1/mとなる．Δe mod m= 0の場合も同様である． 定理4.3. mを素数とし，P₀, P₁, P₂の少なくとも2つは正しくBitShare，EqTestおよび Xorを実行するものとする．このとき，BitShareの処理が正しく終了したならば，Piの出 力は(m− 1)/m以上の確率で0または1のシェアとなる．

Proof. 一般性を失うことなくP1, P2 はBitShare，EqTestおよびXorを正しく実行し，

BitShareの処理が正しく終了したものとする．このときBitShareのステップ( 1 )において P₀がP₁，P₂に送信したデータをそれぞれ(b∗_0,0, b∗_0,1, b∗_0,2), (b∗∗_0,2, b∗∗_0,0)とすると，ステップ

( 2 )，( 3 )よりb∗₀ := b∗_0,0+ b∗_0,1+ b∗_0,2 ∈ {0, 1}, b∗_0,0 = b∗∗_0,0, b∗_0,2 = b∗∗_0,2が成り立ち，ス テップ( 3 )でj = 0について Pi が持つシェアは[b0∗]i = (b∗j,i, b∗j,i+1) と見なすことがで

エラー検出可能な軽量 3 パーティ秘匿関数計算 きる．j = 1, 2についてはP₁, P₂ が正しく実行することを仮定しているため，Piが持つ シェアはbj= bj,0+ bj,1+ bj,2∈ {0, 1}となる[bj]i= (bj,i, bj,i+1)と見なすことができる． BitShareのステップ( 4 )のXorの実行は，定理 4.2より，(m− 1)/m以上の確率で正し くb∗₀⊕ b1⊕ b2のシェアを返すか，異常終了⊥を返す．したがってb∗₀, b1, b2∈ {0, 1}より BitShareのPiの出力は(m− 1)/m以上の確率で0または1のシェアとなる．

5. 実 装 評 価

本章では3章で与えた提案方式を実装した結果について報告する．提案方式の基本プロト コルのうち，Share，Decは単純な秘密分散およびその復元処理であり，Add/Sub，CoMul

は通信をともなわず，固定長（=|m|）演算の影響を無視すれば，各主体から見れば通常の 加減算，定数倍演算の2倍程度の処理である．このような理由から，Mulにエラー検出Verif （3.5節）を付加した演算に特化して実装評価を行った． 測定環境は表1のとおりである．mは32ビットの素数（m = 4,294,967,291）とし，測 定値は3回実行した値の平均である．nは入力数で，並列に処理できるものとする．なお初 期化等の時間を除くため，n入力の実行を10回および20回繰り返して測定し，それらの 測定値を引いた値に10を割った値を最終的な測定値としている．測定結果を表2に示す． 次に通信量について評価する．Mul，Verifはそれぞれおよそ6|m|，22|m|ビットの通信 を必要とする．すなわちエラー検出付き乗算1回あたりおよそ28|m|ビットの通信を必要 表1 測定環境 Table 1 Test environment.

PC 1 台構成

CPU Intel Core2 Quad 3.0 GHz RAM 4 GB

OS Debian 5.0.6 言語 C++ コンパイラ g++ 4.3.2

表2 エラー検出付き乗算（Mul および Verif）

Table 2 Running time of three-party secure multiplication with error detection (Mul and Verif). 入力数n 測定値（秒） 1,000 0.0103 10,000 0.0337 100,000 0.1595 1,000,000 1.5934 とし，mを32ビットとすればおよそ112バイトとなる．一方，表2のn = 1,000,000の 結果から，1秒間におよそ628,000回の乗算を処理できるとすれば，それにともなう通信量 はおよそ70メガバイトと見積もることができる．したがって広域通信においては，FTTH

（Fiber To The Home）やFWA P-P（Fixed Wireless Access Point to Point）のような 高速回線を利用しない限りは通信が大きなボトルネックになるものと考えられる．

6. 考

察

本章では提案方式をプライバシ保護データマイニング技術として利用する場合の運用モ デルの考察を行う． 提案方式は3主体の協調計算により，主体間の結託はないと仮定したとき，semi-honest モデルにおいて入力値を秘匿しつつ各種計算を効率良く実行し，maliciousモデルにおいて エラー検出できる特徴を持つことを示した．2主体が保持する情報を用いてプライバシ保護 データマイニングを行う場合は，図1のように第三者機関を介入させた構成（第三者機関 介入型）があげられる．すなわち，2つの情報保持主体と第三者機関による3主体によって 提案方式を実行する．最終的に計算結果を復元するのは各情報保持主体とすればよい．各情 報保持主体は保持情報を自身を含めた3主体に秘密分散する．なお各情報保持主体から見 れば，第三者機関と他の情報保持主体の結託により保持情報が知られうるため，第三者機関 はプライバシ保護データマイニングをサポートするサービス主体として社会的信頼を得て いることが望ましい． 第三者機関介入型と同様の主体構成として，情報保持主体とは異なる分析主体を第三者機 関と置き換えてもよい（図2）．この場合，どちらかの情報保持主体が計算結果の復元に必 要なシェアを分析主体に送信することで，分析主体のみ計算結果を復元することができる． 3主体が保持する情報を用いてプライバシ保護データマイニングを行う場合は，図3のよ 図1 第三者機関介入型

エラー検出可能な軽量 3 パーティ秘匿関数計算

図2 分析主体介入型

Fig. 2 System configuration consisting of two data holders and an analyst.

図3 全参加型

Fig. 3 System configuration consisting of three data holders.

図4 計算委託型

Fig. 4 System configuration consisting of many data holders and three third parties.

うに提案方式の直接的な利用（全参加型）があげられる．ただし他の情報保持主体の結託に より保持情報が知られうるため，図4のように3つの異なる第三者機関に保持情報を秘密 分散して提供し，計算を委託する主体構成（計算委託型）も考えられる．計算委託型の場合 は，秘匿関数計算を実行する2主体が結託しなければよいため，秘匿関数計算を実行する主 体の1つは情報保持主体や分析主体としてもよい．4以上の主体が保持する情報を用いてプ ライバシ保護データマイニングを行う場合は，3主体の場合と同様に図4の主体構成を適用 できる． 一方，複数の情報保持主体のデータを統合するプライバシ保護データマイニングに必要と される演算種別は文献1)に詳しい．文献1)では水平分割データ（Horizontally Partitioned Data）と垂直分割データ（Vertically Partitioned Data）にデータ統合モデルが分類され ているが，多くの演算は共通しており，相関ルールマイニング，決定木分類，EMクラスタ リング，K-NN分類，単純ベイズ分類器，サポートベクタマシン等のアルゴリズムが例示さ れている．ただしこれらのアルゴリズムは分析精度を高めるための工夫が施される等，統一 されていない場合もあり，そのような場合において，汎用的に適用できる秘匿関数計算は有 用といえる．

7. お わ り に

個人に関する情報の保護と利活用を両立させる汎用的なプライバシ保護データマイニング に資する要素技術として，3主体の協調計算により，主体間の結託はないと仮定したとき， semi-honestモデルにおいて入力値を秘匿でき，maliciousモデルにおいて演算結果の改竄 （エラー）を従来よりも効率良く検出できる3パーティ秘匿関数計算プロトコルを提案した． 提案方式は，情報理論的安全性に基づく秘匿関数計算において一般に処理時間の最小化が期 待できるn = 3に特化して，従来のゼロ知識証明技術を用いずに軽量にエラー検出できる 汎用の秘匿関数計算である．提案方式の効率に関しては，汎用PCを用いた実装評価によ り，32ビット乗算1回を約1.6 μ秒で処理できることを確認した． 謝辞 提案方式の安全性評価に関する記述の不備等について，ご指摘およびコメントいた だきました査読者の方々に深く感謝いたします．

参 考 文 献

1) Aggarwal, C.C. and Yu, P.S.: Privacy-Preserving Data Mining: Models and

Algo-rithms, ISBN 978-0-387-70991-8, Springer-Verlag (July 2009).

2) Algesheimer, J., Camenisch, J. and Shoup, V.: Efficient computation modulo a shared secret with application to the generation of shared safe-prime products,

CRYPTO 2002, LNCS 2442, pp.417–432, Springer-Verlag (2002).

3) Ben-Or, M., Goldwasser, S. and Wigderson, A.: Completeness theorems for non-cryptographic fault-tolerant distributed computation, STOC ’88, pp.1–10, ACM

エラー検出可能な軽量 3 パーティ秘匿関数計算

Press (1988).

4) Bogdanov, D., Laur, S. and Willemson, J.: Sharemind: A framework for fast privacy-preserving computations, ESORICS 2008, LNCS 5283, pp.192–206 (2008). 5) Chaum, D., Crepeau, C. and Damg˚ard, I.: Multiparty unconditionally secure

pro-tocols, STOC ’88, pp.11–19, ACM Press (1988).

6) 千田浩司，濱田浩気，五十嵐大，高橋克巳：軽量検証可能3パーティ秘匿関数計算の 再考，CSS2010 (2010).

7) 千田浩司，五十嵐大，高橋克巳：効率的な3パーティ秘匿関数計算の提案とその運用 モデルの考察，情報処理学会研究報告，第48回CSEC研究会(2010).

8) Cramer, R., Damg˚ard, I. and Nielsen, J.B.: Multiparty computation from threshold homomorphic encryption, EUROCRYPT 2001, LNCS 2045, pp.280–300, Springer-Verlag (2001).

9) Damg˚ard, I., Fitzi, M., Kiltz, E., Nielsen, J.B. and Toft, T.: Unconditionally se-cure constant-rounds multi-party computation for equality, comparison bits and exponentiation, TCC 2006, LNCS 3876, pp.285–304, Springer-Verlag (2006). 10) Electronic Health Information Laboratory – KnowledgeBase, available from

http://www.ehealthinformation.ca/knowledgebase/ (accessed 2011-08-06).

11) FairplayMP, available fromhttp://www.cs.huji.ac.il/project/Fairplay/ fairplayMP.html (accessed 2011-08-06).

12) Feldman, P.: A practical scheme for non-interactive verifiable secret sharing, FOCS

’87, pp.427–437, IEEE Press (1987).

13) Gentry, C.: Fully homomorphic encryption using ideal lattices, STOC ’09, pp.169– 178, ACM Press (2009).

14) Geographic Privacy-aware Knowledge Discovery and Delivery, available from

http://www.geopkdd.eu/ (accessed 2011-08-06).

15) Goldreich, O.: Secure Multi-Party Computation (Final (incomplete) Draft, Version 1.4), Working Draft, June 1998, revised October 27 (2002).

16) Goldreich, O.: Foundations of Cryptography, Vol.2, Cambridge University Press (2004).

17) Goldreich, O., Micali, S. and Wigderson, A.: How to play any mental game, or a completeness theorem for protocols with honest majority, STOC ’87, pp.218–229, ACM Press (1987).

18) 五十嵐大，千田浩司，高橋克巳：高効率3パーティ秘匿関数計算の情報理論的安全性， 情報処理学会研究報告，第50回CSEC研究会(2010).

19) Jakobsson, M. and Juels, A.: Mix and match: Secure function evaluation via ci-phertexts, ASIACRYPT 2000, LNCS 1976, pp.162–177, Springer-Verlag (2000). 20) Lindell, Y. and Pinkas, B.: Privacy preserving data mining, CRYPTO 2000, LNCS

1880, pp.36–54, Springer-Verlag (2000).

21) Nishide, T. and Ohta, K.: Multiparty computation for interval, equality, and com-parison without bit-decomposition protocol, PKC 2007, LNCS 4450, pp.343–360, Springer-Verlag (2007).

22) Pinkas, B., Schneider, T., Smart, N.P. and Williams, S.C.: Secure two-party com-putation is practical, ASIACRYPT 2009, LNCS 5912, pp.250–267, Springer-Verlag (2009).

23) Schoenmakers, B. and Tuyls, P.: Practical two-party computation based on the conditional gate, ASIACRYPT 2004, LNCS 3329, pp.119–136, Springer-Verlag (2004).

24) Schoenmakers, B. and Tuyls, P.: Efficient binary conversion for Paillier encrypted values, EUROCRYPT 2006, LNCS 4004, pp.522–537, Springer-Verlag (2006). 25) SecureSCM Project, available fromhttp://www.securescm.org/

(accessed 2011-08-06).

26) Shamir, A.: How to share a secret, Comm. ACM, Vol.22, No.22, pp.612–613 (1979). 27) Shannon, C.E.: Communication theory of secrecy system, ACM Trans. Knowledge

Discovery from Data, Vol.28, No.4, pp.656–715 (1949).

28) Sharemind, available fromhttp://research.cyber.ee/sharemind/ (accessed 2011-08-06).

29) 柴田賢介，千田浩司，五十嵐大，山本太郎，高橋克巳：表計算ソフトをフロントエン ドとした委託型2パーティ秘匿回路計算システム，CSS2009 (2009).

30) Vaidya, J., Clifton, C.W. and Zhu, Y.M.: Privacy Preserving Data Mining, ISBN 0-387-25886-8, Springer-Verlag (Nov. 2005).

31) VIFF, the Virtual Ideal Functionality Framework, available fromhttp://viff.dk/. 32) Yao, A.C.: Protocols for secure computations, FOCS ’82, pp.160–164, IEEE Press

(1982).

33) Yao, A.C.: How to generate and exchange secrets, FOCS ’86, pp.162–167, IEEE Press (1986). 34) 健康情報活用基盤構築のための標準化及び実証事業， 入手先https://microsite.accenture.com/meti/Pages/default.aspx （参照2011-08-06）. 35) 情報大航海プロジェクト，入手先http://www.meti.go.jp/policy/it policy/ daikoukai/igvp/index/（参照2011-08-06）. 36)「地理空間情報サービス産業の将来ビジョン」及び「G空間プロジェクト」の公表につ いて（METI/経済産業省），入手先http://www.meti.go.jp/press/20080703007/ 20080703007.html（参照2011-08-06）. 37) 日本ユニシスグループ：最新技術によるクラウド型iDC基盤強化と新サービス発表—

クラウド型iDCでは日本初，「ストレージクラウドTM」「Inter iDC」の最先端技術

エラー検出可能な軽量 3 パーティ秘匿関数計算 （参照2011-08-06）. 38) 秘密分散技術を用いて重要情報を保護するデータ管理サービスを2010年秋に提供開 始—データ管理サービスの実証実験を開始(2010年1月13日), 入手先http://www.nri.co.jp/news/2010/100113.html（参照2011-08-06）. 39)「S.T.E.P分散ストレージサービス」の提供開始について(2010年7月29日), 入手先http://www.sptvjsat.com/images/jp/news release/1371/ 100729 stepbunsansutore-jisa-bisuteikyoukaishi%282%29.pdf（参照2011-08-06）. (平成22年12月2日受付) (平成23年 6 月3日採録) 千田 浩司（正会員） 平成12年早稲田大学大学院理工学研究科数理科学専攻修士課程修了． 同年日本電信電話株式会社（NTT）入社．博士（工学）．現在，プライバ シ保護技術，暗号応用技術の研究開発に従事．平成13年電子情報通信学 会SCIS論文賞受賞．電子情報通信学会会員． 五十嵐 大（正会員） 平成20年東京大学大学院情報理工学系研究科コンピュータ科学専攻博 士前期課程修了．同年日本電信電話株式会社（NTT）入社．日本ソフト ウェア科学会会員． 濱田 浩気（正会員） 平成19年京都大学工学部情報学科卒業．平成21年同大学大学院情報 学研究科通信情報システム専攻博士前期課程修了．同年日本電信電話株式 会社（NTT）入社．現在，プライバシ保護技術，暗号応用技術の研究開 発に従事． 高橋 克巳（正会員） 昭和63年東京工業大学理学部数学科卒業．平成18年東京大学大学院 情報理工学系電子情報学専攻博士課程修了．昭和63年日本電信電話株式 会社入社．以来，情報検索，データマイニング，プライバシ保護データ処 理，暗号，情報セキュリティ，セキュリティ社会科学の研究開発に従事． 博士（情報理工学）．平成12年度本会論文賞．電子情報通信学会会員．