説明

復号システム、鍵装置、復号方法、及びプログラム

【課題】端末装置に対する制御を行うことなく、端末装置が暗号文の復号結果を閲覧する権限を無効化する。
【解決手段】何れかの端末装置11−uに対応する登録許可情報を鍵装置12の登録許可情報記憶部121に格納しておく。鍵装置12に暗号文と端末情報とが入力されると、鍵装置12は当該端末情報が登録許可情報記憶部121に格納された何れかの登録許可情報に対応するかを判定する。端末情報が登録許可情報記憶部121に格納された何れかの登録許可情報に対応する場合、鍵装置12は暗号文の復号結果に対応する応答情報を出力する。応答情報は端末装置11−uに送られ、端末装置11−uは応答情報から復号結果を得る。

【発明の詳細な説明】
【技術分野】
【0001】
本発明は、暗号文の復号技術に関する。
【背景技術】
【0002】
秘密文書などの秘密情報が暗号化された暗号文の復号を特定の端末装置のみに許可し、許可された端末装置のみに復号結果を閲覧させる技術がある。このような技術では、許可された端末装置が紛失や盗難などの事情で第三者の手に渡ったときに、その端末装置を入手した第三者が秘密情報を閲覧できるという問題がある。
【0003】
このような問題に対する従来技術には大きく2つの方針がある。第1の方針は、端末装置に対して遠隔操作を施し、第三者の手に渡った端末装置を無効化するものである。第2の方針は、端末装置の他に端末装置と通信する安全なデバイスを設置して、そのデバイスを制御することで、端末装置の復号機能を無効化するものである。
【0004】
第1の方針による技術には、携帯電話に対する遠隔ロックサービスなどがある(例えば、非特許文献1等参照)。第2の方針による技術には、有効期限が限られた鍵を払い出すデバイスを用いる方式がある(例えば、非特許文献2等参照)。例えばIDベース暗号方式などに則り、安全なデバイスに格納されたマスター秘密鍵から一定期間のみ復号アルゴリズムの鍵として機能する二次秘密鍵を生成し、二次秘密鍵のみを端末装置に格納する。端末装置は二次秘密鍵を用いて暗号文を復号できるが、一定期間を過ぎた二次秘密鍵では暗号文を復号できない。第三者の手に渡った端末装置では、格納された二次秘密鍵が更新されないため、一定期間の後にはその端末装置の復号機能が無効化される。
【先行技術文献】
【非特許文献】
【0005】
【非特許文献1】涌井道子、竹内伸夫、一瀬晃弘、小野木雅、”端末管理に対する多様なニーズに対応した端末管理制御基盤システムの開発”、[online]、平成21年10月、NTT DOCOMOテクニカル・ジャーナルVol.17 No.3、P50−54、[平成22年12月31日検索]、インターネット<http://www.nttdocomo.co.jp/binary/pdf/corporate/technology/rd/technical_journal/bn/vol17_3/vol17_3_050jp.pdf>
【非特許文献2】A. Boldyreva, V. Goyal, V. Kumar, “Identity-based Encryption with Efficient Revocation,” Proceedings of the 14th ACM Conference on Computer and Communications Security, CCS 2008, ACM Press, 2008, pp. 417-426.
【発明の概要】
【発明が解決しようとする課題】
【0006】
しかしながら、第1の方針では端末装置の機能を遠隔操作でロックすることができない場合には、端末装置の復号機能を無効化できない。第2の方針では、すべての端末装置に格納された鍵の更新が必要となり、運用のためのコストがかさむ。
【0007】
本発明はこのような点に鑑みてなされたものであり、端末装置に対する制御を行うことなく、端末装置が暗号文の復号結果を閲覧する権限を無効化できる技術を提供することを目的とする。
【課題を解決するための手段】
【0008】
何れかの端末装置に対応する登録許可情報を鍵装置の登録許可情報記憶部に格納しておく。鍵装置に暗号文と端末情報とが入力されると、鍵装置は当該端末情報が登録許可情報記憶部に格納された何れかの登録許可情報に対応する場合に、暗号文の復号結果に対応する応答情報を出力する。
【発明の効果】
【0009】
登録許可情報が登録許可情報記憶部に格納された端末装置に対応する端末情報と暗号文とが鍵装置に入力された場合、当該端末装置は鍵装置から出力された応答情報から復号結果を得ることができる。一方、登録許可情報記憶部から当該登録許可情報が削除された場合には鍵装置から応答情報は出力されず、当該端末装置は復号結果を得ることができない。
【0010】
このように本発明では、端末装置に対する制御を行うことなく、登録許可情報記憶部に格納された登録許可情報を削除することで、削除した登録許可情報に対応する端末装置が暗号文の復号結果を閲覧する権限を無効化できる。
【図面の簡単な説明】
【0011】
【図1】実施形態の復号システムの全体構成を説明するための図。
【図2】第一実施形態の端末装置と鍵装置の機能構成を説明するための図。
【図3】第一実施形態の復号方法を説明するための図。
【図4】第二実施形態の端末装置と鍵装置の機能構成を説明するための図。
【図5】第二実施形態の復号方法を説明するための図。
【図6】第三実施形態の端末装置と鍵装置の機能構成を説明するための図。
【図7】第三実施形態の復号方法を説明するための図。
【図8】実施形態の復号システムの機能構成を説明するための図。
【図9】実施形態の鍵装置DB(データベース)の機能構成を説明するための図。
【図10】実施形態の端末装置と鍵装置の機能構成を説明するための図。
【図11】実施形態の復号処理部の機能構成を説明するための図。
【図12】実施形態の判定復号部の機能構成を説明するための図。
【図13】第五実施形態の入力情報提供部の機能構成を説明するための図。
【図14】第六実施形態の入力情報提供部の機能構成を説明するための図。
【図15】実施形態の復号方法を説明するための図。
【図16】実施形態の自己訂正処理を説明するための図。
【図17】実施形態の自己訂正処理を説明するための図。
【図18】ステップS504dの処理を説明するための図。
【図19】ステップS604dの処理を説明するための図。
【図20】第七実施形態の復号処理部の機能構成を説明するための図。
【図21】第七実施形態の自己訂正処理を説明するための図。
【図22】第八実施形態の復号処理部の機能構成を説明するための図。
【図23】第八実施形態の判定復号部の機能構成を説明するための図。
【図24】第八実施形態の入力情報提供部の機能構成を説明するための図。
【図25】実施形態の自己訂正処理を説明するための図。
【図26】実施形態の自己訂正処理を説明するための図。
【図27】ステップS804dの処理を説明するための図。
【発明を実施するための形態】
【0012】
以下、図面を参照して本発明の実施形態を説明する。
【0013】
[第一実施形態]
本発明の第一実施形態を説明する。
【0014】
<構成>
図1に例示するように、第一実施形態の復号システム1は、U(Uは1以上の整数)個の端末装置11−u(u=1,・・・,U)と鍵装置12とを有し、これらはネットワークを通じて通信可能に構成されている。
【0015】
図2に例示するように、本形態の端末装置11−uは、それぞれアドレス記憶部111−uと暗号文記憶部112−uと入力部113−uと出力部114−uと制御部115−uと復号処理部116−uとを有する。本形態の鍵装置12は、安全に管理される装置であり、登録許可情報記憶部121と秘密鍵記憶部122と入力部123と出力部124と制御部125と復号部126と登録処理部127とを有する。端末装置11−u及び鍵装置12は、ルータ装置、サーバ装置、携帯電話、ICカードなどの計算機能及び記憶機能を備えた機器や、特別なプログラムが読み込まれたCPU(central processing unit)やRAM(random-access memory)を備えた公知又は専用のコンピュータなどである。端末装置11−uは制御部115−uの制御のもとで各処理を実行し、鍵装置12は制御部125の制御のもとで各処理を実行する。
【0016】
<事前処理>
端末装置11−u(図2)の暗号文記憶部112−uには、公開鍵暗号方式に則って公開鍵yで平文mを暗号化して得られる暗号文C=Enc(y,m)が格納されている。公開鍵暗号方式の例は、ElGamal暗号方式、RSA暗号方式、Pailler暗号方式などである。アドレス記憶部111−uには、端末装置11−uのアドレスAdd(u)(端末情報)が格納されている。アドレスの例はIPアドレスなどである。
【0017】
鍵装置12の秘密鍵記憶部122には、公開鍵yに対応する秘密鍵sが格納されている。登録許可情報記憶部121には、何れかの端末装置11−u’(u’=1,・・・,U)のアドレスAdd(u’)(登録許可情報)のリストListが格納されている。登録処理部127は、リストListに端末装置11−u’のアドレスAdd(u’)を追加する旨の指示や、リストListから端末装置11−u’のアドレスAdd(u’)を削除する旨の指示の入力を受け付ける。前者の指示が入力された登録処理部127は、登録許可情報記憶部121に格納されたリストListに、指示された端末装置11−u’のアドレスAdd(u’)を追加する。後者の指示が入力された登録処理部127は、登録許可情報記憶部121に格納されたリストListから、指示された端末装置11−u’のアドレスAdd(u’)を削除する。
【0018】
<復号処理>
図3に例示するように、端末装置11−u(図2)の復号処理部116−uは、復号を行う暗号文Cを暗号文記憶部122−uから読み込み、端末装置11−uのアドレスAdd(u)をアドレス記憶部111−uから読み込み、これらを出力部114−uに送る。出力部114−uには鍵装置12のアドレスまたはそれに対応する情報が格納されており、出力部114−uは暗号文CとアドレスAdd(u)とを鍵装置12に対して出力する(ステップS101)。
【0019】
暗号文CとアドレスAdd(u)はネットワーク経由で鍵装置12に送信され、鍵装置12の入力部123に入力される(ステップS102)。暗号文CとアドレスAdd(u)は復号部126に送られる。復号部126は、送られたアドレスAdd(u)が登録許可情報記憶部121に格納されたリストListが含む何れかのアドレスAdd(u’)に一致するか(対応するか)を判定する(ステップS103)。
【0020】
ステップS103で、送られたアドレスAdd(u)がリストListに含まれる何れかのアドレスAdd(u’)に一致すると判定された場合、復号部126は、秘密鍵記憶部122から秘密鍵sを読み込み、秘密鍵sを用い、公開鍵暗号方式に則って暗号文Cを復号して復号結果m’=Dec(s,C)を生成する(ステップS104)。復号結果m’(暗号文の復号結果に対応する応答情報)は出力部124に送られ、出力部124は、暗号文Cを送信した端末装置11−uに対して復号結果m’を出力する(ステップS105)。
【0021】
ステップS103で、送られたアドレスAdd(u)がリストListに含まれる何れのアドレスAdd(u’)とも一致しないと判定された場合、復号部126は、復号することができなかったことを示すエラー情報⊥を出力する。情報⊥は出力部124に送られ、出力部124は暗号文Cを送信した端末装置11−uに対してエラー情報⊥を出力する(ステップS106)。
【0022】
復号結果m’またはエラー情報⊥は端末装置11−uの入力部113−uに入力され、復号処理部116−uに送られる(ステップS107)。復号処理部116−uは復号結果m’またはエラー情報⊥を出力する(ステップS108)。
【0023】
<第一実施形態の特徴>
本形態では、登録許可情報記憶部121に格納されたリストListが含むアドレスに対応する端末装置11−uから送信された暗号文Cのみが復号される。そのため、登録許可情報記憶部121に格納されたリストListにアドレスAdd(u)を追加したり、リストListからアドレスAdd(u)を削除したりするだけで、端末装置11−uに暗号文Cの復号結果を取得させるか否かを制御できる。その結果、端末装置11−uに対する制御を行うことなく、登録許可情報記憶部121に格納されたアドレスAdd(u)を削除することで、削除したアドレスAdd(u)に対応する端末装置11−uが暗号文Cの復号結果を閲覧する権限を無効化できる。
【0024】
[第二実施形態]
本発明の第二実施形態を説明する。インターネットなどのネットワークでは、DHCP(Dynamic Host Configuration Protocol)等の技術によって端末装置のアドレスが動的に付与される場合がある。このような場合、端末装置のアドレスをあらかじめ鍵装置に格納しておくことは現実的ではない。これに対して第二実施形態では、端末装置に固有な情報を鍵装置に格納し、鍵装置の出力情報を、固有な情報に対応する端末装置によって復号可能なように暗号化する。以下では第一実施形態との相違点を中心に説明し、第一実施形態と処理が共通する部分には同一の参照番号を用いて説明を省略する。
【0025】
<構成>
図1に例示するように、第二実施形態の復号システム2は、U個の端末装置21−u(u=1,・・・,U)と鍵装置22とを有し、これらはネットワークを通じて通信可能に構成されている。
【0026】
図4に例示するように、本形態の端末装置21−uは、それぞれ固有情報記憶部211−uと暗号文記憶部112−uと入力部113−uと出力部114−uと制御部115−uと復号処理部216−uと復号部217−uとを有する。本形態の鍵装置22は、安全に管理される装置であり、登録許可情報記憶部221と秘密鍵記憶部122と入力部123と出力部124と制御部125と復号部226と登録処理部227とを有する。復号部226は判定復号部2261と暗号化部2262とを有する。端末装置21−u及び鍵装置22は、ルータ装置、サーバ装置、携帯電話、ICカードなどの計算機能及び記憶機能を備えた機器や、特別なプログラムが読み込まれたCPUやRAMを備えた公知又は専用のコンピュータなどである。端末装置21−uは制御部115−uの制御のもとで各処理を実行し、鍵装置22は制御部125の制御のもとで各処理を実行する。
【0027】
<事前処理>
本形態ではアドレス情報記憶部にアドレスが格納される代わりに、端末装置21−uの固有情報記憶部211−uに、端末装置21−uに固有な固有公開情報P(u)(端末情報)及び固有秘密情報S(u)(端末復号鍵)が格納されている。固有公開情報P(u)及び固有秘密情報S(u)は、或る暗号化方式における互いに対応する暗号化鍵及び復号鍵のペアである。この暗号化方式の例は、共通鍵暗号、公開鍵暗号、IDベース暗号などである。例えば、この暗号化方式が共通鍵暗号であればP(u)=S(u)である。この暗号化方式が公開鍵暗号方式であれば、固有公開情報P(u)は公開鍵であり、固有秘密情報S(u)はそれに対応する秘密鍵である。この暗号化方式がIDベース暗号方式であれば、固有公開情報P(u)は鍵装置22のIDであり、固有秘密情報S(u)は鍵装置22のIDに対応する秘密鍵である。
【0028】
また本形態では鍵装置の登録許可情報記憶部に何れかの端末装置のアドレスのリストが格納される代わりに、鍵装置22の登録許可情報記憶部221に何れかの端末装置21−u’(u’=1,・・・,U)の固有公開情報P(u’)(登録許可情報)のリストListが格納されている。登録処理部227は、リストListに端末装置21−u’の固有公開情報P(u’)を追加する旨の指示や、リストListから端末装置21−u’の固有公開情報P(u’)を削除する旨の指示の入力を受け付ける。前者の指示が入力された登録処理部227は、登録許可情報記憶部121に格納されたリストListに、指示された固有公開情報P(u’)を追加する。後者の指示が入力された登録処理部127は、登録許可情報記憶部121に格納されたリストListから、指示された固有公開情報P(u’)を削除する。
【0029】
その他は第一実施形態と同様である。
【0030】
<復号処理>
図5に例示するように、端末装置21−u(図4)の復号処理部216−uは、復号を行う暗号文Cを暗号文記憶部122−uから読み込み、端末装置11−uの固有公開情報P(u)を固有情報記憶部211−uから読み込み、これらを出力部114−uに送る。出力部114−uには鍵装置12のアドレスまたはそれに対応する情報が格納されており、出力部114−uは暗号文Cと固有公開情報P(u)とを鍵装置22に対して出力する(ステップS201)。
【0031】
暗号文Cと固有公開情報P(u)はネットワーク経由で鍵装置22に送信され、鍵装置22の入力部123に入力される(ステップS202)。暗号文Cと固有公開情報P(u)は復号部226に送られる。復号部226の判定復号部2261は、送られた固有公開情報P(u)が登録許可情報記憶部121に格納されたリストListが含む何れかの固有公開情報P(u’)に一致するか(対応するか)を判定する(ステップS203)。
【0032】
ステップS203で、送られた固有公開情報P(u)がリストListに含まれる何れかの固有公開情報P(u’)に一致すると判定された場合、判定復号部2261は、秘密鍵記憶部122から秘密鍵sを読み込み、秘密鍵sを用い、公開鍵暗号方式に則って暗号文Cを復号して復号結果m’=Dec(s,C)を生成する(ステップS104)。復号結果m’と固有公開情報P(u)とは暗号化部2262に送られる。暗号化部2262は、固有公開情報P(u)(端末情報に対応する登録許可情報)を暗号化鍵とし、暗号文Cの復号結果m’を暗号化した暗号文C’=Enc’(P(u),m’)を生成する(ステップS204)。暗号文C’(暗号文の復号結果に対応する応答情報)は出力部124に送られ、出力部124は、暗号文Cを送信した端末装置21−uに対して暗号文C’を出力する(ステップS205)。暗号文C’は端末装置21−uの入力部113−uに入力され、復号部217−uに送られる(ステップS207)。復号部217−u(第2復号部)は、固有情報記憶部211−uから固有秘密情報S(u)を読み込み、固有秘密情報S(u)を復号鍵として用いて暗号文C’を復号し、復号結果m’’=Dec’(S(u),C’)を生成する。復号結果m’’は復号処理部216−uに送られ(ステップS208)、復号処理部216−uは復号結果m’’を出力する(ステップS108)。
【0033】
一方ステップS203で、送られた固有公開情報P(u)がリストListに含まれる何れの固有公開情報P(u’)とも一致しないと判定された場合、復号部226は、復号することができなかったことを示すエラー情報⊥を出力する。情報⊥は出力部124に送られ、出力部124は暗号文Cを送信した端末装置11−uに対してエラー情報⊥を出力する(ステップS106)。エラー情報⊥は端末装置21−uの入力部113−uに入力され、復号処理部216−uに送られて(ステップS107)出力される(ステップS108)。
【0034】
<第二実施形態の特徴>
本形態では、登録許可情報記憶部221に格納されたリストListが含む固有公開情報に対応する端末装置21−uから送信された暗号文Cのみが復号される。そのため登録許可情報記憶部121に格納されたリストListに固有公開情報P(u)を追加したり、リストListから固有公開情報P(u)を削除したりするだけで、端末装置21−uに暗号文Cの復号結果を取得させるか否かを制御できる。その結果、端末装置21−uに対する制御を行うことなく、登録許可情報記憶部221に格納された固有公開情報P(u)を削除することで、削除した固有公開情報P(u)に対応する端末装置21−uが暗号文Cの復号結果を閲覧する権限を無効化できる。
【0035】
また、本形態では端末装置に固有な固有公開情報が判定に用いられるため、装置に動的に割り当てられるアドレスが割り当てられる場合であっても利用できる。
【0036】
[第三実施形態]
本発明の第三実施形態を説明する。上述の各実施形態では鍵装置の管理者が暗号文Cの復号結果を知ることができる。したがって、鍵装置の管理者が端末装置の使用者と異なる場合、端末装置の使用者のみが知るべき情報が鍵装置の管理者に知られる可能性がある。これに対して第三実施形態では、鍵装置がランダム帰着可能な暗号文の復号を行う点がこれまでの実施形態と相違する。ランダム帰着可能な暗号化方式は、ランダム化アルゴリズムと復元アルゴリズムとからなる。ランダム化アルゴリズムは、暗号文と乱数とを用いて別の暗号文を出力する確率アルゴリズムで、出力は入力によらずランダムに選ばれた暗号文と識別できない確率分布に従う。復元アルゴリズムはランダム化アルゴリズムの出力である暗号文を復号した結果とランダム化アルゴリズムで用いられた乱数を入力として、もとの暗号文を復号した平文を出力する。このような暗号方式は、例えばElGamal暗号、楕円ElGamal 暗号、RSA暗号、Pailler暗号などの準同型暗号方式を用いて容易に構成できる。第三の実施形態は、準同型暗号方式を用いてランダム自己帰着可能な暗号方式を構成した例を示しながら記述する。以下では第一及び第二実施形態との相違点を中心に説明し、第一及び第二実施形態と処理が共通する部分には同一の参照番号を用いて説明を省略する。
【0037】
<構成>
図1に例示するように、第三実施形態の復号システム3は、U個の端末装置21−u(u=1,・・・,U)と鍵装置32とを有し、これらはネットワークを通じて通信可能に構成されている。
【0038】
図6に例示するように、本形態の端末装置31−uは、それぞれ固有情報記憶部211−uと暗号文記憶部112−uと入力部113−uと出力部114−uと制御部115−uと復号処理部316−uと復号部317−uとを有する。復号処理部316−uは、乱数生成部3161−uと暗号化部3162−uと復号部3163−uとを有する。本形態の鍵装置32は、安全に管理される装置であり、登録許可情報記憶部221と秘密鍵記憶部122と入力部123と出力部124と制御部125と復号部326と登録処理部227とを有する。復号部326は判定復号部3261と暗号化部3262とを有する。端末装置31−u及び鍵装置32は、ルータ装置、サーバ装置、携帯電話、ICカードなどの計算機能及び記憶機能を備えた機器や、特別なプログラムが読み込まれたCPUやRAMを備えた公知又は専用のコンピュータなどである。端末装置31−uは制御部115−uの制御のもとで各処理を実行し、鍵装置32は制御部125の制御のもとで各処理を実行する。
【0039】
<事前処理>
第二実施形態と同様である。
【0040】
<復号処理>
図7に例示するように、端末装置31−u(図6)の復号処理部316−uの乱数生成部3161−uが乱数Randを生成し、それを暗号化部3162−u及び復号部3163−uに送る。乱数Randは暗号化部3162−u及び復号部3163−u内に格納される(ステップS3011)。暗号化部3162−uは、復号を行う暗号文Cを暗号文記憶部122−uから読み込み、暗号方式のランダム自己帰着性から定義されるランダム化アルゴリズムに則り、暗号文C(第2暗号文)と乱数Randとに対応する暗号文Cを生成する。例えば暗号文Cが準同型暗号方式の暗号文である場合、暗号化部3162−uはそれと同じ準同型暗号方式に則って公開鍵yで乱数Randを暗号化して得られる暗号文(乱数暗号文)をEnc(y,Rand)とし、Enc(y,Rand)とCとの乗法によって暗号文C=Enc(y,Rand)・Cを生成する。暗号文Cと固有公開情報P(u)とは出力部114−uに送られる(ステップS3012)。出力部114−uには鍵装置32のアドレスまたはそれに対応する情報が格納されており、出力部114−uは暗号文Cと固有公開情報P(u)とを鍵装置32に対して出力する(ステップS3013)。
【0041】
暗号文Cと固有公開情報P(u)はネットワーク経由で鍵装置32に送信され、鍵装置32の入力部123に入力される(ステップS302)。暗号文Cと固有公開情報P(u)は復号部326に送られる。復号部326の判定復号部3261は、送られた固有公開情報P(u)が登録許可情報記憶部121に格納されたリストListが含む何れかの固有公開情報P(u’)に一致するか(対応するか)を判定する(ステップS203)。
【0042】
ステップS203で、送られた固有公開情報P(u)がリストListに含まれる何れかの固有公開情報P(u’)に一致すると判定された場合、判定復号部3261は、秘密鍵記憶部122から秘密鍵sを読み込み、秘密鍵sを用い、前述の準同型暗号化方式に則って暗号文Cを復号して復号結果m=Dec(s,C)を生成する(ステップS3041)。復号結果mと固有公開情報P(u)とは暗号化部3262に送られる。暗号化部3262は、固有公開情報P(u)(端末情報に対応する登録許可情報)を暗号化鍵とし、暗号文Cの復号結果mを暗号化した暗号文C’=Enc’(P(u),m)を生成する(ステップS3042)。暗号文C’(暗号文の復号結果に対応する応答情報)は出力部124に送られ、出力部124は、暗号文Cを送信した端末装置31−uに対して暗号文C’を出力する(ステップS305)。暗号文C’は端末装置31−uの入力部113−uに入力され、復号部317−uに送られる(ステップS307)。復号部317−u(第2復号部)は、固有情報記憶部321−uから固有秘密情報S(u)を読み込み、固有秘密情報S(u)を復号鍵として用いて暗号文C’を復号し、復号結果m’=Dec’(S(u),C’)を生成する(ステップS308)。復号結果m’は復号処理部316も復号部3163−uに送られ、復号部3163−u(第3復号部)は、暗号方式のランダム自己帰着性から定義される復元アルゴリズムに則り、復号結果m’と前述の乱数Randとから暗号文C(第2暗号文)の復号結果m’を生成する。例えば前述した暗号文C=Enc(y,Rand)・Cである例の場合、復号部3163−uは乱数Randの逆元Rand−1を用い、m’と元Rand−1との乗法m’=(Rand−1)・m’によって暗号文Cの復号結果m’を得ることができる。これは準同型暗号方式の暗号化関数および復号関数が準同型性を持つことに基づく。復号処理部316−uは復号結果m’を出力する(ステップS108)。
【0043】
一方ステップS203で、送られた固有公開情報P(u)がリストListに含まれる何れの固有公開情報P(u’)とも一致しないと判定された場合、復号部326が復号することができなかったことを示すエラー情報⊥を出力し、第二実施形態のステップS106−S108と同様に処理される。
【0044】
<第三実施形態の特徴>
本形態でも端末装置31−uに対する制御を行うことなく、登録許可情報記憶部221に格納された固有公開情報P(u)を削除することで、削除した固有公開情報P(u)に対応する端末装置31−uが暗号文Cの復号結果を閲覧する権限を無効化できる。
【0045】
また、端末装置に固有な固有公開情報が判定に用いられるため、装置に動的に割り当てられるアドレスが割り当てられる場合であっても利用できる。
【0046】
さらに本形態では、鍵装置32で復号されるのは暗号文Cと乱数Randとに対応する暗号文Cであり、暗号文Cそのものではない。鍵装置32は暗号文Cの復号結果mを得ることができても、鍵装置32は乱数Randを知らないため復号結果mから暗号文Cの復号結果を復元することはできない。これにより、鍵装置32の管理者に暗号文Cの復号結果が知られることを防止できる。
【0047】
[第四実施形態]
本発明の第四実施形態を説明する。上述の各実施形態では、あらかじめ信頼できる鍵装置が設定され、そのアドレスまたはそれに対応する情報があらかじめ端末装置に格納されている必要があった。これに対して第四実施形態では自己訂正技術を用いることで、信頼できる鍵装置があらかじめ設定されていない場合や、信頼できるか否かが定かではない複数の鍵装置しか存在しない場合であっても、運用が可能な形態である。以下では上述の各実施形態との相違点を中心に説明し、上述の各実施形態と処理が共通する部分には同一の参照番号を用いて説明を省略する。
【0048】
<構成>
図8に例示するように、第四実施形態の復号システム4は、U個の端末装置21−u(u=1,・・・,U)とK(Kは1以上の整数)個の鍵装置22−k(k=1,・・・,K)と鍵装置DB(データベース)装置43を有し、これらはネットワークを通じて通信可能に構成されている。
【0049】
図9に例示するように、本形態の鍵装置DB装置43は、鍵装置情報記憶部431と入力部432と出力部433と検索部434とを有する。図10に例示するように、本形態の端末装置41−uは、それぞれ固有情報記憶部211−uと暗号文記憶部412−uと入力部113−uと出力部114−uと制御部115−uと復号処理部416−uと復号部417−uとを有する。本形態の鍵装置42−kは、安全に管理される装置であり、登録許可情報記憶部421−kと秘密鍵記憶部422−kと入力部423−kと出力部424−kと制御部425−kと復号部426−kと登録処理部427−kとを有する。復号部426−kは判定復号部4261−kと暗号化部4262−kとを有する。図11に例示するように、本形態の復号処理部416−uは、例えば、自然数記憶部416a−uと自然数選択部416b−uと整数計算部416c−uと入力情報提供部416d−uと第一計算部416e−uと第一べき乗計算部416f−uと第一リスト記憶部416g−uと第二計算部416h−uと第二べき乗計算部416i−uと第二リスト記憶部416j−uと判定部416k−uと最終出力部416m−uと制御部416n−uとを有する。図12に例示するように、本形態の判定復号部4261−kは、例えば、第一出力情報計算部4261a−kと第二出力情報計算部4261b−kと判定部4261c−kと制御部4261n−kとを有する。
【0050】
鍵装置DB装置43、端末装置41−u及び鍵装置42は、ルータ装置、サーバ装置、携帯電話、ICカードなどの計算機能及び記憶機能を備えた機器や、特別なプログラムが読み込まれたCPUやRAMを備えた公知又は専用のコンピュータなどである。端末装置41−uは制御部115−uの制御のもとで各処理を実行し、鍵装置42−kは制御部425−kの制御のもとで各処理を実行する。
【0051】
<事前処理>
鍵装置DB装置43(図9)の鍵装置情報記憶部431には、公開鍵y(k)をキーとして何れかの鍵装置42−kのアドレスKadd(k)(鍵装置を特定するための鍵装置情報)を記録した鍵装置データベースが格納される。例えば、公開鍵のハッシュ値をbase64などの方法でアスキーテキストに変換して、それをホスト名と見なすダイナミックDNSが構成される。鍵装置データベースを用いることで公開鍵y(k)に対応する鍵装置42−kのアドレスが特定される。なお、必ずしも鍵装置42−kのアドレスが真正である必要はなく、鍵装置42−kが公開鍵y(k)に対応する秘密鍵s(k)で常に正しく復号処理を行うことが保証されている必要もない。
【0052】
端末装置41−u(図10)に対する事前処理は、暗号文記憶部に公開鍵暗号方式に則って公開鍵yで平文mを暗号化して得られる暗号文C=Enc(y,m)が格納されている代わりに、暗号文記憶部112−uに、公開鍵暗号方式に則って公開鍵y(k)で平文mを暗号化して得られる暗号文C=Enc(y(k),m)が格納されている。それ以外は第二実施形態と同様である。
【0053】
鍵装置42−kの秘密鍵記憶部122−kには、公開鍵y(k)に対応する秘密鍵s(k)が格納されている。鍵装置42−kの登録許可情報記憶部421−kに何れかの端末装置411−u’(u’=1,・・・,U)の固有公開情報P(u’)(登録許可情報)のリストListが格納されている。登録処理部427−kは、リストListに端末装置411−u’の固有公開情報P(u’)を追加する旨の指示や、リストListから端末装置411−u’の固有公開情報P(u’)を削除する旨の指示の入力を受け付ける。前者の指示が入力された登録処理部427−kは、登録許可情報記憶部421−kに格納されたリストListに、指示された固有公開情報P(u’)を追加する。後者の指示が入力された登録処理部427−kは、登録許可情報記憶部421−kに格納されたリストListから、指示された固有公開情報P(u’)を削除する。
【0054】
<復号処理>
端末装置41−u(図10)の復号処理部は、復号を行う暗号文C=Enc(y(k),m)に対応する公開鍵y(k)を出力部114−uに出力し、出力部114−uは公開鍵y(k)を鍵装置DB装置43に送信する。公開鍵y(k)は鍵装置DB装置43(図9)の入力部432に入力され、検索部434に送られる。検索部434は、公開鍵y(k)に対応する鍵装置42−kのアドレスKadd(k)を抽出し、アドレスKadd(k)は出力部433から出力される。アドレスKadd(k)は端末装置41−uの入力部113−uに入力され復号処理部416−uに送られる。
【0055】
図15に例示するように、次に復号処理部416−uは、復号を行う暗号文Cを暗号文記憶部422−uから読み込み、端末装置41−uの固有公開情報P(u)を固有情報記憶部211−uから読み込み、これらとアドレスKadd(k)とを出力部114−uに送る。出力部114−uは暗号文Cと固有公開情報P(u)とをアドレスKadd(k)で特定される鍵装置42−kに対して出力する(ステップS401)。
【0056】
暗号文Cと固有公開情報P(u)はネットワーク経由で鍵装置42−kに送信され、鍵装置42−kの入力部423−kに入力される(ステップS402)。暗号文Cと固有公開情報P(u)は復号部426−kに送られる。復号部426−kの判定復号部4261−kは、送られた固有公開情報P(u)が登録許可情報記憶部421−kに格納されたリストListが含む何れかの固有公開情報P(u’)に一致するか(対応するか)を判定する(ステップS403)。
【0057】
送られた固有公開情報P(u)が登録許可情報記憶部421−kに格納されたリストListが含む何れの固有公開情報P(u’)とも一致しないと判定された場合、前述したステップS106−S108と同様な処理が実行される。
【0058】
一方、送られた固有公開情報P(u)が登録許可情報記憶部421−kに格納されたリストListが含む何れかの固有公開情報P(u’)に一致すると判定された場合、その旨が端末装置41−uに通知され、端末装置41−uと登録許可情報記憶部421−kとの間で以下の自己訂正処理が実行される(ステップS404)。そして、復号処理部416−uがその結果である暗号文Cの復号結果m’またはエラー情報⊥を出力する(ステップS108)。
【0059】
<自己訂正処理(ステップS404)>
図16及び17を参照して本形態の自己訂正処理を説明する。処理の前提として、G,Hを巡回群、暗号文Cを群Hの元、暗号文Cの復号結果が群Gの元、f(x)を群Hの元である暗号文x=Cを特定の秘密鍵s(k)で復号して群Gの元を得るための復号関数Dec(s(k),x)、群G,Hの生成元をそれぞれμ,μ、X,Xを群Gに値を持つ確率変数、確率変数Xの実現値をx、確率変数Xの実現値をxとする。また、復号処理部416−uの自然数記憶部416a−uには、互いに素である2つの自然数a,bの組(a,b)が複数種類記憶されているものとする。「自然数」とは0以上の整数を意味する。Iを群Gの位数未満の2つの自然数の組で互いに素なものの集合とすると、自然数記憶部416a−uにはIの部分集合Sに対応する自然数a,bの組(a,b)が記憶されていると考えることができる。
【0060】
図16及び17に例示するように、まず、復号処理部416−u(図11)の自然数選択部416b−uが、自然数記憶部416a−uに記憶された複数の自然数の組(a,b)から1つの自然数の組(a,b)をランダムに読み込む。読み込まれた自然数の組(a,b)少なくとも一部の情報は、整数計算部416c−u、入力情報提供部416d−u、第一べき乗計算部416f−u及び第二べき乗計算部416i−uに送られる(ステップS404a)。
【0061】
整数計算部416c−uは、送られた自然数の組(a,b)を用いて、a’a+b’b=1の関係を満たす整数a’,b’を計算する。自然数a,bは互いに素であるため、a’a+b’b=1の関係を満たす整数a’,b’は必ず存在して、その計算方法もよく知られている。たとえば拡張互除法などのよく知られたアルゴリズムによって整数a’,b’を計算して、自然数の組(a’,b’)の情報は、最終出力部416m−uに送られる(ステップS404b)。
【0062】
制御部416n−uは、t=1とする(ステップS404c)。
【0063】
入力情報提供部416d−uは、入力された暗号文xにそれぞれ対応する群Hの元である第一入力情報τ及び第二入力情報τを生成して出力する。好ましくは、第一入力情報τ及び第二入力情報τはそれぞれ暗号文xとの関係をかく乱させた情報である。これにより、復号処理部416−uは、暗号文xを判定復号部4261−kに対して隠蔽できる。また、好ましくは、本形態の第一入力情報τは自然数選択部416b−uで選択された自然数bにさらに対応し、第二入力情報τは自然数選択部416b−uで選択された自然数aにさらに対応する。これにより、判定復号部4261−kから提供された復号能力を復号処理部416−uが高い精度で評価することが可能となる。第一入力情報τ及び第二入力情報τは出力部114−u(図10)から出力され、鍵装置42−kの入力部423−kに入力され判定復号部4261−kに送られる(ステップS404d)。
【0064】
第一入力情報τは判定復号部4261−k(図12)の第一出力情報計算部4261a−kに入力され、第二入力情報τは第二出力情報計算部4261b−kに入力される(ステップS404e)。
【0065】
第一出力情報計算部4261a−kは、第一入力情報τと秘密鍵記憶部422−kに格納された秘密鍵s(k)とを用い、或る確率より大きな確率でf(τ)を正しく計算し、得られた計算結果を第一出力情報zとする(ステップS404f)。第二出力情報計算部4261b−kは、第二入力情報τと秘密鍵記憶部422−kに格納された秘密鍵s(k)とを用い、或る確率より大きな確率でf(τ)を正しく計算し、得られた計算結果を第二出力情報zとする(ステップS404g)。なお、「或る確率」は100%未満の確率である。「或る確率」の例は無視することができない確率であり、「無視することができない確率」の例は、セキュリティパラメータkについての広義単調増加関数である多項式を多項式ψ(k)とした場合の1/ψ(k)以上の確率である。すなわち、第一出力情報計算部4261a−kや第二出力情報計算部4261b−kは、意図的又は意図的ではない誤差を含んだ計算結果を出力する。言い換えると、第一出力情報計算部4261a−kでの計算結果がf(τ)の場合もあればf(τ)でない場合もあり、第二出力情報計算部4261b−kでの計算結果がf(τ)の場合もあればf(τ)でない場合もある。
【0066】
第一出力情報計算部4261a−kは第一出力情報zを出力し、第二出力情報計算部4261b−kは第二出力情報zを出力する。第一出力情報zおよび第二出力情報zは暗号化部4262−kに送られる。暗号化部4262−kは、固有公開情報P(u)(端末情報に対応する登録許可情報)を暗号化鍵とし、第一出力情報zおよび第二出力情報z(以下「z=(z,z))を暗号化した暗号文C=Enc’(P(u),z)を生成する。暗号文C(暗号文の復号結果に対応する応答情報)は出力部424−kに送られ、出力部424−kは、第一入力情報τ及び第二入力情報τを送信した端末装置41−uに対して暗号文Cを出力する(ステップS404h)。暗号文Cは端末装置41−uの入力部113−uに入力され、復号部417−uに送られる。復号部417−u(第2復号部)は、固有情報記憶部421−uから固有秘密情報S(u)を読み込み、固有秘密情報S(u)を復号鍵として用いて暗号文Cを復号し、復号結果z=Dec’(S(u),C)、すなわち第一出力情報zおよび第二出力情報zを生成する。第一出力情報zは復号処理部416−u(図11)の第一計算部416e−uに入力され、第二出力情報zは第二計算部416h−uに入力される。これらの第一出力情報z及び第二出力情報zが、判定復号部4261−kから復号処理部416−uに与えられた復号能力に相当する(ステップS404i)。
【0067】
第一計算部416e−uは、第一出力情報zから計算結果u=f(x)を生成する。ここで、f(x)を生成(計算)するとは、f(x)と定義される式の値を計算することである。式f(x)の値を最終的に計算することができれば、途中の計算方法は問わない。これは、この出願で登場する他の式の計算についても同様である。また、第一実施形態では群で定義された演算を乗法的に表現する。すなわちα∈Gに対する「α」は、群Gで定義された演算をαに対してb回作用させることを意味し、α,α∈Gに対する「αα」は、αとαとを被演算子とした群Gで定義された演算を行うことを意味する(後述する第五から第七実施形態も同様)。計算結果uは第一べき乗計算部416f−uに送られる(ステップS404j)。
【0068】
第一べき乗計算部416f−uはu’=uを計算する。計算結果uとその計算結果に基づいて計算されたu’との組(u,u’)は、第一リスト記憶部416g−uに記憶される(ステップS404k)。
【0069】
判定部416k−uは、第一リスト記憶部416g−uに記憶された組(u,u’)及び第二リスト記憶部416j−uに記憶された組(v,v’)の中で、u’=v’となるものがあるか判定する(ステップS404m)。もし、第二リスト記憶部416j−uに組(v,v’)が記憶されていない場合には、このステップS404mの処理を行わずに、次のステップS404nの処理を行う。u’=v’となるものがあった場合には、ステップS404uに進む。u’=v’となるものがなかった場合には、ステップS404nに進む。
【0070】
ステップS404nでは、第二計算部416h−uが、第二出力情報zから計算結果v=f(x)を生成する。計算結果vは第二べき乗計算部416i−uに送られる(ステップS404n)。
【0071】
第二べき乗計算部416i−uはv’=vを計算する。計算結果vとその計算結果に基づいて計算されたv’との組(v,v’)は、第二リスト記憶部416j−uに記憶される(ステップS404p)。
【0072】
判定部416k−uは、第一リスト記憶部416g−uに記憶された組(u,u’)及び第二リスト記憶部416j−uに記憶された組(v,v’)の中で、u’=v’となるものがあるか判定する(ステップS404q)。u’=v’となるものがあった場合には、ステップS404uに進む。u’=v’となるものがなかった場合には、ステップS404rに進む。
【0073】
ステップS404rでは、制御部416n−uがt=Tmaxであるか判定する(ステップS404r)。Tmaxは予め定められた自然数である。t=Tmaxであれば、制御部416n−uは、計算をすることができなかった旨の情報、例えば記号「⊥」を出力する(ステップS404t)。t=Tmaxでない場合には、制御部416n−uは、tを1だけインクリメント、すなわちt=t+1として(ステップS404s)、ステップS404dに戻る。
【0074】
計算をすることができなかった旨の情報(この例ではエラー情報⊥)は、判定復号部4261−kが正しく計算を行う信頼性がTmaxで定められる基準を下回るということを意味する。言い換えれば、Tmax回の繰り返しで正しい演算を行うことができなかったということを意味する。
【0075】
ステップS404uでは、最終出力部416m−uが、u’=v’であると判定されたu’及びv’に対応するu及びvを用いてm’=ub’a’を計算して、出力する(ステップS404u)。このように計算されたm’=ub’a’は高い確率で暗号文x=Cを特定の秘密鍵s(k)で復号した復号結果f(x)となる(高い確率でub’a’=f(x)となる理由については後述する)。よって、上述した自己訂正処理を複数回繰り返し、ステップS404uで得られた値のうち最も頻度の高い値を復号結果とすればよい。また、後述するように、設定によっては圧倒的な確率でm’=ub’a’=f(x)となる。その場合にはステップS404uで得られた値をそのまま復号結果としてよい。
【0076】
≪高い確率でub’a’=f(x)となる理由について≫
Xを群Gに値を持つ確率変数とする。w∈Gについて、要求を受けるたびに確率変数Xに従った標本x’に対応するwx’を返すものを、wについて誤差Xを持つ標本器(sampler)と呼ぶ。
【0077】
w∈Gについて、自然数aが与えられるたびに確率変数Xに従った標本x’に対応するwx’を返すものを、wについて誤差Xを持つ乱数化可能標本器(randomizable sampler)と呼ぶ。乱数化可能標本器はa=1として用いられれば標本器として機能する。
【0078】
本実施形態の入力情報提供部416d−uと第一出力情報計算部4261a−kと第一計算部416e−uとの組み合わせが、f(x)について誤差Xを持つ乱数化可能標本器(「第一乱数化可能標本器」と呼ぶ)であり、入力情報提供部416d−uと第二出力情報計算部4261b−kと第二計算部416h−uとの組み合わせが、f(x)について誤差Xを持つ乱数化可能標本器(「第二乱数化可能標本器」と呼ぶ)である。
【0079】
u’=v’が成立するのは、すなわちu=vが成立するのは、第一乱数化可能標本器がu=f(x)を正しく計算しており、第二乱数化可能標本器がv=f(x)を正しく計算している(x及びxが群Gの単位元eである)可能性が高いことを発明者は見出した。
【0080】
第一乱数化可能標本器がu=f(x)を正しく計算しており、第二乱数化可能標本器がv=f(x)を正しく計算しているとき(x及びxが群Gの単位元eであるとき)、ub’a’=(f(x)b’(f(x)a’=(f(x)b’(f(x)a’=f(x)bb’b’f(x)aa’a’=f(x)(bb’+aa’)=f(x)となる。
【0081】
また、(q,q)∈Iについて、i=1,2の各々について関数πをπ(q,q)=qで定義する。さらに、L=min(♯π(S),♯π(S))とする。♯・は、集合・の位数である。群Gが巡回群や位数の計算が困難な群であるときには、復号処理部416−uが「⊥」以外を出力するときの出力がf(x)ではない確率は、無視できる程度の誤差の範囲で高々TmaxL/♯S程度と期待することができる。もしL/♯Sが無視できる量でTmaxが多項式オーダー程度の量であれば、復号処理部416−uは圧倒的な確率で正しいf(x)を出力する。L/♯Sが無視できる量になるようなSの例には、例えばS={(1,d)|d∈[2,|G|−1]}がある。
【0082】
<第四実施形態の特徴>
本形態でも端末装置41−uに対する制御を行うことなく、登録許可情報記憶部421−kに格納された固有公開情報P(u)を削除することで、削除した固有公開情報P(u)に対応する端末装置41−uが暗号文Cの復号結果を閲覧する権限を無効化できる。
【0083】
また、端末装置に固有な固有公開情報が判定に用いられるため、装置に動的に割り当てられるアドレスが割り当てられる場合であっても利用できる。
【0084】
さらに本形態では、自己訂正技術を用いて復号を行うため、信頼できる鍵装置が設定されていない場合や、信頼できるか否かが定かではない複数の鍵装置しか存在しない場合であっても運用可能である。なお、上述した自己訂正処理は1つの端末装置と1つの鍵装置との間で実行していたが、1つの端末装置が複数の鍵装置と自己訂正処理を実行してもよい。
【0085】
[第五実施形態]
第五実施形態の復号システムは、第四実施形態の自己訂正処理を具体化した例である。以下、第四実施形態と異なる部分を中心に説明し、共通する部分については重複説明を省略する。以下の説明において、同一の参照番号が付された部分は同一の機能を持つものとし、同一の参照番号が付されたステップは同一の処理を表すものとする。
【0086】
<構成>
図8に例示するように第五実施形態の復号システム5は、第四実施形態の端末装置41−u(u=1,・・・,U)が端末装置51−u(u=1,・・・,U)に置換され、鍵装置42−k(k=1,・・・,K)が鍵装置52−k(k=1,・・・,K)に置換されたものである。図10に例示するように、端末装置51−uは、第四実施形態の復号処理部416−uが復号処理部516−uに置換されたものである。鍵装置52−kは、第四実施形態の判定復号部4261−k及び暗号化部4262−kを含む復号部426−kが、判定復号部5261−k及び暗号化部4262−kを含む復号部526−kに置換されたものである。
【0087】
図11に例示するように、第五実施形態の復号処理部516−uは、例えば、自然数記憶部416a−uと自然数選択部416b−uと整数計算部416c−uと入力情報提供部516d−uと第一計算部516e−uと第一べき乗計算部416f−uと第一リスト記憶部416g−uと第二計算部516h−uと第二べき乗計算部416i−uと第二リスト記憶部416j−uと判定部416k−uと最終出力部416m−uと制御部416n−uとを有する。図13に例示するように、本形態の入力情報提供部516d−uは、例えば、第一乱数生成部516da−uと第一入力情報計算部516db−uと第二乱数生成部516dc−uと第二入力情報計算部516dd−uとを有する。
【0088】
図12に例示するように、第五実施形態の判定復号部5261−kは、例えば、第一出力情報計算部5261a−kと第二出力情報計算部5261b−kと判定部4261c−kと制御部4261n−kとを有する。
【0089】
<自己訂正処理(ステップS504)>
本形態ではステップS404の代わりに以下の自己訂正処理(ステップS504)が実行される。以下に第四実施形態との相違点である自己訂正処理を説明する。第五実施形態では、復号関数f(x)を準同型関数とし、群Hの生成元をμ、群Hの位数をK、ν=f(μ)とする。その他の前提は、復号処理部416−uが復号処理部516−uに置換され、判定復号部4261−kが判定復号部5261−kに置換されている以外、第四実施形態と同一である。
【0090】
図16及び図17に例示するように、第五実施形態の処理は第四形態のステップS404d〜S404g,S404i,S404j,S404nが、それぞれ、ステップS504d〜S504g,S504i,S504j,S504nに置換されたものである。以下ではステップS504d〜S504g,S504i,S504j,S504nの処理のみを説明する。
【0091】
《ステップS504dの処理》
復号処理部516−u(図11)の入力情報提供部516d−uは、入力された暗号文xにそれぞれ対応する群Hの元である第一入力情報τ及び第二入力情報τを生成して出力する(図16/ステップS504d)。以下、図18を用いて本形態のステップS504dの処理を説明する。
【0092】
第一乱数生成部516da−u(図13)は、0以上K未満の自然数の一様乱数rを生成する。生成された乱数rは、第一入力情報計算部516db−u及び第一計算部516e−uに送られる(ステップS504da)。第一入力情報計算部516db−uは、入力された乱数rと暗号文xと自然数bとを用いて第一入力情報τ=μr1を計算する(ステップS504db)。ここで、μの右肩のr1は、rのことである。このように、この出願において、αを第一の文字、βを第二の文字、γを数字として、αβγと表記した場合には、そのβγはβγ、すなわちβの下付きγを意味する。
【0093】
第二乱数生成部516dc−uは、0以上K未満の自然数の一様乱数rを生成する。生成された乱数rは、第二入力情報計算部516dd−u及び第二計算部516h−uに送られる(ステップS504dc)。第二入力情報計算部516dd−uは、入力された乱数rと暗号文xと自然数aとを用いて第二入力情報τ=μr2を計算する(ステップS504dd)。
【0094】
第一入力情報計算部516db−u及び第二入力情報計算部516dd−uは、以上のように生成した第一入力情報τ及び第二入力情報τを出力する。第一入力情報τ及び第二入力情報τは出力部114−u(図10)から出力され、鍵装置52−kの入力部423−kに入力され判定復号部5261−kに送られる(ステップS504de)。なお、本形態の第一入力情報τ及び第二入力情報τは、それぞれ、乱数r,rによって暗号文xとの関係をかく乱させた情報である。これにより、判定復号部5261−kは、暗号文xを判定復号部5261−kに対して隠蔽できる。また、本形態の第一入力情報τは自然数選択部416b−uで選択された自然数bにさらに対応し、第二入力情報τは自然数選択部416b−uで選択された自然数aにさらに対応する。これにより、判定復号部5261−kから提供された復号能力を復号処理部516−uが高い精度で評価することが可能となる。
【0095】
《ステップS504e〜S504gの処理》
図17に例示するように、まず、第一入力情報τ=μr1が判定復号部5261−k(図12)の第一出力情報計算部5261a−kに入力され、第二入力情報τ=μr2が第二出力情報計算部5261b−kに入力される(ステップS504e)。
【0096】
第一出力情報計算部5261a−kは、第一入力情報τ=μr1と秘密鍵記憶部422−kに格納された秘密鍵s(k)とを用い、或る確率より大きな確率でf(μr1)を正しく計算し、得られた計算結果を第一出力情報zとする。この計算結果は正しい場合もあれば正しくない場合もある。すなわち、第一出力情報計算部5261a−kでの計算結果がf(μr1)となる場合もあれば、f(μr1)とならない場合もある(ステップS504f)。
【0097】
第二出力情報計算部5261b−kは、第二入力情報τ=μr2と秘密鍵記憶部422−kに格納された秘密鍵s(k)とを用い、或る確率より大きな確率でf(μr2)を正しく計算し、得られた計算結果を第二出力情報zとする。この計算結果は正しい場合もあれば正しくない場合もある。すなわち、第二出力情報計算部5261b−kでの計算結果がf(μr2)となる場合もあれば、f(μr2)とならない場合もある(ステップS504g)。
【0098】
第一出力情報計算部5261a−kは第一出力情報zを出力し、第二出力情報計算部5261b−kは第二出力情報zを出力する。
【0099】
《ステップS504i及びS504jの処理》
図16に戻り、第四実施形態と同様に復号部417−uで暗号文Cを復号して得られた第一出力情報zは復号処理部516−u(図11)の第一計算部516e−uに入力され、第二出力情報zは第二計算部516h−uに入力される。これらの第一出力情報z及び第二出力情報zが、判定復号部5261−kから復号処理部516−uに与えられた復号能力に相当する(ステップS504i)。
【0100】
第一計算部516e−uは、入力された乱数r及び第一出力情報zを用いてzν−r1を計算してその計算結果をuとする。計算結果uは、第一べき乗計算部416f−uに送られる。ここで、u=zν−r1=f(x)となる。すなわち、zν−r1は、f(x)について誤差Xを持つ乱数化可能標本器となる。その理由については後述する(ステップ504j)。
【0101】
《ステップS504nの処理》
第二計算部516h−uは、入力された乱数r及び第二出力情報zを用いてzν−r2を計算してその計算結果をvとする。計算結果vは、第二べき乗計算部416i−uに送られる。ここで、v=zν−r2=f(x)となる。すなわち、zν−r2は、f(x)について誤差Xを持つ乱数化可能標本器となる。その理由については後述する(ステップS504n)。
【0102】
≪zν−r1,zν−r2がf(x)についてそれぞれ誤差X,Xを持つ乱数化可能標本器となる理由について≫
cを自然数、R及びR’を乱数として、判定復号部5261−kがμを用いて行う計算の計算結果をB(μ)とする。すなわち、第一出力情報計算部5261a−kや第二出力情報計算部5261b−kが復号処理部516−uに返す計算結果をz=B(μ)とする。さらに、群Gに値を持つ確率変数XをX=B(μR’)f(μR’−1と定義する。
【0103】
このとき、zν−R=B(μ)f(μ−R=Xf(μ)f(μ−R=Xf(μf(x)f(μ−R=f(x)Xとなる。すなわち、zν−Rは、f(x)について誤差Xを持つ乱数化可能標本器となる。
【0104】
上記式展開において、X=B(μR’)f(μR’−1=B(μ)f(μ−1であり、B(μ)=Xf(μ)であるという性質を用いている。この性質は、関数f(x)が準同型関数であり、R及びR’が乱数であることに基づく。
【0105】
したがって、a,bが自然数、r,rが乱数であることを考慮すると、同様に、zν−r1,zν−r2がf(x)についてそれぞれ誤差X,Xを持つ乱数化可能標本器となるのである。
【0106】
[第六実施形態]
第六実施形態の復号システムは、第四実施形態の自己訂正処理を具体化した他の例である。具体的には、H=G×G、復号関数f(x)がElGamal暗号の復号関数、すなわち秘密鍵s(k)及び暗号文x=(c,c)に対してf(c,c)=c−sである場合の第一乱数化可能標本器及び第二乱数化可能標本器の例を具体化したものである。以下、第四実施形態と異なる部分を中心に説明し、共通する部分については重複説明を省略する。
【0107】
<構成>
図8に例示するように第六実施形態の復号システム6は、第四実施形態の端末装置41−u(u=1,・・・,U)が端末装置61−u(u=1,・・・,U)に置換され、鍵装置42−k(k=1,・・・,K)が鍵装置62−k(k=1,・・・,K)に置換されたものである。図10に例示するように、端末装置61−uは、第四実施形態の復号処理部416−uが復号処理部616−uに置換されたものである。鍵装置62−kは、第四実施形態の判定復号部4261−k及び暗号化部4262−kを含む復号部426−kが、判定復号部6261−k及び暗号化部4262−kを含む復号部626−kに置換されたものである。
【0108】
図11に例示するように、第六実施形態の復号処理部616−uは、例えば、自然数記憶部416a−uと自然数選択部416b−uと整数計算部416c−uと入力情報提供部616d−uと第一計算部616e−uと第一べき乗計算部416f−uと第一リスト記憶部416g−uと第二計算部616h−uと第二べき乗計算部416i−uと第二リスト記憶部416j−uと判定部416k−uと最終出力部416m−uと制御部416n−uとを有する。図14に例示するように、本形態の入力情報提供部616d−uは、例えば、第四乱数生成部616da−uと第五乱数生成部616db−uと第一入力情報計算部616dc−uと第六乱数生成部616dd−uと第七乱数生成部616de−uと第二入力情報計算部616df−uとを有する。第一入力情報計算部616dc−uは、例えば、第四入力情報計算部616dca−uと第五入力情報計算部616dcb−uとを有し、第二入力情報計算部616df−uは、第六入力情報計算部616dfa−uと第七入力情報計算部616dfb−uとを有する。
【0109】
図12に例示するように、第六実施形態の判定復号部6261−kは、例えば、第一出力情報計算部6261a−kと第二出力情報計算部6261b−kと制御部4261n−kと判定部4261c−kとを有する。
【0110】
<自己訂正処理(ステップS604)>
本形態ではステップS404の代わりに以下の自己訂正処理(ステップS604)が実行される。以下に第四実施形態との相違点である自己訂正処理を説明する。第六実施形態では、群H=G×G、暗号文x=C=(c,c)∈Hであり、f(c,c)が準同型関数であり、群Gの生成元をμとし、群Gの位数をKとし、同じ秘密鍵s(k)に対する暗号文(V,W)∈Hとその暗号文を復号した復号文f(V,W)=Y∈Gとの組が復号処理部616−u及び判定復号部6261−kに事前設定され、復号処理部616−u及び判定復号部6261−kがこの組を利用可能とされているものとする。
【0111】
図16及び図17に例示するように、第六実施形態の処理は第四形態のステップS404d〜S404g,S404i,S404j,S404nが、それぞれ、ステップS604d〜S604g,S604i,S604j,S604nに置換されたものである。以下ではステップS604d〜S604g,S604i,S604j,S604nの処理のみを説明する。
【0112】
《ステップS604dの処理》
復号処理部616−u(図11)の入力情報提供部616d−uは、入力された暗号文x=(c,c)に対応する群Hの元である第一入力情報τ及び暗号文x=(c,c)に対応する群Hの元である第二入力情報τを生成して出力する(図16/ステップS604d)。以下、図19を用いて本形態のステップS604dの処理を説明する。
【0113】
第四乱数生成部616da−u(図14)は、0以上K未満の自然数の一様乱数rを生成する。生成された乱数rは、第四入力情報計算部616dca−u、第五入力情報計算部616dcb−u、及び第一計算部616e−uに送られる(ステップS604da)。第五乱数生成部616db−uは、0以上K未満の自然数の一様乱数rを生成する。生成された乱数rは、第五入力情報計算部616dcb−u、及び第一計算部616e−uに送られる(ステップS604db)。
【0114】
第四入力情報計算部616dca−uは、自然数選択部416b−uで選択された自然数b、暗号文xが含むc、及び乱数rを用い、第四入力情報cr4を計算する(ステップS604dc)。第五入力情報計算部616dcb−uは、自然数選択部416b−uで選択された自然数b、暗号文xが含むc、及び乱数r,rを用い、第五入力情報cr4μr5を計算する(ステップS604dd)。
【0115】
第六乱数生成部616dd−uは、0以上K未満の自然数の一様乱数rを生成する。生成された乱数rは、第六入力情報計算部616dfa−u、第七入力情報計算部616dfb−u、及び第二計算部616h−uに送られる(ステップS604de)。第七乱数生成部616de−uは、0以上K未満の自然数の一様乱数rを生成する。生成された乱数rは、第六入力情報計算部616dfa−u、及び第二計算部616h−uに送られる(ステップS604df)。
【0116】
第六入力情報計算部616dfa−uは、自然数選択部416b−uで選択された自然数a、暗号文xが含むc、及び乱数rを用い、第六入力情報cr6を計算する(ステップS604dg)。第七入力情報計算部616dfb−uは、自然数選択部416b−uで選択された自然数a、暗号文xが含むc、及び乱数rを用い、第七入力情報cr6μr7を計算する(ステップS604dh)。
【0117】
第一入力情報計算部616dc−uは、以上のように生成した第四入力情報cr4及び第五入力情報cr4μr5を第一入力情報τ=(cr4,cr4μr5)として出力する。第二入力情報計算部616df−uは、以上のように生成した第六入力情報cr6及び第七入力情報cr6μr7を第二入力情報τ=(cr6,cr6μr7)として出力する(ステップS604di)。
【0118】
第一入力情報τ及び第二入力情報τは出力部114−u(図10)から出力され、鍵装置62−kの入力部423−kに入力され判定復号部6261−kに送られる。
【0119】
《ステップS604e〜S604gの処理》
図17に例示するように、まず、第一入力情報τ=(cr4,cr4μr5)が判定復号部6261−k(図12)の第一出力情報計算部6261a−kに入力され、第二入力情報τ=(cr6,cr6μr7)が第二出力情報計算部6261b−kに入力される(ステップS604e)。
【0120】
第一出力情報計算部6261a−kは、第一入力情報τ=(cr4,cr4μr5)と秘密鍵記憶部422−kに格納された秘密鍵s(k)とを用い、或る確率より大きな確率でf(cr4μr5,cr4)を正しく計算し、計算結果を第一出力情報zとする。この計算結果は正しい場合もあれば正しくない場合もある。すなわち、第一出力情報計算部6261a−kでの計算結果がf(cr4μr5,cr4)となる場合もあれば、f(cr4μr5,cr4)とならない場合もある(ステップS604f)。
【0121】
第二出力情報計算部6261b−kは、第二入力情報τ=(cr6,cr6μr7)と秘密鍵記憶部422−kに格納された秘密鍵s(k)とを用い、或る確率より大きな確率でf(cr6μr7,cr6)を正しく計算可能であり、得られた計算結果を第二出力情報zとする。この計算結果は正しい場合もあれば正しくない場合もある。すなわち、第二出力情報計算部6261b−kでの計算結果がf(cr6μr7,cr6)となる場合もあれば、f(cr6μr7,cr6)とならない場合もある(ステップS604g)。
【0122】
第一出力情報計算部6261a−kは第一出力情報zを出力し、第二出力情報計算部6261b−kは第二出力情報zを出力する。
【0123】
《ステップS604i及びS604jの処理》
図16に戻り、第四実施形態と同様に復号部417−uで暗号文Cを復号して得られた第一出力情報zは復号処理部616−u(図11)の第一計算部616e−uに入力され、第二出力情報zは第二計算部616h−uに入力される(ステップS604i)。
【0124】
第一計算部616e−uは、入力された第一出力情報z及び乱数r,rを用い、z−r4μ−r5を計算してその計算結果をuとする(ステップS604j)。計算結果uは、第一べき乗計算部416f−uに送られる。ここで、u=z−r4μ−r5=f(c,cとなる。すなわち、z−r4μ−r5は、f(c,c)について誤差Xを持つ乱数化可能標本器となる。その理由については後述する。
【0125】
《ステップS604nの処理》
第二計算部616h−uは、入力された第二出力情報z及び乱数r,rを用い、z−r6μ−r7を計算してその計算結果をvとする(ステップS604n)。計算結果vは、第二べき乗計算部416i−uに送られる。ここで、v=z−r6μ−r7=f(c,cとなる。すなわち、z−r6μ−r7は、f(c,c)について誤差Xを持つ乱数化可能標本器となる。その理由については後述する。
【0126】
≪z−r4μ−r5,z−r6μ−r7がf(c,c)についてそれぞれ誤差X,Xを持つ乱数化可能標本器となる理由について≫
cを自然数、R、R、R’及びR’を乱数として、判定復号部6261−kがcR1μR2及びcR1を用いて行う計算の計算結果をB(cR1μR2,cR1)とする。すなわち、第一出力情報計算部6261a−kや第二出力情報計算部6261b−kが復号処理部616−uに返す計算結果をz=B(cR1μR2,cR1)とする。さらに、群Gに値を持つ確率変数XをX=B(VR1’μR2’,WR1’)f(VR1’μR2’,WR1’−1と定義する。
【0127】
このとき、zY−R1μ−R2=B(cR1μR2,cR1)Y−R1μ−R2=Xf(cR1μR2,cR1)Y−R1μ−R2=Xf(c,cf(V,W)R1f(μ,eR2−R1μ−R2=Xf(c,cR1μR2−R1μ−R2=f(c,cXとなる。すなわち、zY−R1μ−R2は、f(x)について誤差Xを持つ乱数化可能標本器となる。なお、eは、群Gの単位元である。
【0128】
上記式展開において、X=B(VR1’μR2’,WR1’)f(VR1’μR2’,WR1’−1=B(cR1μR2,cR1)f(cR1μR2,cR1)であり、B(cR1μR2,cR1)=Xf(cR1μR2,cR1)であるという性質を用いている。この性質は、R、R、R’及びR’が乱数であることに基づく。
【0129】
したがって、a,bが自然数、r,r,r及びrが乱数であることを考慮すると、同様に、z−r4μ−r5,z−r6μ−r7がf(c,c)についてそれぞれ誤差X,Xを持つ乱数化可能標本器となるのである。
【0130】
[第七実施形態]
第四〜六実施形態では、復号処理部の自然数記憶部416a−uに、互いに素である2つの自然数a,bの組(a,b)が複数種類記憶され、これらの組(a,b)を用いて各処理が実行されることとした。しかしながら、a,bの一方が定数であってもよい。例えば、aが1に固定されていてもよいし、bが1に固定されていてもよい。言い換えると、第一乱数化可能標本器又は第二乱数化可能標本器の一方が標本器に置換されていてもよい。a,bの一方が定数である場合、定数とされたa又はbを選択する処理が不要となり、各処理部は定数とされたa又はbが入力されることなく、それを定数として扱って計算を行うことができる。また、定数とされたa又はbが1である場合には、a’やb’を用いることなく、f(x)=ub’a’をf(x)=v又はf(x)=uとして得ることができる。
【0131】
第七実施形態は、そのような変形の一例であり、bが1に固定され、第二乱数化可能標本器が標本器に置換された形態である。以下では、第四実施形態との相違点を中心に説明する。また、第一乱数化可能標本器の具体例は、第五実施形態および第六実施形態で説明したのと同様であるため、説明を省略する。
【0132】
<構成>
図8に例示するように第七実施形態の復号システム7は、第四実施形態の端末装置41−u(u=1,・・・,U)が端末装置71−u(u=1,・・・,U)に置換され、鍵装置42−k(k=1,・・・,K)が鍵装置72−k(k=1,・・・,K)に置換されたものである。図10に例示するように、端末装置71−uは、第四実施形態の復号処理部416−uが復号処理部716−uに置換されたものである。鍵装置72−kは、第四実施形態の判定復号部4261−k及び暗号化部4262−kを含む復号部426−kが、判定復号部7261−k及び暗号化部4262−kを含む復号部726−kに置換されたものである。
【0133】
図20に例示するように、第七実施形態の復号処理部716−uは、例えば、自然数記憶部716a−uと自然数選択部716b−uと入力情報提供部716d−uと第一計算部716e−uと第一べき乗計算部716f−uと第一リスト記憶部716g−uと第二計算部716h−uと第二リスト記憶部716j−uと判定部716m−uと最終出力部416m−uと制御部416n−uとを有する。
【0134】
図12に例示するように、第七実施形態の判定復号部7261−kは、例えば、第一出力情報計算部7261a−kと第二出力情報計算部7261b−kと制御部4261n−kと判定部4261c−kとを有する。
【0135】
<自己訂正処理(ステップS704)>
本形態ではステップS404の代わりに以下の自己訂正処理(ステップS704)が実行される。以下に第四実施形態との相違点である自己訂正処理を説明する。第七実施形態では、G,Hを巡回群、f(x)を群Hの元である暗号文x=Cを特定の秘密鍵s(k)で復号して群Gの元を得るための復号関数、群G,Hの生成元をそれぞれμ,μ、X,Xを群Gに値を持つ確率変数、確率変数Xの実現値をx、確率変数Xの実現値をxとする。また、復号処理部716−uの自然数記憶部716a−uには、自然数aが複数種類記憶されているものとする。
【0136】
図21に例示するように、復号処理部716−u(図20)の自然数選択部716b−uが、自然数記憶部716a−uに記憶された複数の自然数aから1つの自然数aをランダムに読み込む。読み込まれた自然数aの情報は、入力情報提供部716d−u及び第一べき乗計算部716f−uに送られる(ステップS704a)。
【0137】
制御部416n−uは、t=1とする(ステップS704b)。
【0138】
入力情報提供部716d−uは、入力された暗号文xにそれぞれ対応する群Hの元である第一入力情報τ及び第二入力情報τを生成して出力する。好ましくは、第一入力情報τ及び第二入力情報τはそれぞれ暗号文xとの関係をかく乱させた情報である。これにより、復号処理部716−uは、暗号文xを判定復号部7261−kに対して隠蔽できる。また、好ましくは、本形態の第二入力情報τは自然数選択部716b−uで選択された自然数aにさらに対応する。これにより、判定復号部7261−kから提供された復号能力を復号処理部716−uが高い精度で評価することが可能となる(ステップS704d)。第一入力情報τ及び第二入力情報τの組みの具体例は、第五実施形態および第六実施形態の何れかのb=1とした第一入力情報τ及び第二入力情報τの組みである。第一入力情報τ及び第二入力情報τは出力部114−u(図10)から出力され、鍵装置72−kの入力部423−kに入力され判定復号部7261−kに送られる。図17に例示するように、第一入力情報τは判定復号部7261−k(図12)の第一出力情報計算部7261a−kに入力され、第二入力情報τは第二出力情報計算部7261b−kに入力される(ステップS704e)。
【0139】
第一出力情報計算部7261a−kは、第一入力情報τと秘密鍵記憶部422−kに格納された秘密鍵s(k)とを用い、或る確率より大きな確率でf(τ)を正しく計算し、得られた計算結果を第一出力情報zとする(ステップS704f)。第二出力情報計算部7261b−kは、第二入力情報τと秘密鍵記憶部422−kに格納された秘密鍵s(k)とを用い、或る確率より大きな確率でf(τ)を正しく計算し、得られた計算結果を第二出力情報zとする(ステップS704g)。すなわち、第一出力情報計算部7261a−kや第二出力情報計算部7261b−kは、意図的又は意図的ではない誤差を含んだ計算結果を出力する。言い換えると、第一出力情報計算部7261a−kでの計算結果がf(τ)の場合もあればf(τ)でない場合もあり、第二出力情報計算部7261b−kでの計算結果がf(τ)の場合もあればf(τ)でない場合もある。第一出力情報z及び第二出力情報zの組の具体例は、第五実施形態および第六実施形態の何れかのb=1とした第一出力情報z及び第二出力情報zの組である。
【0140】
第一出力情報計算部7261a−kは第一出力情報zを出力し、第二出力情報計算部7261b−kは第二出力情報zを出力する。第一出力情報zおよび第二出力情報zは第四実施形態と同様に暗号化部4262−kで暗号化され、出力部424−kは、第一入力情報τ及び第二入力情報τを送信した端末装置41−uに対して暗号文Cを出力する(ステップS404h)。
【0141】
図21に戻り、第四実施形態と同様に復号部417−uで暗号文Cを復号して得られた第一出力情報zは復号処理部716−u(図20)の第一計算部716e−uに入力され、第二出力情報zは第二計算部716h−uに入力される。これらの第一出力情報z及び第二出力情報zが、判定復号部7261−kから復号処理部716−uに与えられた復号能力に相当する(ステップS704i)。
【0142】
第一計算部716e−uは、第一出力情報zから計算結果u=f(x)xを生成する。計算結果uの具体例は、第五実施形態および第六実施形態の何れかのb=1とした計算結果uである。計算結果uは第一べき乗計算部716f−uに送られる(ステップS704j)。
【0143】
第一べき乗計算部716f−uはu’=uを計算する。計算結果uとその計算結果に基づいて計算されたu’との組(u,u’)は、第一リスト記憶部416g−uに記憶される(ステップS704k)。
【0144】
第二計算部716h−uは、第二出力情報zから計算結果v=f(x)を生成する。計算結果vの具体例は、第五実施形態および第六実施形態の何れかの計算結果vである。計算結果vは第二リスト記憶部716j−uに記憶される(ステップS704n)。
【0145】
判定部716m−uは、第一リスト記憶部416g−uに記憶された組(u,u’)及び第二リスト記憶部716j−uに記憶されたvの中で、u’=vとなるものがあるか判定する(ステップS704q)。u’=vとなるものがあった場合には、ステップ704u進む。u’=vとなるものがなかった場合には、ステップS404rに進む。
【0146】
ステップS404rでは、制御部416n−uがt=Tmaxであるか判定する(ステップS404r)。Tmaxは予め定められた自然数である。t=Tmaxであれば、制御部416n−uは、計算をすることができなかった旨の情報、例えば記号「⊥」を出力して(ステップS404t)、処理を終える。t=Tmaxでない場合には、制御部416n−uは、tを1だけインクリメント、すなわちt=t+1として(ステップS404s)、ステップS704dに戻る。
【0147】
ステップS704uでは、最終出力部416m−uが、u’=vであると判定されたu’に対応するuを復号結果m’として出力する(ステップS704u)。このように得られたuは、第四実施形態から第六実施形態でb=1とした場合のub’a’に相当する。すなわち、このように得られたuは高い確率で暗号文xを特定の秘密鍵s(k)で復号した復号結果f(x)=m’となる。よって、上述した処理を複数回繰り返し、ステップS704uで得られた値のうち最も頻度の高い値を復号結果とすればよい。また、後述するように、設定によっては圧倒的な確率でu=f(x)=m’となる。その場合にはステップS704uで得られた値をそのまま復号結果としてよい。
【0148】
≪復号結果f(x)が得られる理由について≫
次に、本形態の復号処理部716−uで復号結果f(x)が得られる理由を説明する。まず、説明に必要な事項を定義する。
【0149】
ブラックボックス(black−box):
f(τ)のブラックボックスF(τ)とは、τ∈Hを入力としてz∈Gを出力する処理部を意味する。本形態では、第一出力情報計算部7261a−k及び第二出力情報計算部7261b−kが、それぞれ復号関数f(τ)のブラックボックスF(τ)に相当する。群Hから任意に選択された元τ∈H及びz=F(τ)に対してz=f(τ)を満たす確率がδ(0<δ≦1)よりも大きい場合、すなわち、
Pr[z=f(τ)|τ∈H,z=F(τ)]>δ …(1)
を満たすf(τ)のブラックボックスF(τ)のことを、信頼性δ(δ−reliable)のf(τ)のブラックボックスF(τ)という。なお、δは正の値であり、前述した「或る確率」に相当する。
【0150】
自己訂正器(self−corrector):
自己訂正器C(x)とは、x∈Hを入力とし、f(τ)のブラックボックスF(τ)を用いて計算を行い、j∈G∪⊥を出力する処理部を意味する。本形態では、復号処理部716−uが自己訂正器C(x)に相当する。
【0151】
オールモスト自己訂正器(almost self−corrector):
自己訂正器C(x)が、x∈Hを入力とし、δ−reliableのf(τ)のブラックボックスF(τ)を用い、正しい値j=f(x)を出力する確率が、誤った値j≠f(x)を出力する確率よりも十分大きい場合を想定する。すなわち、
Pr[j=f(x)|j=C(x),j≠⊥]
>Pr[j≠f(x)|j=C(x),j≠⊥]+Δ …(2)
を満たす場合を想定する。なお、Δは或る正の値(0<Δ<1)である。このような場合、自己訂正器C(x)はオールモスト自己訂正器であるという。例えば、或る正の値Δ’(0<Δ’<1)に対して
Pr[j=f(x)|j=C(x)]>(1/3)+Δ’
Pr[j=⊥|j=C(x)]<1/3
Pr[j≠f(x)かつj≠⊥|j=C(x)]<1/3
を満たす場合、自己訂正器C(x)はオールモスト自己訂正器である。Δ’の例はΔ’=1/12や1/3である。
【0152】
ローバスト自己訂正器(robust self−corrector):
自己訂正器C(x)が、x∈Hを入力とし、δ−reliableのf(τ)のブラックボックスF(τ)を用い、正しい値j=f(x)又はj=⊥を出力する確率が圧倒的である場合を想定する。すなわち、無視することができる誤差ξ(0≦ξ<1)に対して
Pr[j=f(x)またはj=⊥|j=C(x)]>1−ξ …(3)
を満たす場合を想定する。このような場合、自己訂正器C(x)はローバスト自己訂正器であるという。なお、無視することができる誤差ξの例は、セキュリティパラメータkの関数値ξ(k)である。関数値ξ(k)の例は、任意の多項式p(k)について、十分大きいkに対して{ξ(k)p(k)}が0に収束するものである。関数値ξ(k)の具体例は、ξ(k)=2−kやξ(k)=2−√kなどである。
【0153】
また、オールモスト自己訂正器からローバスト自己訂正器を構成することができる。すなわち、同一のxに対してオールモスト自己訂正器を複数回実行させ、⊥を除いて最も頻度が高い出力値をjとすることで、ローバスト自己訂正器を構成できる。例えば、同一のxに対してオールモスト自己訂正器をO(log(1/ξ))回実行させ、最も頻度が高い出力値をjとすることで、ローバスト自己訂正器を構成できる。なお、O(・)はオー記法を表す。
【0154】
擬似自由(pseudo−free)な作用:
群G、自然数の集合Ω={0,...,M}(Mは1以上の自然数)、群Gに値を持つ確率変数X,Xの各実現値α∈X(α≠e),β∈X、及びa∈Ωについて、α=βとなる確率
Pr[α=βかつα≠e|a∈Ω,α∈X,β∈X] …(4)
について、あらゆる可能なX,Xに関する上限値を、組(G,Ω)の疑似自由指標とよび、これをP(G,Ω)と表すことにする。ある無視することができる関数ζ(k)が存在して、
P(G,Ω)<ζ(k) …(5)
である場合、組(G,Ω)によって定義される演算は擬似自由な作用であるという。なお、第5実施形態では群で定義された演算を乗法的に表現する。すなわちα∈Gに対する「α」は、群Gで定義された演算をαに対してa回作用させることを意味する。また、無視することができる関数ζ(k)の例は、任意の多項式p(k)について、十分大きいkに対して{ζ(k)p(k)}が0に収束するものである。関数ζ(k)の具体例は、ζ(k)=2−kやζ(k)=2−√kなどである。例えば、セキュリティパラメータkとに対し、式(4)の確率がO(2−k)未満である場合、組(G,Ω)によって定義される演算は擬似自由な作用である。また、例えば、任意のα∈Gでα≠eであるものについて、集合Ω・α={a(α)|a∈Ω}の要素数|Ω・α|が2を超える場合、組(G,Ω)によって定義される演算は擬似自由な作用といえる。このような具体例は数多く存在する。例えば、群Gが素数pを法とする剰余群Z/pZであり、素数pが2のオーダーであり、集合Ω={0,...,p−2}であり、a(α)がα∈Z/pZであり、α≠eである場合、Ω・α={α|a=0,...,p−2}={e,α,...,αp−2}となり、|Ω・α|=p−1である。素数pが2のオーダーであるため、ある定数Cが存在して、kが十分大きければ|Ω・α|>C2を満たす。ここで式(4)の確率はC−1−k未満であり、このような組(G,Ω)によって定義される演算は擬似自由な作用である。
【0155】
信頼性δγ(δγ−reliable)の乱数化可能標本器:
自然数aが与えられるたびに、δ−reliableのf(τ)のブラックボックスF(τ)を用い、w∈Gについて、確率変数Xに従った標本x’に対応するwx’を返す乱数化可能標本器であって、wx’=wである確率がδγよりも大きい(γは正定数)、すなわち、
Pr[wx’=w]>δγ …(6)
を満たすものを、信頼性δγの乱数化可能標本器という。本形態の入力情報提供部716d−uと第二出力情報計算部7261b−kと第二計算部716h−uとの組は、w=f(x)について、信頼性δγの乱数化可能標本器である。
【0156】
次に、これらの定義を用い、本形態の復号処理部716−uで復号結果f(x)が得られる理由を説明する。
【0157】
本形態のステップS704qではu’=vであるか、すなわち、u=vであるかを判定している。本形態の入力情報提供部716d−uと第二出力情報計算部7261b−kと第二計算部716h−uとの組は信頼性δγの乱数化可能標本器であるため(式(6))、Tmaxをk、δ、γから定まる一定値よりも大きい値とすれば、漸近的に大きい確率でu=vが成立する(ステップS704qでyesとなる)場合が生じる。たとえば、Tmax≧4/δγとすれば、u=vが成立する(ステップS704qでyesとなる)確率は1/2よりも大きいことがMarkovの不等式によってわかる。
【0158】
また、本形態ではu=f(x)x及びv=f(x)なのであるから、u=vが成立する場合にはx=xが成立する。x=xが成立する場合には、x=x=eである場合とx≠eである場合とがある。x=x=eである場合には、u=f(x)となるのであるから、ステップS704uで出力されるuは正しい復号結果f(x)となる。一方、x≠eである場合には、u≠f(x)となるのであるから、ステップS704uで出力されるuは正しい復号結果f(x)ではない。
【0159】
群Gと自然数aが属する集合Ωとの組(G,Ω)によって定義される演算が擬似自由な作用であるか、疑似自由指標P(G,Ω)についてTmaxP(G,Ω)が漸近的に小さい場合、u=vの場合にx≠eである確率(式(4))は漸近的に小さい。したがって、u=vの場合にx=eである確率は漸近的に大きい。よって、組(G,Ω)によって定義される演算が擬似自由な作用であるか、TmaxP(G,Ω)が漸近的に小さい場合、u=vの場合に誤った復号結果f(x)が出力される確率は、u=vの場合に正しい復号結果f(x)が出力される確率よりも十分小さい。この場合の復号処理部716−uはオールモスト自己訂正器であるといえる(式(2)参照)。そのため、前述のように、復号処理部716−uからローバスト自己訂正器を構成することが可能であり、圧倒的な確率で正しい復号結果f(x)を得ることができる。(G,Ω)で定義される演算が疑似自由な作用である場合には、u=vの場合に誤った復号結果f(x)が出力される確率も無視できる。この場合の復号処理部716−uは、圧倒的な確率で正しい復号結果f(x)または⊥を出力する。
【0160】
なお、任意の定数ρに対してkが定まり、このkに対してk<k’を満たす任意のk’に対する関数値η(k’)がρ未満となる場合「η(k’)が漸近的に小さい」という。k’の例はセキュリティパラメータkである。
【0161】
また、任意の定数ρに対してkが定まり、このkに対してk<k’を満たす任意のk’に対する関数値1−η(k’)がρ未満となる場合「η(k’)が漸近的に大きい」という。
【0162】
《信頼性δγの乱数化可能標本器と安全性について》
以下のような攻撃を想定する。
【0163】
・ブラックボックスF(τ)又はその部分が意図的に不正なzを出力する、又は、ブラックボックスF(τ)から出力された値が不正なzに改ざんされる。
【0164】
・不正なzに対応するwx’が乱数化可能標本器から出力される。
【0165】
・不正なzに対応するwx’は、自己訂正器C(x)でu=vが成立する(ステップS704qでyesなる)にもかかわらず、自己訂正器C(x)が誤った値を出力する確率を増加させる。
【0166】
このような攻撃は、与えられた自然数aに対して乱数化可能標本器から出力されたwx’の誤差の確率分布D=wx’w−aが自然数aに依存する場合に可能となる。例えば、第二計算部716h−uから出力されるvがf(x)となるような不正が行われた場合、xの値にかかわらず、必ずu=vが成立することになる。よって、乱数化可能標本器は、与えられた自然数aに対して乱数化可能標本器から出力されたwx’の誤差の確率分布D=wx’w−aが当該自然数aに依存しないことが望ましい。
【0167】
あるいは、集合Ωのいかなる元a∈Ωについても、wx’の誤差の確率分布D=wx’w−aと区別することができない群Gに値を持つ確率分布Dが存在する(確率分布Dと確率分布Dとが統計的に近似する(statistically−close))乱数化可能標本器であることが望ましい。なお、確率分布Dは自然数aに依存しない。また、確率分布Dと確率分布Dとを区別することができないとは、多項式時間アルゴリズムによって確率分布Dと確率分布Dとを区別することができないことを意味し、例えば、無視することができるζ(0≦ζ<1)に対して
Σg∈G|Pr[g∈D]−Pr[g∈D]|<ζ …(7)
を満たすならば、多項式時間アルゴリズムによって確率分布Dと確率分布Dとを区別することができない。無視することができるζの例は、セキュリティパラメータkの関数値ζ(k)である。関数値ζ(k)の例は、任意の多項式p(k)について、十分大きなkに対して{ζ(k)p(k)}が0に収束するものである。関数値ζ(k)の具体例は、ζ(k)=2−kやζ(k)=2−√kなどである。また、これらの点は自然数a及びbを使用する第四実施形態から第六実施形態についても同様である。
【0168】
[第八実施形態]
第八実施形態の復号システムは、第四実施形態の自己訂正処理を具体化した他の例である。本形態は、格子暗号の一種であるGHV暗号化方式(参考文献1「C. Genrty, S. Halevi and V. Vaikuntanathan, “A Simple BGNType Cryptosystem from LWE,”Advances in Cryptology - EUROCRYPT 2010, LNCS 6110, pp.506-522, Springer-Verlag, 2010.」等参照)の復号処理に本発明を適用する形態である。以下では、第四実施形態との相違点を中心に説明する。
【0169】
<構成>
図8に例示するように第八実施形態の復号システム8は、第四実施形態の端末装置41−u(u=1,・・・,U)が端末装置81−u(u=1,・・・,U)に置換され、鍵装置42−k(k=1,・・・,K)が鍵装置82−k(k=1,・・・,K)に置換されたものである。図10に例示するように、端末装置81−uは、第四実施形態の復号処理部416−uが復号処理部816−uに置換されたものである。鍵装置82−kは、第四実施形態の判定復号部4261−k及び暗号化部4262−kを含む復号部426−kが、判定復号部8261−k及び暗号化部4262−kを含む復号部826−kに置換されたものである。
【0170】
図22に例示するように、第八実施形態の復号処理部816−uは、例えば、行列記憶部816a−uと行列選択部816b−uと入力情報提供部816d−uと第一計算部816e−uと行列積計算部816f−uと第一リスト記憶部816g−uと第二計算部816h−uと第二リスト記憶部816j−uと判定部816k−uと最終出力部816m−uと制御部416n−uとを有する。
【0171】
図24に例示するように、本形態の入力情報提供部816d−uは、例えば、第一ランダム行列選択部816da−uと第二ランダム行列選択部816db−uと第一暗号化部816dc−uと第二暗号化部816dd−uと第一入力情報計算部816de−uと第三ランダム行列選択部816df−uと第四ランダム行列選択部816dg−uと第三暗号化部816dh−uと第四暗号化部816di−uと第二入力情報計算部816dj−uとを有する。
【0172】
図23に例示するように、第八実施形態の判定復号部8261−kは、例えば、第一出力情報計算部8261a−kと第二出力情報計算部8261b−kと制御部4261n−kと判定部4261c−kを有する。
【0173】
<自己訂正処理(ステップS804)>
本形態ではステップS404の代わりに以下の自己訂正処理(ステップS804)が実行される。以下に第四実施形態との相違点である自己訂正処理を説明する。本形態では、Gをι×ι行列の集合、Hをι×ι行列の集合、暗号文x=CをHの元、暗号文x=Cの復号結果がGの元、を集合Gに値を持つ確率変数、を確率変数の実現値、を確率変数の実現値、aを集合Hの元とする。また本形態では、y(k)を暗号化鍵(公開鍵)であるι×κ行列、s(k)をy(k)・s(k)=0を満たすι×ι行列である復号鍵(秘密鍵)、CMをκ×ι行列、NMをι×ι行列、UMをι×ι単位行列、PTを集合Gの元である平文PT∈G、xを集合Hの元である暗号文x∈H、ENCを集合Gの元である平文PTを暗号化して暗号文x∈Hを得るための暗号化関数、f(x)を暗号文x∈Hを特定の秘密鍵s(k)で復号して集合Gの元である平文PTを得るための復号関数とする。復号関数f(x)は準同型関数である。例えば、Gをι×ι行列(Z/2Z)ι×ιの集合、Hをι×ι行列(Z/qZ)ι×ιの集合、暗号化鍵y(k)をι×κ行列(Z/qZ)ι×κ、秘密鍵s(k)をι×ι行列(Z/qZ)ι×ι、CMをランダムに選択されたκ×ι行列(Z/qZ)κ×ι、NMをガウス分布に従うι×ι行列(Z/qZ)ι×ι、UMをι×ι単位行列(Z/2Z)ι×ιとし、暗号化関数ENC(PT)をy(k)・CM+2・NM+PT(mod q)とし、復号関数f(x)をs(k)−1{s(k)・x・s(k)(mod q)}(s(k)−1(mod 2)とする。ただし、κ,ι,qは正整数、κ,ι,qは正整数、・は・の転置行列、(Z/qZ)κ×ιはqを法とする剰余環Z/qZを要素とするκ行ι列行列である。また、第八実施形態では行列α,α間の積をα・αと表し、和をα+αと表現する。また、行列αの各要素を自然数β倍した行列をβ・αと表す。
【0174】
本形態の処理の前提として、復号処理部816−u(図22)の行列記憶部816a−uには、行列a∈Hが複数種類記憶されているものとする。
【0175】
図25に例示するように、まず、復号処理部816−u(図22)の行列選択部816b−uが、行列記憶部816a−uに記憶された複数の行列から一様ランダムに1つの行列aを選択して読み込む。読み込まれた行列aの情報は、入力情報提供部816d−u及び行列積計算部816f−uに送られる(ステップS804a)。
【0176】
制御部416n−uは、t=1とする(ステップS804c)。
【0177】
入力情報提供部816d−uは、入力された暗号文xにそれぞれ対応する対応する集合Hの元である第一入力情報τ及び第二入力情報τを生成して出力する。好ましくは、第一入力情報τ及び第二入力情報τはそれぞれ暗号文xとの関係をかく乱させた情報である。これにより、復号処理部816−uは暗号文xを判定復号部8261−kに対して隠蔽できる。また、第二入力情報τは元aにさらに対応する。これにより、判定復号部8261−kから提供された復号能力を復号処理部816−uが高い精度で評価することが可能となる(ステップS804d)。以下、図27を用いてステップS804dの具体例を説明する。
【0178】
[ステップS804dの具体例]
入力情報提供部816d−u(図24)の第一ランダム行列選択部816da−uが集合Gの元MR1を一様ランダムに選択する(ステップS804da)。選択されたMR1は第一暗号化部816dc−uと第一計算部816e−uに送られる(ステップS804da)。第二ランダム行列選択部816db−uがκ×ιの一様ランダムな行列CM11及びCM12∈(Z/qZ)κ×ιを選択する。選択されたCM11及びCM12は第一入力情報計算部816de−uに送られる(ステップS804db)。第一暗号化部816dc−uが公開鍵y(k)を用い、MR1の暗号文ENC(y(k),MR1)である第一暗号文CR1=y(k)・CM+2・NM+MR1(mod q)を生成する。第一暗号文CR1は第一入力情報計算部816de−uに送られる(ステップS804dc)。第二暗号化部816dd−uが公開鍵y(k)を用い、単位行列UMの暗号文ENC(y(k),UM)である第二暗号文CUM=y(k)・CM+2・NM+UM(mod q)を生成する。第二暗号文CUMは第一入力情報計算部816de−uに送られる(ステップS804dd)。第一入力情報計算部816de−uにはさらに暗号文x=Cが入力される。第一入力情報計算部816de−uは、第一入力情報τとして(x・CUM+CR1)+y(k)・CM11+2・NM+CM12・y(k)を得て出力する。なお、行列の積の順序に特段の必然性はない。すなわち第一入力情報計算部816de−uは、C=x・CUM+CR1としたRe(C)=C+y(k)・CM11+2・NM+CM12・y(k)を計算して第一入力情報τを生成してもよいし、C=CUM・x+CR1としたRe(C)を計算して第一入力情報τを生成してもよい(ステップS804de)。
【0179】
第三ランダム行列選択部816df−uが集合Gの元MR2を一様ランダムに選択する。選択されたMR2は第三暗号化部816dh−uと第二計算部816h−uに送られる(ステップS804df)。第四ランダム行列選択部816dg−uが、κ×ιのランダムな行列CM21及びCM22∈(Z/qZ)κ×ιを選択する。選択されたCM21及びCM22は第二入力情報計算部816dj−uに送られる(ステップS804dg)。第三暗号化部816dh−uが公開鍵y(k)を用い、MR2の暗号文ENC(y(k),MR2)である第三暗号文CR2=y(k)・CM+2・NM+MR2(mod q)を生成する。第三暗号文CR2は第二入力情報計算部816dj−uに送られる(ステップS804dh)。第四暗号化部6104iに行列aが入力される。第四暗号化部6104iは公開鍵y(k)を用い、行列aの暗号文ENC(y(k),a)である第四暗号文C=y(k)・CM+2・NM+a(mod q)を生成する。第四暗号文Cは第二入力情報計算部816dj−uに送られる(ステップS804di)。第二入力情報計算部816dj−uにはさらに暗号文x=Cが入力される。第二入力情報計算部816dj−uは、第二入力情報τとして(x・C+CR2)+y(k)・CM21+2・NM+CM22・y(k)を得て出力する。第二入力情報計算部816dj−uは、C=x・C+CR2としたRe(C)を計算して第二入力情報τを生成してもよいし、C=x・C+CR2としたRe(C)を計算して第二入力情報τを生成してもよい((ステップS804dj)/[ステップS804dの具体例]の説明終わり)。
【0180】
第一入力情報τ及び第二入力情報τは出力部114−u(図10)から出力され、鍵装置82−kの入力部423−kに入力され判定復号部8261−kに送られる。図26に例示するように、第一入力情報τは判定復号部8261−k(図23)の第一出力情報計算部8261a−kに入力され、第二入力情報τは第二出力情報計算部8261b−kに入力される(ステップS804e)。
【0181】
第一出力情報計算部8261a−kは、第一入力情報τと秘密鍵記憶部422−kに格納された秘密鍵s(k)とを用い、或る確率より大きな確率でfτ)=s(k)−1{s(k)・τ・s(k)(mod q)}(s(k)−1(mod 2)を正しく計算し、得られた計算結果を第一出力情報とする(ステップS804f)。第二出力情報生成部6202は、第二入力情報τと秘密鍵記憶部422−kに格納された秘密鍵s(k)とを用い、或る確率より大きな確率でfτ)=s(k)−1{s(k)・τ・s(k)(mod q)}(s(k)−1(mod 2)を正しく計算し、得られた計算結果を第二出力情報とする(ステップS804g)。すなわち、第一出力情報計算部8261a−kや第二出力情報計算部8261b−kは、意図的又は意図的ではない誤差を含んだ計算結果を出力する。言い換えると、第一出力情報計算部8261a−kでの計算結果がfτ)の場合もあればfτ)でない場合もあり、第二出力情報計算部8261b−kでの計算結果がfτ)の場合もあればfτ)でない場合もある。
【0182】
第一出力情報計算部8261a−kは第一出力情報を出力し、第二出力情報計算部8261b−kは第二出力情報を出力する(ステップS804g)。第一出力情報および第二出力情報は第四実施形態と同様に暗号化部4262−kで暗号化され、出力部424−kは、第一入力情報τ及び第二入力情報τを送信した端末装置41−uに対して第一出力情報および第二出力情報の暗号文Cを出力する(ステップS804h)。
【0183】
図25に戻り、第四実施形態と同様に復号部417−uで暗号文Cを復号して得られた第一出力情報は復号処理部816−u(図22)の第一計算部816e−uに入力され、第二出力情報は第二計算部816h−uに入力される。これらの第一出力情報及び第二出力情報が、判定復号部8261−kから復号処理部816−uに与えられた復号能力に相当する(ステップS804i)。
【0184】
第一計算部716e−uは、第一出力情報を用いて−MR1を計算してその計算結果をuとする。計算結果uは行列積計算部816f−uに送られる。ここで、u−MR1=f(x)+となる。すなわち、uはf(x)について誤差を持つ標本器となる。その理由については後述する(ステップS804j)。
【0185】
行列積計算部816f−uはu’=u・aを得る。なお、行列積計算部816f−uはu・aの計算によってu’を得てもよいし、a・uの計算によってu’を得てもよい。計算結果uとその計算結果に基づいて計算されたu’との組(u,u’)は、第一リスト記憶部816g−uに記憶される(ステップS804k)。
【0186】
第二計算部816h−uは、第二出力情報を用いて−MR2を計算してその計算結果をvとする。計算結果vは第二リスト記憶部816j−uに記憶される。ここで、v−MR2=f(x)・aとなる。すなわち、vはf(x)について誤差を持つ乱数化可能標本器となる。その理由については後述する(ステップS804n)。
【0187】
判定部816k−uは、第一リスト記憶部816g−uに記憶された組(u,u’)及び第二リスト記憶部816j−uに記憶されたvの中で、u’=vとなるものがあるか判定する(ステップS804q)。u’=vとなるものがあった場合には、ステップS804uに進む。u’=vとなるものがなかった場合には、ステップS404rに進む。
【0188】
ステップS404rでは、制御部416n−uがt=Tmaxであるか判定する(ステップS404r)。Tmaxは予め定められた自然数である。t=Tmaxであれば、制御部416n−uは、計算をすることができなかった旨の情報、例えば記号「⊥」を出力して(ステップS404t)、処理を終える。t=Tmaxでない場合には、制御部416n−uは、tを1だけインクリメント、すなわちt=t+1として(ステップS404s)、ステップS804dに戻る。
【0189】
ステップS804uでは、最終出力部816m−uが、u’=vであると判定されたu’に対応するuを出力する(ステップS804u)。このように得られたuは高い確率で暗号文xを秘密鍵s(k)で復号した復号結果f(x)となる(その理由は後述する)。よって、上述した処理を複数回繰り返し、ステップS804uで得られた値のうち最も頻度の高い値を復号結果とすればよい。また、設定によっては圧倒的な確率でu=f(x)となる。その場合にはステップS804uで得られた値をそのまま復号結果としてよい。
【0190】
−MR1−MR2がf(x)についてそれぞれ誤差を持つ標本器,乱数化可能標本器となる理由について≫
(x)の準同型性より、f(x・C+CR2)=f(x)・f(C)+f(CR2)=f(x)・a+MR2を満たし、f(x)・a=f(x・C+CR2)−MR2=fτ)−MR2を満たし、MR2=fτ)−f(x)・aを満たす。よって=Fτ)とおくと、−MR2=Fτ)−fτ)+f(x)・a=f(x)・a+{Fτ)−fτ)}を満たす。τに対応するCM21,CM22,MR2の一様ランダム性から、−MR2はf(x)・aと統計的に近似する。ただし、は確率変数=F(ENC))−はG上で一様ランダムに分布)の実現値である。したがって、−MR2はf(x)についてそれぞれ誤差を持つ乱数化可能標本器となる。
【0191】
同様にf(x・CUM+CR1)=f(x)・f(CUM)+f(CR1)=f(x)・UM+MR1を満たし、f(x)=f(x・CUM+CR1)−MR1=fτ)−MR1を満たし、MR1=fτ)−f(x)を満たす。よって=Fτ)とおくと、−MR1=Fτ)−fτ)+f(x)=f(x)+{Fτ)−fτ)}を満たす。τに対応するCM11,CM12,MR1の一様ランダム性から、−MR1はf(x)+と統計的に近似する。ただし、は確率変数=F(ENC))−はG上で一様ランダムに分布)の実現値である。したがって、−MR1はf(x)についてそれぞれ誤差を持つ標本器となる。
【0192】
≪復号結果f(x)が得られる理由について≫
第七実施形態の≪復号結果f(x)が得られる理由について≫で説明したのと同様な理由により、本形態でも正しい復号結果f(x)が得られる。ただし本形態では行列を扱う関係上、第七実施形態の≪復号結果f(x)が得られる理由について≫のG,HがG,Hに、f(x)がf(x)に、τがτに、F(τ)がFτ)に、zがzに、xがxに、X,Xに、x,xに、eがι×ιの単位行列に、乗法的表現が加法的表現に(例えばαβγがα・β+γに)それぞれ置き換えられる。さらに本形態では「擬似自由(pseudo−free)な作用」の定義が以下のようにされる。
【0193】
擬似自由(pseudo−free)な作用:
、行列の集合Ω={0,...,M}、G上の確率変数の各実現値α(α),β、及びa∈Ωについて、α・a=βとなる確率
Pr[α・aかつα|aΩ,α,β
について、あらゆる可能なに関する上限値を、組(G,Ω)の疑似自由指標とよび、これをP(G,Ω)と表すことにする。ある無視することができる関数ζ(k)が存在して、
P(G,Ω)<ζ(k)
である場合、組(G,Ω)によって定義される演算は擬似自由な作用であるという。
【0194】
[変形例等]
確率変数X、X及びXは、同じでも異なっていてもよい。同様に、確率変数及びは、同じでも異なっていてもよい。
【0195】
第一乱数生成部、第二乱数生成部、第三乱数生成部、第四乱数生成部、第五乱数生成部、第六乱数生成部及び第七乱数生成部のそれぞれは、一様乱数を生成することにより、復号システムの安全性が最も高くなる。しかし、求める安全性のレベルがそれほど高くない場合には、第一乱数生成部、第二乱数生成部、第三乱数生成部、第四乱数生成部、第五乱数生成部、第六乱数生成部及び第七乱数生成部の少なくとも一部が、一様乱数ではない乱数を生成してもよい。同様に、第八実施形態で行列を一様ランダムに選択する代わりに、一様ではないランダムな行列が選択されてもよい。また、演算効率上からは、上述の各実施形態のように0以上K未満の自然数である乱数や0以上K未満の自然数である乱数が選択されることが望ましいが、それらの代わりにK以上やK以上の自然数の乱数が選択されてもよい。
【0196】
復号処理部が同一のa,bに対応する群Hの元である第一入力情報τ及び第二入力情報τを判定復号部に提供するたびに、判定復号部の処理が複数回実行させてもよい。これにより、復号処理部が第一入力情報τ及び第二入力情報τを判定復号部に一回提供するたびに、復号処理部は第一出力情報zや第二出力情報zや第三出力情報zを複数個得ることができる。これにより、復号処理部と判定復号部との間のやり取り回数や通信量を減らすことができる。第八実施形態の第一入力情報τ及び第二入力情報τについても同様である。
【0197】
また、復号処理部が複数種類の第一入力情報τ及び第二入力情報τを判定復号部にまとめて提供し、対応する第一出力情報zや第二出力情報zや第三出力情報zを複数個まとめて取得してもよい。これにより、復号処理部と判定復号部との間のやり取り回数を減らすことができる。第八実施形態の第一入力情報τ及び第二入力情報τについても同様である。
【0198】
また、第一実施形態から第七実施形態の第一計算部や第二計算部において得られたuやvが群Gの元であるかを確認し、群Gの元であった場合には上述した処理を続行し、u又はvが群Gの元でなかった場合には、計算をすることができなかった旨の情報、例えば記号「⊥」が出力されてもよい。同様に、第八実施形態の第一計算部や第二計算部において得られたuやvがGの元であるかを確認し、Gの元であった場合には上述した処理を続行し、u又はvがGの元でなかった場合には、計算をすることができなかった旨の情報、例えば記号「⊥」が出力されてもよい。
【0199】
本発明は上述の実施の形態に限定されるものではなく、上述の各種の処理は、記載に従って時系列に実行されるのみならず、処理を実行する装置の処理能力あるいは必要に応じて並列的にあるいは個別に実行されてもよい。その他、本発明の趣旨を逸脱しない範囲で適宜変更が可能であることはいうまでもない。
【0200】
また、上述の構成をコンピュータによって実現する場合、各装置が有すべき機能の処理内容はプログラムによって記述される。そして、このプログラムをコンピュータで実行することにより、上記処理機能がコンピュータ上で実現される。
【0201】
この処理内容を記述したプログラムは、コンピュータで読み取り可能な記録媒体に記録しておくことができる。コンピュータで読み取り可能な記録媒体としては、例えば、磁気記録装置、光ディスク、光磁気記録媒体、半導体メモリ等どのようなものでもよい。
【0202】
また、このプログラムの流通は、例えば、そのプログラムを記録したDVD、CD−ROM等の可搬型記録媒体を販売、譲渡、貸与等することによって行う。さらに、このプログラムをサーバコンピュータの記憶装置に格納しておき、ネットワークを介して、サーバコンピュータから他のコンピュータにそのプログラムを転送することにより、このプログラムを流通させる構成としてもよい。
【0203】
このようなプログラムを実行するコンピュータは、例えば、まず、可搬型記録媒体に記録されたプログラムもしくはサーバコンピュータから転送されたプログラムを、一旦、自己の記憶装置に格納する。そして、処理の実行時、このコンピュータは、自己の記録装置に格納されたプログラムを読み取り、読み取ったプログラムに従った処理を実行する。また、このプログラムの別の実行形態として、コンピュータが可搬型記録媒体から直接プログラムを読み取り、そのプログラムに従った処理を実行することとしてもよく、さらに、このコンピュータにサーバコンピュータからプログラムが転送されるたびに、逐次、受け取ったプログラムに従った処理を実行することとしてもよい。また、サーバコンピュータから、このコンピュータへのプログラムの転送は行わず、その実行指示と結果取得のみによって処理機能を実現する、いわゆるASP(Application Service Provider)型のサービスによって、上述の処理を実行する構成としてもよい。なお、本形態におけるプログラムには、電子計算機による処理の用に供する情報であってプログラムに準ずるもの(コンピュータに対する直接の指令ではないがコンピュータの処理を規定する性質を有するデータ等)を含むものとする。
【0204】
また、この形態では、コンピュータ上で所定のプログラムを実行させることにより、本装置を構成することとしたが、これらの処理内容の少なくとも一部をハードウェア的に実現することとしてもよい。
【符号の説明】
【0205】
1〜8 復号システム
41−u〜81−u 端末装置
42−k〜82−k 鍵装置
43 鍵装置DB装置

【特許請求の範囲】
【請求項1】
何れかの端末装置に対応する登録許可情報を格納する登録許可情報記憶部と、
暗号文と端末情報とが入力される入力部と、
前記暗号文の復号結果に対応する応答情報を生成する復号部と、
前記端末情報が前記登録許可情報記憶部に格納された何れかの前記登録許可情報に対応する場合に、前記応答情報を出力する出力部と、を含む鍵装置
を有する復号システム。
【請求項2】
請求項1の復号システムであって、
前記端末装置に対応する登録許可情報は、前記端末装置に固有な情報であり、
前記端末情報は、何れかの端末装置に固有な情報である、
ことを特徴とする復号システム。
【請求項3】
請求項1又は2の復号システムであって、
前記端末情報に対応する復号鍵である端末復号鍵を格納する端末情報記憶部を含む端末装置を有し、
前記端末情報に対応する前記登録許可情報は暗号化鍵であり、
前記応答情報は、前記端末情報に対応する前記登録許可情報を暗号化鍵とし、前記暗号文の復号結果を暗号化した情報であり、
前記端末装置は、前記端末復号鍵を用いて前記応答情報を復号する第2復号部を含む、
ことを特徴とする復号システム。
【請求項4】
請求項1から3の何れかの復号システムであって、
第2暗号文と乱数とに対応する前記暗号文を生成する暗号化部と、
前記暗号文の復号結果と前記乱数とから前記第2暗号文の復号結果を得る第3復号部と、を含む端末装置を有する、
ことを特徴とする復号システム。
【請求項5】
請求項4の復号システムであって、
前記暗号文及び前記第2暗号文は準同型暗号方式に則って暗号化された暗号文であり、
前記暗号化部は、前記乱数を暗号化して得られる乱数暗号文と前記第2暗号文との乗法によって前記暗号文を生成し、
前記第3復号部は、前記暗号文の復号結果と前記乱数の逆元の乗法によって前記第2暗号文の復号結果を得る、
ことを特徴とする復号システム。
【請求項6】
請求項1から3の何れかの復号システムであって、
G,Hが巡回群、f(x)が群Hの元である第3暗号文xを特定の秘密鍵で復号して群Gの元を得るための復号関数、X,Xが群Gに値を持つ確率変数、xが確率変数Xの実現値、xが確率変数Xの実現値、a,bが互いに素である自然数であり、
前記第3暗号文xの生成に用いられた公開鍵に対応する鍵装置情報で特定される鍵装置に対し、前記第3暗号文xに対応する群Hの元である第一入力情報τ及び第二入力情報τである前記暗号文と前記端末装置に対応する端末情報とを出力する入力情報提供部を含む端末装置を有し、
前記鍵装置の前記復号部は、
前記端末情報が前記登録許可情報記憶部に格納された何れかの前記登録許可情報に対応する場合に、前記第一入力情報τを用い、或る確率より大きな確率でf(τ)を正しく計算し、得られた計算結果を第一出力情報zとする第一出力情報生成部と、
前記端末情報が前記登録許可情報記憶部に格納された何れかの前記登録許可情報に対応する場合に、前記第二入力情報τを用い、或る確率より大きな確率でf(τ)を正しく計算し、得られた計算結果を第二出力情報zとする第二出力情報生成部と、を含み、
前記応答情報は、前記第一出力情報z及び前記第二出力情報zであり、
前記端末装置は、
前記第一出力情報zから計算結果u=f(x)を生成する第一計算部と、
前記第二出力情報zから計算結果v=f(x)を生成する第二計算部と、
前記計算結果u及びvがu=vを満たす場合に、a’a+b’b=1を満たす整数a’,b’についてのub’a’を出力する最終出力部と、を含む、
ことを特徴とする復号システム。
【請求項7】
請求項1から3の何れかの復号システムであって、
,Hが行列の集合、f(x)が集合Hの元である第3暗号文xを特定の秘密鍵で復号して集合Gの元を得るための復号関数、が集合Gに値を持つ確率変数、が確率変数の実現値、が確率変数の実現値、aが集合Hの元であり、
前記第3暗号文xの生成に用いられた公開鍵に対応する鍵装置情報で特定される鍵装置に対し、前記第3暗号文xに対応する群Hの元である第一入力情報τ及び第二入力情報τである前記暗号文と前記端末装置に対応する端末情報とを出力する入力情報提供部を含む端末装置を有し、
前記鍵装置の前記復号部は、
前記端末情報が前記登録許可情報記憶部に格納された何れかの前記登録許可情報に対応する場合に、前記第一入力情報τを用い、或る確率より大きな確率でfτ)を正しく計算し、得られた計算結果を第一出力情報とする第一出力情報生成部と、
前記端末情報が前記登録許可情報記憶部に格納された何れかの前記登録許可情報に対応する場合に、前記第二入力情報τを用い、或る確率より大きな確率でfτ)を正しく計算し、得られた計算結果を第二出力情報とする第二出力情報生成部と、を含み、
前記応答情報は、前記第一出力情報及び前記第二出力情報であり、
前記端末装置は、
前記第一出力情報から計算結果u=f(x)+を生成する第一計算部と、
前記第二出力情報から計算結果v=f(x)aを生成する第二計算部と、
前記計算結果u及びvがu・a=vを満たす場合にuを出力する最終出力部と、を含む、
ことを特徴とする復号システム。
【請求項8】
何れかの端末装置に対応する登録許可情報を格納する登録許可情報記憶部と、
暗号文と端末情報とが入力される入力部と、
前記暗号文の復号結果に対応する応答情報を生成する復号部と、
前記端末情報が前記登録許可情報記憶部に格納された何れかの前記登録許可情報に対応する場合に、前記応答情報を出力する出力部と、
を有する鍵装置。
【請求項9】
何れかの端末装置に対応する登録許可情報を鍵装置の登録許可情報記憶部に格納するステップと、
暗号文と端末情報とが前記鍵装置の入力部に入力されるステップと、
前記端末情報が前記登録許可情報記憶部に格納された何れかの前記登録許可情報に対応する場合に、前記鍵装置の出力部で前記暗号文の復号結果に対応する応答情報を出力するステップと、
を有する復号方法。
【請求項10】
請求項9の復号方法の各ステップをコンピュータに実行させるためのプログラム。

【図1】
image rotate

【図2】
image rotate

【図3】
image rotate

【図4】
image rotate

【図5】
image rotate

【図6】
image rotate

【図7】
image rotate

【図8】
image rotate

【図9】
image rotate

【図10】
image rotate

【図11】
image rotate

【図12】
image rotate

【図13】
image rotate

【図14】
image rotate

【図15】
image rotate

【図16】
image rotate

【図17】
image rotate

【図18】
image rotate

【図19】
image rotate

【図20】
image rotate

【図21】
image rotate

【図22】
image rotate

【図23】
image rotate

【図24】
image rotate

【図25】
image rotate

【図26】
image rotate

【図27】
image rotate


【公開番号】特開2012−151756(P2012−151756A)
【公開日】平成24年8月9日(2012.8.9)
【国際特許分類】
【出願番号】特願2011−10027(P2011−10027)
【出願日】平成23年1月20日(2011.1.20)
【出願人】(000004226)日本電信電話株式会社 (13,992)
【Fターム(参考)】