エルガマル暗号による情報授受伝達方法及び装置
【課題】一部暗号化した情報を効率よく授受伝達し、受け手やユーザ側のプライバシが計算量的安全性を備え、送り手やデータベース側のプライバシが情報量的安全性を備える方法と装置を提供すること。
【解決手段】送り手が複数の秘密データを有し受け手がその中の一部データを欲している場合、岡本-内山暗号ないしはPaillier暗号を用いて紛失通信を構成するに当たり、まず、受け手は岡本-内山暗号に従って秘密鍵と公開鍵に関するパラメータを取り、システムパラメータを生成し送り手への問い合わせを計算して送り、送り手は、岡本-内山暗号ないしはPaillier暗号に従う暗号化によって多項式時間の計算を行ない、その計算結果を回答として受け手へ戻す。受け手は、岡本-内山暗号ないしはPaillier暗号に従う復号によって多項式時間の計算を行ない、所望のデータを得る。
【解決手段】送り手が複数の秘密データを有し受け手がその中の一部データを欲している場合、岡本-内山暗号ないしはPaillier暗号を用いて紛失通信を構成するに当たり、まず、受け手は岡本-内山暗号に従って秘密鍵と公開鍵に関するパラメータを取り、システムパラメータを生成し送り手への問い合わせを計算して送り、送り手は、岡本-内山暗号ないしはPaillier暗号に従う暗号化によって多項式時間の計算を行ない、その計算結果を回答として受け手へ戻す。受け手は、岡本-内山暗号ないしはPaillier暗号に従う復号によって多項式時間の計算を行ない、所望のデータを得る。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、一部を暗号化した情報を、効率よく授受伝達する方法と、その方法を実施する装置に関する。
【背景技術】
【０００２】
インターネット等の通信網が発達するに伴い、送受する情報の秘匿性に対する要求も高まっている。
それには、情報の一部に暗号を組み込むことが有効であるが、実用性の点では、まだ十分普及するに至っていない。
従来の有望な情報授受伝達手段としては、紛失通信(Oblivious Transfer, 略して, OT)と、秘匿情報検索スキーム(Private Information Retrieval Schemes, 略して, PIR)とが挙げられる。
【０００３】
紛失通信(OT)とは、受け手側が、送り手側から送られてきた情報から権限範囲以外の情報を得られないこと、かつ、送り手側が受け手側から送られてきた情報に内包する情報を得られないこと、の2つの条件が満たされているプライバシ保護の機能がある2者間のプロトコルの総称である。
【０００４】
【数１】
の概念は、RabinによるOTの概念(非特許文献１)の拡張として非特許文献２で導入された。さらに一般化として、非特許文献３においてBrassardとCrepeau とRobertによりAll-Or-Nothing Disclosure (略して, ANDOS)という名称で
【数２】
が導入された。
ANDOSでは、いくつかの秘密情報を有する送り手側は、その中から1つの情報を受け手側に開示するが、その他の情報は暴かれないような保証がされ、さらに、受け手側は、どの情報を開示されたのかが送り手側には暴かれないよう保証されている。
【０００５】
秘匿情報検索スキーム(PIR)とは、ユーザが、データベース上にあるN個のデータm1,m2,・・・,mN(通常これらは1ビット)にアクセスする際に、データベース側が、ユーザ側のアクセスしたデータがどれなのかが判別できないようなスキームのことを指す。
【０００６】
PIRは、ユーザ側が1つ以上のデータについて知ることについて、特に制限はないが、1回のアクセスで1つの指定したデータ以外の情報を取得できない性質を有するものをSymmetric PIR(略して, sPIR)という。非特許文献４では、情報量的理論の観点でPIRの概念が導入されたが、その後、非特許文献５などにおいて、計算量的な観点でPIR の概念が導入され(Computational PIR, 略して, cPIR)、さらに、非特許文献６において、単一のデータベースで構成される計算量的に安全なPIR の概念が導入されるに至った(Quadratic Residuosity 仮定に基づく)。
【０００７】
Stern(非特許文献７)は、強秘匿性を有する準同型暗号系を使って一般的なANDOS の構成を提示している。また、Tzeng(非特許文献８)は、Decisional Diffie-Hellman Problem (DDH)に基づいたOTを提示している。
本件発明者も、特許文献１にて、類似する情報授受伝達手段を提示している。
【０００８】
しかしながら、そのような従来技術は、必ずしも十分効率のよい暗号情報授受伝達手段とはいえず、また、受け手やユーザ側のプライバシが計算量的安全性を備え、送り手やデータベース側のプライバシが情報量的安全性を備えているものではなかった。
【０００９】
以下の本発明で構成するPIRとSternのANDOSは非常に近いように思われるが、PIRで利用している仮定は、部分群メンバーシップ問題であり、p-部分群仮定よりも弱い。また、SternのANDOSはゼロ知識証明のテクニックを使っているものの、本実施例で(ユーザUが正直であるとの条件の下)示すようなデータベースDBのプライバシが情報量的には保証されていない。
本発明では、同じ暗号プリミティブを使ってsPIRを作るために
【数３】
とPIRを一体化するアプローチを取る。
【００１０】
【特許文献１】特開2003-29633「データベース情報処理方法及びプライベートインフォメーションリトリーバル装置並びにそのプログラム」
【非特許文献１】M. Rabin, “How to exchange secrets by oblivious transfer,” Technical Report TR-81, Aiken Computation Laboratory, Harvard University, 1981.
【非特許文献２】S. Even, O. Goldreich and A. Lempel, “A randomized protocol for signing contracts,” Communications of the ACM 28, pp.637-647, ACM, 1985.
【非特許文献３】G. Brassard, C. Crepeau and J. M. Robert, “All-or-Nothing Disclosure of Secrets,” CRYPTO’86, LNCSVol.263, pp.234-238, Springer-Verlag, 1987.
【非特許文献４】B. Chor, O. Goldreich, E. Kushilevitz and M. Sudan,“Private Information Retrieval,” FOCS’95, pp.41-50,IEEE, 1995. (Journal of the ACM 45 (6), pp.965-982,ACM, 1998.)
【非特許文献５】B. Chor, N. Gilboa, “Computationally Private Information Retrieval,” STOC’97, pp.304-313, ACM, 1997.
【非特許文献６】E. Kushilevitz and R. Ostrovsky, “One-Way Trapdoor Permutations Are Sufficient for Non-trivial Single-Server Private Information Retrieval,” Eurocrypt2000, LNCS Vol.1807, pp.104-121, Springer-Verlag, 2000.
【非特許文献７】J. Stern, “A new and efficient all-or-nothing disclosure of secrets protocol,” Asiacrypt’98 LNCS Vol.1514,pp.357-371, Springer-Verlag, 1998.
【非特許文献８】W. Tzeng, “Efficient 1-Out-n Oblivious Transfer Schemes,” PKC 2002, LNCS Vol.2274, pp.159-171, Springer-Verlag, 2002.
【非特許文献９】T. Okamoto, S. Uchiyama, “A New Public-key Cryptosystems Secure as Factoring,” Eurocrypt’98 LNCSVol.1403, pp.308-318, Springer-Verlag, 1998.
【非特許文献１０】A. Yamamura, T. Saito, “Private Information Retrieval Based on the Subgroup Membership Problem,” ACISP2001, LNCS Vol.2119, pp.206-220, Springer-Verlag, 2001.
【非特許文献１１】A. Yamamura and T. Saito, “Subgroup membership problems and applications to information security,”Scientiae Mathematicae Japonicae, (1) 57, pp.25-41,2003.
【非特許文献１２】J. Nieto, C. Boyd and E. Dawson, “A public key cryptosystem based on the subgroup membership problem,”ICICS 2001, pp.352-363, 2001.
【非特許文献１３】H. Riesel, “Prime Numbers and Computer Methods for Factorization,” Progress in Mathematics, Vol.126, Birkhauser, 1994.
【非特許文献１４】Pascal Paillier, “Public-Key Cryptosystems Based on Composite Degree Residuosity Classes,” Eurocrypt’99, LNCS Vol.1592, pp. 223-238, Springer-Verlag, 1999.
【非特許文献１５】Y. Gertner, Y. Ishai, E. Kushilevitz, T. Malkin, “Protecting data privacy in private data information retrieval schemes,” STOC’98, pp.151-160, ACM, 1998.
【非特許文献１６】M. Naor and B. Pinkas, “Oblivious transfer and polynomial evaluation,” STOC’99, pp.245-254, ACM, 1999.
【非特許文献１７】C. Cachin, S. Micali, M. Stadler, “Computationally Private Information Retrieval with Polylogarithmic Communication,” Eurocrypt’99, LNCS Vol.1592,pp.402-414, Springer-Verlag, 1999.
【発明の開示】
【発明が解決しようとする課題】
【００１１】
そこで、本発明は、一部暗号化した情報を、効率よく授受伝達する手段であり、受け手やユーザ側のプライバシが計算量的安全性を備え、送り手やデータベース側のプライバシが情報量的安全性を備える方法と、その方法を実施する装置を提供することを課題とする。
【課題を解決するための手段】
【００１２】
上記課題を解決するために、本発明のエルガマル暗号による情報授受伝達方法は、次の構成を備える。
すなわち、少なくともデータの入出力手段、記録手段、演算手段を備えた複数のコンピュータと、それらの間でデータの授受を行う通信手段とを有し、平文と乱数と公開鍵から暗号文を作成し、秘密鍵で復号するエルガマル暗号を用いて、情報の授受伝達が可能なネットワークシステムにおいて、送り手が複数の秘密データを有していて、受け手がその中の一部データを欲している場合、岡本-内山暗号を用いて紛失通信(Oblivious Transfer)を構成するに当たり、まず、受け手は、岡本-内山暗号に従って、秘密鍵と公開鍵に関するパラメータを取り、システムパラメータを生成し、送り手への問い合わせを計算して送り、それに対して、送り手は、岡本-内山暗号に従う暗号化によって、多項式時間の計算を行ない、その計算結果を回答として受け手へ戻し、それにより、受け手は、岡本-内山暗号に従う復号によって、多項式時間の計算を行ない、所望のデータを得ることを特徴とする。
【００１３】
また、少なくともデータの入出力手段、記録手段、演算手段を備えた複数のコンピュータと、それらの間でデータの授受を行う通信手段とを有し、平文と乱数と公開鍵から暗号文を作成し、秘密鍵で復号するエルガマル暗号を用いて、情報の授受伝達が可能なネットワークシステムにおいて、送り手が複数の秘密データを有していて、受け手がその中の一部データを欲している場合、Paillier暗号を用いて紛失通信(Oblivious Transfer)を構成するに当たり、まず、受け手は、Paillier暗号に従って、秘密鍵と公開鍵に関するパラメータを取り、システムパラメータを生成し、送り手への問い合わせを計算して送り、それに対して、送り手は、Paillier暗号に従う暗号化によって、多項式時間の計算を行ない、その計算結果を回答として受け手へ戻し、それにより、受け手は、Paillier暗号に従う復号によって、多項式時間の計算を行ない、所望のデータを得るようにしてもよい。
【００１４】
同様に、少なくともデータの入出力手段、記録手段、演算手段を備えた複数のコンピュータと、それらの間でデータの授受を行う通信手段とを有し、平文と乱数と公開鍵から暗号文を作成し、秘密鍵で復号するエルガマル暗号を用いて、情報の授受伝達が可能なネットワークシステムにおいて、データベースが複数の秘密データを有していて、ユーザがその中の一部データを欲している場合、岡本-内山暗号を用いて秘匿情報検索(Private Information Retrieval)を構成するに当たり、まず、ユーザは、岡本-内山暗号に従って、秘密鍵と公開鍵に関するパラメータを取り、システムパラメータを生成し、データベースへの問い合わせを計算して送り、それに対して、データベースは、岡本-内山暗号に従う暗号化によって、多項式時間の計算を行ない、その計算結果を回答としてユーザへ戻し、それにより、ユーザは、岡本-内山暗号に従う復号によって、多項式時間の計算を行ない、所望のデータを得るようにしてもよい。
【００１５】
少なくともデータの入出力手段、記録手段、演算手段を備えた複数のコンピュータと、それらの間でデータの授受を行う通信手段とを有し、平文と乱数と公開鍵から暗号文を作成し、秘密鍵で復号するエルガマル暗号を用いて、情報の授受伝達が可能なネットワークシステムにおいて、データベースが複数の秘密データを有していて、ユーザがその中の一部データを欲している場合、Paillier暗号を用いて秘匿情報検索(Private Information Retrieval)を構成するに当たり、まず、ユーザは、Paillier暗号に従って、秘密鍵と公開鍵に関するパラメータを取り、システムパラメータを生成し、データベースへの問い合わせを計算して送り、それに対して、データベースは、Paillier暗号に従う暗号化によって、多項式時間の計算を行ない、その計算結果を回答としてユーザへ戻し、それにより、ユーザは、Paillier暗号に従う復号によって、多項式時間の計算を行ない、所望のデータを得るようにしてもよい。
【００１６】
ここで、ゼロ知識証明による工程を組み込み、能動的な攻撃を抑止するようにしてもよい。
【００１７】
また、1回のアクセスで、指定した1つのデータ以外の情報を取得できないプライバシ保護機能を設けてもよい。
【００１８】
本発明のエルガマル暗号による情報授受伝達装置は、次の構成を備える。
すなわち、少なくともデータの入出力手段、記録手段、演算手段を備えた複数のコンピュータと、それらの間でデータの授受を行う通信手段とを有し、平文と乱数と公開鍵から暗号文を作成し、秘密鍵で復号するエルガマル暗号を用いて、情報の授受伝達が可能なネットワークシステムにおいて、送り手が複数の秘密データを有していて、受け手がその中の一部データを欲している場合、岡本-内山暗号を用いて紛失通信(Oblivious Transfer)を構成するに当たり、受け手は、岡本-内山暗号に従って、秘密鍵と公開鍵に関するパラメータを取り、システムパラメータを生成し、送り手への問い合わせを計算して送る問い合わせ手段を備え、それに対する送り手は、岡本-内山暗号に従う暗号化によって、多項式時間の計算を行ない、その計算結果を回答として受け手へ戻す回答手段を備え、また、受け手は、岡本-内山暗号に従う復号によって、多項式時間の計算を行ない、所望のデータを得る求値手段を備えることを特徴とする。
【００１９】
また、少なくともデータの入出力手段、記録手段、演算手段を備えた複数のコンピュータと、それらの間でデータの授受を行う通信手段とを有し、平文と乱数と公開鍵から暗号文を作成し、秘密鍵で復号するエルガマル暗号を用いて、情報の授受伝達が可能なネットワークシステムにおいて、送り手が複数の秘密データを有していて、受け手がその中の一部データを欲している場合、Paillier暗号を用いて紛失通信(Oblivious Transfer)を構成するに当たり、受け手は、Paillier暗号に従って、秘密鍵と公開鍵に関するパラメータを取り、システムパラメータを生成し、送り手への問い合わせを計算して送る問い合わせ手段を備え、それに対する送り手は、Paillier暗号に従う暗号化によって、多項式時間の計算を行ない、その計算結果を回答として受け手へ戻す回答手段を備え、また、受け手は、Paillier暗号に従う復号によって、多項式時間の計算を行ない、所望のデータを得る求値手段を備えるようにしてもよい。
【００２０】
同様に、少なくともデータの入出力手段、記録手段、演算手段を備えた複数のコンピュータと、それらの間でデータの授受を行う通信手段とを有し、平文と乱数と公開鍵から暗号文を作成し、秘密鍵で復号するエルガマル暗号を用いて、情報の授受伝達が可能なネットワークシステムにおいて、データベースが複数の秘密データを有していて、ユーザがその中の一部データを欲している場合、岡本-内山暗号を用いて秘匿情報検索(Private Information Retrieval)を構成するに当たり、ユーザは、岡本-内山暗号に従って、秘密鍵と公開鍵に関するパラメータを取り、システムパラメータを生成し、データベースへの問い合わせを計算して送る問い合わせ手段を備え、それに対するデータベースは、岡本-内山暗号に従う暗号化によって、多項式時間の計算を行ない、その計算結果を回答としてユーザへ戻す回答手段を備え、また、ユーザは、岡本-内山暗号に従う復号によって、多項式時間の計算を行ない、所望のデータを得る求値手段を備えるようにしてもよい。
【００２１】
少なくともデータの入出力手段、記録手段、演算手段を備えた複数のコンピュータと、それらの間でデータの授受を行う通信手段とを有し、平文と乱数と公開鍵から暗号文を作成し、秘密鍵で復号するエルガマル暗号を用いて、情報の授受伝達が可能なネットワークシステムにおいて、データベースが複数の秘密データを有していて、ユーザがその中の一部データを欲している場合、Paillier暗号を用いて秘匿情報検索(Private Information Retrieval)を構成するに当たり、ユーザは、Paillier暗号に従って、秘密鍵と公開鍵に関するパラメータを取り、システムパラメータを生成し、データベースへの問い合わせを計算して送る問い合わせ手段を備え、それに対するデータベースは、Paillier暗号に従う暗号化によって、多項式時間の計算を行ない、その計算結果を回答としてユーザへ戻す回答手段を備え、また、ユーザは、Paillier暗号に従う復号によって、多項式時間の計算を行ない、所望のデータを得る求値手段を備えるようにしてもよい。
【発明の効果】
【００２２】
本発明によると、岡本-内山暗号系およびPaillier暗号系で用いられる準同型暗号関数をベースにして、効率的なOTとPIRを実施でき、受け手とユーザのプライバシに計算量的安全性を与え、送り手とデータベースのプライバシに情報量的安全性を与えることができ、暗号化された情報の授受伝達システムに寄与する。
【発明を実施するための最良の形態】
【００２３】
以下に、図面を基に本発明の実施形態を説明する。
図１は、問い合わせを行うコンピュータとデータベースの設定例を示す説明図であり、図２は、受け手またはユーザと、送り手またはデータベースとのデータ授受の概要を示す説明図であり、図３は、紛失通信及び秘密情報検索の一般的な処理の流れを示す流れ図である。
送り手Sは、N個の秘密データ(m1,m2,・・・,mN)をもっていて、受け手Rはその中から1つデータmαが欲しいものとする。
まず、OTの場合、受け手Rは、岡本-内山暗号に従って、秘密鍵や公開鍵に関するパラメータを取り、システムパラメータを生成し、送り手Sへの問い合わせQuery(α)= (n,k,g1,g2,f)を計算して送る。
それに対して、送り手Sは、岡本-内山暗号に従う暗号化によって、多項式時間の計算を行ない、その計算結果を回答Answer(Query(α))=(c1,c2,・・・,cN)として受け手Rへ戻す。
それにより、受け手Rは、岡本-内山暗号に従う復号によって、多項式時間の計算を行ない、所望のデータmαを得る。
【００２４】
Paillier暗号の場合も同様である。
また、PIRの場合は、受け手RがユーザUに代わり、送り手SがデータベースDBに代わるが、工程の概要は同様である。
【００２５】
なお、システム構成の詳細は省略するが、本発明構成が、少なくともデータの入出力手段、記録手段、演算手段を備えた複数のコンピュータと、それらの間でデータの授受を行う通信手段とを有した通常公知のネットワークシステムを前提にし、記録手段としては例えばハードディスクやメモリ、演算手段としては例えばCPU等が挙げられることは明らかである。
【００２６】
本発明で用いる岡本-内山暗号系およびPaillier暗号系とOTおよびPIRの実施形態は、以下の通りである。
岡本-内山暗号系においては、p,qを、長さ|p|,|q|がそれぞれkに等しい奇素数とし、
n = p2qとおき、φをEuler関数とする。
【数４】
の位数はφ(p2) = p(p-1)である。
Γを
【数５】
のp-Sylow部分群とすると、これは唯一存在し、位数pの巡回群であって、
【数６】
と表される。
【数７】
は、Γと巡回群
【数８】
と同型の位数p-1の部分群Uとの直積となるが、pとp-1は互いに素であるから、
【数９】
も巡回群である。
x ≡ 1 mod pならばxp ≡1 mod p2であるから、
【数１０】
と表される。
【００２７】
Γから加法群
【数１１】
への準同型写像Lが、L(x) := (x -1)=pにより定義される。中国剰余定理より、
【数１２】
が成り立つ。
【数１３】
を、この式の第1成分への射影とし、
【数１４】
を
【数１５】
により定義する。
【００２８】
以下、集合Xの元xを、Xからランダムかつ一様に選択することをx∈2R Xにより表わすことにする。
また、gの位数をord(g)と記することにする。
【００２９】
岡本-内山暗号は、p2q型合成数の素因数分解の困難性に基づいた新しい落し戸付き一方向性関数を導入し、その関数を使って暗号系を構成した(非特許文献９)。
p,qを|p|=|q|=kである奇素数とし、n=p2q(|n|=3k)とする。
【数１６】
をgp := gp-1 mod p2の位数がpとなるように取り、h =gn mod nとおく。L(gp)≠0 mod pである。
【００３０】
公開鍵は、(n,k,g,h)であり、秘密鍵は、(p,q)である。
暗号化においては、平文m(0<m<2k-1)に対して、
【数１７】
を選び、暗号文C = gmhr mod nを計算する。
復号においては、暗号文Cに対して、L(Cp-1 mod p2)=L(gp-1 mod p2) mod pを計算する。
【００３１】
秘密鍵を知らないでこの暗号関数の逆演算をすることは、p2q型合成数を素因数分解することと同値であること、および、この暗号スキームが(能動的でない攻撃に対して) 強秘匿性(semantic security)を有することはp-部分群仮定と同値である。(非特許文献９）
【００３２】
Gを入力1kに対して(n,g,C)を出力する岡本-内山暗号スキームの生成系とし、(n,g,k)を公開鍵、b∈2R [0,1]としてCをbの暗号文とする。
p-部分群問題とは、任意の(一様/非一様な)確率的多項式時間アルゴリズムA、任意の定数cと十分大きなkに対して、下式が成り立つことをいう。
【数１８】
p-部分群仮定とは、p-部分群問題が不可能であるという仮定のことをいう。
【００３３】
Gを群とし、Hをその部分群とすると、部分群メンバーシップ問題とはg∈Gがg∈Hであるかどうかを決定することである(非特許文献１０)(非特許文献１１)。
ここで、Gの任意の元は、セキュリティパラメータkによって決まる長さkのバイナリで表現されるものと仮定する。
【００３４】
部分群のメンバーシップに関する述語をMemと記することにすると、x ∈ HならばMem(G,H,x)=1であり、x∈G＼HならばMem(G,H,x)=0である。
部分群メンバーシップ問題とは、生成系IGへの入力１Kに対して、b ∈R[0,1]に応じて元gをそれぞれG ∈R G＼HかあるいはG ∈RG＼Hから選択するときに、kに関する多項式時間で述語Memを計算することである。
【００３５】
1/2以上の正解確率で述語Memを計算する確率的多項式時間アルゴリズムが存在しない場合、 部分群メンバーシップ問題が不可能であるという。例えば、
【数１９】
の場合は、 平方剰余問題(Quadratic Residuosity Problem, 略して, QR)である。また、G' = 巡回群< x >,G = [(xe, xf ) ∈ G'G'|0 ≦ e, f < |x|g] H = G
の巡回部分群<(x, xa)>の場合は、Decisional Diffie-Hellman問題である。他の例については、非特許文献１０〜１２に開示されている。
【００３６】
p-部分群問題は、
【数２０】
における
【数２１】
の部分群メンバーシップ問題よりも強い仮定である。すなわち、p-部分群問題は、この部分群メンバーシップ問題に帰着できる。
また、
【数２２】
における
【数２３】
の部分群メンバーシップ問題は、p2q型合成数の素因数分解問題よりも強い仮定である。すなわち、この部分群メンバーシップ問題はp2q型合成数の素因数分解問題に帰着できる。
【００３７】
Paillier 暗号系においては、Carmichael関数をλとし(非特許文献１３)、p, q を奇素数とし、n=pqとおくと、
【数２４】
である。
【００３８】
【数２５】
が、
n2を法としてn次のべき乗剰余である(n-th residue modulo n2 )とは、z=yn mod n2を満たす
【数２６】
が存在する場合をいう。
【００３９】
n次のべき乗剰余の元からなる
【数２７】
の部分集合は、位数がφ(n2)=nφ(n)である部分群をなす。
QRの場合と同様に、n次のべき乗剰余性(n-th residuosity)を決定する部分群メンバーシップ問題を考えることができる。これをCR[n]と記することにする。CR[n]問題を解く確率的多項式時間アルゴリズムが存在しないという仮定のことを、Decisional Composite Residuosity Assumption (略して, DCRA)という。
【数２８】
に対して、関数Egを、
【数２９】
【数３０】
【００４０】
n|ord(g)(ord(g)≠0)ならば、Egは全単射である。
【００４１】
Ｂαを位数がnαであるような
【数３１】
の元の集合とし、
【数３２】
とおく。
【数３３】
に対して、Eg(x,y)を満たす
【数３４】
が存在するとき、唯一決まる
【数３５】
のことをgに関するwのn次のべき乗剰余類(n-th residuosity class of w with respect to g) といい、[[w]]gで表わすことにする。Egの性質より、任意のg∈βに対して、関数
【数３６】
は、
【数３７】
から
【数３８】
への準同型写像であり、その核(kernel)は、n2を法としたn次のべき乗剰余のなす群となることがわかる。
【００４２】
基底gにおいて
【数３９】
から[[w]]gを計算する問題のことを基底gのn次のべき乗剰余類問題といい、Class[n,g]と記することにする。Class[n,g]は、
【数４０】
およびg∈βに関して、random-self-reducibleという性質を有するので(非特許文献)[12]、Class[n,g]の計算量的困難性は、実際は
【数４１】
およびg∈Bの選択に依存しない。 従って、単に、
【数４２】
から[[w]]gを計算する問題のことをn次のべき乗剰余類問題といい、Class[n]と記することにする。そして、Class[n]を解く確率的多項式時間アルゴリズムが存在しないという仮定のことを、Computational Composite Residuosity Assumption (略して, CCRA)という。
Sn = [u < n2|u ≡ 1 mod n]とおくと、Sn上の関数Lが、L(u) = (u-1)/nで定義される。
【００４３】
Paillier暗号は、p,qを素数とし、n=pqとする。λ=λ(n)と おき、g∈RBとする。これは、gcd(L(gλmod n2),n) = 1 をチェックことで検証される。
公開鍵は、(n,g)であり、秘密鍵は、(p,q,λ)である。
暗号化は、平文m(m<n)に対して、r<nをランダムに選び、暗号文C = gmrn mod n2を計算する。
復号は、暗号文Cに対して、L(Cλmod n2)=L(gλ mod n2) mod nを計算する。
【００４４】
秘密鍵を知らないでこの暗号関数の逆演算をすることは、CCRAと同値であること、および、この暗号スキームが(能動的でない攻撃に対して)強秘匿性(semantic security)を有することはDCRAと同値であることが示されている(非特許文献１４)。
【００４５】
紛失通信において、送り手SはN個の秘密データm1,m2,……,mNをもっているものとする。X=( m1,m2,……,mN)とおき、受け手Rは、Xの中から1つデータ(例えば、mα)が欲しいものとし、送り手Sへ問い合わせ(query)をし、送り手Sがその結果を受け手Rに返す際、送り手Sはαについて情報を得ることができないことと、受け手Rは得るはずのデータ(例えば、mα)以外の情報を得ることができないこと、の2つの要求がある点が、秘匿情報検索スキームと異なっている。
【００４６】
一般的な1ラウンドのOTのプロトコルは、以下のような要件を満たす手順である。
まず、受け手Rは、システムパラメータを生成し、受け手Rは問い合わせQuery(α) を計算して、Query(α)を送り手Sに送る。
次に、送り手Sは、Query(α)を受け取り、多項式時間の計算を行い、Answer(Query(α))をその計算結果として得て、送り手SはAnswer(Query(α))を送り手Rに戻す。
そして、受け手RはAnswer(Query(α))を受け取り、多項式時間の計算を行い、 知りたかった情報(Xにおけるα番目のデータmα)を得る。
【００４７】
正当性(Correctness)については、受け手Rも送り手Sも正直に手順を踏んでいる場合、どのようなX、どのようなQuery(α)であっても、受け手Rはmαを得る。
【００４８】
受け手RのプライバシSでは、任意のα,βに対してα番目のデータmαとβ番目のデータmβの区別が付かない。本発明では、受け手Rのプライバシは計算量的な安全性を有する、すなわち、送り手Sは、受け手Rからの2つの問い合わせを確率的多項式時間アルゴリズムによって無視できない確率で区別することができない。
【００４９】
形式的には、任意のc、長さnの任意のデータベース、任意のα,β(1≦α,β≦Ｎ)、任意の(一様/非一様な)確率的多項式時間アルゴリズムAに対して、ある整数Kが存在して、任意のk>Kに対して、
【数４３】
kはプロトコルのセキュリティパラメータであり、
【数４４】
を満たすことである。
【００５０】
送り手Sのプライバシでは、受け手Rは、得たもの(mα)以外のデータmβ(β≠α)については如何なる情報も得ることができない。本発明では、送り手Sのプライバシは情報量的な安全性を有する、すなわち、受け手Rはどのような計算能力を有するにしても、データmβ(β≠α)を情報を得ることができない。
なお、本実施例では、受け手Rまたは送り手Sの能動的な攻撃については考慮していない。つまり、受け手Rと送り手Sは、両方とも正直にプロトコルに従っているものとする。
【００５１】
計算量については、受け手Rと送り手Sの両方の計算量は、データベースのサイズのNとセキュリティパラメータkに関する多項式により上から抑えられている。
【００５２】
ここで、本発明では、岡本-内山暗号を利用して
【数４５】
を構成する。
送り手SはN個の秘密データm1,m2,……,mNをもっているものとする。受け手Rは、その中から1つデータmαが欲しいものとする。
セキュリティパラメータkは、
【数４６】
が成り立つように十分大きくとる。例えば、N≦2k-1が成り立っていると仮定しても良い。
【００５３】
まず、受け手Rは、岡本-内山暗号と同じようにパラメータを(p,q,n)を取る。
【数４７】
を
【数４８】
となるように取り、
【数４９】
とし、
【数５０】
とおく。
【数５１】
として、
【数５２】
とおく。送り手Sへの問い合わせQuery(α)=(n,k,g1,g2,f)を送る。
【００５４】
次に、送り手Sは、
【数５３】
を選び、
【数５４】
を計算する。受け手Rへ回答Answer(Query(α))=(c1,c2,……,cN)を送る。
【００５５】
そして、受け手Rは、
【数５５】
を計算して、mαを得る。
【００５６】
プライバシは、受け手Rのプライバシに対して計算量的安全性を有し、送り手Sのプライバシに対して(能動的でない攻撃に対して)情報量的安全性を有することを示す。
能動的な攻撃に対しては、ゼロ知識証明によるテクニックを組み込む必要がある(非特許文献７)。
【００５７】
p-部分群仮定の下で、受け手Rのプライバシが保証される。
情報量的に送り手Sのプライバシが保証される。
【００５８】
Paillier暗号を利用して
【数５６】
を構成するには、次のように行う。
まず、受け手Rは、Paillier暗号と同じようにパラメータを(p,q,n)を取る。G1 ∈R Bを取り、
【数５７】
とし、
【数５８】
とおく。
【数５９】
として、
【数６０】
とおく。送り手Sへの問い合わせQuery(α)=(n,k,g1,g2,f)を送る。
次に、送り手Sは、
【数６１】
を選び、
【数６２】
を計算する。受け手Rへ回答Answer(Query(α))=(c1,c2,……,cN)を送る。
そして、受け手Rは、
【数６３】
を計算して、mαを得る。
【００５９】
プライバシは、受け手Rのプライバシに対して計算量的安全性を有し、送り手S のプライバシに対して(能動的でない攻撃に対して)情報量的安全性を有することを示す。
能動的な攻撃に対しては、ゼロ知識証明によるテクニックを組み込む必要がある(非特許文献７)。
【００６０】
DCRA仮定の下で、受け手Rのプライバシが保証される。
情報量的に送り手Sのプライバシが保証される。
【００６１】
Tzeng(非特許文献８)は、Decisional Diffie-Hellman Problem (DDH)に基づいた効率的なOTを提案している。それに対して、本実施例では、p-部分群仮定、並びにDCRA仮定に依存している。
Tzengの
【数６４】
では、送り手Sのプライバシは計算量的安全性を、受け手Rのプライバシは情報量的安全性を備えているのに対して、本実施例ではその逆に、送り手Sのプライバシは情報量的安全性を、受け手Rのプライバシは計算量的安全性を備えている。
【００６２】
cPIR(非特許文献５)は、2者、つまり、ユーザUとデータベースDBの間のプロトコルであり、両者はそれぞれ確率的多項式時間アルゴリズムを実行できる。DBは、同じ長さのビット列の列X=(m1,m2,……,mN)をデータベースとして保持している。通常は、m1,m2... ,mN ∈ [0, 1]であり1ビット以上のデータが欲しければPIRを繰り返し行う必要がある。
【００６３】
計算量的に安全な単一データベースのPIRを構成するには、まず、ユーザUはシステムパラメータを生成する。ユーザUは、問い合わせQuery(α)を計算して、Query(α)をデータベースDBに送る。
次に、データベースDBはQuery(α)を受け取り、多項式時間の計算を行い、Answer(Query(α))をその計算結果として得る。データベースDBはAnswer(Query(α))をユーザUに戻す。
そして、ユーザUはAnswer(Query(α))を受け取り、多項式時間の計算を行い、知りたかった情報(Xにおけるα番目のデータmα)を得る。
【００６４】
正当性については、どちら側も正直に手順を踏んでいる場合、どのようなX、どのようなQuery(α)であっても、ユーザUはmαを得る。
【００６５】
プライバシについては、データベースDBは、ユーザUからの2つの問い合わせを確率的多項式時間アルゴリズムによって無視できない確率で区別することができない。形式的には、任意のc、長さnの任意のデータベースUB、任意のα,β(1≦α,β≦N)、任意の(一様/非一様な)確率的多項式時間アルゴリズムAに対して、ある整数Kが存在して、任意のk>Kに対して、|Prob(A(Query(α)) = 1)−Prob(A(Query(β)) = 1)｜< σ(kはプロトコルのセキュリティパラメータであり、
【数６５】
を満たすことである。
【００６６】
ユーザUとデータベースDBの両方の計算量は、データベースDBのサイズのNとセキュリティパラメータkに関する多項式により上から抑えられている。
【００６７】
ここで、岡本-内山暗号を利用してPIRを構成する。
まず、ユーザUは、α番目の情報mαを欲しいものとする。ユーザUは、
【数６６】
を満たすようにgi(1≦i≦N)を生成する。
次に、データベースDBは、
【数６７】
を選び、回答
【数６８】
をユーザUへを送る。
そして、ユーザUは、
【数６９】
を計算することで、所望のmαを得る。
【００６８】
ユーザUのプライバシは、
【数７０】
における
【数７１】
の部分群メンバーシップ問題の仮定の下で保証される。
【００６９】
Paillier 暗号を利用してPIRを構成するには、次のように行う。
まず、ユーザUは、α番目の情報mαを欲しいものとする。ユーザUは、
【数７２】
【数７３】
を満たすようにgi(1≦i≦Ｎ)を生成する。
次に、データベースDBは、
【数７４】
を選び、回答
【数７５】
をユーザUへを送る。
そして、ユーザUは、
【数７６】
を計算することで、所望のmαを得る。
【００７０】
ユーザUのプライバシは、DCRA仮定の下で保証される。
【００７１】
本来、PIRはデータベースDBのプライバシを保証していない。非特許文献１５において、sPIRが提案されている。非特許文献１６で、OTとPIRを結合してsPIRを構成することが可能である。本発明においても、同一の暗号プリミティブを使ってOTとPIRを構成可能であり、ユーザUのプライバシはそれぞれの困難性の仮定の下で、データベースDBのプライバシは情報量的安全性に基づいた、1ラウンドで単一サーバであるsPIRを構成可能である。
【産業上の利用可能性】
【００７２】
本発明によると、一部暗号化した情報を効率よく授受伝達できると共に、受け手やユーザ側のプライバシが計算量的安全性を備え、送り手やデータベース側のプライバシが情報量的安全性を備えるので、電子認証や電子商取引など、プライバシが関わるあらゆる暗号通信技術の基幹になり得て、産業上利用価値が高い。
【図面の簡単な説明】
【００７３】
【図１】問い合わせを行うコンピュータとデータベースの設定例を示す説明図
【図２】受け手またはユーザと、送り手またはデータベースとのデータ授受の概要を示す説明図
【図３】紛失通信及び秘密情報検索の一般的な処理の流れを示す流れ図である。
【技術分野】
【０００１】
本発明は、一部を暗号化した情報を、効率よく授受伝達する方法と、その方法を実施する装置に関する。
【背景技術】
【０００２】
インターネット等の通信網が発達するに伴い、送受する情報の秘匿性に対する要求も高まっている。
それには、情報の一部に暗号を組み込むことが有効であるが、実用性の点では、まだ十分普及するに至っていない。
従来の有望な情報授受伝達手段としては、紛失通信(Oblivious Transfer, 略して, OT)と、秘匿情報検索スキーム(Private Information Retrieval Schemes, 略して, PIR)とが挙げられる。
【０００３】
紛失通信(OT)とは、受け手側が、送り手側から送られてきた情報から権限範囲以外の情報を得られないこと、かつ、送り手側が受け手側から送られてきた情報に内包する情報を得られないこと、の2つの条件が満たされているプライバシ保護の機能がある2者間のプロトコルの総称である。
【０００４】
【数１】
の概念は、RabinによるOTの概念(非特許文献１)の拡張として非特許文献２で導入された。さらに一般化として、非特許文献３においてBrassardとCrepeau とRobertによりAll-Or-Nothing Disclosure (略して, ANDOS)という名称で
【数２】
が導入された。
ANDOSでは、いくつかの秘密情報を有する送り手側は、その中から1つの情報を受け手側に開示するが、その他の情報は暴かれないような保証がされ、さらに、受け手側は、どの情報を開示されたのかが送り手側には暴かれないよう保証されている。
【０００５】
秘匿情報検索スキーム(PIR)とは、ユーザが、データベース上にあるN個のデータm1,m2,・・・,mN(通常これらは1ビット)にアクセスする際に、データベース側が、ユーザ側のアクセスしたデータがどれなのかが判別できないようなスキームのことを指す。
【０００６】
PIRは、ユーザ側が1つ以上のデータについて知ることについて、特に制限はないが、1回のアクセスで1つの指定したデータ以外の情報を取得できない性質を有するものをSymmetric PIR(略して, sPIR)という。非特許文献４では、情報量的理論の観点でPIRの概念が導入されたが、その後、非特許文献５などにおいて、計算量的な観点でPIR の概念が導入され(Computational PIR, 略して, cPIR)、さらに、非特許文献６において、単一のデータベースで構成される計算量的に安全なPIR の概念が導入されるに至った(Quadratic Residuosity 仮定に基づく)。
【０００７】
Stern(非特許文献７)は、強秘匿性を有する準同型暗号系を使って一般的なANDOS の構成を提示している。また、Tzeng(非特許文献８)は、Decisional Diffie-Hellman Problem (DDH)に基づいたOTを提示している。
本件発明者も、特許文献１にて、類似する情報授受伝達手段を提示している。
【０００８】
しかしながら、そのような従来技術は、必ずしも十分効率のよい暗号情報授受伝達手段とはいえず、また、受け手やユーザ側のプライバシが計算量的安全性を備え、送り手やデータベース側のプライバシが情報量的安全性を備えているものではなかった。
【０００９】
以下の本発明で構成するPIRとSternのANDOSは非常に近いように思われるが、PIRで利用している仮定は、部分群メンバーシップ問題であり、p-部分群仮定よりも弱い。また、SternのANDOSはゼロ知識証明のテクニックを使っているものの、本実施例で(ユーザUが正直であるとの条件の下)示すようなデータベースDBのプライバシが情報量的には保証されていない。
本発明では、同じ暗号プリミティブを使ってsPIRを作るために
【数３】
とPIRを一体化するアプローチを取る。
【００１０】
【特許文献１】特開2003-29633「データベース情報処理方法及びプライベートインフォメーションリトリーバル装置並びにそのプログラム」
【非特許文献１】M. Rabin, “How to exchange secrets by oblivious transfer,” Technical Report TR-81, Aiken Computation Laboratory, Harvard University, 1981.
【非特許文献２】S. Even, O. Goldreich and A. Lempel, “A randomized protocol for signing contracts,” Communications of the ACM 28, pp.637-647, ACM, 1985.
【非特許文献３】G. Brassard, C. Crepeau and J. M. Robert, “All-or-Nothing Disclosure of Secrets,” CRYPTO’86, LNCSVol.263, pp.234-238, Springer-Verlag, 1987.
【非特許文献４】B. Chor, O. Goldreich, E. Kushilevitz and M. Sudan,“Private Information Retrieval,” FOCS’95, pp.41-50,IEEE, 1995. (Journal of the ACM 45 (6), pp.965-982,ACM, 1998.)
【非特許文献５】B. Chor, N. Gilboa, “Computationally Private Information Retrieval,” STOC’97, pp.304-313, ACM, 1997.
【非特許文献６】E. Kushilevitz and R. Ostrovsky, “One-Way Trapdoor Permutations Are Sufficient for Non-trivial Single-Server Private Information Retrieval,” Eurocrypt2000, LNCS Vol.1807, pp.104-121, Springer-Verlag, 2000.
【非特許文献７】J. Stern, “A new and efficient all-or-nothing disclosure of secrets protocol,” Asiacrypt’98 LNCS Vol.1514,pp.357-371, Springer-Verlag, 1998.
【非特許文献８】W. Tzeng, “Efficient 1-Out-n Oblivious Transfer Schemes,” PKC 2002, LNCS Vol.2274, pp.159-171, Springer-Verlag, 2002.
【非特許文献９】T. Okamoto, S. Uchiyama, “A New Public-key Cryptosystems Secure as Factoring,” Eurocrypt’98 LNCSVol.1403, pp.308-318, Springer-Verlag, 1998.
【非特許文献１０】A. Yamamura, T. Saito, “Private Information Retrieval Based on the Subgroup Membership Problem,” ACISP2001, LNCS Vol.2119, pp.206-220, Springer-Verlag, 2001.
【非特許文献１１】A. Yamamura and T. Saito, “Subgroup membership problems and applications to information security,”Scientiae Mathematicae Japonicae, (1) 57, pp.25-41,2003.
【非特許文献１２】J. Nieto, C. Boyd and E. Dawson, “A public key cryptosystem based on the subgroup membership problem,”ICICS 2001, pp.352-363, 2001.
【非特許文献１３】H. Riesel, “Prime Numbers and Computer Methods for Factorization,” Progress in Mathematics, Vol.126, Birkhauser, 1994.
【非特許文献１４】Pascal Paillier, “Public-Key Cryptosystems Based on Composite Degree Residuosity Classes,” Eurocrypt’99, LNCS Vol.1592, pp. 223-238, Springer-Verlag, 1999.
【非特許文献１５】Y. Gertner, Y. Ishai, E. Kushilevitz, T. Malkin, “Protecting data privacy in private data information retrieval schemes,” STOC’98, pp.151-160, ACM, 1998.
【非特許文献１６】M. Naor and B. Pinkas, “Oblivious transfer and polynomial evaluation,” STOC’99, pp.245-254, ACM, 1999.
【非特許文献１７】C. Cachin, S. Micali, M. Stadler, “Computationally Private Information Retrieval with Polylogarithmic Communication,” Eurocrypt’99, LNCS Vol.1592,pp.402-414, Springer-Verlag, 1999.
【発明の開示】
【発明が解決しようとする課題】
【００１１】
そこで、本発明は、一部暗号化した情報を、効率よく授受伝達する手段であり、受け手やユーザ側のプライバシが計算量的安全性を備え、送り手やデータベース側のプライバシが情報量的安全性を備える方法と、その方法を実施する装置を提供することを課題とする。
【課題を解決するための手段】
【００１２】
上記課題を解決するために、本発明のエルガマル暗号による情報授受伝達方法は、次の構成を備える。
すなわち、少なくともデータの入出力手段、記録手段、演算手段を備えた複数のコンピュータと、それらの間でデータの授受を行う通信手段とを有し、平文と乱数と公開鍵から暗号文を作成し、秘密鍵で復号するエルガマル暗号を用いて、情報の授受伝達が可能なネットワークシステムにおいて、送り手が複数の秘密データを有していて、受け手がその中の一部データを欲している場合、岡本-内山暗号を用いて紛失通信(Oblivious Transfer)を構成するに当たり、まず、受け手は、岡本-内山暗号に従って、秘密鍵と公開鍵に関するパラメータを取り、システムパラメータを生成し、送り手への問い合わせを計算して送り、それに対して、送り手は、岡本-内山暗号に従う暗号化によって、多項式時間の計算を行ない、その計算結果を回答として受け手へ戻し、それにより、受け手は、岡本-内山暗号に従う復号によって、多項式時間の計算を行ない、所望のデータを得ることを特徴とする。
【００１３】
また、少なくともデータの入出力手段、記録手段、演算手段を備えた複数のコンピュータと、それらの間でデータの授受を行う通信手段とを有し、平文と乱数と公開鍵から暗号文を作成し、秘密鍵で復号するエルガマル暗号を用いて、情報の授受伝達が可能なネットワークシステムにおいて、送り手が複数の秘密データを有していて、受け手がその中の一部データを欲している場合、Paillier暗号を用いて紛失通信(Oblivious Transfer)を構成するに当たり、まず、受け手は、Paillier暗号に従って、秘密鍵と公開鍵に関するパラメータを取り、システムパラメータを生成し、送り手への問い合わせを計算して送り、それに対して、送り手は、Paillier暗号に従う暗号化によって、多項式時間の計算を行ない、その計算結果を回答として受け手へ戻し、それにより、受け手は、Paillier暗号に従う復号によって、多項式時間の計算を行ない、所望のデータを得るようにしてもよい。
【００１４】
同様に、少なくともデータの入出力手段、記録手段、演算手段を備えた複数のコンピュータと、それらの間でデータの授受を行う通信手段とを有し、平文と乱数と公開鍵から暗号文を作成し、秘密鍵で復号するエルガマル暗号を用いて、情報の授受伝達が可能なネットワークシステムにおいて、データベースが複数の秘密データを有していて、ユーザがその中の一部データを欲している場合、岡本-内山暗号を用いて秘匿情報検索(Private Information Retrieval)を構成するに当たり、まず、ユーザは、岡本-内山暗号に従って、秘密鍵と公開鍵に関するパラメータを取り、システムパラメータを生成し、データベースへの問い合わせを計算して送り、それに対して、データベースは、岡本-内山暗号に従う暗号化によって、多項式時間の計算を行ない、その計算結果を回答としてユーザへ戻し、それにより、ユーザは、岡本-内山暗号に従う復号によって、多項式時間の計算を行ない、所望のデータを得るようにしてもよい。
【００１５】
少なくともデータの入出力手段、記録手段、演算手段を備えた複数のコンピュータと、それらの間でデータの授受を行う通信手段とを有し、平文と乱数と公開鍵から暗号文を作成し、秘密鍵で復号するエルガマル暗号を用いて、情報の授受伝達が可能なネットワークシステムにおいて、データベースが複数の秘密データを有していて、ユーザがその中の一部データを欲している場合、Paillier暗号を用いて秘匿情報検索(Private Information Retrieval)を構成するに当たり、まず、ユーザは、Paillier暗号に従って、秘密鍵と公開鍵に関するパラメータを取り、システムパラメータを生成し、データベースへの問い合わせを計算して送り、それに対して、データベースは、Paillier暗号に従う暗号化によって、多項式時間の計算を行ない、その計算結果を回答としてユーザへ戻し、それにより、ユーザは、Paillier暗号に従う復号によって、多項式時間の計算を行ない、所望のデータを得るようにしてもよい。
【００１６】
ここで、ゼロ知識証明による工程を組み込み、能動的な攻撃を抑止するようにしてもよい。
【００１７】
また、1回のアクセスで、指定した1つのデータ以外の情報を取得できないプライバシ保護機能を設けてもよい。
【００１８】
本発明のエルガマル暗号による情報授受伝達装置は、次の構成を備える。
すなわち、少なくともデータの入出力手段、記録手段、演算手段を備えた複数のコンピュータと、それらの間でデータの授受を行う通信手段とを有し、平文と乱数と公開鍵から暗号文を作成し、秘密鍵で復号するエルガマル暗号を用いて、情報の授受伝達が可能なネットワークシステムにおいて、送り手が複数の秘密データを有していて、受け手がその中の一部データを欲している場合、岡本-内山暗号を用いて紛失通信(Oblivious Transfer)を構成するに当たり、受け手は、岡本-内山暗号に従って、秘密鍵と公開鍵に関するパラメータを取り、システムパラメータを生成し、送り手への問い合わせを計算して送る問い合わせ手段を備え、それに対する送り手は、岡本-内山暗号に従う暗号化によって、多項式時間の計算を行ない、その計算結果を回答として受け手へ戻す回答手段を備え、また、受け手は、岡本-内山暗号に従う復号によって、多項式時間の計算を行ない、所望のデータを得る求値手段を備えることを特徴とする。
【００１９】
また、少なくともデータの入出力手段、記録手段、演算手段を備えた複数のコンピュータと、それらの間でデータの授受を行う通信手段とを有し、平文と乱数と公開鍵から暗号文を作成し、秘密鍵で復号するエルガマル暗号を用いて、情報の授受伝達が可能なネットワークシステムにおいて、送り手が複数の秘密データを有していて、受け手がその中の一部データを欲している場合、Paillier暗号を用いて紛失通信(Oblivious Transfer)を構成するに当たり、受け手は、Paillier暗号に従って、秘密鍵と公開鍵に関するパラメータを取り、システムパラメータを生成し、送り手への問い合わせを計算して送る問い合わせ手段を備え、それに対する送り手は、Paillier暗号に従う暗号化によって、多項式時間の計算を行ない、その計算結果を回答として受け手へ戻す回答手段を備え、また、受け手は、Paillier暗号に従う復号によって、多項式時間の計算を行ない、所望のデータを得る求値手段を備えるようにしてもよい。
【００２０】
同様に、少なくともデータの入出力手段、記録手段、演算手段を備えた複数のコンピュータと、それらの間でデータの授受を行う通信手段とを有し、平文と乱数と公開鍵から暗号文を作成し、秘密鍵で復号するエルガマル暗号を用いて、情報の授受伝達が可能なネットワークシステムにおいて、データベースが複数の秘密データを有していて、ユーザがその中の一部データを欲している場合、岡本-内山暗号を用いて秘匿情報検索(Private Information Retrieval)を構成するに当たり、ユーザは、岡本-内山暗号に従って、秘密鍵と公開鍵に関するパラメータを取り、システムパラメータを生成し、データベースへの問い合わせを計算して送る問い合わせ手段を備え、それに対するデータベースは、岡本-内山暗号に従う暗号化によって、多項式時間の計算を行ない、その計算結果を回答としてユーザへ戻す回答手段を備え、また、ユーザは、岡本-内山暗号に従う復号によって、多項式時間の計算を行ない、所望のデータを得る求値手段を備えるようにしてもよい。
【００２１】
少なくともデータの入出力手段、記録手段、演算手段を備えた複数のコンピュータと、それらの間でデータの授受を行う通信手段とを有し、平文と乱数と公開鍵から暗号文を作成し、秘密鍵で復号するエルガマル暗号を用いて、情報の授受伝達が可能なネットワークシステムにおいて、データベースが複数の秘密データを有していて、ユーザがその中の一部データを欲している場合、Paillier暗号を用いて秘匿情報検索(Private Information Retrieval)を構成するに当たり、ユーザは、Paillier暗号に従って、秘密鍵と公開鍵に関するパラメータを取り、システムパラメータを生成し、データベースへの問い合わせを計算して送る問い合わせ手段を備え、それに対するデータベースは、Paillier暗号に従う暗号化によって、多項式時間の計算を行ない、その計算結果を回答としてユーザへ戻す回答手段を備え、また、ユーザは、Paillier暗号に従う復号によって、多項式時間の計算を行ない、所望のデータを得る求値手段を備えるようにしてもよい。
【発明の効果】
【００２２】
本発明によると、岡本-内山暗号系およびPaillier暗号系で用いられる準同型暗号関数をベースにして、効率的なOTとPIRを実施でき、受け手とユーザのプライバシに計算量的安全性を与え、送り手とデータベースのプライバシに情報量的安全性を与えることができ、暗号化された情報の授受伝達システムに寄与する。
【発明を実施するための最良の形態】
【００２３】
以下に、図面を基に本発明の実施形態を説明する。
図１は、問い合わせを行うコンピュータとデータベースの設定例を示す説明図であり、図２は、受け手またはユーザと、送り手またはデータベースとのデータ授受の概要を示す説明図であり、図３は、紛失通信及び秘密情報検索の一般的な処理の流れを示す流れ図である。
送り手Sは、N個の秘密データ(m1,m2,・・・,mN)をもっていて、受け手Rはその中から1つデータmαが欲しいものとする。
まず、OTの場合、受け手Rは、岡本-内山暗号に従って、秘密鍵や公開鍵に関するパラメータを取り、システムパラメータを生成し、送り手Sへの問い合わせQuery(α)= (n,k,g1,g2,f)を計算して送る。
それに対して、送り手Sは、岡本-内山暗号に従う暗号化によって、多項式時間の計算を行ない、その計算結果を回答Answer(Query(α))=(c1,c2,・・・,cN)として受け手Rへ戻す。
それにより、受け手Rは、岡本-内山暗号に従う復号によって、多項式時間の計算を行ない、所望のデータmαを得る。
【００２４】
Paillier暗号の場合も同様である。
また、PIRの場合は、受け手RがユーザUに代わり、送り手SがデータベースDBに代わるが、工程の概要は同様である。
【００２５】
なお、システム構成の詳細は省略するが、本発明構成が、少なくともデータの入出力手段、記録手段、演算手段を備えた複数のコンピュータと、それらの間でデータの授受を行う通信手段とを有した通常公知のネットワークシステムを前提にし、記録手段としては例えばハードディスクやメモリ、演算手段としては例えばCPU等が挙げられることは明らかである。
【００２６】
本発明で用いる岡本-内山暗号系およびPaillier暗号系とOTおよびPIRの実施形態は、以下の通りである。
岡本-内山暗号系においては、p,qを、長さ|p|,|q|がそれぞれkに等しい奇素数とし、
n = p2qとおき、φをEuler関数とする。
【数４】
の位数はφ(p2) = p(p-1)である。
Γを
【数５】
のp-Sylow部分群とすると、これは唯一存在し、位数pの巡回群であって、
【数６】
と表される。
【数７】
は、Γと巡回群
【数８】
と同型の位数p-1の部分群Uとの直積となるが、pとp-1は互いに素であるから、
【数９】
も巡回群である。
x ≡ 1 mod pならばxp ≡1 mod p2であるから、
【数１０】
と表される。
【００２７】
Γから加法群
【数１１】
への準同型写像Lが、L(x) := (x -1)=pにより定義される。中国剰余定理より、
【数１２】
が成り立つ。
【数１３】
を、この式の第1成分への射影とし、
【数１４】
を
【数１５】
により定義する。
【００２８】
以下、集合Xの元xを、Xからランダムかつ一様に選択することをx∈2R Xにより表わすことにする。
また、gの位数をord(g)と記することにする。
【００２９】
岡本-内山暗号は、p2q型合成数の素因数分解の困難性に基づいた新しい落し戸付き一方向性関数を導入し、その関数を使って暗号系を構成した(非特許文献９)。
p,qを|p|=|q|=kである奇素数とし、n=p2q(|n|=3k)とする。
【数１６】
をgp := gp-1 mod p2の位数がpとなるように取り、h =gn mod nとおく。L(gp)≠0 mod pである。
【００３０】
公開鍵は、(n,k,g,h)であり、秘密鍵は、(p,q)である。
暗号化においては、平文m(0<m<2k-1)に対して、
【数１７】
を選び、暗号文C = gmhr mod nを計算する。
復号においては、暗号文Cに対して、L(Cp-1 mod p2)=L(gp-1 mod p2) mod pを計算する。
【００３１】
秘密鍵を知らないでこの暗号関数の逆演算をすることは、p2q型合成数を素因数分解することと同値であること、および、この暗号スキームが(能動的でない攻撃に対して) 強秘匿性(semantic security)を有することはp-部分群仮定と同値である。(非特許文献９）
【００３２】
Gを入力1kに対して(n,g,C)を出力する岡本-内山暗号スキームの生成系とし、(n,g,k)を公開鍵、b∈2R [0,1]としてCをbの暗号文とする。
p-部分群問題とは、任意の(一様/非一様な)確率的多項式時間アルゴリズムA、任意の定数cと十分大きなkに対して、下式が成り立つことをいう。
【数１８】
p-部分群仮定とは、p-部分群問題が不可能であるという仮定のことをいう。
【００３３】
Gを群とし、Hをその部分群とすると、部分群メンバーシップ問題とはg∈Gがg∈Hであるかどうかを決定することである(非特許文献１０)(非特許文献１１)。
ここで、Gの任意の元は、セキュリティパラメータkによって決まる長さkのバイナリで表現されるものと仮定する。
【００３４】
部分群のメンバーシップに関する述語をMemと記することにすると、x ∈ HならばMem(G,H,x)=1であり、x∈G＼HならばMem(G,H,x)=0である。
部分群メンバーシップ問題とは、生成系IGへの入力１Kに対して、b ∈R[0,1]に応じて元gをそれぞれG ∈R G＼HかあるいはG ∈RG＼Hから選択するときに、kに関する多項式時間で述語Memを計算することである。
【００３５】
1/2以上の正解確率で述語Memを計算する確率的多項式時間アルゴリズムが存在しない場合、 部分群メンバーシップ問題が不可能であるという。例えば、
【数１９】
の場合は、 平方剰余問題(Quadratic Residuosity Problem, 略して, QR)である。また、G' = 巡回群< x >,G = [(xe, xf ) ∈ G'G'|0 ≦ e, f < |x|g] H = G
の巡回部分群<(x, xa)>の場合は、Decisional Diffie-Hellman問題である。他の例については、非特許文献１０〜１２に開示されている。
【００３６】
p-部分群問題は、
【数２０】
における
【数２１】
の部分群メンバーシップ問題よりも強い仮定である。すなわち、p-部分群問題は、この部分群メンバーシップ問題に帰着できる。
また、
【数２２】
における
【数２３】
の部分群メンバーシップ問題は、p2q型合成数の素因数分解問題よりも強い仮定である。すなわち、この部分群メンバーシップ問題はp2q型合成数の素因数分解問題に帰着できる。
【００３７】
Paillier 暗号系においては、Carmichael関数をλとし(非特許文献１３)、p, q を奇素数とし、n=pqとおくと、
【数２４】
である。
【００３８】
【数２５】
が、
n2を法としてn次のべき乗剰余である(n-th residue modulo n2 )とは、z=yn mod n2を満たす
【数２６】
が存在する場合をいう。
【００３９】
n次のべき乗剰余の元からなる
【数２７】
の部分集合は、位数がφ(n2)=nφ(n)である部分群をなす。
QRの場合と同様に、n次のべき乗剰余性(n-th residuosity)を決定する部分群メンバーシップ問題を考えることができる。これをCR[n]と記することにする。CR[n]問題を解く確率的多項式時間アルゴリズムが存在しないという仮定のことを、Decisional Composite Residuosity Assumption (略して, DCRA)という。
【数２８】
に対して、関数Egを、
【数２９】
【数３０】
【００４０】
n|ord(g)(ord(g)≠0)ならば、Egは全単射である。
【００４１】
Ｂαを位数がnαであるような
【数３１】
の元の集合とし、
【数３２】
とおく。
【数３３】
に対して、Eg(x,y)を満たす
【数３４】
が存在するとき、唯一決まる
【数３５】
のことをgに関するwのn次のべき乗剰余類(n-th residuosity class of w with respect to g) といい、[[w]]gで表わすことにする。Egの性質より、任意のg∈βに対して、関数
【数３６】
は、
【数３７】
から
【数３８】
への準同型写像であり、その核(kernel)は、n2を法としたn次のべき乗剰余のなす群となることがわかる。
【００４２】
基底gにおいて
【数３９】
から[[w]]gを計算する問題のことを基底gのn次のべき乗剰余類問題といい、Class[n,g]と記することにする。Class[n,g]は、
【数４０】
およびg∈βに関して、random-self-reducibleという性質を有するので(非特許文献)[12]、Class[n,g]の計算量的困難性は、実際は
【数４１】
およびg∈Bの選択に依存しない。 従って、単に、
【数４２】
から[[w]]gを計算する問題のことをn次のべき乗剰余類問題といい、Class[n]と記することにする。そして、Class[n]を解く確率的多項式時間アルゴリズムが存在しないという仮定のことを、Computational Composite Residuosity Assumption (略して, CCRA)という。
Sn = [u < n2|u ≡ 1 mod n]とおくと、Sn上の関数Lが、L(u) = (u-1)/nで定義される。
【００４３】
Paillier暗号は、p,qを素数とし、n=pqとする。λ=λ(n)と おき、g∈RBとする。これは、gcd(L(gλmod n2),n) = 1 をチェックことで検証される。
公開鍵は、(n,g)であり、秘密鍵は、(p,q,λ)である。
暗号化は、平文m(m<n)に対して、r<nをランダムに選び、暗号文C = gmrn mod n2を計算する。
復号は、暗号文Cに対して、L(Cλmod n2)=L(gλ mod n2) mod nを計算する。
【００４４】
秘密鍵を知らないでこの暗号関数の逆演算をすることは、CCRAと同値であること、および、この暗号スキームが(能動的でない攻撃に対して)強秘匿性(semantic security)を有することはDCRAと同値であることが示されている(非特許文献１４)。
【００４５】
紛失通信において、送り手SはN個の秘密データm1,m2,……,mNをもっているものとする。X=( m1,m2,……,mN)とおき、受け手Rは、Xの中から1つデータ(例えば、mα)が欲しいものとし、送り手Sへ問い合わせ(query)をし、送り手Sがその結果を受け手Rに返す際、送り手Sはαについて情報を得ることができないことと、受け手Rは得るはずのデータ(例えば、mα)以外の情報を得ることができないこと、の2つの要求がある点が、秘匿情報検索スキームと異なっている。
【００４６】
一般的な1ラウンドのOTのプロトコルは、以下のような要件を満たす手順である。
まず、受け手Rは、システムパラメータを生成し、受け手Rは問い合わせQuery(α) を計算して、Query(α)を送り手Sに送る。
次に、送り手Sは、Query(α)を受け取り、多項式時間の計算を行い、Answer(Query(α))をその計算結果として得て、送り手SはAnswer(Query(α))を送り手Rに戻す。
そして、受け手RはAnswer(Query(α))を受け取り、多項式時間の計算を行い、 知りたかった情報(Xにおけるα番目のデータmα)を得る。
【００４７】
正当性(Correctness)については、受け手Rも送り手Sも正直に手順を踏んでいる場合、どのようなX、どのようなQuery(α)であっても、受け手Rはmαを得る。
【００４８】
受け手RのプライバシSでは、任意のα,βに対してα番目のデータmαとβ番目のデータmβの区別が付かない。本発明では、受け手Rのプライバシは計算量的な安全性を有する、すなわち、送り手Sは、受け手Rからの2つの問い合わせを確率的多項式時間アルゴリズムによって無視できない確率で区別することができない。
【００４９】
形式的には、任意のc、長さnの任意のデータベース、任意のα,β(1≦α,β≦Ｎ)、任意の(一様/非一様な)確率的多項式時間アルゴリズムAに対して、ある整数Kが存在して、任意のk>Kに対して、
【数４３】
kはプロトコルのセキュリティパラメータであり、
【数４４】
を満たすことである。
【００５０】
送り手Sのプライバシでは、受け手Rは、得たもの(mα)以外のデータmβ(β≠α)については如何なる情報も得ることができない。本発明では、送り手Sのプライバシは情報量的な安全性を有する、すなわち、受け手Rはどのような計算能力を有するにしても、データmβ(β≠α)を情報を得ることができない。
なお、本実施例では、受け手Rまたは送り手Sの能動的な攻撃については考慮していない。つまり、受け手Rと送り手Sは、両方とも正直にプロトコルに従っているものとする。
【００５１】
計算量については、受け手Rと送り手Sの両方の計算量は、データベースのサイズのNとセキュリティパラメータkに関する多項式により上から抑えられている。
【００５２】
ここで、本発明では、岡本-内山暗号を利用して
【数４５】
を構成する。
送り手SはN個の秘密データm1,m2,……,mNをもっているものとする。受け手Rは、その中から1つデータmαが欲しいものとする。
セキュリティパラメータkは、
【数４６】
が成り立つように十分大きくとる。例えば、N≦2k-1が成り立っていると仮定しても良い。
【００５３】
まず、受け手Rは、岡本-内山暗号と同じようにパラメータを(p,q,n)を取る。
【数４７】
を
【数４８】
となるように取り、
【数４９】
とし、
【数５０】
とおく。
【数５１】
として、
【数５２】
とおく。送り手Sへの問い合わせQuery(α)=(n,k,g1,g2,f)を送る。
【００５４】
次に、送り手Sは、
【数５３】
を選び、
【数５４】
を計算する。受け手Rへ回答Answer(Query(α))=(c1,c2,……,cN)を送る。
【００５５】
そして、受け手Rは、
【数５５】
を計算して、mαを得る。
【００５６】
プライバシは、受け手Rのプライバシに対して計算量的安全性を有し、送り手Sのプライバシに対して(能動的でない攻撃に対して)情報量的安全性を有することを示す。
能動的な攻撃に対しては、ゼロ知識証明によるテクニックを組み込む必要がある(非特許文献７)。
【００５７】
p-部分群仮定の下で、受け手Rのプライバシが保証される。
情報量的に送り手Sのプライバシが保証される。
【００５８】
Paillier暗号を利用して
【数５６】
を構成するには、次のように行う。
まず、受け手Rは、Paillier暗号と同じようにパラメータを(p,q,n)を取る。G1 ∈R Bを取り、
【数５７】
とし、
【数５８】
とおく。
【数５９】
として、
【数６０】
とおく。送り手Sへの問い合わせQuery(α)=(n,k,g1,g2,f)を送る。
次に、送り手Sは、
【数６１】
を選び、
【数６２】
を計算する。受け手Rへ回答Answer(Query(α))=(c1,c2,……,cN)を送る。
そして、受け手Rは、
【数６３】
を計算して、mαを得る。
【００５９】
プライバシは、受け手Rのプライバシに対して計算量的安全性を有し、送り手S のプライバシに対して(能動的でない攻撃に対して)情報量的安全性を有することを示す。
能動的な攻撃に対しては、ゼロ知識証明によるテクニックを組み込む必要がある(非特許文献７)。
【００６０】
DCRA仮定の下で、受け手Rのプライバシが保証される。
情報量的に送り手Sのプライバシが保証される。
【００６１】
Tzeng(非特許文献８)は、Decisional Diffie-Hellman Problem (DDH)に基づいた効率的なOTを提案している。それに対して、本実施例では、p-部分群仮定、並びにDCRA仮定に依存している。
Tzengの
【数６４】
では、送り手Sのプライバシは計算量的安全性を、受け手Rのプライバシは情報量的安全性を備えているのに対して、本実施例ではその逆に、送り手Sのプライバシは情報量的安全性を、受け手Rのプライバシは計算量的安全性を備えている。
【００６２】
cPIR(非特許文献５)は、2者、つまり、ユーザUとデータベースDBの間のプロトコルであり、両者はそれぞれ確率的多項式時間アルゴリズムを実行できる。DBは、同じ長さのビット列の列X=(m1,m2,……,mN)をデータベースとして保持している。通常は、m1,m2... ,mN ∈ [0, 1]であり1ビット以上のデータが欲しければPIRを繰り返し行う必要がある。
【００６３】
計算量的に安全な単一データベースのPIRを構成するには、まず、ユーザUはシステムパラメータを生成する。ユーザUは、問い合わせQuery(α)を計算して、Query(α)をデータベースDBに送る。
次に、データベースDBはQuery(α)を受け取り、多項式時間の計算を行い、Answer(Query(α))をその計算結果として得る。データベースDBはAnswer(Query(α))をユーザUに戻す。
そして、ユーザUはAnswer(Query(α))を受け取り、多項式時間の計算を行い、知りたかった情報(Xにおけるα番目のデータmα)を得る。
【００６４】
正当性については、どちら側も正直に手順を踏んでいる場合、どのようなX、どのようなQuery(α)であっても、ユーザUはmαを得る。
【００６５】
プライバシについては、データベースDBは、ユーザUからの2つの問い合わせを確率的多項式時間アルゴリズムによって無視できない確率で区別することができない。形式的には、任意のc、長さnの任意のデータベースUB、任意のα,β(1≦α,β≦N)、任意の(一様/非一様な)確率的多項式時間アルゴリズムAに対して、ある整数Kが存在して、任意のk>Kに対して、|Prob(A(Query(α)) = 1)−Prob(A(Query(β)) = 1)｜< σ(kはプロトコルのセキュリティパラメータであり、
【数６５】
を満たすことである。
【００６６】
ユーザUとデータベースDBの両方の計算量は、データベースDBのサイズのNとセキュリティパラメータkに関する多項式により上から抑えられている。
【００６７】
ここで、岡本-内山暗号を利用してPIRを構成する。
まず、ユーザUは、α番目の情報mαを欲しいものとする。ユーザUは、
【数６６】
を満たすようにgi(1≦i≦N)を生成する。
次に、データベースDBは、
【数６７】
を選び、回答
【数６８】
をユーザUへを送る。
そして、ユーザUは、
【数６９】
を計算することで、所望のmαを得る。
【００６８】
ユーザUのプライバシは、
【数７０】
における
【数７１】
の部分群メンバーシップ問題の仮定の下で保証される。
【００６９】
Paillier 暗号を利用してPIRを構成するには、次のように行う。
まず、ユーザUは、α番目の情報mαを欲しいものとする。ユーザUは、
【数７２】
【数７３】
を満たすようにgi(1≦i≦Ｎ)を生成する。
次に、データベースDBは、
【数７４】
を選び、回答
【数７５】
をユーザUへを送る。
そして、ユーザUは、
【数７６】
を計算することで、所望のmαを得る。
【００７０】
ユーザUのプライバシは、DCRA仮定の下で保証される。
【００７１】
本来、PIRはデータベースDBのプライバシを保証していない。非特許文献１５において、sPIRが提案されている。非特許文献１６で、OTとPIRを結合してsPIRを構成することが可能である。本発明においても、同一の暗号プリミティブを使ってOTとPIRを構成可能であり、ユーザUのプライバシはそれぞれの困難性の仮定の下で、データベースDBのプライバシは情報量的安全性に基づいた、1ラウンドで単一サーバであるsPIRを構成可能である。
【産業上の利用可能性】
【００７２】
本発明によると、一部暗号化した情報を効率よく授受伝達できると共に、受け手やユーザ側のプライバシが計算量的安全性を備え、送り手やデータベース側のプライバシが情報量的安全性を備えるので、電子認証や電子商取引など、プライバシが関わるあらゆる暗号通信技術の基幹になり得て、産業上利用価値が高い。
【図面の簡単な説明】
【００７３】
【図１】問い合わせを行うコンピュータとデータベースの設定例を示す説明図
【図２】受け手またはユーザと、送り手またはデータベースとのデータ授受の概要を示す説明図
【図３】紛失通信及び秘密情報検索の一般的な処理の流れを示す流れ図である。
【特許請求の範囲】
【請求項１】
少なくともデータの入出力手段、記録手段、演算手段を備えた複数のコンピュータと、それらの間でデータの授受を行う通信手段とを有し、
平文と乱数と公開鍵から暗号文を作成し、秘密鍵で復号するエルガマル暗号を用いて、情報の授受伝達が可能なネットワークシステムにおいて、
送り手が複数の秘密データを有していて、受け手がその中の一部データを欲している場合、
岡本-内山暗号を用いて紛失通信(Oblivious Transfer)を構成するに当たり、
まず、受け手は、
岡本-内山暗号に従って、秘密鍵と公開鍵に関するパラメータを取り、システムパラメータを生成し、送り手への問い合わせを計算して送り、
それに対して、送り手は、
岡本-内山暗号に従う暗号化によって、多項式時間の計算を行ない、その計算結果を回答として受け手へ戻し、
それにより、受け手は、
岡本-内山暗号に従う復号によって、多項式時間の計算を行ない、所望のデータを得る
ことを特徴とするエルガマル暗号による情報授受伝達方法。
【請求項２】
少なくともデータの入出力手段、記録手段、演算手段を備えた複数のコンピュータと、それらの間でデータの授受を行う通信手段とを有し、
平文と乱数と公開鍵から暗号文を作成し、秘密鍵で復号するエルガマル暗号を用いて、情報の授受伝達が可能なネットワークシステムにおいて、
送り手が複数の秘密データを有していて、受け手がその中の一部データを欲している場合、
Paillier暗号を用いて紛失通信(Oblivious Transfer)を構成するに当たり、
まず、受け手は、
Paillier暗号に従って、秘密鍵と公開鍵に関するパラメータを取り、システムパラメータを生成し、送り手への問い合わせを計算して送り、
それに対して、送り手は、
Paillier暗号に従う暗号化によって、多項式時間の計算を行ない、その計算結果を回答として受け手へ戻し、
それにより、受け手は、
Paillier暗号に従う復号によって、多項式時間の計算を行ない、所望のデータを得る
ことを特徴とするエルガマル暗号による情報授受伝達方法。
【請求項３】
少なくともデータの入出力手段、記録手段、演算手段を備えた複数のコンピュータと、それらの間でデータの授受を行う通信手段とを有し、
平文と乱数と公開鍵から暗号文を作成し、秘密鍵で復号するエルガマル暗号を用いて、情報の授受伝達が可能なネットワークシステムにおいて、
データベースが複数の秘密データを有していて、ユーザがその中の一部データを欲している場合、
岡本-内山暗号を用いて秘匿情報検索(Private Information Retrieval)を構成するに当たり、
まず、ユーザは、
岡本-内山暗号に従って、秘密鍵と公開鍵に関するパラメータを取り、システムパラメータを生成し、データベースへの問い合わせを計算して送り、
それに対して、データベースは、
岡本-内山暗号に従う暗号化によって、多項式時間の計算を行ない、その計算結果を回答としてユーザへ戻し、
それにより、ユーザは、
岡本-内山暗号に従う復号によって、多項式時間の計算を行ない、所望のデータを得る
ことを特徴とするエルガマル暗号による情報授受伝達方法。
【請求項４】
少なくともデータの入出力手段、記録手段、演算手段を備えた複数のコンピュータと、それらの間でデータの授受を行う通信手段とを有し、
平文と乱数と公開鍵から暗号文を作成し、秘密鍵で復号するエルガマル暗号を用いて、情報の授受伝達が可能なネットワークシステムにおいて、
データベースが複数の秘密データを有していて、ユーザがその中の一部データを欲している場合、
Paillier暗号を用いて秘匿情報検索(Private Information Retrieval)を構成するに当たり、
まず、ユーザは、
Paillier暗号に従って、秘密鍵と公開鍵に関するパラメータを取り、システムパラメータを生成し、データベースへの問い合わせを計算して送り、
それに対して、データベースは、
Paillier暗号に従う暗号化によって、多項式時間の計算を行ない、その計算結果を回答としてユーザへ戻し、
それにより、ユーザは、
Paillier暗号に従う復号によって、多項式時間の計算を行ない、所望のデータを得る
ことを特徴とするエルガマル暗号による情報授受伝達方法。
【請求項５】
ゼロ知識証明による工程を組み込み、能動的な攻撃を抑止する
請求項１ないし４に記載のエルガマル暗号による情報授受伝達方法。
【請求項６】
1回のアクセスで、指定した1つのデータ以外の情報を取得できないプライバシ保護機能をもつ請求項１ないし５に記載のエルガマル暗号による情報授受伝達方法。
【請求項７】
少なくともデータの入出力手段、記録手段、演算手段を備えた複数のコンピュータと、それらの間でデータの授受を行う通信手段とを有し、
平文と乱数と公開鍵から暗号文を作成し、秘密鍵で復号するエルガマル暗号を用いて、情報の授受伝達が可能なネットワークシステムにおいて、
送り手が複数の秘密データを有していて、受け手がその中の一部データを欲している場合、
岡本-内山暗号を用いて紛失通信(Oblivious Transfer)を構成するに当たり、
受け手は、
岡本-内山暗号に従って、秘密鍵と公開鍵に関するパラメータを取り、システムパラメータを生成し、送り手への問い合わせを計算して送る問い合わせ手段を備え、
それに対する送り手は、
岡本-内山暗号に従う暗号化によって、多項式時間の計算を行ない、その計算結果を回答として受け手へ戻す回答手段を備え、
また、受け手は、
岡本-内山暗号に従う復号によって、多項式時間の計算を行ない、所望のデータを得る求値手段を備える
ことを特徴とするエルガマル暗号による情報授受伝達装置。
【請求項８】
少なくともデータの入出力手段、記録手段、演算手段を備えた複数のコンピュータと、それらの間でデータの授受を行う通信手段とを有し、
平文と乱数と公開鍵から暗号文を作成し、秘密鍵で復号するエルガマル暗号を用いて、情報の授受伝達が可能なネットワークシステムにおいて、
送り手が複数の秘密データを有していて、受け手がその中の一部データを欲している場合、
Paillier暗号を用いて紛失通信(Oblivious Transfer)を構成するに当たり、
受け手は、
Paillier暗号に従って、秘密鍵と公開鍵に関するパラメータを取り、システムパラメータを生成し、送り手への問い合わせを計算して送る問い合わせ手段を備え、
それに対する送り手は、
Paillier暗号に従う暗号化によって、多項式時間の計算を行ない、その計算結果を回答として受け手へ戻す回答手段を備え、
また、受け手は、
Paillier暗号に従う復号によって、多項式時間の計算を行ない、所望のデータを得る求値手段を備える
ことを特徴とするエルガマル暗号による情報授受伝達装置。
【請求項９】
少なくともデータの入出力手段、記録手段、演算手段を備えた複数のコンピュータと、それらの間でデータの授受を行う通信手段とを有し、
平文と乱数と公開鍵から暗号文を作成し、秘密鍵で復号するエルガマル暗号を用いて、情報の授受伝達が可能なネットワークシステムにおいて、
データベースが複数の秘密データを有していて、ユーザがその中の一部データを欲している場合、
岡本-内山暗号を用いて秘匿情報検索(Private Information Retrieval)を構成するに当たり、
ユーザは、
岡本-内山暗号に従って、秘密鍵と公開鍵に関するパラメータを取り、システムパラメータを生成し、データベースへの問い合わせを計算して送る問い合わせ手段を備え、
それに対するデータベースは、
岡本-内山暗号に従う暗号化によって、多項式時間の計算を行ない、その計算結果を回答としてユーザへ戻す回答手段を備え、
また、ユーザは、
岡本-内山暗号に従う復号によって、多項式時間の計算を行ない、所望のデータを得る求値手段を備える
ことを特徴とするエルガマル暗号による情報授受伝達装置。
【請求項１０】
少なくともデータの入出力手段、記録手段、演算手段を備えた複数のコンピュータと、それらの間でデータの授受を行う通信手段とを有し、
平文と乱数と公開鍵から暗号文を作成し、秘密鍵で復号するエルガマル暗号を用いて、情報の授受伝達が可能なネットワークシステムにおいて、
データベースが複数の秘密データを有していて、ユーザがその中の一部データを欲している場合、
Paillier暗号を用いて秘匿情報検索(Private Information Retrieval)を構成するに当たり、
ユーザは、
Paillier暗号に従って、秘密鍵と公開鍵に関するパラメータを取り、システムパラメータを生成し、データベースへの問い合わせを計算して送る問い合わせ手段を備え、
それに対するデータベースは、
Paillier暗号に従う暗号化によって、多項式時間の計算を行ない、その計算結果を回答としてユーザへ戻す回答手段を備え、
また、ユーザは、
Paillier暗号に従う復号によって、多項式時間の計算を行ない、所望のデータを得る求値手段を備える
ことを特徴とするエルガマル暗号による情報授受伝達装置。
【請求項１】
少なくともデータの入出力手段、記録手段、演算手段を備えた複数のコンピュータと、それらの間でデータの授受を行う通信手段とを有し、
平文と乱数と公開鍵から暗号文を作成し、秘密鍵で復号するエルガマル暗号を用いて、情報の授受伝達が可能なネットワークシステムにおいて、
送り手が複数の秘密データを有していて、受け手がその中の一部データを欲している場合、
岡本-内山暗号を用いて紛失通信(Oblivious Transfer)を構成するに当たり、
まず、受け手は、
岡本-内山暗号に従って、秘密鍵と公開鍵に関するパラメータを取り、システムパラメータを生成し、送り手への問い合わせを計算して送り、
それに対して、送り手は、
岡本-内山暗号に従う暗号化によって、多項式時間の計算を行ない、その計算結果を回答として受け手へ戻し、
それにより、受け手は、
岡本-内山暗号に従う復号によって、多項式時間の計算を行ない、所望のデータを得る
ことを特徴とするエルガマル暗号による情報授受伝達方法。
【請求項２】
少なくともデータの入出力手段、記録手段、演算手段を備えた複数のコンピュータと、それらの間でデータの授受を行う通信手段とを有し、
平文と乱数と公開鍵から暗号文を作成し、秘密鍵で復号するエルガマル暗号を用いて、情報の授受伝達が可能なネットワークシステムにおいて、
送り手が複数の秘密データを有していて、受け手がその中の一部データを欲している場合、
Paillier暗号を用いて紛失通信(Oblivious Transfer)を構成するに当たり、
まず、受け手は、
Paillier暗号に従って、秘密鍵と公開鍵に関するパラメータを取り、システムパラメータを生成し、送り手への問い合わせを計算して送り、
それに対して、送り手は、
Paillier暗号に従う暗号化によって、多項式時間の計算を行ない、その計算結果を回答として受け手へ戻し、
それにより、受け手は、
Paillier暗号に従う復号によって、多項式時間の計算を行ない、所望のデータを得る
ことを特徴とするエルガマル暗号による情報授受伝達方法。
【請求項３】
少なくともデータの入出力手段、記録手段、演算手段を備えた複数のコンピュータと、それらの間でデータの授受を行う通信手段とを有し、
平文と乱数と公開鍵から暗号文を作成し、秘密鍵で復号するエルガマル暗号を用いて、情報の授受伝達が可能なネットワークシステムにおいて、
データベースが複数の秘密データを有していて、ユーザがその中の一部データを欲している場合、
岡本-内山暗号を用いて秘匿情報検索(Private Information Retrieval)を構成するに当たり、
まず、ユーザは、
岡本-内山暗号に従って、秘密鍵と公開鍵に関するパラメータを取り、システムパラメータを生成し、データベースへの問い合わせを計算して送り、
それに対して、データベースは、
岡本-内山暗号に従う暗号化によって、多項式時間の計算を行ない、その計算結果を回答としてユーザへ戻し、
それにより、ユーザは、
岡本-内山暗号に従う復号によって、多項式時間の計算を行ない、所望のデータを得る
ことを特徴とするエルガマル暗号による情報授受伝達方法。
【請求項４】
少なくともデータの入出力手段、記録手段、演算手段を備えた複数のコンピュータと、それらの間でデータの授受を行う通信手段とを有し、
平文と乱数と公開鍵から暗号文を作成し、秘密鍵で復号するエルガマル暗号を用いて、情報の授受伝達が可能なネットワークシステムにおいて、
データベースが複数の秘密データを有していて、ユーザがその中の一部データを欲している場合、
Paillier暗号を用いて秘匿情報検索(Private Information Retrieval)を構成するに当たり、
まず、ユーザは、
Paillier暗号に従って、秘密鍵と公開鍵に関するパラメータを取り、システムパラメータを生成し、データベースへの問い合わせを計算して送り、
それに対して、データベースは、
Paillier暗号に従う暗号化によって、多項式時間の計算を行ない、その計算結果を回答としてユーザへ戻し、
それにより、ユーザは、
Paillier暗号に従う復号によって、多項式時間の計算を行ない、所望のデータを得る
ことを特徴とするエルガマル暗号による情報授受伝達方法。
【請求項５】
ゼロ知識証明による工程を組み込み、能動的な攻撃を抑止する
請求項１ないし４に記載のエルガマル暗号による情報授受伝達方法。
【請求項６】
1回のアクセスで、指定した1つのデータ以外の情報を取得できないプライバシ保護機能をもつ請求項１ないし５に記載のエルガマル暗号による情報授受伝達方法。
【請求項７】
少なくともデータの入出力手段、記録手段、演算手段を備えた複数のコンピュータと、それらの間でデータの授受を行う通信手段とを有し、
平文と乱数と公開鍵から暗号文を作成し、秘密鍵で復号するエルガマル暗号を用いて、情報の授受伝達が可能なネットワークシステムにおいて、
送り手が複数の秘密データを有していて、受け手がその中の一部データを欲している場合、
岡本-内山暗号を用いて紛失通信(Oblivious Transfer)を構成するに当たり、
受け手は、
岡本-内山暗号に従って、秘密鍵と公開鍵に関するパラメータを取り、システムパラメータを生成し、送り手への問い合わせを計算して送る問い合わせ手段を備え、
それに対する送り手は、
岡本-内山暗号に従う暗号化によって、多項式時間の計算を行ない、その計算結果を回答として受け手へ戻す回答手段を備え、
また、受け手は、
岡本-内山暗号に従う復号によって、多項式時間の計算を行ない、所望のデータを得る求値手段を備える
ことを特徴とするエルガマル暗号による情報授受伝達装置。
【請求項８】
少なくともデータの入出力手段、記録手段、演算手段を備えた複数のコンピュータと、それらの間でデータの授受を行う通信手段とを有し、
平文と乱数と公開鍵から暗号文を作成し、秘密鍵で復号するエルガマル暗号を用いて、情報の授受伝達が可能なネットワークシステムにおいて、
送り手が複数の秘密データを有していて、受け手がその中の一部データを欲している場合、
Paillier暗号を用いて紛失通信(Oblivious Transfer)を構成するに当たり、
受け手は、
Paillier暗号に従って、秘密鍵と公開鍵に関するパラメータを取り、システムパラメータを生成し、送り手への問い合わせを計算して送る問い合わせ手段を備え、
それに対する送り手は、
Paillier暗号に従う暗号化によって、多項式時間の計算を行ない、その計算結果を回答として受け手へ戻す回答手段を備え、
また、受け手は、
Paillier暗号に従う復号によって、多項式時間の計算を行ない、所望のデータを得る求値手段を備える
ことを特徴とするエルガマル暗号による情報授受伝達装置。
【請求項９】
少なくともデータの入出力手段、記録手段、演算手段を備えた複数のコンピュータと、それらの間でデータの授受を行う通信手段とを有し、
平文と乱数と公開鍵から暗号文を作成し、秘密鍵で復号するエルガマル暗号を用いて、情報の授受伝達が可能なネットワークシステムにおいて、
データベースが複数の秘密データを有していて、ユーザがその中の一部データを欲している場合、
岡本-内山暗号を用いて秘匿情報検索(Private Information Retrieval)を構成するに当たり、
ユーザは、
岡本-内山暗号に従って、秘密鍵と公開鍵に関するパラメータを取り、システムパラメータを生成し、データベースへの問い合わせを計算して送る問い合わせ手段を備え、
それに対するデータベースは、
岡本-内山暗号に従う暗号化によって、多項式時間の計算を行ない、その計算結果を回答としてユーザへ戻す回答手段を備え、
また、ユーザは、
岡本-内山暗号に従う復号によって、多項式時間の計算を行ない、所望のデータを得る求値手段を備える
ことを特徴とするエルガマル暗号による情報授受伝達装置。
【請求項１０】
少なくともデータの入出力手段、記録手段、演算手段を備えた複数のコンピュータと、それらの間でデータの授受を行う通信手段とを有し、
平文と乱数と公開鍵から暗号文を作成し、秘密鍵で復号するエルガマル暗号を用いて、情報の授受伝達が可能なネットワークシステムにおいて、
データベースが複数の秘密データを有していて、ユーザがその中の一部データを欲している場合、
Paillier暗号を用いて秘匿情報検索(Private Information Retrieval)を構成するに当たり、
ユーザは、
Paillier暗号に従って、秘密鍵と公開鍵に関するパラメータを取り、システムパラメータを生成し、データベースへの問い合わせを計算して送る問い合わせ手段を備え、
それに対するデータベースは、
Paillier暗号に従う暗号化によって、多項式時間の計算を行ない、その計算結果を回答としてユーザへ戻す回答手段を備え、
また、ユーザは、
Paillier暗号に従う復号によって、多項式時間の計算を行ない、所望のデータを得る求値手段を備える
ことを特徴とするエルガマル暗号による情報授受伝達装置。
【図１】
【図２】
【図３】
【図２】
【図３】
【公開番号】特開２００６−２１０９６４（Ｐ２００６−２１０９６４Ａ）
【公開日】平成１８年８月１０日（２００６．８．１０）
【国際特許分類】
【出願番号】特願２００５−１６１８２（Ｐ２００５−１６１８２）
【出願日】平成１７年１月２４日（２００５．１．２４）
【出願人】（３０１０２２４７１）独立行政法人情報通信研究機構 (1,071)
【Ｆターム（参考）】
【公開日】平成１８年８月１０日（２００６．８．１０）
【国際特許分類】
【出願日】平成１７年１月２４日（２００５．１．２４）
【出願人】（３０１０２２４７１）独立行政法人情報通信研究機構 (1,071)
【Ｆターム（参考）】
[ Back to top ]