特集セキュリティ基盤技術/紛失通信プロトコルの考察193 特集ネットワークセキュリティ特集 4-3 紛失通信プロトコルの考察 4-3 A Survey on Oblivious Transfer Protocols Le Trieu Phong Le Trieu Phong 要旨本論文では公開

Size: px

Start display at page:

Download "特集セキュリティ基盤技術/紛失通信プロトコルの考察193 特集ネットワークセキュリティ特集 4-3 紛失通信プロトコルの考察 4-3 A Survey on Oblivious Transfer Protocols Le Trieu Phong Le Trieu Phong 要旨本論文では公開"

おさむひろき
5 years ago
Views:

1 セキュリティ基盤技術/紛失通信プロトコルの考察193 ネットワークセキュリティ 4-3 紛失通信プロトコルの考察 4-3 A Survey on Oblivious Transfer Protocols Le Trieu Phong Le Trieu Phong 要旨本論文では公開鍵による暗号化スキームから紛失通信 (OT) プロトコルを構築することに関する考察を行う送信者と受信者の双方が誠実であることを想定した単純な 1-out-of-2 OT の構築をまず行うその後不誠実な送信者または受信者がいわゆる完全にシミュレーション可能なセキュリティを活用する状況を想定したより複雑な構造について考察するその後 DDH 仮定および DLIN 仮定によって構築されたセキュアなインスタンス化について説明する In this paper, we survey some constructions of oblivious transfer (OT) protocols from public key encryption schemes. We begin with a simple construction of 1-out-of-2 OT when both the sender and the receiver are assumed to be honest. We then move to a more complex construction assuming either dishonest sender or receiver, enjoying the so-called fully simulatable security. We then highlight some concrete instantiations secure under the decisional Diffie-Hellman (DDH) and the decision linear assumptions. [ キーワード ] 紛失通信, 公開鍵による暗号化スキーム Oblivious transfer, Public key encryption schemes 1 はじめに 1.1 本論文の背景紛失通信プロトコル [2] は論文において広く研究が行われている単純な形態においては送信者が2つのメッセージを保有し受信者が 2つのメッセージのうちの 1 つを受信したいと考えどちらのメッセージを受信したかを送信者に開示しない形態が挙げられるこれは論文において 1-out-of-2 と呼ばれより複雑なプロトコル ([3] を参照のこと ) を構築するための基本的なツールとなる構造については図 1 のとおりである送信者と受信者が存在する適応性のあるクエリーを含む紛失通信 ( 適応性のある OT と呼ばれる ) は Naor と Pinkas が初めて研究を行った [12] 送信者は n 個のメッセージを保有し受信者はそのうち k 個のメッセージを 1 つずつ受信したいと考えるそれによって (1) 送信者は受信者がどのメッセージを受信したかを確認することができず (2) 受信者は k 個のメッセージ以外のメッセー (m0,m1) (b=0 or 1) b m b 図 1 1-out-of-2 紛失通信

2 ネットワークセキュリティジを受信することができないこのような種類の OT は主に特許検索紛失検索医学データベース等に活用されている上記の要件を満たすセキュリティのコンセプトは研究に基づいて進化してきた完全にシミュレーション可能なスキームは現実世界と理想世界のパラダイムに基づいて [1] に基づいて Camenisch をはじめとする研究者によって紹介された理想的なパラダイムにおいては信頼できる第三者 (TTP) が存在し送信者は TTP に対して全てのメッセージを提供する受信者がメッセージを受信したい場合は受信者は該当するインデックスを TTP に送付するだけでよい一方現実のパラダイムにおいては TTP は存在せず適応性のある OT のプロトコルは送信者と受信者によって運用される完全にシミュレーション可能なスキームの考えとして繰り返し発生する脅威に関しては現実世界と理想世界とを区別することはできないさらに Camenisch をはじめとする研究者はランダムオラクルモデル (ROM) と標準モデルにおいて完全にシミュレーション可能な適応性の高い OT のモデルを初めて提供した特に Ogata および Kurosawa[15] による ROM のスキームが完全にシミュレーション可能なセキュリティを実現できることを示すことに成功したさらに組み合わせのグループにおいて q ベースの仮定 (q が n によって影響を受ける ) を使用した標準モデルのシステムを構築した Camenisch をはじめとする研究者の研究成果を受けてこの点についてさらに研究が行われた [5] においては Green と Hohenberger がいわゆる q-hidden LRSW 仮定に基づいて汎用的結合可能性 (UC) を提供しかつ完全にシミュレーション可能なスキームを構築した Jarecki および Liu[8] は RSA グループに含まれる q-dhi(diffie- Hellman Inversion) 仮定に基づくスキームに関する研究を行った q ベースではない仮定に関しては Kurosawa および Nojima[9] が DDH 仮定に基づく完全にシミュレーション可能な単純なスキームを示したしかしながら本スキームでは Green と Hohenberger が [6] で示すとおり各通信において O (n) の大きな通信コストが必要となったその後 Green と Hohenberger は組み合わせのグループにおいて decision 3-party DDH(3DDH) 仮定に基づくシステムを構築したその結果 Kurosawa Nojima および Phong[10] は検証可能なシャッフルプロトコルを使用して DDH 仮定に基づいてセキュリティを確保したうえでコストを O (1) に削減することで [9] のデメリットを克服したさらに [11] において上記の研究者は適応性のある OT の標準システムについて提案し当該 OT システムは標準の良く知られた仮定に基づいてセキュアなインスタンス化を実現する 1.2 本論文の目的本論文の主な目的は公開鍵の暗号化スキームに基づいて構築した OT のいくつかのシステムについて考察することにあるまず PKE スキームに基づいて構築したよく知られた単純な 1-outof-2 OT のシステムについて考える ([3] を参照 ) その後 Kurosawa Nojima および Phong[11] が提案する標準モデルに基づく完全にシミュレーション可能な適応性の高い OT( 主な構成要素として特別なプロパティを持つ PKE を使用する ) の標準の構築方法について説明する本主要によって DDH 仮定と DLIN(d 2) 仮定によってプロトコルが生成される簡単な比較は表 1 のとおりである紛失通信に関するこれらの手法は two-party computation(2pc) プロトコルのような複雑かつ高機能なプロトコルを構築するために必須である理論的には紛失通信において暗号文を構築することが可能であるため紛失通信は Security Fundamentals Group の研究課題としては適切なものであった 2 注記本論文において OT n k 1 は送信者の n 個のメッセージと受信者の k 個の選択肢を含む適応性のある OT を指す ZKPK は zero-knowledge proof of knowledge( 知識のゼロ知識証明 ) を指し ZKPM は zero-knowledge proof of membership( メンバーシップのゼロ知識証明 ) を指す WIPK は witness-indistinguishable proof of knowledge( 証拠識別不能知識証明 ) を指す 194 情報通信研究機構季報 Vol. 57 Nos. 3/4 2011

3 セキュリティ基盤技術/紛失通信プロトコルの考察195 表 1 完全にシミュレーション可能な適応性の高い OT スキームスキーム仮定通信コスト (1 回あたり ) 初期化コスト CNS [1] q-strong DH および q-pddh O (1) O (n) GH [5] q-hidden LRSW(UC secure) O (1) O (n) JL [8] q-dhi(rsa グループ ) O (1) O (n) KN [9] DDH O (n) O (n) GH [6] decision 3-party DH (3DDH) O (1) O (n) KNP [10] DDH O (1) O (n) ( 変動が多い ) O (n) DDH KNP [11] O (1) ( 変動が少ない ) DLIN O (n) ( ランダムオラクルを含まない ) a [ i ] は a の i - 番目の要素を指す例えば a がビットスリングであるとき a [ i ] は i 番目のビットを指す a が複数の要素を含むタプルであるとき a [ i ] は i 番目の要素となる 3 単純な 1-out-of-2 OT の構築受信者が m 1 b を取得することができないように Enc (pk 1 b, m 1 b ) がゼロの Enc (pk 1 b, 0) の暗号化と区別できない必要があるゼロの Enc (pk 1 b, 0) は PKE の標準の強秘匿性 [4] のことを指す本条件も論文における多くのスキームで実現している (KGen, Enc, Dec) のアルゴリズムで構成される PKE が存在するとするアルゴリズム KGen は公開鍵 pkと秘密鍵 sk を戻す pk を使用して Enc はメッセージ mを入力し暗号文 c を戻し暗号文 c は skを使用して Dec によって解読される送信者が 2 つのメッセージ m 0, m 1 を保有し受信者がビット b を保有するとする受信者は送信者に b を開示することなく m b を取得したいとするその際以下が実行される 1. 受信者は送信者に対して (pk b, sk b ) KGen と完全にランダム化した pk 1 b を送信する 2. 送信者は受信者に対して c 0 = Enc (pk 0, m 0 ) と c 1 = Enc (pk 1, m 1 ) を送信する 3. 受信者は sk b を使用して c b を解読し m b を取得する送信者がビット b について認識することができないように pk b は乱数と区別できない必要があるつまり KGen が乱数に見える公開鍵を発行する必要がある本条件は実際に使用されている多くの PKE スキームで実現している 4 検証可能シャッフルに基づいて構築した一般的な適応性のある OT ここで完全にシミュレーション可能なセキュリティを有する適応性のある OT の一般的な構築について説明するまず構成要素がいくつか必要となる 4.1 主要な要素閾値公開鍵暗号 2-out-of-2 閾値公開鍵暗号 (TPKE) スキームは以下のアルゴリズムによって構成される TGen : Sと Rの 2 者がプロトコルを運用しそれぞれ (pk, sk S ) と (pk, sk R ) を取得する pk は合意された公開鍵を指し sk S, sk R は共有された秘密鍵を指す ( 公開鍵は以下の全てのアルゴリズムで必要である明確に説明するために公開鍵については記載しない ) TEnc (M; r) : プレーンテキスト Mとランダムコイン r に対して暗号文 C を出力する

4 ネットワークセキュリティ TDec (sk P, C) : P {S, R} の場合 μ( P 秘密鍵 key sk P に基づいて暗号文 C を解読したもの ) を出力する TComb (C, μ S, μ R ): 入力 C, μ S, μ R を組み合わせることによってプレーンテキスト M を出力する TPKE スキームには以下のプロパティが必要である準同型 : TEnc (M; r) TEnc (M'; r') = TEnc (M M'; r r') 上記において,, は対応するスペースにおける演算子を指す強秘匿性 : 全ての M について乱数 r に対応する暗号文 Enc (M; r) は暗号文スペースを通じてほぼ常に配布される検証可能なシャッフル TPKE の 1 i n に対して一連の暗号文 C i = TEnc (M i ; r i ) が S によって作成されたとする I はメッセージスペースの単位元であるとする R が {1,, n} 上の順列 πを選択し s i をランダム化して 1 i nに対して一連の C i ' = C π ( i ) TEnc (I; s i ) を構築することで両方の暗号文に同じプレーンテキストが含まれるようにすることは容易なことである C i ' (1 i n) のセットはオリジナルのシャッフルと呼ばれるスキーム TPKE が強秘匿性である場合シャッフル C i ' (1 i n) を公開することでは順列 π のどの情報も S には開示されないシャッフルの正確性は以下のプロトコルで検証される ZKPK {(π, s i ): C i ' = C π ( i ) TEnc (I; s i ) 1 i n}, Groth および Lu[7] による研究のとおり上記のプロトコルは ElGamal や Paillier 等の準同型の暗号化スキームでは効果的に機能するより広い意味で Groth and Lu による研究成果は以下のプロパティを有する準同型の暗号化スキームに適用することができる適切なメッセージスペース : メッセージスペースに小さな素因数 ( 例 : 2 80 より小さい素因数 ) が存在しないことルートの抽出 : C e = TEnc (M; R) から効率的にそれぞれの eとメッセージスペースの次数とが互いに素となる組み合わせについて C = TEnc (m; r) となるような (m; r) を抽出することができる文献 [7] で説明される検証可能なシャッフルのプロトコルは統計情報に基づいた 3 ラウンドの honest verifier zero-knowledge(hvzk) に基づく引数であり標準の手法に基づいて完全なゼロ知識に変更することができる 4.2 一般的な OT プロトコル初期化 1. 送信者 Sと受信者 R がプロトコル TGen を運用し両者が共通の公開鍵 pk を取得し S が秘密鍵 sk S を取得し R が秘密鍵 sk R を取得する受信者 R は ZKPK によって pk に対応する sk R を認識していることを証明する 2. 1 i n について S は以下を計算し R に送信する C i = TEnc (M i ; r i ) r i は TEnc が使用する乱数列を指す 3. その後送信者 S は ZKPK によって R に対して全ての i について M i を認識していることを証明する ( 上記は以下のインスタンス化において r i を認識していることを証明することと等しい ) 4. ( シャッフリング ) 受信者 R は {1,, n} 上の順列 πと 1 i n に対する乱数列数 s i を選択し全ての i に関して以下を計算し S に対して送信する C i ' = C π ( i ) TEnc (I; s i ), I はメッセージスペースの単位元である 5. 受信者 R は ZKPK によって S に対してステップ 4.2 で説明される式を満足する πと s i (1 i n) について認識していることを証明する j 番目の送信 1. 受信者 R は入力項目としてインデックス σを取得し S に送信する 2. 送信者 S は以下を確認し C' {C 1 ',, C n '} その後以下を計算し R に送信する 196 情報通信研究機構季報 Vol. 57 Nos. 3/4 2011

5 セキュリティ基盤技術/紛失通信プロトコルの考察197 μ S = TDec (sk S, C) 3. その後送信者 S は ZKPM によって上位のステップにおいて適切な暗号解読を行ったことを証明する 4. 受信者 R も以下の通り暗号解読を行い μ R = TDec (sk R, C) その後 TComb (pk, C, μ S, μ R ) によって M σ を取得する以下の結果は [11] において Kurosawa Nojima および Phong によって構築されたものである証明については [11] を参照すること命題 : TPKE が強秘匿性を有する場合上記の検証可能なシャッフルに基づいて構築した一般的な OT n k 1 は完全にシミュレーション可能である 4.3 DDH 仮定および DLIN 仮定によるインスタンス化 DDH 仮定に基づいて構築した OT n k 1 閾値 ElGamal による暗号化スキームを使用する本スキームは巡回群 G = (G, g, q) において機能し本巡回群において g は一次配列 q を生成し G における DDH 仮定に基づいて強秘匿性を有する TGen : S は sk S = x 0 Z q を選択し h 0 g x 0 を計算し R に送信する同様に R は sk R = x 1 Z q を選択し S に h 1 g x 1 を送信する同意された公開鍵は h = h 0 h 1 である TEnc (M; r) : r Z q および M G の場合に以下を出力する C = (C [1], C [2]) = (g r, M h r ) TDec (sk P, C) : P が S または R の場合に μ P = C [1] sk P を出力する TComb (C, μ S, μ R ) : C [2] / (μ S μ R ) を出力する TPKE スキームは 4.1 で説明した全ての条件を満たすしたがって閾値 ElGamal の暗号化スキームに基づいて OT n k 1 プロトコルを実現することができる閾値 ElGamal の暗号化スキームは上記命題のとおり DDH 仮定に基づいて強秘匿性を有するため OT n k 1 は本仮定に基づいて完全にシミュレーション可能である DLIN 仮定に基づいて構築した OT n k 1 G = (G, g, q) についても研究を行う注記を追加する以下のベクトルについて v = (v [1],, v [l]) G 1 l u = (u [1],, u [l]) Z q 1 l 以下を定義する v u = u v = l π i = 1 v [ i ] u [ i ] G. マトリックスマトリックス乗数およびマトリックスベクトル乗数は同様に規定できる場合によっては演算子は暗黙的に理解されるまた u, u' Z q 1 l の場合通常 u + u' = (u [1] + u' [1],, u [l] + u' [l]) となる (u + u') v = (u v ) (u' v ) G および v (u + u') = (v u ) (v u' ) G. であることは容易に検証できる d 2, の場合は Naor および Segev[13] が紹介した以下の PKE スキームは DLIN 仮定に基づいて強秘匿性を有する Gen : sk Z q (d + 1) 1, φ G d (d + 1). ψ = φ sk G d 1 の場合秘密鍵は sk であり公開鍵は pk = (φ, ψ) である Enc (M; R) : M G のメッセージとランダム化した R Z q 1 d を入力し以下の暗号文を出力する C = (Rφ, (Rψ) M) G 1 (d + 1) G. Dec (sk, C) : C および sk の入力に対して C [2] / (C [1] sk) を出力する PKE スキームの確度は式 (R φ) sk = R (φ sk) によって得られる PKE スキームの強秘匿性によって φ, ψ の場合ペア Enc (1; R) = (Rφ, Rψ) は G 1 (d + 1) G 上の乱数と区別できないここで上記の PKE に関連して 2-out-of-2 閾値変化について説明するこれは DLIN 仮定に基づく適応性のある OT によって実現するものである TGen : S と R は G を使用してマトリックス φ G d (d + 1) について同意するその後両者はそれぞれ Z q (d + 1) 1 において秘密鍵 sk S および sk R を選択する S は ψ S = φ sk S G d 1 を公開し R は ψ R = φ sk R G d 1 を公開する同意

6 ネットワークセキュリティされた共通の公開鍵は φ, ψ S, ψ R である本公開鍵において ψ = ψ S ψ R = (ψ S [1] ψ R [1],, ψ S [d] ψ R [d]) G d 1 が暗号化のために使用される ψ = φ (sk S + sk R ) の条件が存在する TEnc (M; R) : 以下を出力する C = Enc (M; R) = (Rφ, (Rψ) M) G 1 (d + 1) G TDec (sk P, C) : P {S, R} の場合以下を出力する μ P = C [1] sk P G TComb (C, μ S, μ R ): C [2] / (μ S μ R ) を出力する OT の一般的な構築の際に上記のスキームを使用することで DLIN 仮定に基づいて完全にシミュレーション可能なインスタンス化を実現することができる 5 結論本稿においては暗号の基本的な要素と考えられる OT を構築するためのいくつかの手法について考察した現実的なメリットとしてクラウドストレージやクラウドコンピューティングにおいてプライバシーを保護するシステムを開発するために役立つ手法が可能になるものと考えられる本手法には改善の余地があり将来的にはより優れた OT スキームが提供されるようになるものと考えられる参考文献 1 J. Camenisch, G. Neven, and A. Shelat, Simulatable adaptive oblivious transfer, In M. Naor, editor, EUROCRYPT, Vol of Lecture Notes in Computer Science, pp , Springer, S. Even, O. Goldreich, and A. Lempel, A randomized protocol for signing contracts, In CRYPTO, pp , Y. Gertner, S. Kannan, T. Malkin, O. Reingold, and M. Viswanathan, The relationship between public key encryption and oblivious transfer, In FOCS, pp , S. Goldwasser and S. Micali, Probabilistic encryption, J. Comput. Syst. Sci., 28(2): , M. Green and S. Hohenberger, Universally composable adaptive oblivious transfer, In J. Pieprzyk, editor, ASIACRYPT, volume 5350 of Lecture Notes in Computer Science, pp , Springer, M. Green and S. Hohenberger, Practical adaptive oblivious transfer from a simple assumption, Cryptology eprint Archive, Report 2010/109, J. Groth and S. Lu, Verifiable shuffle of large size ciphertexts, In T. Okamoto and X. Wang, editors, Public Key Cryptography, Vol of Lecture Notes in Computer Science, pp , Springer, S. Jarecki and X. Liu, Efficient oblivious pseudorandom function with applications to adaptive OT and secure computation of set intersection, In O. Reingold, editor, TCC, Vol of Lecture Notes in Computer Science, pp , Springer, K. Kurosawa and R. Nojima, Simple adaptive oblivious transfer without random oracle, In M. Matsui, editor, ASIACRYPT, Vol of Lecture Notes in Computer Science, pp , Springer, K. Kurosawa, R. Nojima, and L. T. Phong Efficiency-improved fully simulatable adaptive ot under the DDH assumption, In J. A. Garay and R. D. Prisco, editors, SCN, Vol of Lecture Notes in Computer Science, pp , Springer, K. Kurosawa, R. Nojima, and L. T. Phong, Generic fully simulatable adaptive oblivious transfer, In 9th International Conference on Applied Cryptography and Network Security (ACNS 11), To appear. 12 M. Naor and B. Pinkas, Oblivious transfer with adaptive queries, In M. J. Wiener, editor, CRYPTO, Vol of Lecture Notes in Computer Science, pp , Springer, 情報通信研究機構季報 Vol. 57 Nos. 3/4 2011

セキュリティ基盤技術/紛失通信プロトコルの考察199 13 M. Naor and G. Segev, Public-key cryptosystems resilient to key leakage, In S. Halevi, editor, CRYPTO, Vol. 5677 of Lecture Notes in Computer Science, pp.

7 セキュリティ基盤技術/紛失通信プロトコルの考察 M. Naor and G. Segev, Public-key cryptosystems resilient to key leakage, In S. Halevi, editor, CRYPTO, Vol of Lecture Notes in Computer Science, pp , Springer, Full version available at eprint.iacr.org/2009/105.pdf 14 C. A. Neff, A verifiable secret shuffle and its application to e-voting, In ACM Conference on Computer and Communications Security, pp , W. Ogata and K. Kurosawa, Oblivious keyword search, J. Complexity, 20(2-3): , Also available at Le Trieu Phong ネットワークセキュリティ研究所セキュリティ基盤研究室専攻研究員博士 ( 学術 ) 暗号プロトコル ( 平成 23 年 6 月 15 日採録 )

04.™ƒ”R/’Ô”�/’Xﬂ©

04.™ƒ”R/’Ô”�/’Xﬂ© Digicashecash PC IC AI LicenseCoin License Pk A L Pk A W Rc C Coin License Okamoto and Ohta Okamoto and Ohta IC Digicashecash TTP Trusted Third Party TTP TTP TTP TTP: Trusted Third Party TTPTTP TTP TTP

特集セキュリティ基盤技術/紛失通信プロトコルの考察193 特集 ネットワークセキュリティ特集 4-3 紛失通信プロトコルの考察 4-3 A Survey on Oblivious Transfer Protocols Le Trieu Phong Le Trieu Phong 要旨 本論文では 公開

特集セキュリティ基盤技術/紛失通信プロトコルの考察193 特集ネットワークセキュリティ特集 4-3 紛失通信プロトコルの考察 4-3 A Survey on Oblivious Transfer Protocols Le Trieu Phong Le Trieu Phong 要旨本論文では公開