エラー検出可能な軽量3パーティ秘匿関数計算の提案と実装評価

全文

(1)情報処理学会論文誌. Vol. 52. No. 9. 2674–2685 (Sep. 2011). エラー検出可能な軽量 3 パーティ秘匿関数計算の提案と実装評価1. 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）への適用について考察を行う．. ライバシへの配慮がいっそう重要な課題となっている．その中で最近では情報を複数個所に分散させて情報漏洩を防ぐ秘密分散技術26) の実用化が国内においても進みつつある37)–39) ．さらに分散された情報を復元することなく意中の演算結果を導く暗号プロトコル3),5) についても実用化を見据えた開発プロジェクトの動きが見られる11),25),28),31) ．特定のデータを秘匿しつつ意中の演算結果を導く技術は秘匿計算（Secure Computation）や秘匿関数計算（Secure Function Evaluation）と呼ばれ，2 章で述べるように様々な手法が提案されている．秘密分散技術は情報の保管時のセキュリティ対策としては有効だが，利用時は一般に復元する必要があるため漏洩リスクが高まる．これに対し文献 3)，5) に代表される秘密分散に基づく秘匿関数計算は，本来の入力値の代わりに分散された情報を計算の入力とすることができ，計算過程においても本来の入力値がいっさい復元されないため，秘密分散技術の機能を利用時も維持したより高度なセキュリティ技術といえる．しかし分散データを保有する複数の主体が通常よりも膨大な計算を必要とし，主体間で大量のデータ通信をともなう場合も. 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 exists honest majority, the proposed protocol obtains the outcome of arithmetic and/or logic operations from three-shared values without disclosing the original 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 implementation 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.. 2674. あるため，現時点での実利用は限定的といえる．一方，個人情報保護やプライバシの観点から，国内外において法制度・ガイドラインや標準化の整備とともに，個人に関する情報を安全に利活用するための技術的対策が検討されている10),14),34)–36) ．現在検討されている主な技術的対策は，いわゆる広義の匿名化である．すなわち，個人に関する情報が個人と結び付くことのないように情報を加工する手段全般である．しかし一般に匿名化による対策は，情報の利用が限定的になることに加え，個人に関する情報が個人と結び付かないことの保証が容易ではない．その理由の 1 つとして，個人に関する情報と個人の結び付けが，あらかじめ備えている知識や情報に大きく左右されることがあげられる．たとえば，氏名，住所，年齢，性別，職業，購買履歴（日時，店舗名，商品名）からなるデータをマーケティング用途に氏名，住所を ID 番号に置き換えて第三者提供や一般公開を行った場合，年齢，性別，職業，および一部の購買履歴から ID 番号に対応する個人を †1 NTT 情報流通プラットフォーム研究所 NTT Information Sharing Platform Laboratories 1 本稿は文献 6)，7)，18) の内容を含む．. c 2011 Information Processing Society of Japan .

(2) 2675. エラー検出可能な軽量 3 パーティ秘匿関数計算. 特定できる者がいないとも限らず，その ID 番号から特定の個人の購買履歴がすべて紐付い. 提案方式は，情報理論的安全性に基づく秘匿関数計算において一般に処理時間の最小化が期. てしまう可能性があり，これはプライバシの観点から望ましくない．このように，個人に関. 待できる n = 3 に特化して，主体間の結託はないと仮定したとき，malicious モデルにおい. する情報をどの程度まで開示可能かという問題は，情報の利活用と保護の両方の観点から慎. て従来のゼロ知識証明技術を用いずに軽量にエラー検出を可能とし，semi-honest モデルに. 重に考える必要があるといえる．そして当該開示問題の有力な解決手段として，秘匿関数計. おいて入力値の秘匿性を保証する汎用の秘匿関数計算である．. 算が近年注目されている．特に情報を保護しつつデータマイニングを行う技術の総称である. 以降，2 章で関連研究を紹介し，3 章で提案方式について説明する．提案方式の安全性お. プライバシ保護データマイニング（Privacy-Preserving Data Mining）は，Lindell らによ. よび実装評価をそれぞれ 4，5 章で示し，6 章では 3 パーティ秘匿関数計算プロトコルの応. る研究成果20) を端緒に秘匿関数計算を利用した手法が数多く提案されている1),30) ．しかし. 用として，プライバシ保護データマイニングへの適用について考察を行う．最後に 7 章で. ながら秘匿関数計算は前述のとおり，一般に通常の演算と比べ処理時間が著しく増加し，特. 本稿をまとめる．. にデータマイニングは入力データ数や計算量が膨大となる場合があるため，秘匿関数計算を利用する場合は処理時間の軽減が特に大きな課題となる．なお本稿では，情報を保護しつつ統計処理を行うための技術も合わせてプライバシ保護データマイニングと呼ぶことにする1 ．. 2. 関連研究秘匿関数計算は一般に，意中の演算の入力値を秘匿処理したうえで提供する主体と，そ. 上述の状況をふまえ，本稿では，軽量かつ汎用の秘匿関数計算を提案し，実装評価により. の入力値を復元することなく処理する主体の少なくとも 2 主体が関与し，秘匿方法は暗号. その有用性を検証する．対象とする演算を限定して処理軽減を図る方式は数多く提案され. 化や秘密分散が代表的である．その概念および具体的な実現方法は Yao によって提案され. ているものの，代表的な演算への適用にとどまっているのが現状である．提案方式は，3 主. た32),33) . Yao の手法は，論理回路演算を実行可能な状態のまま秘匿する主体と，その秘匿. 体の協調計算により入力値を秘匿しつつ各種演算を効率良く実行し，主体間の結託はない. された論理回路演算を実行する主体によって構成され，実行には複数主体の協調計算が必. と仮定したとき，semi-honest モデルにおいて入力値を秘匿でき，malicious モデルにおい. 要なことからマルチパーティプロトコルとも呼ばれる（2 主体に特化した方式は区別して 2. て演算結果の改竄（エラー）を従来よりも効率良く検出できるという特徴を持つ．これに. パーティプロトコルと呼ぶ場合が多い）．論理回路演算を実行するマルチパーティプロトコ. よりウィルス感染や操作ミス，内部不正等の早期発見および対策に有効と考えられる．秘. ルとして，紛失通信（Oblivious Transfer）を利用した方式17) や，MIX-net を利用した方. 密分散を拡張した秘匿関数計算，すなわち情報理論的安全性に基づく秘匿関数計算は少な. 式19) 等が提案されている．なお論理回路演算の実行を可能とする秘匿関数計算は秘匿回路. くとも 3 以上の主体を必要とし，主体数を n としたとき閾値 t（< n/2）以下の結託に耐. 計算（Secure Circuit Evaluation）と呼ばれる．特に最近では秘匿回路計算の実行を単独で. 性を持つよう設計される. 15). ．攻撃者は semi-honest および malicious のモデルに分類され，. 行うことを可能とする準同型暗号が注目を集めている13) ．また Yao の手法に基づく 2 パー. semi-honest モデルでは，攻撃者は正しくプロトコルを実行した主体の閾値以下のログから. ティプロトコル22) や，それを計算委託型に変形した 2 パーティプロトコル29) 等の実装報. 入力値を得ようとし，malicious モデルでは，攻撃者は閾値以下の主体を自由に操作して入. 告もみられるようになり，実用に向けた動きが加速しつつある．ここで計算委託型とは，入. 力値の取得や演算結果の改竄（エラー）といった不正を試みる．既存技術として，より強い. 力提供主体と計算主体が異なる主体構成を指し，文献 29) では計算主体が 2 主体となる．. 攻撃モデルである malicious 攻撃の対策がいくつか知られている．文献 3) では n ≥ 4 のと. 一方，環 Z/mZ（m は適当な整数）上の算術演算を可能とする秘匿関数計算も提案され. き一般化 Reed-Solomon 符号を用いた対策が述べられている．文献 12) では任意の n（≥ 3）. ており，1 章で述べた秘密分散に基づく方式3),5) や準同型暗号に基づく方式8),23) が知られ. についてゼロ知識証明技術を用いて不正の有無を検証する方式が提案されている．しかしゼ. ている．なお秘匿回路計算は一般に処理効率が悪いため，秘匿関数計算を論理回路演算と算. ロ知識証明技術は一般に計算量・通信量が大きく，大規模や複雑な計算には適用が難しい．. 術演算に分けて全体の処理効率を上げる手法も提案されている2),9),21),24) ．以下では，提案方式同様に加法的な秘密分散に基づく既存の秘匿関数計算4) について説明. 1 最近ではより広範の技術を指す，プライバシ保護データ分析（Privacy-Preserving Data Analysis）やプライバシ保護データ活用（Privacy-Preserving Data Utilization）といった用語も見受けられる．. 情報処理学会論文誌. Vol. 52. No. 9. 2674–2685 (Sep. 2011). する．これは Sharemind と呼ばれるシステム28) の要素技術であり，提案方式同様に 3 主体による処理を基本とするが，semi-honest モデルを仮定している．文献 4) の手法は，環. c 2011 Information Processing Society of Japan .

(3) 2676. エラー検出可能な軽量 3 パーティ秘匿関数計算. Z/mZ 上で加法的に分散したデータ（シェア）について，復元することなく加算，定数倍お. 上記同様の手続きを式 (1) の. よび乗算結果のシェアを求める．そしてこれらの基本演算を組み合わせて型変換（2 進数と. ai b i +. 整数の相互変換）や大小比較等の演算を構成している．m は文献 3)，5) と異なり任意の値と. a ∈ Z/mZ としたとき，Pi が受信する a のシェアは a =. j=k. aj bk のすべての項について行い，Pi は [ab]i =. [a b ] を得る． j=k j k i. 3. 提案方式. してよく，計算効率を考慮して m = 232 としている．主体を Pi（i = 0, . . . , n − 1），入力を. n−1. . . ai を満たす ai ∈ Z/mZ，た. 提案方式は前述のとおり n = 3 に特化した方式であり，主体間の結託はないと仮定したと. だし a0 , . . . , an−1 の任意の n − 1 個の元は Z/mZ 上の互いに独立な乱数とする．加算は Pi. き，malicious モデルにおいて従来のゼロ知識証明技術を用いずに軽量にエラー検出を可能. が持つ a, b ∈ Z/mZ のシェア ai , bi から di = ai + bi を計算すればよく，. とし，semi-honest モデルにおいて入力値の秘匿性を保証する汎用の秘匿関数計算である．. i=0. n−1 i=0. di = a + b. かつ d0 , . . . , dn−1 の任意の n − 1 個の元は Z/mZ 上の互いに独立な乱数と見なせるため，. 本章ではまず semi-honest モデルにおける秘密分散・復元，加減算・定数倍，乗算，論理回. di は a + b の Pi のシェアとなっていることが分かる．定数倍については入力を a のシェア. 路演算の順に提案方式を説明する．次に malicious モデルにおけるエラー検出手続きを与え. および定数 c としたとき，Pi の ac のシェアは cai とすればよい．. る．なお本手続きは従来のゼロ知識証明技術と異なり，エラーを起こした主体を特定するこ. 次に，文献 4) における乗算について説明する．加算および定数倍は各主体が通信することなくシェアを計算できるが，乗算は通信をともなう．文献 4) では，Pi の入力を a =. b=. n−1 i=0. ab =. n−1 i=0. とはできない．したがっていずれかの主体が（事実にかかわらず）エラー検出を主張した時. ai ,. 点でプロトコルは途中終了する．最後に，文献 9) で提案された手法に基づき，エラー検出. bi のシェア ai , bi ∈ Z/mZ としたとき，. n−1 . ai b i +. i=0. . 可能な型変換の手続きを与える．これらの安全性評価は 4 章で論じる．. 3.1 秘密分散・復元 aj b k. 入力 a ∈ Z/mZ の秘密分散は，Pi が持つシェアを [a]i = (ai , ai+1 ) とする．なお記述. (1). j=k. の簡略化のため，i ± 1 は 3 で割った余りと見なす．すなわち，たとえば i = 2 であれば. となり，特に任意の α, β ∈ Z/mZ について. ai+1 = a0 である．いま a を入力として Pi が [a]i を得る手続きを Share としたとき，Share. aj bk = −(aj + α)(bk + β) + aj (bk + β) + (aj + α)bk + αβ. は任意の主体が実行してよく，Pi のいずれかでもよいし，それ以外の外部の主体でもよい．. を満たすことを利用する．たとえば n = 3 としたとき，式 (1) の項 a0 b1 を次のように分散する．なお以降 Pi の入力または出力が x であることを Pi (x) で表し，Pi が持つ x のシェアを [x]i で表す．. P0 , P1 が持つ値の乗算結果を P0 , P1 , P2 に分散. . 具体的な手続きは次のようになる． Share：2-out-of-3 秘密分散. . 入力：a ∈ Z/mZ 出力：Pi ([a]i ). 入力：P0 (a0 ), P1 (b1 ). (1). a0 , a1 ∈ Z/mZ をランダムに選択する．. 出力：P0 ([a0 b1 ]0 ), P1 ([a0 b1 ]1 ), P2 ([a0 b1 ]2 ). (2). a2 := a − a0 − a1 を計算する．. (3). i = 0, 1, 2 について，[a]i := (ai , ai+1 ) として Pi に送信する．. (1). P2 は α, β ∈ Z/mZ をランダムに選択してそれぞれ P0 , P1 に送信し， [a0 b1 ]2 := αβ を計算する．. (2). P0 , P1 はそれぞれ a0 + α, b1 + β を計算して P1 , P0 に送信する．. (3). P0 , P1 はそれぞれ [a0 b1 ]0 := −(a0 + α)(b1 + β) + a0 (b1 + β), [a0 b1 ]1 := (a0 + α)b1 を計算する．. . 情報処理学会論文誌. Vol. 52. No. 9. 2674–2685 (Sep. 2011). . . a = a0 + a1 + a2 より，任意の異なる 2 つの [a]i から a を復元できる．また明らかに任意の [a]i から a は復元できない，すなわち 2-out-of-3 秘密分散の性質を有している．なお復元処理は各主体が持つシェアの冗長性によりエラー検出が可能である．具体的には次の手. 続き Dec のようにすればよい．. c 2011 Information Processing Society of Japan .

(4) 2677. エラー検出可能な軽量 3 パーティ秘匿関数計算. Dec：2-out-of-3 秘密分散のエラー検出を含む復元. Mul：a, b のシェアから ab のシェアを生成. 入力：Pi ([a]i ). 入力：Pi ([a]i , [b]i ). 出力：a or ⊥. 出力：Pi ([ab]i ). (1). Pi は (αi , βi ) := (ai , ai+1 ) を開示する．. (1). (2). i = 0, 1, 2 について βi = αi+1 となる βi , αi+1 が存在すれば，異常を示す ⊥ を. c1 := (a0 + a1 )(b0 + b1 ) − r1 − r2 − c0 を計算して P1 , P2 にそれぞれ (r1 , c1 ),. 返して終了する．. (r2 , c0 ) を送信し，[ab]0 := (c0 , c1 ) とする．. (3). a = α0 + α1 + α2 を計算する．. . (2). . 3.2 加減算・定数倍. (3). P1 , P2 はそれぞれ y := a1 b2 + a2 b1 + r1 , z := a2 b0 + a0 b2 + r2 を計算して P1 , P2 は c2 := y + z + a2 b2 を計算してそれぞれ [ab]1 := (c1 , c2 ), [ab]2 := (c2 , c0 ) とする．. . . シェアの正当性について，. 入力：Pi ([a]i , [b]i ). c0 + c1 + c2 = (a0 + a1 )(b0 + b1 ) − r1 − r2 + y + z + a2 b2. 出力：Pi ([a ± b]i ). • Pi は [a ± b]i := (ai ± bi , ai+1 ± bi+1 ) を計算する．. CoMul：a のシェアおよび定数 c から ac のシェアを生成. = (a0 + a1 )(b0 + b1 ) + a1 b2 + a2 b1 + a2 b0 + a0 b2 + a2 b2. . 入力：Pi ([a]i ), c. = (a0 + a1 + a2 )(b0 + b1 + b2 ) = ab となり，c0 , c1 , c2 の任意の 2 つの元は Z/mZ 上の互いに独立な乱数と見なせるため，c0 ,. c1 , c2 は正しく ab のシェアとなっていることが分かる．. 出力：Pi ([ca]i ). • Pi は [ca]i := (cai , cai+1 ) を計算する．. . 3.3 乗. P0 は r1 , r2 , c0 ∈ Z/mZ をランダムに選択してから，. P2 , P1 に送信する．. 加減算や定数倍演算はそれぞれ以下の Add/Sub，CoMul により実現される．. Add/Sub：a, b のシェアから a ± b のシェアを生成. . 算. 乗算は文献 3)，4) 等と同様に各主体の協調計算が必要となる．手続き Mul は次のように. 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]2 := (−a2 , 1 − a0 ) を計算する．. . 論理積，論理和，および排他的論理和は，a, b ∈ {0, 1} についてそれぞれ. • a ∧ b = ab. 情報処理学会論文誌. Vol. 52. No. 9. 2674–2685 (Sep. 2011). c 2011 Information Processing Society of Japan . .

(5) 2678. エラー検出可能な軽量 3 パーティ秘匿関数計算. • a ∨ b = a + b − ab. 仮定し，P1 , P2 のみが知る乱数を用いて P0 に特別な処理を行わせる．具体的には，乱数. • a ⊕ b = a + b − 2ab. を s として [a], [b] から [ab] を得るとともに [sa], [b] から [sab] を求める手続きを行う．そ. となるから，a, b ∈ {0, 1} のシェアについて加減算 Add/Sub，定数倍 CoMul，および乗. して P1 , P2 は，[ab], [sab] の復元結果が s 倍の関係になっているかどうか，それらを復元. 算 Mul を適用すればよい．具体的には以下のようになる．なお以降，x のシェアの組を. せずに検証し，s を知らない P0 がそのような関係を保ちながらエラーを起こすことを困難. [x] := ([x]0 , [x]1 , [x]2 ) と表記する．. とする．ただしすでに述べたとおり提案方式はエラー検出のみを保証し，エラーを起こした. • 論理積：And([a], [b]) := Mul([a], [b]). 主体は特定できない．. • 論理和：Or([a], [b]) := Sub(Add([a], [b]), Mul([a], [b])). 以下同様の特別な処理を P1 , P2 それぞれにも行わせることで，すべての主体に対するエ. • 排他的論理和：Xor([a], [b]) := Sub(Add([a], [b]), CoMul(Mul([a], [b]), 2)). ラー検出を行う．以下に一般性を失うことなく，P1 , P2 は正しいと仮定した場合のエラー. 3.5 エラー検出. 検出の手続きを与える．. 3.1∼3.4 節で与えた semi-honest モデルを仮定した方式は，Pi のいずれかの主体が不正. Verif：[c] ← Mul([a], [b]) におけるエラー検出. 値を他の主体に送信することでエラーを起こすことが可能となるだけでなく，不正値を受信. 入力：Pi ([a]i , [b]i , [c]i ) ただし P0 が正しければ c = ab. した主体が，その不正値に基づく何らかの計算結果を不正な主体に与えることで入力値の秘. 出力：true/false. 匿性が損なわれる可能性がある．一方，3.1∼3.4 節で与えた手続きのうち，各主体が不正値. (1). を他の主体に送信する機会は秘密分散 Share，および乗算 Mul 実行時のみとなる．以下では. (2). malicious モデルにおける Share および Mul のエラー検出について考える．まず Share におけるエラー検出手続きとして，複数の主体が共有しているシェアが一致し. P1 , P2 はそれぞれ (Share(sa1 ), Share(sa2 )), Share(sa0 ) を実行し，Pi はわち d := sa のシェアを得る．. . 入力：Pi ([a]i ). (3) (4). . 出力：true/false. (1). P1 , P2 は s ∈ Z/mZ をランダムに選択する． (di , di+1 ) := ((sa0 )i + (sa1 )i + (sa2 )i , (sa0 )i+1 + (sa1 )i+1 + (sa2 )i+1 )，すな. ているかどうか確認する手続き EqTest を与える．. EqTest：複数の主体が共有しているシェアの一致性検証. Mul([d], [b]) を実行し，Pi は e := db = sab のシェア (ei , ei+1 ) を得る． P1 , P2 はそれぞれ f := sc1 + sc2 − e1 − e2 , g := sc0 − e0 を計算して互いに送信し，f + g = 0 であれば true を，そうでなければ false を返す．. (2). Pi は αi = ai であれば 1 を，そうでなければ 0 を開示する．. (3). すべての Pi から 1 が開示されれば true を，そうでなければ false を返す．. を損ねることもない．. EqTest の ( 2 ) において，Pi は偽の結果を開示する不正が考えられるが，これは結局，自. . 上記手続き Verif が正しく実行され，入力も正しければ，f + g = s(c0 + c1 + c2 ) − (e0 +. Pi は αi+1 := ai+1 を Pi+1 に送信する．. e1 + e2 ) = sc − sab = 0 より上記手続きは true を返し，P1 , P2 に対して g, f から秘匿性. . . . ここで Verif の特徴および効率について，1 章で触れた n = 3 に適用可能なゼロ知識証明技術12) と比較しながら簡単に考察を与える．Verif は乱数生成および単純な積和演算からな. 身が保持するシェアを書き換える操作に等しく，EqTest におけるエラーとは見なさない．す. り，群位数 m は適当な素数であればよく，5 章で紹介する実装評価では m を 32 ビットの. なわち，たとえば EqTest 実行後に Dec を実行する場合，偽の結果を開示することで Dec. 素数としている．一方，文献 12) の方式は準同型暗号を用いた計算量仮定に基づく方式であ. 実行時にエラー検出されるか，エラー検出されないように Dec 実行前に正しいシェアに書. り，準同型暗号が安全となるような群上（たとえば群位数が 1,024 ビットとなるような群）. き直す必要があることは明らかである．. でのべき乗演算をすべての主体が行い，演算結果の群要素を他の主体に送信する必要がある. 次に Mul におけるエラー検出手続きを与える．基本アイデアは，まず P1 , P2 は正しいと. 情報処理学会論文誌. Vol. 52. No. 9. 2674–2685 (Sep. 2011). ため，Verif の方が計算効率および通信効率に優れると考えられる．ただし 3 章で述べたよ. c 2011 Information Processing Society of Japan .

(6) 2679. エラー検出可能な軽量 3 パーティ秘匿関数計算. うに，文献 12) の方式は各主体の不正の有無を検証できるのに対し，Verif はエラー検出の. {0, 1} となることから，すべての主体が正しく手続きを行えば，実行結果はランダムなビッ. 機能のみである．. トのシェアとなる．. 3.6 型変換. 整数変換は文献 9) にもあるように，a =. k−1 i=0. 2i ai より. [a] = Add(· · · Add(Add([a0 ], CoMul([a1 ], 2)), CoMul([a2 ], 22 )) · · · ,. 2 章で述べたとおり，秘匿回路計算は一般に処理効率が悪いため，秘匿関数計算を論理回. CoMul([ak−1 ], 2k−1 )). 路演算と算術演算に分けて全体の処理効率を上げる手法がいくつか提案されている．基本的な方針は，a ∈ Z/mZ のシェアから，a = (ak−1 · · · a0 )2 となる ai のシェア，およびその. の計算を行えばよい．. 逆を a を復元することなく求めることである．ここで前者の処理を 2 進変換，後者の処理. 4. 安全性. を整数変換，それらをまとめて型変換と呼び，(ak−1 · · · a0 )2 は a の 2 進表記，すなわち k. 4.1 準. ビット整数 a について ai は a を 2 進表記したときの下位 i + 1 番目のビットを表すものとする．すると論理回路演算と算術演算は基本的に独立した処理であっても，型変換によりそ. 備. 攻撃者にとって秘密のデータの推定分布がある関数による開示データを見てもまったく変化しないとき，その関数は完全秘匿性（perfect secrecy）を持つといい27) ，以下によって. れらを組み合わせた秘匿関数計算が可能となる．. 2 進変換は m を素数とすれば文献 9) で提案されている手法を適用できる．すなわち提. 定義される．. 案方式に基づき 2 進変換を行う場合は m を素数とする必要がある．なお文献 9) の手法は，. 定義 4.1. 集合 S 上の確率変数 S と独立であるような，S から集合 D への確率的関数 F. どの主体も知りえないランダムなビットのシェアを生成する必要がある．提案方式に基づき. が完全秘匿性を持つとは，任意の実際の秘密のデータ s ∈ S と出力 d ∈ D に対して，. 文献 9) の手法を適用する場合は，以下に示す単純な方法でランダムビットのシェアを生成. Pr(S = s|F (S) = d) = Pr(S = s) となることをいう．. してもよい．. BitShare：ランダムなビットのシェアを生成出力：Pi ([b]i ) or ⊥ ただし b はランダムなビット. 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). . 上記で S が秘密のデータであり F (S) が開示されるデータである．一方，マルチパーティプロトコルにおける完全秘匿性の定義を文献 15)，16) に基づき以. 入力：なし. (1). . Xor(Xor([b0 ], [b1 ]), [b2 ]) を実行し，Pi は実行結果を [b]i とする．. 上記手続き BitShare について，b0 , b1 , b2 はランダムなビットであり，b := b0 ⊕ b1 ⊕ b2 ∈. 下のように与える．定義 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 ) の確率分布は等しい．. − →I = {xi , . . . , xi }, fI = (fi , . . . , fi ), VIEWI = (VIEWi , . . . , VIEWi ) でただし x 1 1 1 |I| |I| |I|. ある．上記定義の中で主体の集合 I が 2 主体以上の集合の場合は当該主体が結託したことを表現している．このため本定義の安全性は，主体どうしがどのように結託しようとも安全であ. 情報処理学会論文誌. Vol. 52. No. 9. 2674–2685 (Sep. 2011). c 2011 Information Processing Society of Japan .

(7) 2680. エラー検出可能な軽量 3 パーティ秘匿関数計算. V σ : Z/mZ → [[(Z/mZ)2 ]] × [[(Z/mZ)2 ]] × [[(Z/mZ)2 ]]. ることを保証する．そこで各主体は結託をしないことを仮定する提案方式においては，定. a → ((Rx , Ry ), (Ry , a − Rx − Ry ), (a − Rx − Ry , Rx )). 義 4.2 の条件を主体集合 I ごとに分離した以下の定義をおく．定義 4.3. 定義 4.2 と同様のプロトコルを考え，I = {i1 , . . . , it } ⊆ {1, . . . , N } とする．この. V. μ. : (Z/mZ)6 → {Ø} × [[(Z/mZ)3 ]] × [[(Z/mZ)3 ]]. (a0 , a1 , a2 , b0 , b1 , b2 ) → (Ø,. プロトコルが semi-honest モデルで主体集合 I に対して完全秘匿性を持つとは，semi-honest. (R1 , (a0 + a1 )(b0 + b1 ) − R1 − R2 − R0 ,. モデルにおける攻撃者に対して以下のような確率的関数 S が存在することである． − →I , fI (− → → → 任意の入力 − x )) と VIEWI (− x ) の確率分 x = {x1 , . . . , xN } に対して S(I, x. (a − a0 − a1 )b0 + a0 (b − b0 − b1 ) + R2 ), (R2 , R0 , a1 (b − b0 − b1 ) + (a − a0 − a1 )b1 + R1 )). 布は等しい．特に以下は本稿の証明で用いる，定義 4.3 の条件の十分条件である．命題 4.1. 定義 4.2 と同様のプロトコルを考え，I ⊆ {1, . . . , n} とする．このとき， → VIEWI (− x ) が一様乱数ならば，プロトコルは semi-honest モデルで主体集合 I に対し. ただし Rx , Ry , R0 , R1 , R2 は互いに独立な一様乱数，Ø は空データ，集合 Ω に対して [[ Ω ]] は Ω 上の確率変数の集合を表す．両者とも，関数値の第 1 成分から順に P0 , P1 , P2 の VIEW である．これらを順に VIEW0 , VIEW1 , VIEW2 で表す．. て完全秘匿性を持つ．. 命題 4.1 より複合プロトコルが一様乱数であることを示せばよいのだが，その前にまず. Proof. 定義中，S をつねに一様乱数を出力する関数とすればよい．. σ. V , V μ が一様乱数であることを示す．. 4.2 semi-honest モデル. 補題 4.1. 任意の a, a0 , a1 , a2 , b0 , b1 , b2 ∈ Z/mZ に対して，V0σ (a), V1σ (a), V2σ (a), V0μ (a0 ,. 提案方式は単一のプロトコルではなく，3 章で与えた各手続きの複合からなるプロトコル. a1 , a2 , b0 , b1 , b2 ), V1μ (a0 , a1 , a2 , b0 , b1 , b2 ), V2μ (a0 , a1 , a2 , b0 , b1 , b2 ) は一様乱数である．た. の集合である．そのため，すべての複合したプロトコルが安全であることを示す必要があ. だし Viσ , Viμ はそれぞれ V σ , V μ の VIEWi を表す．. る．特に 3.1∼3.4 節で与えたプロトコル，すなわち Share，Dec，Add/Sub，CoMul，Mul，. Proof. （補題）. Not，And，Or，Xor は semi-honest モデルを仮定している．以降，3.1∼3.4 節で与えたプ. Rx , Ry , R0 , R1 , R2 が互いに独立な一様乱数であることから，それぞれの一様乱数性を調. ロトコル群を基本プロトコル，並列および直列の接続によりそれらを複合したプロトコルを. べればよい．. 複合プロトコルと呼ぶ．すると本稿の示すべき命題は以下となる．. Viσ ： Rx , Ry が一様乱数より一様乱数．. 定理 4.1. 3.1∼3.4 節で与えたプロトコル Share，Dec，Add/Sub，CoMul，Mul，Not，And，. V0μ ：値域が一点集合より一様乱数．. Or，Xor の任意の複合プロトコルは，主体間の結託を許さない semi-honest モデルにおい. Viμ ： R0 , R1 , R2 が一様乱数より一様乱数．. て完全秘匿性を持つ．. Proof. P0 , P1 , P2 の 3 パーティの VIEW に関しては，まず各基本プロトコルの VIEW を. 補題により，Share および Mul 単体が安全であることが示された．次にこれらが複合され. 考え，そこから帰納的に VIEW を定義する．基本プロトコルのうち，Add/Sub，CoMul，. た場合の一様乱数性について考える．複合プロトコルはある時点までの VIEW および定数. Not はデータ送受信をともなわないため，VIEW は空である．Dec の送受信データは明ら. を入力としてさらに基本プロトコルを行うことで生成される．このとき VIEW はその時点. かに入出力データと等価であるため，やはり VIEW は空と見なすことができる．また And. の VIEW にそのまま次の処理の VIEW が直積として追加される．. は Mul に等しく，Or，Xor は Add/Sub，CoMul，Mul から構成されるため複合プロトコル. まず P0 の VIEW について考える．P0 の VIEW は Share に関するもののみであり，元. であると見なすことができる．これらから，結局 Share，Mul のみが実際考慮する必要のあ. の入力 a が k 種類とすれば，複合プロトコルにおける P0 の VIEW は Share の VIEW の直. る対象である．Share，Mul の VIEW を表す確率的関数をそれぞれ V σ , V μ とすると，そ. 積 (Rx,1 , Ry,1 , . . . , Rx,k , Ry,k ) である．各 Rx,1 , . . . , Ry,k は互いに独立な一様乱数であり，. れぞれ以下のようになる．. P0 の VIEW も一様乱数であることが分かる． P1 , P2 に関しては，Share および Mul の実行回数に関する帰納法で VIEW が一様乱数で. 情報処理学会論文誌. Vol. 52. No. 9. 2674–2685 (Sep. 2011). c 2011 Information Processing Society of Japan .

(8) 2681. エラー検出可能な軽量 3 パーティ秘匿関数計算. あることを示す．. =. (1) Share 実行後，すなわち P1 , P2 に a のシェアが入力された状態を初期状態とする．このとき VIEW1 , VIEW2 は一様乱数である．. Pr(V1σ (a(r)) = d2 ). r∈v −1 ({d1 }). よって帰納法の仮定により，任意の有限回の Share，Mul の実行について VIEW1 , VIEW2. 合プロトコルが存在して，その VIEW を VIEWi1 , VIEWi2 とおけば，両者は一様乱数で. は一様乱数である．. ある．また入力の確率変数を A，i 回の実行および秘匿処理に使用された乱数をまとめて. 4.3 エラー検出. R とおけば，乱数生成以外の処理は決定的であるから，ある決定的関数 v1 , v2 が存在して. . 1 = 2 m |Dv |. (2) 実行回数が i 回以下の任意の複合プロトコルに対する VIEW1 , VIEW2 が一様乱数であると仮定する．実行回数が i + 1 の複合プロトコルを考えると，実行回数 i 回のある複. 1 |Dv |. 3.5 節で与えたエラー検出手続き Verif，BitShare について以下がいえる．. v1 (A, R) = VIEWi1 , v2 (A, R) = VIEWi2 であり，i + 1 回目の実行の入力に関しても同様に. 定理 4.2. m を素数とする．このとき，Mul において P1 , P2 は正しく処理を行い，P0 は. i+1 A，R の決定的関数で表すことができる．よって実行後の VIEW を VIEWi+1 1 , VIEW2. P1 または P2 にエラーを起こす不正値を送信した場合，Verif は (m − 1)/m 以上の確率で. とおけば，両者は次のように表される．. false を返す．. (I) i + 1 回目が秘匿処理の場合. Proof. P1 , P2 は f + g = 0 のときエラー検出することから，P0 は少なくとも s(˜ c0 + c˜1 + c˜2 ) ≡ e˜0 + e˜1 + e˜2. 秘匿処理の入力を a(A, R) とおけば. VIEWi+1 1 VIEWi+1 2. = =. (v1 (A, R), V1σ (a(A, R))) (v2 (A, R), V2σ (a(A, R))). 乗算処理の入力を a0 (A, R), a1 (A, R), a2 (A, R), b0 (A, R), b1 (A, R), b2 (A, R) とおけば. VIEWi+1 1. 次に VIEWi+1 = (v1 (A, R), V1σ (a(A, R))) が一様乱数であることを示す．その他の 3 つ 1. はできない．いま本来の値とエラーを起こす不正値の差分を Δc = c − (˜ c0 + c˜1 + c˜2 ),. s(c − Δc) ≡ sc − Δe. 関数 vY の値域集合を Dv とおけば，任意の d1 ∈ Dv , d2 ∈ (Z/mZ)2 に対して以下のよ. = (d1 , d2 )) が等しいことが分かり，一様乱数性が示される． = (d1 , d2 )) = =. Pr((v(A, R), V1σ (a(A, R))) = (d1 , d2 )) Pr(v(A, R) = d1 )Pr(V1σ (a(A, R)) = d2 |v(A, R). = d1 ) 1 = Pr(V1σ (a(A, R)) = d2 |(A, R) ∈ v −1 ({d1 })) |Dv | 1 = Pr(V1σ (a(A, R)) = d2 |(A, R) = r) |Dv | r∈v −1 ({d1 }). 情報処理学会論文誌. Vol. 52. No. 9. (mod m). (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 の場合も同様である．. の場合も同様に証明すればよい．. Pr(VIEWi+1 1. を満たす ci , ej の不正値 c˜i , e˜j （0 ≤ i, j ≤ 2）を生成しない限りエラーを起こすこと. sΔc ≡ Δe. = (v1 (A, R), V1μ (a0 (A, R), a1 (A, R), a2 (A, R), b0 (A, R), b1 (A, R), b2 (A, R))) VIEWi+1 2 = (v2 (A, R), V2μ (a0 (A, R), a1 (A, R), a2 (A, R), b0 (A, R), b1 (A, R), b2 (A, R))). うに. (2). Δe = sc − (˜ e0 + e˜1 + e˜2 ) とおくと，式 (2) は. (II) i + 1 回目が乗算処理の場合. Pr(VIEWi+1 1. (mod m). 2674–2685 (Sep. 2011). 定理 4.3. m を素数とし，P0 , P1 , P2 の少なくとも 2 つは正しく BitShare，EqTest および. Xor を実行するものとする．このとき，BitShare の処理が正しく終了したならば，Pi の出力は (m − 1)/m 以上の確率で 0 または 1 のシェアとなる．. Proof. 一般性を失うことなく P1 , P2 は BitShare，EqTest および Xor を正しく実行し， BitShare の処理が正しく終了したものとする．このとき BitShare のステップ ( 1 ) において ∗∗ P0 が P1 ，P2 に送信したデータをそれぞれ (b∗0,0 , b∗0,1 , b∗0,2 ), (b∗∗ 0,2 , b0,0 ) とすると，ステップ ∗ ∗∗ ( 2 )，( 3 ) より b∗0 := b∗0,0 + b∗0,1 + b∗0,2 ∈ {0, 1}, b∗0,0 = b∗∗ 0,0 , b0,2 = b0,2 が成り立ち，ス. テップ ( 3 ) で j = 0 について Pi が持つシェアは [b∗0 ]i = (b∗j,i , b∗j,i+1 ) と見なすことがで. c 2011 Information Processing Society of Japan .

(9) 2682. エラー検出可能な軽量 3 パーティ秘匿関数計算. きる．j = 1, 2 については P1 , P2 が正しく実行することを仮定しているため，Pi が持つ. とし，m を 32 ビットとすればおよそ 112 バイトとなる．一方，表 2 の n = 1,000,000 の. シェアは bj = bj,0 + bj,1 + bj,2 ∈ {0, 1} となる [bj ]i = (bj,i , bj,i+1 ) と見なすことができる．. 結果から，1 秒間におよそ 628,000 回の乗算を処理できるとすれば，それにともなう通信量. BitShare のステップ ( 4 ) の Xor の実行は，定理 4.2 より，(m − 1)/m 以上の確率で正し. はおよそ 70 メガバイトと見積もることができる．したがって広域通信においては，FTTH. く b∗0 ⊕ b1 ⊕ b2 のシェアを返すか，異常終了 ⊥ を返す．したがって b∗0 , b1 , b2 ∈ {0, 1} より. （Fiber To The Home）や FWA P-P（Fixed Wireless Access Point to Point）のような. BitShare の Pi の出力は (m − 1)/m 以上の確率で 0 または 1 のシェアとなる．. 5. 実装評価. 高速回線を利用しない限りは通信が大きなボトルネックになるものと考えられる．. 6. 考. 本章では 3 章で与えた提案方式を実装した結果について報告する．提案方式の基本プロトコルのうち，Share，Dec は単純な秘密分散およびその復元処理であり，Add/Sub，CoMul. 察. 本章では提案方式をプライバシ保護データマイニング技術として利用する場合の運用モデルの考察を行う．. は通信をともなわず，固定長（= |m|）演算の影響を無視すれば，各主体から見れば通常の. 提案方式は 3 主体の協調計算により，主体間の結託はないと仮定したとき，semi-honest. 加減算，定数倍演算の 2 倍程度の処理である．このような理由から，Mul にエラー検出 Verif. モデルにおいて入力値を秘匿しつつ各種計算を効率良く実行し，malicious モデルにおいて. （3.5 節）を付加した演算に特化して実装評価を行った．. エラー検出できる特徴を持つことを示した．2 主体が保持する情報を用いてプライバシ保護. 測定環境は表 1 のとおりである．m は 32 ビットの素数（m = 4,294,967,291）とし，測. データマイニングを行う場合は，図 1 のように第三者機関を介入させた構成（第三者機関. 定値は 3 回実行した値の平均である．n は入力数で，並列に処理できるものとする．なお初. 介入型）があげられる．すなわち，2 つの情報保持主体と第三者機関による 3 主体によって. 期化等の時間を除くため，n 入力の実行を 10 回および 20 回繰り返して測定し，それらの. 提案方式を実行する．最終的に計算結果を復元するのは各情報保持主体とすればよい．各情. 測定値を引いた値に 10 を割った値を最終的な測定値としている．測定結果を表 2 に示す．. 報保持主体は保持情報を自身を含めた 3 主体に秘密分散する．なお各情報保持主体から見. 次に通信量について評価する．Mul，Verif はそれぞれおよそ 6|m|，22|m| ビットの通信. れば，第三者機関と他の情報保持主体の結託により保持情報が知られうるため，第三者機関. を必要とする．すなわちエラー検出付き乗算 1 回あたりおよそ 28|m| ビットの通信を必要. はプライバシ保護データマイニングをサポートするサービス主体として社会的信頼を得ていることが望ましい．. 表 1 測定環境 Table 1 Test environment.. PC CPU RAM OS 言語コンパイラ. 1 台構成 Intel Core2 Quad 3.0 GHz 4 GB Debian 5.0.6 C++ g++ 4.3.2. 第三者機関介入型と同様の主体構成として，情報保持主体とは異なる分析主体を第三者機関と置き換えてもよい（図 2）．この場合，どちらかの情報保持主体が計算結果の復元に必要なシェアを分析主体に送信することで，分析主体のみ計算結果を復元することができる．. 3 主体が保持する情報を用いてプライバシ保護データマイニングを行う場合は，図 3 のよ. 表 2 エラー検出付き乗算（Mul および Verif） Table 2 Running time of three-party secure multiplication with error detection (Mul and Verif). 入力数 n. 1,000 10,000 100,000 1,000,000. 情報処理学会論文誌. Vol. 52. No. 9. 測定値（秒）. 0.0103 0.0337 0.1595 1.5934. 2674–2685 (Sep. 2011). 図 1 第三者機関介入型 Fig. 1 System configuration consisting of two data holders and a third party.. c 2011 Information Processing Society of Japan .

(10) 2683. エラー検出可能な軽量 3 パーティ秘匿関数計算. 体の 1 つは情報保持主体や分析主体としてもよい．4 以上の主体が保持する情報を用いてプライバシ保護データマイニングを行う場合は，3 主体の場合と同様に図 4 の主体構成を適用できる．一方，複数の情報保持主体のデータを統合するプライバシ保護データマイニングに必要とされる演算種別は文献 1) に詳しい．文献 1) では水平分割データ（Horizontally Partitioned 図 2 分析主体介入型 Fig. 2 System configuration consisting of two data holders and an analyst.. Data）と垂直分割データ（Vertically Partitioned Data）にデータ統合モデルが分類されているが，多くの演算は共通しており，相関ルールマイニング，決定木分類，EM クラスタリング，K-NN 分類，単純ベイズ分類器，サポートベクタマシン等のアルゴリズムが例示されている．ただしこれらのアルゴリズムは分析精度を高めるための工夫が施される等，統一されていない場合もあり，そのような場合において，汎用的に適用できる秘匿関数計算は有用といえる．. Fig. 3. 図 3 全参加型 System configuration consisting of three data holders.. 7. おわりに個人に関する情報の保護と利活用を両立させる汎用的なプライバシ保護データマイニングに資する要素技術として，3 主体の協調計算により，主体間の結託はないと仮定したとき，. semi-honest モデルにおいて入力値を秘匿でき，malicious モデルにおいて演算結果の改竄（エラー）を従来よりも効率良く検出できる 3 パーティ秘匿関数計算プロトコルを提案した．提案方式は，情報理論的安全性に基づく秘匿関数計算において一般に処理時間の最小化が期待できる n = 3 に特化して，従来のゼロ知識証明技術を用いずに軽量にエラー検出できる汎用の秘匿関数計算である．提案方式の効率に関しては，汎用 PC を用いた実装評価により，32 ビット乗算 1 回を約 1.6 μ 秒で処理できることを確認した．謝辞提案方式の安全性評価に関する記述の不備等について，ご指摘およびコメントいただきました査読者の方々に深く感謝いたします．. Fig. 4. 図 4 計算委託型 System configuration consisting of many data holders and three third parties.. うに提案方式の直接的な利用（全参加型）があげられる．ただし他の情報保持主体の結託により保持情報が知られうるため，図 4 のように 3 つの異なる第三者機関に保持情報を秘密分散して提供し，計算を委託する主体構成（計算委託型）も考えられる．計算委託型の場合は，秘匿関数計算を実行する 2 主体が結託しなければよいため，秘匿関数計算を実行する主. 情報処理学会論文誌. Vol. 52. No. 9. 2674–2685 (Sep. 2011). 参. 考. 文. 献. 1) Aggarwal, C.C. and Yu, P.S.: Privacy-Preserving Data Mining: Models and Algorithms, 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 noncryptographic fault-tolerant distributed computation, STOC ’88, pp.1–10, ACM. c 2011 Information Processing Society of Japan .

(11) 2684. エラー検出可能な軽量 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 protocols, 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, SpringerVerlag (2001). 9) Damg˚ ard, I., Fitzi, M., Kiltz, E., Nielsen, J.B. and Toft, T.: Unconditionally secure 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 from http://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 ciphertexts, 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).. 情報処理学会論文誌. Vol. 52. No. 9. 2674–2685 (Sep. 2011). 21) Nishide, T. and Ohta, K.: Multiparty computation for interval, equality, and comparison 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 computation 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 from http://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 from http://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 from http://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」の最先端技術 (2009 年 10 月 7 日), 入手先http://www.unisys.co.jp/news/nr 091007 cloud.html. c 2011 Information Processing Society of Japan .

(12) 2685. エラー検出可能な軽量 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）.. 濱田浩気（正会員）平成 19 年京都大学工学部情報学科卒業．平成 21 年同大学大学院情報学研究科通信情報システム専攻博士前期課程修了．同年日本電信電話株式会社（NTT）入社．現在，プライバシ保護技術，暗号応用技術の研究開発に従事．. (平成 22 年 12 月 2 日受付) (平成 23 年 6 月 3 日採録). 高橋克巳（正会員）昭和 63 年東京工業大学理学部数学科卒業．平成 18 年東京大学大学院. 千田浩司（正会員）. 情報理工学系電子情報学専攻博士課程修了．昭和 63 年日本電信電話株式. 平成 12 年早稲田大学大学院理工学研究科数理科学専攻修士課程修了．. 会社入社．以来，情報検索，データマイニング，プライバシ保護データ処. 同年日本電信電話株式会社（NTT）入社．博士（工学）．現在，プライバ. 理，暗号，情報セキュリティ，セキュリティ社会科学の研究開発に従事．. シ保護技術，暗号応用技術の研究開発に従事．平成 13 年電子情報通信学. 博士（情報理工学）．平成 12 年度本会論文賞．電子情報通信学会会員．. 会 SCIS 論文賞受賞．電子情報通信学会会員．. 五十嵐大（正会員）平成 20 年東京大学大学院情報理工学系研究科コンピュータ科学専攻博士前期課程修了．同年日本電信電話株式会社（NTT）入社．日本ソフトウェア科学会会員．. 情報処理学会論文誌. Vol. 52. No. 9. 2674–2685 (Sep. 2011). c 2011 Information Processing Society of Japan .

(13)