(57)【要約】  準同型公開鍵暗号において暗号化の実行権限と準同型演算の実行権限とを分離し、準同型演算の実行権限では暗号化を実行できない準同型公開鍵暗号を実現する。暗号システムは、平文から暗号文を生成する権限に係る暗号化鍵と、暗号化されたまま暗号文の準同型演算を実行する権限に係る、前記暗号化鍵よりも権限が弱い準同型演算鍵と、暗号文を復号する権限に係る復号鍵とを生成する鍵生成装置と、前記暗号化鍵を用いて平文から暗号文を生成する暗号化装置と、前記準同型演算鍵を用いて前記暗号文に対する準同型演算を実行する準同型演算装置と、前記復号鍵を用いて暗号文を復号する復号装置とを備える。
2020174515.tif 000002
【特許請求の範囲】
【請求項１】
平文から暗号文を生成する権限に係る暗号化鍵と、暗号化されたまま暗号文の準同型演算を実行する権限に係る、前記暗号化鍵よりも権限が弱い準同型演算鍵と、暗号文を復号する権限に係る復号鍵とを生成する鍵生成装置と、
前記暗号化鍵を用いて平文から暗号文を生成する暗号化装置と、
前記準同型演算鍵を用いて前記暗号文に対する準同型演算を実行する準同型演算装置と、
前記復号鍵を用いて暗号文を復号する復号装置と、
を備えることを特徴とする暗号システム。
【請求項２】
前記鍵生成装置は、公開鍵暗号方式を用いて前記暗号化鍵と前記復号鍵のペアを生成し、前記暗号化鍵の要素のうち、前記準同型演算に用いない要素を取り除くことで前記準同型演算鍵を生成する、ことを特徴とする請求項１に記載の暗号システム。
【請求項３】
入力された暗号文が前記暗号化鍵を用いて生成されたか否かを検証する鍵検証装置をさらに備える請求項１または請求項２に記載の暗号システム。
【請求項４】
前記鍵検証装置は、前記復号鍵を用いて前記検証をすることを特徴とする請求項３に記載の暗号システム。
【請求項５】
前記平文は被登録認証情報であり、
前記準同型演算装置は、入力された認証情報と前記暗号化された被登録認証情報とに対する準同型演算によって、前記認証情報と前記被登録認証情報との間の認証結果の暗号文を生成し、
前記復号装置は、前記認証結果の暗号文を復号することで、前記入力された認証情報の認証結果を取得する、
ことを特徴とする請求項１から請求項４のいずれか１項に記載の暗号システム。
【請求項６】
前記暗号化装置は、複数の平文から複数の暗号文を生成し、
前記準同型演算装置は、入力された前記複数の暗号文に対する準同型演算によって、前記複数の平文に対する分析結果の暗号文を生成し、
前記復号装置は、前記分析結果の暗号文を復号することで、前記複数の平文に対する分析結果を取得する、
ことを特徴とする請求項１から請求項４のいずれか１項に記載の暗号システム。
【請求項７】
公開鍵暗号方式を用いて暗号化鍵と復号鍵のペアを生成し、
前記暗号化鍵を用いて生成された暗号文を暗号化されたまま準同型演算を実行するための準同型演算鍵を、前記暗号化鍵の要素のうち、前記準同型演算に用いない要素を取り除くことで生成する、
ことを特徴とする鍵生成装置。
【請求項８】
公開鍵暗号方式を用いて暗号化鍵と復号鍵のペアを生成し、
前記暗号化鍵を用いて生成された暗号文を暗号化されたまま準同型演算を実行するための準同型演算鍵を、前記暗号化鍵の要素のうち、前記準同型演算に用いない要素を取り除くことで生成する、
ことを特徴とする鍵生成方法。
【請求項９】
平文から暗号文を生成する権限に係る暗号化鍵と、暗号化されたまま暗号文の準同型演算を実行する権限に係る準同型演算鍵と、暗号文を復号する権限に係る復号鍵とを生成する鍵生成装置において実行される鍵生成プログラムであって、
公開鍵暗号方式を用いて前記暗号化鍵と前記復号鍵のペアを生成するステップと、
前記暗号化鍵の要素のうち、前記準同型演算に用いない要素を取り除くことで準同型演算鍵を生成するステップと、
を含むことを特徴とする鍵生成プログラム。
【請求項１０】
公開鍵暗号方式を用いて生成された暗号化鍵と復号鍵のペアのうち、前記暗号化鍵を用いて生成された暗号文の入力を受け付ける暗号文入力部と、
前記暗号文を暗号化されたまま準同型演算を実行する権限に係る、前記暗号化鍵よりも権限が弱い準同型演算鍵を取得する準同型演算鍵取得部と、
前記準同型演算鍵を用いて前記暗号文を暗号化されたまま前記準同型演算を実行する準同型演算部と、
を備えることを特徴とする準同型演算装置。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は暗号システム、鍵生成装置、鍵生成方法、鍵生成プログラム、および準同型演算装置に関する。
【背景技術】
【０００２】
個人認証の一例として、生体認証がある。「生体認証」は、被登録者の生体情報と、被認証者の生体情報とを照合することにより、被登録者と被認証者とが一致するか否かを確認する個人認証の手法である。ここで、「生体情報」とは、身体や行動に関する個人の一部の特徴から抽出されたデータである。【０００３】
ところで、日本の「個人情報の保護に関する法律」では、個人を識別可能な情報である生体情報は個人情報であると定められており、電子的なデータベースで管理される個人情報が保護の対象であることが定められている。この観点から、クライアントサーバシステムで個人認証を行う場合、生体情報をクライアントからサーバへ送信せずに認証を行うことが好ましい。また、個人情報の漏洩を防ぐ観点からは生体情報を暗号化した状態でクライアント保存する必要がある。【０００４】
そして、生体情報を用いた個人認証に限らず、認証システムでは生体情報を扱うのと同等の安全管理をすることが好ましい。【０００５】
このような要請を満たす暗号方式として準同型公開鍵暗号がある。「準同型公開鍵暗号」とは、準同型性を有する公開鍵暗号のことであり、平文同士の演算結果の暗号文を暗号文から計算可能なものである。簡単に言うと、準同型公開鍵暗号では暗号文のまま行った演算（準同型演算）が復号化後においても維持されることになる。【０００６】
乗法準同型性を有する公開鍵暗号では、演算を繰り返し実行することにより、定数乗などのより複雑な演算も実行可能である。加法準同型性を有する公開鍵暗号の場合、演算を繰り返し実行することにより、定数倍や内積などのより複雑な演算も実行可能である。さらに、Ｓｏｍｅｗｈａｔ準同型性を有する公開鍵暗号や完全準同型性を有する公開鍵暗号の場合、加法と乗法をより複雑に組み合わせた演算も実行可能である。例えば、準同型公開鍵暗号として以下の暗号方式が知られている。【０００７】
特許文献１には、「Ｐａｉｌｌｉｅｒ暗号」として知られている加法準同型性を有する公開鍵暗号が記載されている。また、特許文献２には、「Ｏｋａｍｏｔｏ−Ｕｃｈｉｙａｍａ」として知られている加法準同型性を有する公開鍵暗号が記載されている。【０００８】
非特許文献１には、「Ｅｌｇａｍａｌ暗号」として知られている乗法準同型性を有する公開鍵暗号が記載されている。また，「Ｅｌｇａｍａｌ暗号」を変形して得られる加法準同型性を有する公開鍵暗号として、「Ｌｉｆｔｅｄ−Ｅｌｇａｍａｌ暗号」と「楕円Ｅｌｇａｍａｌ暗号」とが知られている。【０００９】
非特許文献２には、「ＢＧＮ暗号」として知られているＳｏｍｅｗｈａｔ準同型性を有する公開鍵暗号が記載されている。また、非特許文献３には、「Ｂｒａｋｅｒｓｋｉ−Ｖａｉｋｕｎｔａｎａｔｈａｎ暗号」として知られているＳｏｍｅｗｈａｔ準同型性を有する公開鍵暗号が記載されている。【００１０】
準同型公開鍵暗号を用いた個人認証は、例えば次のように実行される。まず登録時には、ユーザが入力したパスワードや生体情報などの認証情報を、認証サーバが生成した暗号化鍵で暗号化して、ユーザが用いる認証端末に保存しておく。そして、認証を実行する際に認証端末では、ユーザが入力した認証情報と、端末に保存されている暗号化された認証情報とを照合して認証結果の暗号文が生成される。この処理は暗号化鍵を用いた準同型演算であり、認証情報が暗号化されたまま行われる。認証サーバには、この認証結果の暗号文のみが送信され、認証サーバは、自身の保持している復号鍵を用いて認証結果を得ることができる。この方法では、認証サーバがユーザの認証情報を知ることはない。【００１１】
また、準同型公開鍵暗号は秘匿計算にも応用可能である。準同型公開鍵暗号を用いた秘匿計算は、例えば次のように実行される。まずデータ利用者は、暗号鍵をデータ提供者達およびデータ分析者に配布する。データ提供者達はこの暗号鍵を用いてデータを暗号化し、暗号化されたデータをデータ分析者に渡す。データ分析者は、受け取った複数の暗号文に対して、暗号化鍵を用いて準同型演算を行うことによって暗号化されたままのデータの分析し、その結果の暗号文を生成する。データ利用者は、受け取った分析結果の暗号文を自身の持つ復号鍵を用いて復号し、分析結果を得る。この方法では、データ利用者は、データの分析結果を得ることができるが、個々のデータの内容を知ることはない。【００１２】
特許文献３には、準同型公開鍵暗号を暗号文の照合に用いる技術の例が記載されている。また、特許文献４には、公開鍵（検証鍵）よりも権限が強い準同型演算鍵を用いた「準同型署名」と呼ばれる方式の技術の例が記載されている。
【先行技術文献】
【特許文献】
【００１３】
【特許文献１】特許第４１３７３８５号公報
【特許文献２】特許第３４０２４４１号公報
【特許文献３】国際公開第２０１７／１７０７８０号公報
【特許文献４】国際公開第２０１７／０６１０１７号公報
【非特許文献】
【００１４】
【非特許文献１】Ｔａｈｅｒ  ＥｌＧａｍａｌ．  ”Ａ  ｐｕｂｌｉｃ  ｋｅｙ  ｃｒｙｐｔｏｓｙｓｔｅｍ  ａｎｄ  ａ  ｓｉｇｎａｔｕｒｅ  ｓｃｈｅｍｅ  ｂａｓｅｄ  ｏｎ  ｄｉｓｃｒｅｔｅ  ｌｏｇａｒｉｔｈｍｓ．”  ＩＥＥＥ  ｔｒａｎｓａｃｔｉｏｎｓ  ｏｎ  ｉｎｆｏｒｍａｔｉｏｎ  ｔｈｅｏｒｙ  ３１．４  （１９８５）：  ４６９−４７２．
【非特許文献２】Ｄａｎ  Ｂｏｎｅｈ，  Ｅｕ−Ｊｉｎ  Ｇｏｈ，  ａｎｄ  Ｋｏｂｂｉ  Ｎｉｓｓｉｍ．  ”Ｅｖａｌｕａｔｉｎｇ  ２−ＤＮＦ  ｆｏｒｍｕｌａｓ  ｏｎ  ｃｉｐｈｅｒｔｅｘｔｓ．”  Ｔｈｅｏｒｙ  ｏｆ  Ｃｒｙｐｔｏｇｒａｐｈｙ  Ｃｏｎｆｅｒｅｎｃｅ．  Ｓｐｒｉｎｇｅｒ，  Ｂｅｒｌｉｎ，  Ｈｅｉｄｅｌｂｅｒｇ，  ２００５．
【非特許文献３】Ｚｖｉｋａ  Ｂｒａｋｅｒｓｋｉ，  Ｃｒａｉｇ  Ｇｅｎｔｒｙ，  ａｎｄ  Ｖｉｎｏｄ  Ｖａｉｋｕｎｔａｎａｔｈａｎ．  ”（Ｌｅｖｅｌｅｄ）  ｆｕｌｌｙ  ｈｏｍｏｍｏｒｐｈｉｃ  ｅｎｃｒｙｐｔｉｏｎ  ｗｉｔｈｏｕｔ  ｂｏｏｔｓｔｒａｐｐｉｎｇ．”  ＡＣＭ  Ｔｒａｎｓａｃｔｉｏｎｓ  ｏｎ  Ｃｏｍｐｕｔａｔｉｏｎ  Ｔｈｅｏｒｙ  ６．３  （２０１４）：  １３．
【発明の概要】
【発明が解決しようとする課題】
【００１５】
なお、上記先行技術文献の各開示を、本書に引用をもって織り込むものとする。以下の分析は、本発明者らによってなされたものである。【００１６】
上記準同型公開鍵暗号方式では、暗号化鍵を持っていれば誰でも暗号化アルゴリズムおよび準同型演算アルゴリズムを実行可能である。つまり、暗号化の実行権限と準同型演算の実行権限が等しい。これにより、例えば以下のような問題が生じる虞がある。【００１７】
準同型公開鍵暗号を用いた個人認証の端末は、認証時には暗号化処理を行わないが、準同型演算処理のために暗号化鍵を保持している。したがって、悪意を持つ人が端末を手に入れた場合、端末に保存されている暗号化鍵を用いて自身の認証情報を暗号化することができ、しかも暗号化された自身の認証情報に対しも準同型演算を行うことができる。その結果、悪意を持つ人が認証に成功しまう可能性がある。【００１８】
また、準同型公開鍵暗号を用いた秘匿計算におけるデータ分析者は、暗号化処理を行わないが、準同型演算処理のために暗号化鍵を取得する。したがって、悪意を持つデータ分析者は、正当な暗号化データの代わりに任意のデータを暗号化し、改ざん後のデータ準同型演算を行うことができる。その結果、データ利用者が取得する分析結果は、データ提供者からの正当なデータに対する分析結果ではなく、悪意を持つデータ分析者によって改ざんされた分析結果となってしまう可能性がある。【００１９】
本発明は、暗号化の実行権限と準同型演算の実行権限とを分離し、準同型演算の実行権限では暗号化を実行できない準同型公開鍵暗号を実現することに寄与する暗号システム、鍵生成装置、鍵生成方法、鍵生成プログラム、および準同型演算装置を提供することを目的とする。
【課題を解決するための手段】
【００２０】
本発明の第１の視点によれば、平文から暗号文を生成する権限に係る暗号化鍵と、暗号化されたまま暗号文の準同型演算を実行する権限に係る、前記暗号化鍵よりも権限が弱い準同型演算鍵と、暗号文を復号する権限に係る復号鍵とを生成する鍵生成装置と、前記暗号化鍵を用いて平文から暗号文を生成する暗号化装置と、前記準同型演算鍵を用いて前記暗号文に対する準同型演算を実行する準同型演算装置と、前記復号鍵を用いて暗号文を復号する復号装置と、を備えることを特徴とする暗号システムが提供される。【００２１】
本発明の第２の視点によれば、公開鍵暗号方式を用いて暗号化鍵と復号鍵のペアを生成し、前記暗号化鍵を用いて生成された暗号文を暗号化されたまま準同型演算を実行するための準同型演算鍵を、前記暗号化鍵の要素のうち、前記準同型演算に用いない要素を取り除くことで生成する、ことを特徴とする鍵生成装置が提供される。【００２２】
本発明の第３の視点によれば、公開鍵暗号方式を用いて暗号化鍵と復号鍵のペアを生成し、前記暗号化鍵を用いて生成された暗号文を暗号化されたまま準同型演算を実行するための準同型演算鍵を、前記暗号化鍵の要素のうち、前記準同型演算に用いない要素を取り除くことで生成する、ことを特徴とする鍵生成方法が提供される。【００２３】
本発明の第４の視点によれば、平文から暗号文を生成する権限に係る暗号化鍵と、暗号化されたまま暗号文の準同型演算を実行する権限に係る準同型演算鍵と、暗号文を復号する権限に係る復号鍵とを生成する鍵生成装置において実行される鍵生成プログラムであって、公開鍵暗号方式を用いて前記暗号化鍵と前記復号鍵のペアを生成するステップと、前記暗号化鍵の要素のうち、前記準同型演算に用いない要素を取り除くことで準同型演算鍵を生成するステップと、を含むことを特徴とする鍵生成プログラムが提供される。【００２４】
なお、このプログラムは、コンピュータが読み取り可能な記憶媒体に記憶することができる。記憶媒体は、半導体メモリ、ハードディスク、磁気記憶媒体、光記憶媒体等の非トランジェントなものとすることができる。本発明は、コンピュータプログラム製品として具現することも可能である。【００２５】
本発明の第５の視点によれば、公開鍵暗号方式を用いて生成された暗号化鍵と復号鍵のペアのうち、前記暗号化鍵を用いて生成された暗号文の入力を受け付ける暗号文入力部と、前記暗号文を暗号化されたまま準同型演算を実行する権限に係る、前記暗号化鍵よりも権限が弱い準同型演算鍵を取得する準同型演算鍵取得部と、前記準同型演算鍵を用いて前記暗号文を暗号化されたまま前記準同型演算を実行する準同型演算部と、を備えることを特徴とする準同型演算装置が提供される。
【発明の効果】
【００２６】
発明の各視点によれば、暗号化の実行権限と準同型演算の実行権限とを分離し、準同型演算の実行権限では暗号化を実行できない準同型公開鍵暗号を実現することに寄与する暗号システム、鍵生成装置、鍵生成方法、鍵生成プログラム、および準同型演算装置が、提供される。
【図面の簡単な説明】
【００２７】
【図１】図１は、第１の実施形態に係る準同型暗号システムの構成を示すブロック図である。
【図２】図２は、第１の実施形態に係る準同型暗号システムの鍵生成処理を説明するフロー図である。
【図３】図３は、第１の実施形態に係る準同型暗号システムの暗号化処理を説明するフロー図である。
【図４】図４は、第１の実施形態に係る準同型暗号システムの復号処理を説明するフロー図である。
【図５】図５は、第１の実施形態に係る準同型暗号システムの準同型演算処理を説明するフロー図である。
【図６】図６は、第２の実施形態に係る準同型暗号システムの構成を示すブロック図である。
【図７】図７は、第２の実施形態に係る準同型暗号システムの鍵検証処理を説明するフロー図である。
【図８】図８は、第３の実施形態に係る準同型暗号システムの構成を示すブロック図である。
【図９】図９は、第３の実施形態に係る準同型暗号システムの鍵検証処理を説明するフロー図である。
【図１０】図１０は、第４の実施形態に係る準同型暗号システムの構成を示すブロック図である。
【図１１】図１１は、第５の実施形態に係る準同型暗号システムの構成を示すブロック図である。
【発明を実施するための形態】
【００２８】
本発明を実施するための形態について図面を参照して詳細に説明する。なお、各図面及び明細書記載の各実施形態において、同様の構成要素には同一の符号を付与し、説明を適宜省略する。また、以下には、個人認証および秘匿計算を例にした実施形態の説明が含まれるが、本発明の実施の形態はこれに限定されるものではない。
【００２９】
［第１の実施形態］
図１は、第１の実施形態に係る準同型暗号システム１００の構成を示すブロック図である。図１に示されるように、準同型暗号システム１００は、鍵生成装置１１０と、準同型演算鍵記憶装置１２０と、暗号化鍵記憶装置１３０と、復号鍵記憶装置１４０と、暗号化装置１５０と、復号装置１６０と、準同型演算装置１７０と、を備えている。ただし、準同型暗号システム１００が備える上記各装置は、別個の装置として構成することも、適宜用途に応じて同一の装置内に実装されることもある。準同型暗号システム１００は、上記各装置をサーバとクライアントとに分けて実装することによって、サーバクライアントシステムとして実現することも可能である。
【００３０】
鍵生成装置１１０は、公開パラメータの入力を受け付ける公開パラメータ入力部１１１と、公開パラメータ入力部１１１に入力された公開パラメータから準同型演算鍵と暗号化鍵と復号鍵とを生成する鍵生成部１１２と、鍵生成部１１２で生成された準同型演算鍵を出力する準同型演算鍵出力部１１３と、鍵生成部１１２で生成された暗号化鍵を出力する暗号化鍵出力部１１４と、鍵生成部１１２で生成された復号鍵を出力する復号鍵出力部１１５とを有する。
【００３１】
準同型演算鍵記憶装置１２０は、鍵生成装置１１０の準同型演算鍵出力部１１３が出力した準同型演算鍵を記憶する準同型演算鍵記憶部１２１を有し、暗号化鍵記憶装置１３０は、鍵生成装置１１０の暗号化鍵出力部１１４が出力した暗号化鍵を記憶する暗号化鍵記憶部１３１を有し、復号鍵記憶装置１４０は鍵生成装置１１０の復号鍵出力部１１５が出力した復号鍵を記憶する復号鍵記憶部１４１を有する。
【００３２】
暗号化装置１５０は、メッセージの入力を受け付けるメッセージ入力部１５１と、記憶されている暗号化鍵を取得する暗号化鍵取得部１５２と、暗号化鍵取得部１５２が取得した暗号化鍵を用いて入力されたメッセージの暗号文を生成する暗号化部１５３と、生成された暗号文を出力する暗号文出力部１５４とを有する。ここで、メッセージとは、いわゆる「平文」であり、文字情報に限らず画像や音声などの情報であってもよい。
【００３３】
復号装置１６０は、暗号文の入力を受け付ける暗号文入力部１６１と、記憶されている復号鍵を取得する復号鍵取得部１６２と、復号鍵取得部１６２が取得した復号鍵を用いて前記暗号文の復号処理を行い、復号結果を生成する復号部１６３と、復号結果を出力する復号結果出力部１６４とを有する。ここで、暗号文入力部１６１に入力される暗号文は典型的には暗号化装置１５０または準同型演算装置１７０の出力である。
【００３４】
準同型演算装置１７０は、暗号文の入力を受け付ける暗号文入力部１７１と、記憶されている準同型演算鍵を取得する準同型演算鍵取得部１７２と、準同型演算鍵取得部１７２が取得した準同型演算鍵を用いて入力された暗号文の準同型演算を行い、準同型演算結果を生成する準同型演算部１７３と、準同型演算結果を出力する準同型演算結果出力部１７４とを有する。なお、準同型演算結果出力部１７４が出力する準同型演算結果はそれ自体も暗号文である。
【００３５】
次に、図２から図３を参照しながら、準同型暗号システム１００において行われる処理について説明する。準同型暗号システム１００において行われる処理は、鍵生成処理、暗号化処理、復号処理、準同型演算処理の４つに分割できる。以下では各処理の動作例についてそれぞれ説明する。
【００３６】
図２は、鍵生成処理を説明するフロー図である。鍵生成処理は鍵生成装置１１０と準同型演算鍵記憶装置１２０と暗号化鍵記憶装置１３０と復号鍵記憶装置１４０とにより、次のように実行される。
【００３７】
まず、鍵生成装置１１０の公開パラメータ入力部１１１に公開パラメータが入力される（ステップＡ１）。
【００３８】
次に、鍵生成装置１１０の鍵生成部１１２は、公開パラメータに基づいて準同型演算鍵と暗号化鍵と復号鍵とを生成する（ステップＡ２）。
【００３９】
次に、鍵生成装置１１０の準同型演算鍵出力部１１３は、ステップＡ２で生成した準同型演算鍵を出力する（ステップＡ３）。出力された準同型演算鍵は、準同型演算鍵記憶装置１２０の準同型演算鍵記憶部１２１に記憶される（ステップＡ４）。
【００４０】
次に、鍵生成装置１１０の暗号化鍵出力部１１４は、ステップＡ２で生成した暗号化鍵を出力する（ステップＡ５）。出力された暗号化鍵は、暗号化鍵記憶装置１３０の暗号化鍵記憶部１３１に記憶される（ステップＡ６）。
【００４１】
最後に、鍵生成装置１１０の復号鍵出力部１１５は、ステップＡ２で生成した復号鍵を出力する（ステップＡ７）。出力された復号鍵は、復号鍵記憶装置１４０の復号鍵記憶部１４１に記憶される（ステップＡ８）。
【００４２】
なお、上記処理の手順は一例である。例えば、各鍵の出力であるステップＡ３、ステップＡ５、およびステップＡ７の順番は交換することが可能である。
【００４３】
図３は暗号化処理を説明するフロー図である。暗号化処理は暗号化装置１５０により次のように実行される。
【００４４】
まず、メッセージ入力部１５１に暗号化対象のメッセージが入力される（ステップＢ１）。先述のように、ここでメッセージとは文字情報に限定されない。
【００４５】
次に、暗号化鍵取得部１５２は、暗号化鍵記憶装置１３０の暗号化鍵記憶部１３１に記憶されている暗号化鍵を取得する（ステップＢ２）。
【００４６】
次に、暗号化部１５３は、ステップＢ２で取得した暗号化鍵を用い、ステップＢ１で受け取ったメッセージを暗号化し、暗号文を生成する（ステップＢ３）。
【００４７】
最後に、暗号文出力部１５４は、ステップＢ３で生成した暗号文を出力する（ステップＢ４）。
【００４８】
なお、以上は処理の例である。例えば、ステップＢ２がステップＢ１より先に実行されても構わない。
【００４９】
図４は復号処理を説明するフロー図である。復号処理は復号装置１６０により次のように実行される。
【００５０】
まず、暗号文入力部１６１に復号対象の暗号文が入力される（ステップＣ１）。
【００５１】
次に、復号鍵取得部１６２は、復号鍵記憶装置１４０の復号鍵記憶部１４１に記憶されている復号鍵を取得する（ステップＣ２）。
【００５２】
次に、復号部１６３は、ステップＣ２で取得した復号鍵を用い、ステップＣ１で受け取った暗号文を復号し、復号結果を生成する（ステップＣ３）。
【００５３】
最後に、復号結果出力部１６４は、ステップＣ３で生成した復号結果を出力する（ステップＣ４）。
【００５４】
ただし、以上は処理の例である。例えば、ステップＣ２がステップＣ１より先に実行されても構わない。
【００５５】
図５は準同型演算処理を説明するフロー図である。準同型演算処理は準同型演算装置１７０により次のように実行される。
【００５６】
まず、暗号文入力部１７１に準同型演算対象の複数の暗号文が入力される（ステップＤ１）。
【００５７】
次に、準同型演算鍵取得部１７２は、準同型演算鍵記憶装置１２０の準同型演算鍵記憶部１２１に記憶されている準同型演算鍵を取得する（ステップＤ２）。
【００５８】
次に、準同型演算部１７３は、ステップＤ２で取得した準同型演算鍵を用い、ステップＤ１で受け取った複数の暗号文に対し準同型演算を施し、準同型演算結果を生成する（ステップＤ３）。
【００５９】
最後に、準同型演算結果出力部１７４は、ステップＤ３で生成した準同型演算結果を出力する（ステップＤ４）。
【００６０】
ただし、以上は処理の例である。例えば、ステップＤ２がステップＤ１より先に実行されても構わない。
【００６１】
［第１の実施形態に係る実施例１］
次に、Ｌｉｆｔｅｄ−Ｅｌｇａｍａｌ暗号を基礎とした、本実施形態に係る準同型暗号システム１００の処理の一例を説明する。Ｌｉｆｔｅｄ−Ｅｌｇａｍａｌ暗号は、加法準同型性を有する公開鍵暗号の一例である。以下では、準同型公開鍵暗号の説明とＬｉｆｔｅｄ−Ｅｌｇａｍａｌ暗号の説明とをした後に、本実施形態に係る準同型暗号システム１００の処理の説明を行う。
【００６２】
（準同型公開鍵暗号）
公開鍵暗号方式は、鍵生成アルゴリズム（ＫｅｙＧｅｎ）、暗号化アルゴリズム（Ｅｎｃ）、復号アルゴリズム（Ｄｅｃ）の３つのアルゴリズムで構成される。
【００６３】
鍵生成アルゴリズムは、セキュリティパラメータと呼ばれる鍵の強度を表すパラメータを用いて、暗号化鍵ｅｋおよび復号鍵ｄｋを生成する。この動作は、セキュリティパラメータをκとすると、次式のように表すことができる。
ＫｅｙＧｅｎ（κ）→（ｅｋ，ｄｋ）
【００６４】
暗号化アルゴリズムは、暗号化鍵ｅｋにより平文のメッセージｍを暗号化した結果である暗号文ｃを生成する。これは次式のように表すことができる。
Ｅｎｃ（ｅｋ，ｍ）→ｃ
【００６５】
復号アルゴリズムは、復号鍵ｄｋにより暗号文ｃを復号した結果であるｍ′を生成する。これは次式のように表すことができる。
Ｄｅｃ（ｄｋ，ｃ）→ｍ′
【００６６】
公開鍵暗号方式は正しく暗号文を復号できる必要がある。すなわち、鍵生成アルゴリズムで生成された任意の暗号化鍵ｅｋおよび復号鍵ｄｋのペアに対し、任意のメッセージｍを暗号化鍵ｅｋで暗号化した結果である暗号文ｃを復号鍵ｄｋによって復号した結果ｍ′はｍと等しくなる必要がある。すなわち、ＫｅｙＧｅｎ（κ）→（ｅｋ，ｄｋ）に対し、任意のメッセージｍについて
Ｄｅｃ（ｄｋ，Ｅｎｃ（ｅｋ，ｍ））→ｍ
が成り立つ必要がある。
【００６７】
公開鍵暗号方式では、暗号化鍵を持っていれば誰でも暗号化アルゴリズムを実行可能であるが、復号鍵なしでは復号アルゴリズムは実行できない。
【００６８】
準同型性を有する公開鍵暗号方式は、公開鍵暗号の各アルゴリズムに加え、準同型演算アルゴリズム（Ｈｏｍ）を有する。
【００６９】
準同型演算アルゴリズムは、暗号化鍵により、入力された複数の暗号文に対応するメッセージの演算結果の暗号文を生成する。入力できるメッセージが２つである場合、次式のように表すことができる。
Ｈｏｍ（ｅｋ，ｃ１，ｃ２）→ｃ
【００７０】
なお、準同型演算アルゴリズムに３つ以上の暗号文を入力可能な方式や、暗号文と平文を入力可能な方式も存在する。また、複数種類の演算に対応する準同型演算を実行可能な方式などでは、準同型演算アルゴリズムの実行時に、実行する演算を指定する方式も存在する。
【００７１】
例えば、加法準同型性を有する公開鍵暗号の場合、メッセージｍ１の暗号化鍵ｅｋによる暗号文ｃ１と、メッセージｍ２の暗号化鍵ｅｋによる暗号文ｃ２と、から生成される暗号文ｃは２つのメッセージの和ｍ１＋ｍ２の暗号文である。すなわち、ＫｅｙＧｅｎ（κ）→（ｅｋ，ｄｋ）に対し、任意のメッセージｍ１とメッセージｍ２について、
Ｅｎｃ（ｅｋ，ｍ１）→ｃ１，Ｅｎｃ（ｅｋ，ｍ２）→ｃ２
とすると、
Ｄｅｃ（ｄｋ，Ｈｏｍ（ｅｋ，ｃ１，ｃ２））→ｍ１＋ｍ２
が成り立つ必要がある。
また、例えば、乗法準同型性を有する公開鍵暗号の場合、メッセージｍ１の暗号化鍵ｅｋによる暗号文ｃ１と、メッセージｍ２の暗号化鍵ｅｋによる暗号文ｃ２と、から生成される暗号文ｃは、２つのメッセージの積ｍ１・ｍ２の暗号文である必要がある。すなわち、ＫｅｙＧｅｎ（κ）→（ｅｋ，ｄｋ）に対し、任意のメッセージｍ１とメッセージｍ２について、
Ｅｎｃ（ｅｋ，ｍ１）→ｃ１，Ｅｎｃ（ｅｋ，ｍ２）→ｃ２
とすると、
Ｄｅｃ（ｄｋ，Ｈｏｍ（ｅｋ，ｃ１，ｃ２））→ｍ１・ｍ２
が成り立つ必要がある。
【００７２】
（Ｌｉｆｔｅｄ−Ｅｌｇａｍａｌ暗号）
Ｌｉｆｔｅｄ−Ｅｌｇａｍａｌ暗号は、加法準同型性を有する公開鍵暗号の一例である。Ｌｉｆｔｅｄ−Ｅｌｇａｍａｌ暗号の各アルゴリズムは次のように動作する。
【００７３】
鍵生成アルゴリズムは、まず、セキュリティパラメータκを入力として受け取る。次に、κビットの素数ｑをランダムに選び、位数がｑである乗法群Ｇおよびその生成元ｇを選ぶ。次に、１以上ｑ未満の整数ｘを一様ランダムに選択し、ｈ：＝ｇｘと定める。最後に、暗号化鍵ｅｋ＝（κ，ｑ，Ｇ，ｇ，ｈ）および復号鍵ｄｋ＝（ｅｋ，ｘ）を出力する。
【００７４】
暗号化アルゴリズムは、まず、暗号化鍵ｅｋ＝（κ，ｑ，Ｇ，ｇ，ｈ）およびメッセージｍを入力として受け取る。次に、１以上ｑ未満の整数ｒを一様ランダムに選択し、ｃａ＝ｇｒ、ｃｂ＝ｇｍ・ｈｒと定める。最後に、暗号文ｃ＝（ｃａ，ｃｂ）を出力する。
【００７５】
復号アルゴリズムは、まず、復号鍵ｄｋ＝（ｅｋ，ｘ）および暗号文ｃ＝（ｃａ，ｃｂ）を入力として受け取る。次に、Ｍ′＝ｃｂ／（（ｃａ）ｘ）を計算する。最後に、復号結果ｍ′＝Ｄｌｏｇｇ（Ｍ′）を出力する。ただし、Ｄｌｏｇは、Ｄｌｏｇｇ（ｇｘ）＝ｘとなる関数である。
【００７６】
メッセージｍの暗号文ｃ＝（ｃａ，ｃｂ）＝（ｇｒ，ｇｍ・ｈｒ）に対し、Ｌｉｆｔｅｄ−Ｅｌｇａｍａｌ暗号の復号アルゴリズムにより、暗号文ｃをｍに正しく復号できることを、次式によって確認できる。
Ｍ′＝ｃｂ／（ｃａ）ｘ＝（ｇｍ・ｈｒ）／（ｇｒ）ｘ＝（ｇｍ・ｇｘ・ｒ）／（ｇｒ）ｘ＝ｇｍ
ｍ′＝Ｄｌｏｇｇ（ｇｍ）＝ｍ
【００７７】
準同型演算アルゴリズムは、まず、暗号化鍵ｅｋ＝（κ，ｑ，Ｇ，ｇ，ｈ）および第一の暗号文ｃ１＝（ｃ１，ａ，ｃ１，ｂ）および第二の暗号文ｃ２＝（ｃ２，ａ，ｃ２，ｂ）を入力として受け取る。次に、ｃａ＝ｃ１，ａ・ｃ２，ａ，ｃｂ＝ｃ１，ｂ・ｃ２，ｂを計算する。最後に、準同型演算結果ｃ＝（ｃａ，ｃｂ）を出力する。
【００７８】
メッセージｍ１の暗号文（ｃ１，ａ＝ｇｒ，ｃ１，ｂ＝ｇｍ１・ｈｒ）（ただし、ｇｍ１はｇをｍ１乗したものを表す）およびメッセージｍ２の暗号文（ｃ２，ａ＝ｇｓ，ｃ２，ｂ＝ｇｍ２・ｈｓ（ただし、ｇｍ２はｇをｍ２乗したものを表す））に対し、次の２式が成り立つ。
ｃａ＝ｇ（ｒ＋ｓ）
ｃｂ＝ｇ（ｍ１＋ｍ２）・ｈ（ｒ＋ｓ）（ただし、ｇ（ｍ１＋ｍ２）はｇをｍ１＋ｍ２乗したものを表す）
【００７９】
したがって、ｃはｍ１＋ｍ２の暗号文であり、Ｌｉｆｔｅｄ−Ｅｌｇａｍａｌ暗号は加法準同型性を有する。
【００８０】
（本実施例）
第１の実施形態に係る実施例１は、Ｌｉｆｔｅｄ−Ｅｌｇａｍａｌ暗号を基礎とし、以下に説明するような修正を加える。以下では、図１から図５に記載の符号を参照しながら、準同型暗号システム１００が実行する実施例の説明を行う。
【００８１】
鍵生成装置１１０と準同型演算鍵記憶装置１２０と暗号化鍵記憶装置１３０と復号鍵記憶装置１４０は、以下のような処理を行う。
【００８２】
まず、鍵生成装置１１０の公開パラメータ入力部１１１にセキュリティパラメータκが入力される（ステップＡ１）。
【００８３】
次に、鍵生成装置１１０の鍵生成部１１２はκビットの素数ｑをランダムに選び、位数がｑである乗法群Ｇおよびその生成元ｇを選ぶ。そして、１以上ｑ未満の整数ｘを一様ランダムに選択し、ｈ：＝ｇｘとする。
【００８４】
次に、鍵生成部１１２が、暗号鍵と復号鍵だけではなく、準同型演算鍵も生成する。具体的には、準同型演算鍵をｈｋ＝（κ，ｑ，Ｇ）、暗号化鍵をｅｋ＝（κ，ｑ，Ｇ，ｇ，ｈ）、復号鍵をｄｋ＝（ｅｋ，ｘ）とする（ステップＡ２）。
【００８５】
次に、鍵生成装置１１０の準同型演算鍵出力部１１３はステップＡ２で生成した準同型演算鍵ｈｋを出力する（ステップＡ３）。出力された準同型演算鍵ｈｋは、準同型演算鍵記憶装置１２０の準同型演算鍵記憶部１２１に記憶される（ステップＡ４）。
【００８６】
次に、鍵生成装置１１０の暗号化鍵出力部１１４はステップＡ２で生成した暗号化鍵ｅｋを出力する（ステップＡ５）。出力された暗号化鍵ｅｋは、暗号化鍵記憶装置１３０の暗号化鍵記憶部１３１に記憶される（ステップＡ６）。
【００８７】
最後に、鍵生成装置１１０の復号鍵出力部１１５はステップＡ２で生成した復号鍵ｄｋを出力する（ステップＡ７）。出力された復号鍵ｄｋは、復号鍵記憶装置１４０の復号鍵記憶部１４１に記憶される（ステップＡ８）。
【００８８】
暗号化装置１５０は、以下のような処理を行う。
【００８９】
まず、メッセージ入力部１５１に暗号化対象のメッセージｍが入力される（ステップＢ１）。
【００９０】
そして、暗号化鍵取得部１５２は暗号化鍵記憶装置１３０の暗号化鍵記憶部１３１に記憶されている暗号化鍵ｅｋ＝（κ，ｑ，Ｇ，ｇ，ｈ）を取得する（ステップＢ２）。
【００９１】
次に、暗号化部１５３は１以上ｑ未満の整数ｒを一様ランダムに選択し、ｃａ＝ｇｒ、ｃｂ＝ｇｍ・ｈｒを計算する（ステップＢ３）。
【００９２】
最後に、暗号文出力部１５４はステップＢ３で生成した（ｃａ，ｃｂ）を暗号文として出力する（ステップＢ４）。
【００９３】
復号装置１６０は、以下のような処理を行う。
【００９４】
まず、暗号文入力部１６１に復号対象の暗号文ｃ＝（ｃａ，ｃｂ）が入力される（ステップＣ１）。
【００９５】
次に、復号鍵取得部１６２は復号鍵記憶装置１４０の復号鍵記憶部１４１に記憶されている復号鍵ｄｋ＝（κ，ｑ，Ｇ，ｇ，ｈ，ｘ）を取得する（ステップＣ２）。
【００９６】
次に、復号部１６３はＭ′＝ｃｂ／（（ｃａ）ｘ）を計算する。さらに、復号部１６３はｍ′＝Ｄｌｏｇｇ（Ｍ′）を計算する（ステップＣ３）。
【００９７】
最後に、復号結果出力部１６４は、ステップＣ３で生成した復号結果ｍ′を出力する（ステップＣ４）。
【００９８】
準同型演算装置１７０は、以下のような処理を行う。
【００９９】
まず、暗号文入力部１７１に準同型演算対象の第一の暗号文ｃ１＝（ｃ１，ａ，ｃ１，ｂ）および第二の暗号文ｃ２＝（ｃ２，ａ，ｃ２，ｂ）が入力される（ステップＤ１）。
【０１００】
そして、準同型演算鍵取得部１７２は準同型演算鍵記憶装置１２０の準同型演算鍵記憶部１２１に記憶されている準同型演算鍵ｈｋ＝（κ，ｑ，Ｇ）を取得する（ステップＤ２）。
【０１０１】
次に、準同型演算部１７３はｃａ＝ｃ１，ａ・ｃ２，ａおよびｃｂ＝ｃ１，ｂ・ｃ２，ｂを計算する（ステップＤ３）。
【０１０２】
最後に、準同型演算結果出力部１７４はステップＤ３で生成した準同型演算結果ｃ＝（ｃａ，ｃｂ）を出力する（ステップＤ４）。
【０１０３】
上記のように、暗号化鍵ｅｋ＝（κ，ｑ，Ｇ，ｇ，ｈ）と準同型演算鍵ｈｋ＝（κ，ｑ，Ｇ）が異なる。さらに、暗号化におけるｃａ＝ｇｒ、ｃｂ＝ｇｍ・ｈｒの計算にはｇおよびｈが必要であるところ、準同型演算鍵ｈｋ＝（κ，ｑ，Ｇ）にはｇおよびｈが含まれないので、準同型演算鍵ｈｋ＝（κ，ｑ，Ｇ）を入手しても、暗号化を実行することはできない。本実施例は暗号化の実行権限と準同型演算の実行権限とが異なり、準同型演算鍵の権限が暗号化鍵よりも弱い。つまり、準同型演算の実行権限では暗号化を実行できない。
【０１０４】
また、暗号化鍵ｅｋ＝（κ，ｑ，Ｇ，ｇ，ｈ）と準同型演算鍵ｈｋ＝（κ，ｑ，Ｇ）の生成方法から解るように、準同型演算鍵ｈｋ＝（κ，ｑ，Ｇ）は、暗号化鍵ｅｋ＝（κ，ｑ，Ｇ，ｇ，ｈ）の要素のうち、準同型演算に用いない要素ｇおよびｈを取り除くことで得られる。
【０１０５】
［第１の実施形態に係る実施例２］
次に、Ｐａｉｌｌｉｅｒ暗号を基礎とした、本実施形態に係る準同型暗号システム１００の処理の一例を説明する。Ｐａｉｌｌｉｅｒ暗号は、加法準同型性を有する公開鍵暗号の一例である。以下では、Ｐａｉｌｌｉｅｒ暗号の説明をした後に、本実施形態に係る準同型暗号システム１００の処理の説明を行う。なお、準同型公開鍵暗号に関する事項は実施例１の場合と同様なので説明を省略する。
【０１０６】
（Ｐａｉｌｌｉｅｒ暗号）
Ｐａｉｌｌｉｅｒ暗号は、加法準同型性を有する公開鍵暗号の一例である。Ｐａｉｌｌｉｅｒ暗号の各アルゴリズムは次のように動作する。
【０１０７】
鍵生成アルゴリズムは、まず、セキュリティパラメータκを入力として受け取る。次にκビットの２つの素数ｐ、ｑをランダムに選び、ｎ＝ｐｑとする。次に、１以上ｎ以下の整数ｋをランダムに選び、ｇ＝１＋ｋｎ  ｍｏｄ  ｎ２とする。最後に、暗号化鍵ｅｋ＝（κ，ｎ，ｇ）および復号鍵ｄｋ＝（ｅｋ，ｐ，ｑ）を出力する。
【０１０８】
暗号化アルゴリズムは、まず、暗号化鍵ｅｋ＝（κ，ｎ，ｇ）およびメッセージｍを入力として受け取る。次に、ｎ２未満の整数ｒを一様ランダムに選択し、ｃ＝ｇｍ・ｒｎ  ｍｏｄ  ｎ２とする。最後に、暗号文ｃを出力する。
【０１０９】
復号アルゴリズムは、まず、復号鍵ｄｋ＝（ｅｋ，ｐ，ｑ）および暗号文ｃを入力として受け取る。次に、λをｐ−１とｑ−１の最小公倍数とする。次に、ｃλ＝ｃλ  ｍｏｄ  ｎ２とし、さらに、ｃＬ＝（ｃλ−１）／ｎとする。次に、ｇλ＝ｇλ  ｍｏｄ  ｎ２とし、さらに、ｇＬ＝（ｇλ−１）／ｎとする。最後に、復号結果ｍ′＝ｃＬ／ｇＬ  ｍｏｄ  ｎを出力する。
【０１１０】
任意の整数ｈに対し、ｈｎλ  ｍｏｄ  ｎ２＝１が成り立つことを利用すると、メッセージｍの暗号文ｃ＝ｇｍ・ｒｎ  ｍｏｄ  ｎ２に対し、Ｐａｉｌｌｉｅｒ暗号の復号アルゴリズムにより、暗号文ｃをｍに正しく復号できることを、次式によって確認できる。
【０１１１】
ｃλ＝ｃλ  ｍｏｄ  ｎ２＝（ｇｍ・ｒｎ）λ  ｍｏｄ  ｎ２＝ｇｍλ・ｒｎλ  ｍｏｄ  ｎ２＝ｇｍλ  ｍｏｄ  ｎ２＝（１＋ｋｎ）ｍλ  ｍｏｄ  ｎ２＝１＋ｎ（ｋｍλ  ｍｏｄ  ｎ）
ｃＬ＝（ｃλ−１）／ｎ＝ｋｍλ  ｍｏｄ  ｎ
ｇλ＝ｇλ  ｍｏｄ  ｎ２＝＝ｇλ  ｍｏｄ  ｎ２＝（１＋ｋｎ）λ  ｍｏｄ  ｎ２＝１＋ｎ（ｋλ  ｍｏｄ  ｎ）
ｇＬ＝（ｇλ−１）／ｎ＝ｋλ  ｍｏｄ  ｎ
ｍ′＝ｃλ／ｇλ  ｍｏｄ  ｎ＝ｋｍλ／ｋλ  ｍｏｄ  ｎ＝ｍ
【０１１２】
準同型演算アルゴリズムは、まず、暗号化鍵ｅｋ＝（κ，ｎ，ｇ）および第一の暗号文ｃ１および第二の暗号文ｃ２を入力として受け取る。次に、ｃ＝ｃ１・ｃ２  ｍｏｄ  ｎ２を計算する。最後に、準同型演算結果ｃを出力する。
【０１１３】
メッセージｍ１の暗号文ｃ１＝ｇｍ１・ｒｎ  ｍｏｄ  ｎ２（ただし、ｇｍ１はｇをｍ１乗したものを表す）およびメッセージｍ２の暗号文ｃ２＝ｇｍ２・ｓｎ  ｍｏｄ  ｎ２（ただし、ｇｍ２はｇをｍ２乗したものを表す）に対し、次式が成り立つ。
ｃ＝ｇ（ｍ１＋ｍ２）・（ｒ・ｓ）ｎ  ｍｏｄ  ｎ２（ただし、ｇ（ｍ１＋ｍ２）はｇをｍ１＋ｍ２乗したものを表す）
【０１１４】
したがって、ｃはｍ１＋ｍ２の暗号文であり、Ｐａｉｌｌｉｅｒ暗号は加法準同型性を有する。
【０１１５】
（本実施例）
第１の実施形態に係る実施例２は、Ｐａｉｌｌｉｅｒ暗号を基礎とし、以下に説明するような修正を加える。以下では、図１から図５に記載の符号を参照しながら、準同型暗号システム１００が実行する実施例の説明を行う。
【０１１６】
鍵生成装置１１０と準同型演算鍵記憶装置１２０と暗号化鍵記憶装置１３０と復号鍵記憶装置１４０は、以下のような処理を行う。
【０１１７】
まず、鍵生成装置１１０の公開パラメータ入力部１１１にセキュリティパラメータκが入力される（ステップＡ１）。
【０１１８】
次に、鍵生成装置１１０の鍵生成部１１２はκビットの２つの素数ｐ、ｑをランダムに選び、ｎ＝ｐｑとする。次に、１以上ｎ以下の整数ｋをランダムに選び、ｇ＝１＋ｋｎ  ｍｏｄ  ｎ２とする。
【０１１９】
次に、鍵生成部１１２が、暗号鍵と復号鍵だけではなく、準同型演算鍵も生成する。具体的には、準同型演算鍵をｈｋ＝（κ，ｎ）、暗号化鍵をｅｋ＝（κ，ｎ，ｇ）、復号鍵をｄｋ＝（ｅｋ，ｐ，ｑ）とする（ステップＡ２）。
【０１２０】
次に、鍵生成装置１１０の準同型演算鍵出力部１１３はステップＡ２で生成した準同型演算鍵ｈｋを出力する（ステップＡ３）。出力された準同型演算鍵ｈｋは、準同型演算鍵記憶装置１２０の準同型演算鍵記憶部１２１に記憶される（ステップＡ４）。
【０１２１】
次に、鍵生成装置１１０の暗号化鍵出力部１１４はステップＡ２で生成した暗号化鍵ｅｋを出力する（ステップＡ５）。出力された暗号化鍵ｅｋは、暗号化鍵記憶装置１３０の暗号化鍵記憶部１３１に記憶される（ステップＡ６）。
【０１２２】
最後に、鍵生成装置１１０の復号鍵出力部１１５はステップＡ２で生成した復号鍵ｄｋを出力する（ステップＡ７）。出力された復号鍵ｄｋは、復号鍵記憶装置１４０の復号鍵記憶部１４１に記憶される（ステップＡ８）。
【０１２３】
暗号化装置１５０は、以下のような処理を行う。
【０１２４】
まず、メッセージ入力部１５１に暗号化対象のメッセージｍが入力される（ステップＢ１）。
【０１２５】
次に、暗号化鍵取得部１５２は暗号化鍵記憶装置１３０の暗号化鍵記憶部１３１に記憶されている暗号化鍵ｅｋ＝（κ，ｎ，ｇ）を取得する（ステップＢ２）。
【０１２６】
次に、１以上ｎ２以下の整数ｒをランダムに選び、ｃ＝ｇｍ・ｒｎ  ｍｏｄ  ｎ２を計算する（ステップＢ３）。
【０１２７】
最後に、暗号文出力部１５４はステップＢ３で生成した暗号文ｃを出力する（ステップＢ４）。
【０１２８】
復号装置１６０は、以下のような処理を行う。
【０１２９】
まず、暗号文入力部１６１に復号対象の暗号文ｃが入力される（ステップＣ１）。
【０１３０】
次に、復号鍵取得部１６２は復号鍵記憶装置１４０の復号鍵記憶部１４１に記憶されている復号鍵ｄｋ＝（κ，ｎ，ｇ，ｐ，ｑ）を取得する（ステップＣ２）。
【０１３１】
次に、復号部１６３はλをｐ−１とｑ−１の最小公倍数とする。そして、復号部１６３はステップＣ１で受け取った暗号文ｃからｃλ＝ｃλ  ｍｏｄ  ｎ２を計算し、さらに、ｃＬ＝（ｃλ−１）／ｎを計算する。次に、復号部１６３はステップＣ２で取得した復号鍵ｄｋからｇλ＝ｇλ  ｍｏｄ  ｎ２を計算し、さらに、ｇＬ＝（ｇλ−１）／ｎを計算する。次に、ｍ′＝ｃＬ／ｇＬ  ｍｏｄ  ｎを計算する（ステップＣ３）。
【０１３２】
最後に、復号結果出力部１６４は、ステップＣ３で生成した復号結果ｍ′を出力する（ステップＣ４）。
【０１３３】
準同型演算装置１７０は、以下のような処理を行う。
【０１３４】
まず、暗号文入力部１７１に準同型演算対象の第一の暗号文ｃ１および第二の暗号文ｃ２入力される（ステップＤ１）。
【０１３５】
次に、準同型演算鍵取得部１７２は準同型演算鍵記憶装置１２０の準同型演算鍵記憶部１２１に記憶されている準同型演算鍵ｈｋ＝（κ，ｎ）を取得する（ステップＤ２）。
【０１３６】
次に、準同型演算部１７３はｃ＝ｃ１・ｃ２  ｍｏｄ  ｎ２を計算する（ステップＤ３）。
【０１３７】
最後に、準同型演算結果出力部１７４はステップＤ３で生成した準同型演算結果ｃを出力する（ステップＤ４）。
【０１３８】
上記のように、暗号化鍵ｅｋ＝（κ，ｎ，ｇ）と準同型演算鍵ｈｋ＝（κ，ｎ）が異なる。さらに、暗号化におけるｃ＝ｇｍ・ｒｎ  ｍｏｄ  ｎ２の計算にはｇが必要であるところ、準同型演算鍵ｈｋ＝（κ，ｎ）にはｇが含まれないので、準同型演算鍵ｈｋ＝（κ，ｎ）を入手しても、暗号化を実行することはできない。本実施例は暗号化の実行権限と準同型演算の実行権限とが異なり、準同型演算鍵の権限が暗号化鍵よりも弱い。つまり、準同型演算の実行権限では暗号化を実行できない。
【０１３９】
また、暗号化鍵ｅｋ＝（κ，ｎ，ｇ）と準同型演算鍵ｈｋ＝（κ，ｎ）の生成方法から解るように、準同型演算鍵ｈｋ＝（κ，ｎ）は、暗号化鍵ｅｋ＝（κ，ｎ，ｇ）の要素のうち、準同型演算に用いない要素ｇを取り除くことで得られる。
【０１４０】
［第１の実施形態に係る実施例３］
次に、Ｏｋａｍｏｔｏ−Ｕｃｈｉｙａｍａ暗号を基礎とした、本実施形態に係る準同型暗号システム１００の処理の一例を説明する。Ｏｋａｍｏｔｏ−Ｕｃｈｉｙａｍａ暗号は、加法準同型性を有する公開鍵暗号の一例である。以下では、Ｏｋａｍｏｔｏ−Ｕｃｈｉｙａｍａ暗号の説明をした後に、本実施形態に係る準同型暗号システム１００の処理の説明を行う。なお、準同型公開鍵暗号に関する事項は実施例１の場合と同様なので説明を省略する。
【０１４１】
（Ｏｋａｍｏｔｏ−Ｕｃｈｉｙａｍａ暗号）
Ｏｋａｍｏｔｏ−Ｕｃｈｉｙａｍａ暗号は、加法準同型性を有する公開鍵暗号の一例である。Ｏｋａｍｏｔｏ−Ｕｃｈｉｙａｍａ暗号の各アルゴリズムは次のように動作する。
【０１４２】
（Ｏｋａｍｏｔｏ−Ｕｃｈｉｙａｍａ暗号）
鍵生成アルゴリズムは、まず、セキュリティパラメータκを入力として受け取る。次にκビットの２つの素数ｐ、ｑをランダムに選び、ｎ＝ｐ２ｑとする。次に、１以上ｎ以下で、ｎと互いに素である（すなわちｎとの最大公約数が１である）整数ｇをランダムに選ぶ。ｇｐ−１  ｍｏｄ  ｐ２＝１であったらｇを選びなおす。次に、ｈ＝ｇｎ  ｍｏｄ  ｎを計算する。最後に、暗号化鍵ｅｋ＝（κ，ｎ，ｇ，ｈ）および復号鍵ｄｋ＝（ｅｋ，ｐ，ｑ）を出力する。
【０１４３】
暗号化アルゴリズムは、まず、暗号化鍵ｅｋ＝（κ，ｎ，ｇ，ｈ）およびメッセージｍを入力として受け取る。次に、ｎ未満の整数ｒを一様ランダムに選択し、ｃ＝ｇｍ・ｈｒ  ｍｏｄ  ｎとする。最後に、暗号文ｃを出力する。
【０１４４】
復号アルゴリズムは、まず、復号鍵ｄｋ＝（ｅｋ，ｐ，ｑ）および暗号文ｃを入力として受け取る。次に、ｃｐ＝ｃｐ−１  ｍｏｄ  ｐ２とし、さらに、ｃＬ＝（ｃｐ−１）／ｐとする。次に、ｇｐ＝ｇｐ−１  ｍｏｄ  ｐ２とし、さらに、ｇＬ＝（ｇｐ−１）／ｐとする。
最後に、復号結果ｍ′＝ｃＬ／ｇＬ  ｍｏｄ  ｐを出力する。
【０１４５】
任意の整数ｈに対し，ｈｐｑ（ｐ−１）  ｍｏｄ  ｎ＝１が成り立つことと、ある整数ｋを用いてｈｐ−１＝１＋ｋｐと表せることを利用すると，メッセージｍの暗号文ｃ＝ｇｍ・ｈｒ  ｍｏｄ  ｎに対し、Ｐａｉｌｌｉｅｒ暗号の復号アルゴリズムにより、暗号文ｃをｍに正しく復号できることを、次式によって確認できる。
【０１４６】
ｃｐ＝ｃｐ−１  ｍｏｄ  ｐ２＝（ｇｍ・ｈｒ）ｐ−１  ｍｏｄ  ｐ２＝ｇｍ（ｐ−１）・ｇｒｎ（ｐ−１）  ｍｏｄ  ｐ２＝ｇｍ（ｐ−１）  ｍｏｄ  ｐ２＝（１＋ｋｐ）ｍ  ｍｏｄ  ｐ２＝１＋ｐ（ｋｍ  ｍｏｄ  ｐ）
ｃＬ＝（ｃｐ−１）／ｐ＝ｋｍ  ｍｏｄ  ｐ
ｇｐ＝ｇｐ−１  ｍｏｄ  ｐ２＝（１＋ｋｐ）  ｍｏｄ  ｐ２＝１＋ｐ（ｋ  ｍｏｄ  ｐ）
ｇＬ＝（ｇｐ−１）／ｐ＝ｋ  ｍｏｄ  ｐ
ｍ′＝ｃＬ／ｇＬ  ｍｏｄ  ｐ＝ｋｍ／ｋ  ｍｏｄ  ｐ＝ｍ
【０１４７】
準同型演算アルゴリズムは、まず、暗号化鍵ｅｋ＝（κ，ｎ，ｇ，ｈ）および第一の暗号文ｃ１および第二の暗号文ｃ２を入力として受け取る。次に、ｃ＝ｃ１・ｃ２  ｍｏｄ  ｎを計算する。最後に、準同型演算結果ｃを出力する。
【０１４８】
メッセージｍ１の暗号文ｃ１＝ｇｍ１・ｈｒ  ｍｏｄ  ｎ（ただし、ｇｍ１はｇをｍ１乗したものを表す）およびメッセージｍ２の暗号文ｃ２＝ｇｍ２・ｈｓ  ｍｏｄ  ｎ（ただし、ｇｍ２はｇをｍ２乗したものを表す）に対し、次式が成り立つ。
ｃ＝ｇ（ｍ１＋ｍ２）・ｈ（ｒ＋ｓ）  ｍｏｄ  ｎ（ただし、ｇ（ｍ１＋ｍ２）はｇをｍ１＋ｍ２乗したものを表す）
【０１４９】
したがって、ｃはｍ１＋ｍ２の暗号文であり、Ｏｋａｍｏｔｏ−Ｕｃｈｉｙａｍａ暗号は加法準同型性を有する。
【０１５０】
（本実施例）
第１の実施形態に係る実施例３は、Ｏｋａｍｏｔｏ−Ｕｃｈｉｙａｍａ暗号を基礎とし、以下に説明するような修正を加える。以下では、図１から図５に記載の符号を参照しながら、準同型暗号システム１００が実行する実施例の説明を行う。
【０１５１】
鍵生成装置１１０と準同型演算鍵記憶装置１２０と暗号化鍵記憶装置１３０と復号鍵記憶装置１４０は、以下のような処理を行う。
【０１５２】
まず、鍵生成装置１１０の公開パラメータ入力部１１１にセキュリティパラメータκが入力される（ステップＡ１）。
【０１５３】
次に、鍵生成部１１２が、暗号鍵と復号鍵だけではなく、準同型演算鍵も生成する。具体的には、鍵生成装置１１０の鍵生成部１１２はκビットの２つの素数ｐ、ｑをランダムに選び、ｎ＝ｐ２ｑとする。次に、１以上ｎ以下で、ｎと互いに素である（すなわちｎとの最大公約数が１である）整数ｇをランダムに選ぶ。ｇｐ−１  ｍｏｄ  ｐ２＝１であったらｇを選びなおす。次に、ｈ＝ｇｎ  ｍｏｄ  ｎを計算する。そして、準同型演算鍵をｈｋ＝（κ，ｎ）、暗号化鍵をｅｋ＝（κ，ｎ，ｇ，ｈ）、復号鍵ｄｋ＝（ｅｋ，ｐ，ｑ）をとする（ステップＡ２）。
【０１５４】
次に、鍵生成装置１１０の準同型演算鍵出力部１１３はステップＡ２で生成した準同型演算鍵ｈｋを出力する（ステップＡ３）。出力された準同型演算鍵ｈｋは、準同型演算鍵記憶装置１２０の準同型演算鍵記憶部１２１に記憶される（ステップＡ４）。
【０１５５】
次に、鍵生成装置１１０の暗号化鍵出力部１１４はステップＡ２で生成した暗号化鍵ｅｋを出力する（ステップＡ５）。出力された暗号化鍵ｅｋは、暗号化鍵記憶装置１３０の暗号化鍵記憶部１３１に記憶される（ステップＡ６）。
【０１５６】
最後に、鍵生成装置１１０の復号鍵出力部１１５はステップＡ２で生成した復号鍵ｄｋを出力する（ステップＡ７）。出力された復号鍵ｄｋは、復号鍵記憶装置１４０の復号鍵記憶部１４１に記憶される（ステップＡ８）。
【０１５７】
暗号化装置１５０は、以下のような処理を行う。
【０１５８】
まず、メッセージ入力部１５１に暗号化対象のメッセージｍが入力される（ステップＢ１）。
【０１５９】
次に、暗号化鍵取得部１５２は暗号化鍵記憶装置１３０の暗号化鍵記憶部１３１に記憶されている暗号化鍵ｅｋ＝（κ，ｎ，ｇ，ｈ）を取得する（ステップＢ２）。
【０１６０】
次に、暗号化部１５３はｎ未満の整数ｒを一様ランダムに選択し、ｃ＝ｇｍ・ｈｒ  ｍｏｄ  ｎを計算する（ステップＢ３）。
【０１６１】
最後に、暗号文出力部１５４はステップＢ３で生成した暗号文ｃを出力する（ステップＢ４）。
【０１６２】
復号装置１６０は、以下のような処理を行う。
【０１６３】
まず、暗号文入力部１６１に復号対象の暗号文ｃが入力される（ステップＣ１）。
【０１６４】
次に、復号鍵取得部１６２は復号鍵記憶装置１４０の復号鍵記憶部１４１に記憶されている復号鍵ｄｋ＝（κ，ｎ，ｇ，ｈ，ｐ，ｑ）を取得する（ステップＣ２）。
【０１６５】
次に、復号部１６３はｃｐ＝ｃｐ−１  ｍｏｄ  ｐ２を計算し、さらに、ｃＬ＝（ｃｐ−１）／ｐを計算する。次に、ｇｐ＝ｇｐ−１  ｍｏｄ  ｐ２を計算し、さらに、ｇＬ＝（ｇｐ−１）／ｐを計算する。最後に、ｍ′＝ｃＬ／ｇＬ  ｍｏｄ  ｐを計算する（ステップＣ３）。
【０１６６】
最後に、復号結果出力部１６４は、ステップＣ３で生成した復号結果ｍ′を出力する（ステップＣ４）。
【０１６７】
準同型演算装置１７０は、以下のような処理を行う。
【０１６８】
まず、暗号文入力部１７１に準同型演算対象の第一の暗号文ｃ１および第二の暗号文ｃ２が入力される（ステップＤ１）。
【０１６９】
次に、準同型演算鍵取得部１７２は準同型演算鍵記憶装置１２０の準同型演算鍵記憶部１２１に記憶されている準同型演算鍵ｈｋ＝（κ，ｎ）を取得する（ステップＤ２）。
【０１７０】
次に、準同型演算部１７３はｃ＝ｃ１・ｃ２  ｍｏｄ  ｎを計算する（ステップＤ３）。
【０１７１】
最後に、準同型演算結果出力部１７４はステップＤ３で生成した準同型演算結果ｃを出力する（ステップＤ４）。
【０１７２】
上記のように、暗号化鍵ｅｋ＝（κ，ｎ，ｇ，ｈ）と準同型演算鍵ｈｋ＝（κ，ｎ）が異なる。さらに、暗号化におけるｃ＝ｇｍ・ｈｒ  ｍｏｄ  ｎの計算にはｇおよびｈが必要であるところ、準同型演算鍵ｈｋ＝（κ，ｎ）にはｇおよびｈが含まれないので、準同型演算鍵ｈｋ＝（κ，ｎ）を入手しても、暗号化を実行することはできない。本実施例は暗号化の実行権限と準同型演算の実行権限とが異なり、準同型演算鍵の権限が暗号化鍵よりも弱い。つまり、準同型演算の実行権限では暗号化を実行できない。
【０１７３】
また、暗号化鍵ｅｋ＝（κ，ｎ，ｇ，ｈ）と準同型演算鍵ｈｋ＝（κ，ｎ）の生成方法から解るように、準同型演算鍵ｈｋ＝（κ，ｎ）は、暗号化鍵ｅｋ＝（κ，ｎ，ｇ，ｈ）の要素のうち、準同型演算に用いない要素ｇおよびｈを取り除くことで得られる。
【０１７４】
［第２の実施形態］
図６は、第２の実施形態に係る準同型暗号システム２００の構成を示すブロック図である。図６に示されるように、準同型暗号システム２００は、第１の実施形態に係る準同型暗号システム１００の構成に加え、鍵検証装置２８０を備えている。したがって、以下の説明では、鍵生成装置１１０、準同型演算鍵記憶装置１２０、暗号化鍵記憶装置１３０、復号鍵記憶装置１４０、暗号化装置１５０、復号装置１６０、および準同型演算装置１７０の構成の説明は省略する。
【０１７５】
鍵検証装置２８０は、暗号文の入力を受け付ける暗号文入力部２８１と、入力された暗号文が鍵生成装置１１０で生成された暗号化鍵で生成された暗号文であるかの検証結果を生成する検証部２８４と、その検証結果を出力する検証結果出力部２８５とを有する。
【０１７６】
鍵検証装置２８０は、次のように鍵検証処理を実行する。図７は鍵検証処理を説明するフロー図である。
【０１７７】
まず、暗号文入力部２８１に検証対象の暗号文が入力される（ステップＥ１）。
【０１７８】
次に、検証部２８４は、ステップＥ１で受け取った暗号文が、ステップＡ２で生成された暗号化鍵で生成された暗号文であるかを検証し、検証結果を生成する（ステップＥ２）。
【０１７９】
最後に、検証結果出力部２８５は、ステップＥ２で生成した検証結果を出力する（ステップＥ３）。
【０１８０】
ただし、以上は処理の例である。例えば、ステップＥ２がステップＥ１より先に実行されても構わない。
【０１８１】
［第２の実施形態に係る実施例１］
次に、Ｅｌｇａｍａｌ暗号を基礎とした、本実施形態に係る準同型暗号システム２００の処理の一例を説明する。Ｅｌｇａｍａｌ暗号は、乗法準同型性を有する公開鍵暗号の一例である。以下では、Ｅｌｇａｍａｌ暗号の説明をした後に、本実施形態に係る準同型暗号システム２００の処理の説明を行う。
【０１８２】
（Ｅｌｇａｍａｌ暗号）
Ｅｌｇａｍａｌ暗号は、乗法準同型性を有する公開鍵暗号の一例である。Ｅｌｇａｍａｌ暗号の各アルゴリズムは次のように動作する。
【０１８３】
鍵生成アルゴリズムは、まず、セキュリティパラメータκを入力として受け取る。次に、κビットの素数ｑをランダムに選び、位数がｑである乗法群Ｇおよびその生成元ｇを選ぶ。次に、１以上ｑ未満の整数ｘを一様ランダムに選択し，ｈ＝ｇｘとする。最後に、暗号化鍵ｅｋ＝（κ，ｑ，Ｇ，ｇ，ｈ）と、復号鍵ｄｋ＝（ｅｋ，ｘ）とを出力する。
【０１８４】
暗号化アルゴリズムは、まず、暗号化鍵ｅｋ＝（κ，ｑ，Ｇ，ｇ，ｈ）およびメッセージｍを入力として受け取る。次に、１以上ｑ未満の整数ｒを一様ランダムに選択し、ｃａ＝ｇｒ、ｃｂ＝ｍ・ｈｒとする。最後に、暗号文ｃ＝（ｃａ，ｃｂ）を出力する。
【０１８５】
復号アルゴリズムは、まず、復号鍵ｄｋ＝（ｅｋ，ｘ）および暗号文ｃ＝（ｃａ，ｃｂ）を入力として受け取る。次に、ｍ′＝ｃｂ／（（ｃａ）ｘ）を計算する。最後に、復号結果ｍ′を出力する。
【０１８６】
メッセージｍの暗号文ｃ＝（ｃａ，ｃｂ）＝（ｇｒ，ｍ・ｈｒ）に対し、Ｅｌｇａｍａｌ暗号の復号アルゴリズムにより、暗号文ｃをｍに正しく復号できることを、次式によって確認できる。
ｍ′＝ｃｂ／（ｃａ）ｘ＝（ｍ・ｈｒ）／（ｇｒ）ｘ＝（ｍ・ｇｘ・ｒ）／（ｇｒ）ｘ＝ｍ
【０１８７】
準同型演算アルゴリズムは、まず、暗号化鍵ｅｋ＝（κ，ｑ，Ｇ，ｇ，ｈ）および第一の暗号文ｃ１＝（ｃ１，ａ，ｃ１，ｂ）および第二の暗号文ｃ２＝（ｃ２，ａ，ｃ２，ｂ）を入力として受け取る。次に、ｃａ＝ｃ１，ａ・ｃ２，ａ，ｃｂ：＝ｃ１，ｂ・ｃ２，ｂを計算する。最後に、準同型演算結果ｃ＝（ｃａ，ｃｂ）を出力する。
【０１８８】
メッセージｍ１の暗号文（ｃ１，ａ＝ｇｒ，ｃ１，ｂ＝ｍ１・ｈｒ）およびメッセージｍ２の暗号文（ｃ２，ａ＝ｇｓ，ｃ２，ｂ＝ｍ２・ｈｓ）に対し、次の２式が成り立つ。
ｃａ＝ｇ（ｒ＋ｓ）
ｃｂ＝（ｍ１・ｍ２）・ｈ（ｒ＋ｓ）
【０１８９】
したがって、ｃはｍ１・ｍ２の暗号文であり、Ｅｌｇａｍａｌ暗号は乗法準同型性を有する。
【０１９０】
（本実施例）
第２の実施形態に係る実施例１は、Ｅｌｇａｍａｌ暗号を基礎とし、以下に説明するような修正を加える。以下では、図２から図７に記載の符号を参照しながら、準同型暗号システム２００が実行する実施例の説明を行う。
【０１９１】
鍵生成装置１１０と準同型演算鍵記憶装置１２０と暗号化鍵記憶装置１３０と復号鍵記憶装置１４０は、以下のような処理を行う。
【０１９２】
まず、鍵生成装置１１０の公開パラメータ入力部１１１にセキュリティパラメータκが入力される（ステップＡ１）。
【０１９３】
次に、鍵生成部１１２が、暗号鍵と復号鍵だけではなく、準同型演算鍵も生成する。具体的には、鍵生成装置１１０の鍵生成部１１２はκビットの素数ｑをランダムに選び、位数がｑである乗法群Ｇおよびその生成元ｇを選ぶ。次に、１以上ｑ未満の整数ｘを一様ランダムに選択し，ｈ＝ｇｘとする。次に、準同型演算鍵をｈｋ＝（κ，ｑ，Ｇ）暗号化鍵ｅｋ＝（κ，ｑ，Ｇ，ｇ，ｈ）と、復号鍵ｄｋ＝（ｅｋ，ｘ）とする（ステップＡ２）。
【０１９４】
次に、鍵生成装置１１０の準同型演算鍵出力部１１３はステップＡ２で生成した準同型演算鍵ｈｋを出力する（ステップＡ３）。出力された準同型演算鍵ｈｋは、準同型演算鍵記憶装置１２０の準同型演算鍵記憶部１２１に記憶される（ステップＡ４）。
【０１９５】
次に、鍵生成装置１１０の暗号化鍵出力部１１４はステップＡ２で生成した暗号化鍵ｅｋを出力する（ステップＡ５）。出力された暗号化鍵ｅｋは、暗号化鍵記憶装置１３０の暗号化鍵記憶部１３１に記憶される（ステップＡ６）。
【０１９６】
最後に、鍵生成装置１１０の復号鍵出力部１１５はステップＡ２で生成した復号鍵ｄｋを出力する（ステップＡ７）。出力された復号鍵ｄｋは、復号鍵記憶装置１４０の復号鍵記憶部１４１に記憶される（ステップＡ８）。
【０１９７】
暗号化装置１５０は、以下のような処理を行う。
【０１９８】
まず、メッセージ入力部１５１に暗号化対象のメッセージｍが入力される（ステップＢ１）。
【０１９９】
次に、暗号化鍵取得部１５２は暗号化鍵記憶装置１３０の暗号化鍵記憶部１３１に記憶されている暗号化鍵ｅｋ＝（κ，ｑ，Ｇ，ｇ，ｈ）を取得する（ステップＢ２）。
【０２００】
次に、暗号化部１５３は１以上ｑ未満の整数ｒを一様ランダムに選択し、ｃａ＝ｇｒ、ｃｂ＝ｍ・ｈｒとする（ステップＢ３）。
【０２０１】
最後に、暗号文出力部１５４はステップＢ３で生成した暗号文ｃ＝（ｃａ，ｃｂ）を出力する（ステップＢ４）。
【０２０２】
復号装置１６０は、以下のような処理を行う。
【０２０３】
まず、暗号文入力部１６１に復号対象の暗号文ｃが入力される（ステップＣ１）。
【０２０４】
次に、復号鍵取得部１６２は復号鍵記憶装置１４０の復号鍵記憶部１４１に記憶されている復号鍵ｄｋ＝（κ，ｑ，Ｇ，ｇ，ｈ，ｘ）を取得する（ステップＣ２）。
【０２０５】
次に、復号部１６３はｍ′＝ｃｂ／（（ｃａ）ｘ）を計算する（ステップＣ３）。
【０２０６】
最後に、復号結果出力部１６４は、ステップＣ３で生成した復号結果ｍ′を出力する（ステップＣ４）。
【０２０７】
準同型演算装置１７０は、以下のような処理を行う。
【０２０８】
まず、暗号文入力部１７１に準同型演算対象の第一の暗号文ｃ１＝（ｃ１，ａ，ｃ１，ｂ）および第二の暗号文ｃ２＝（ｃ２，ａ，ｃ２，ｂ）暗号文が入力される（ステップＤ１）。
【０２０９】
次に、準同型演算鍵取得部１７２は準同型演算鍵記憶装置１２０の準同型演算鍵記憶部１２１に記憶されている準同型演算鍵ｈｋ＝（κ，ｑ，Ｇ）を取得する（ステップＤ２）。
【０２１０】
次に、準同型演算部１７３はｃａ＝ｃ１，ａ・ｃ２，ａ，ｃｂ：＝ｃ１，ｂ・ｃ２，ｂを計算する（ステップＤ３）。
【０２１１】
最後に、準同型演算結果出力部１７４はステップＤ３で生成した準同型演算結果ｃ＝（ｃａ，ｃｂ）を出力する（ステップＤ４）。
【０２１２】
鍵検証装置２８０は、以下のような処理を行う。
【０２１３】
まず、暗号文入力部２８１に検証対象の暗号文ｃ＝（ｃａ，ｃｂ）が入力される（ステップＥ１）。
【０２１４】
次に、検証部２８４は、ｃａ＝１であったらｒｅｓｕｌｔ＝ＮＧ、そうでなければｒｅｓｕｌｔ＝ＯＫとする（ステップＥ２）。
【０２１５】
最後に、検証結果出力部２８５は、ステップＥ２で生成した検証結果ｒｅｓｕｌｔを出力する（ステップＥ３）。
【０２１６】
第２の実施形態に係る実施例１では、準同型演算鍵にはｇおよびｈが含まれないため、準同型演算鍵のみを用いると、メッセージｍに対する暗号文ｃａ＝ｇｒ、ｃｂ＝ｍ・ｈｒとして計算することができるのはｒ＝０の場合の暗号文であるｃａ＝１、ｃｂ＝ｍのみである。そこで、鍵検証処理ではｃａ＝１を満たす暗号文であるかどうかを確認し、検証対象の暗号文ｃ＝（ｃａ，ｃｂ）が、暗号化鍵に含まれるｇおよびｈを知らない攻撃者によって作られたものでないことを確認する。本実施例は暗号化の実行権限と準同型演算の実行権限とが異なり、準同型演算鍵の権限が暗号化鍵よりも弱い。したがって、準同型演算の実行権限ではｒ＝０の場合の暗号文以外の暗号文を生成できない。
【０２１７】
また、第２の実施形態に係る実施例１は、第１の実施形態の場合と同様に、準同型演算鍵は、暗号化鍵の要素のうち、準同型演算に用いない要素を取り除くことで得られる。
【０２１８】
［第２の実施形態に係る実施例２］
次に、Ｌｉｆｔｅｄ−Ｅｌｇａｍａｌ暗号を基礎とした、本実施形態に係る準同型暗号システム２００の処理の一例を説明する。Ｌｉｆｔｅｄ−Ｅｌｇａｍａｌ暗号は、加法準同型性を有する公開鍵暗号の一例である。なお、準同型公開鍵暗号およびＬｉｆｔｅｄ−Ｅｌｇａｍａｌ暗号に関する事項は実施例１の場合と同様なので説明を省略する。
【０２１９】
鍵生成装置１１０と準同型演算鍵記憶装置１２０と暗号化鍵記憶装置１３０と復号鍵記憶装置１４０は、以下のような処理を行う。
【０２２０】
まず、鍵生成装置１１０の公開パラメータ入力部１１１にセキュリティパラメータκが入力される（ステップＡ１）。
【０２２１】
次に、鍵生成装置１１０の鍵生成部１１２はκビットの素数ｑをランダムに選び、位数がｑである乗法群Ｇおよびその生成元ｇを選ぶ。次に、１以上ｑ未満の整数ｘを一様ランダムに選択し、ｈ：＝ｇｘとする。
【０２２２】
次に、鍵生成部１１２が、暗号鍵と復号鍵だけではなく、準同型演算鍵も生成する。具体的には、準同型演算鍵をｈｋ＝（κ，ｑ，Ｇ，ｇ）、暗号化鍵をｅｋ＝（κ，ｑ，Ｇ，ｇ，ｈ）、復号鍵をｄｋ＝（ｅｋ，ｘ）とする（ステップＡ２）。
【０２２３】
次に、鍵生成装置１１０の準同型演算鍵出力部１１３はステップＡ２で生成した準同型演算鍵ｈｋを出力する（ステップＡ３）。出力された準同型演算鍵ｈｋは、準同型演算鍵記憶装置１２０の準同型演算鍵記憶部１２１に記憶される（ステップＡ４）。
【０２２４】
次に、鍵生成装置１１０の暗号化鍵出力部１１４はステップＡ２で生成した暗号化鍵ｅｋを出力する（ステップＡ５）。出力された暗号化鍵ｅｋは、暗号化鍵記憶装置１３０の暗号化鍵記憶部１３１に記憶される（ステップＡ６）。
【０２２５】
最後に、鍵生成装置１１０の復号鍵出力部１１５はステップＡ２で生成した復号鍵ｄｋを出力する（ステップＡ７）。出力された復号鍵ｄｋは、復号鍵記憶装置１４０の復号鍵記憶部１４１に記憶される（ステップＡ８）。
【０２２６】
暗号化装置１５０は、以下のような処理を行う。
【０２２７】
まず、メッセージ入力部１５１に暗号化対象のメッセージｍが入力される（ステップＢ１）。
【０２２８】
次に、暗号化鍵取得部１５２は暗号化鍵記憶装置１３０の暗号化鍵記憶部１３１に記憶されている暗号化鍵ｅｋ＝（κ，ｑ，Ｇ，ｇ，ｈ）を取得する（ステップＢ２）。
【０２２９】
次に、暗号化部１５３は１以上ｑ未満の整数ｒを一様ランダムに選択し、ｃａ＝ｇｒ、ｃｂ＝ｇｍ・ｈｒを計算する（ステップＢ３）。
【０２３０】
最後に、暗号文出力部１５４はステップＢ３で生成した（ｃａ，ｃｂ）を暗号文として出力する（ステップＢ４）。
【０２３１】
復号装置１６０は、以下のような処理を行う。
【０２３２】
まず、暗号文入力部１６１に復号対象の暗号文ｃ＝（ｃａ，ｃｂ）が入力される（ステップＣ１）。
【０２３３】
次に、復号鍵取得部１６２は復号鍵記憶装置１４０の復号鍵記憶部１４１に記憶されている復号鍵ｄｋ＝（κ，ｑ，Ｇ，ｇ，ｈ，ｘ）を取得する（ステップＣ２）。
【０２３４】
次に、復号部１６３はＭ′＝ｃｂ／（（ｃａ）ｘ）を計算する。さらに、ｍ′＝Ｄｌｏｇｇ（Ｍ′）を計算する（ステップＣ３）。
【０２３５】
最後に、復号結果出力部１６４は、ステップＣ３で生成した復号結果ｍ′を出力する（ステップＣ４）。
【０２３６】
準同型演算装置１７０は、以下のような処理を行う。
【０２３７】
まず、暗号文入力部１７１に準同型演算対象の第一の暗号文ｃ１＝（ｃ１，ａ，ｃ１，ｂ）および第二の暗号文ｃ２＝（ｃ２，ａ，ｃ２，ｂ）が入力される（ステップＤ１）。
【０２３８】
次に、準同型演算鍵取得部１７２は準同型演算鍵記憶装置１２０の準同型演算鍵記憶部１２１に記憶されている準同型演算鍵ｈｋ＝（κ，ｑ，Ｇ，ｇ）を取得する（ステップＤ２）。
【０２３９】
次に、準同型演算部１７３はｃａ＝ｃ１，ａ・ｃ２，ａおよびｃｂ＝ｃ１，ｂ・ｃ２，ｂを計算する（ステップＤ３）。
最後に、準同型演算結果出力部１７４はステップＤ３で生成した準同型演算結果ｃ＝（ｃａ，ｃｂ）を出力する（ステップＤ４）。
【０２４０】
鍵検証装置２８０は、以下のような処理を行う。
【０２４１】
まず、暗号文入力部２８１に検証対象の暗号文ｃ＝（ｃａ，ｃｂ）が入力される（ステップＥ１）。
【０２４２】
次に、検証部２８４は、ｃａ＝１であったらｒｅｓｕｌｔ＝ＮＧ、そうでなければｒｅｓｕｌｔ＝ＯＫとする（ステップＥ２）。
【０２４３】
最後に、検証結果出力部２８５は、ステップＥ２で生成した検証結果ｒｅｓｕｌｔを出力する（ステップＥ３）。
【０２４４】
第２の実施形態に係る実施例２では、準同型演算鍵にはｈが含まれないため、準同型演算鍵のみを用いると、メッセージｍに対する暗号文ｃａ＝ｇｒ、ｃｂ＝ｍ・ｈｒとして計算することができるのはｒ＝０の場合の暗号文であるｃａ＝１、ｃｂ＝ｍのみである。そこで、鍵検証処理ではｃａ＝１を満たす暗号文であるかどうかを確認し、検証対象の暗号文ｃ＝（ｃａ，ｃｂ）が、暗号化鍵に含まれるｈを知らない攻撃者によって作られたものでないことを確認する。本実施例は暗号化の実行権限と準同型演算の実行権限とが異なり、準同型演算鍵の権限が暗号化鍵よりも弱い。したがって、準同型演算の実行権限ではｒ＝０の場合の暗号文以外の暗号文を生成できない。
【０２４５】
また、第２の実施形態に係る実施例２は、第１の実施形態の場合と同様に、準同型演算鍵は、暗号化鍵の要素のうち、準同型演算に用いない要素を取り除くことで得られる。
【０２４６】
［第２の実施形態に係る実施例３］
次に、楕円Ｅｌｇａｍａｌ暗号を基礎とした、本実施形態に係る準同型暗号システム２００の処理の一例を説明する。楕円Ｅｌｇａｍａｌ暗号は、加法準同型性を有する公開鍵暗号の一例である。以下では、楕円Ｅｌｇａｍａｌ暗号の説明をした後に、本実施形態に係る準同型暗号システム２００の処理の説明を行う。
【０２４７】
（楕円Ｅｌｇａｍａｌ暗号）
楕円Ｅｌｇａｍａｌ暗号は、加法準同型性を有する公開鍵暗号の一例である。楕円Ｅｌｇａｍａｌ暗号の各アルゴリズムは次のように動作する。
【０２４８】
鍵生成アルゴリズムは、まず、セキュリティパラメータκを入力として受け取る。次に、κビットの素数ｑをランダムに選び、楕円曲線Ｅ上の位数がｑである群の生成元Ｇを選ぶ。次に、１以上ｑ未満の整数ｘを一様ランダムに選択し、Ｐ＝ｘ・Ｇとする。最後に、暗号化鍵ｅｋ＝（κ，ｑ，Ｅ，Ｇ，Ｐ）および復号鍵ｄｋ＝（ｅｋ，ｘ）を出力する。
【０２４９】
暗号化アルゴリズムは、まず、暗号化鍵ｅｋ＝（κ，ｑ，Ｇ，ｇ，ｈ）およびメッセージｍを入力として受け取る。次に、１以上ｑ未満の整数ｒを一様ランダムに選択し、Ｃａ：＝ｒ・Ｇ、Ｃｂ：＝ｍ＋ｒ・Ｐとする。最後に、暗号文ｃ＝（Ｃａ，Ｃｂ）を出力する。
【０２５０】
復号アルゴリズムは、まず、復号鍵ｄｋ＝（ｅｋ，ｘ）および暗号文ｃ＝（Ｃａ，Ｃｂ）を入力として受け取る。次に、ｍ′＝Ｃｂ−ｘ・Ｃａを計算する。最後に、復号結果ｍ′を出力する。
【０２５１】
メッセージｍの暗号文ｃ＝（Ｃａ，Ｃｂ）＝（ｒ・Ｇ，ｍ＋ｒ・Ｐ）に対し、楕円Ｅｌｇａｍａｌ暗号の復号アルゴリズムにより、暗号文ｃをｍに正しく復号できることを、次式によって確認できる。
ｍ′＝Ｃｂ−ｘ・Ｃａ＝（ｍ＋ｒ・Ｐ）−ｘ・（ｒ・Ｇ）＝ｍ＋ｒ・（ｘ・Ｇ）−ｘ・（ｒ・Ｇ）＝ｍ
【０２５２】
準同型演算アルゴリズムは、まず、暗号化鍵ｅｋ＝（κ，ｑ，Ｇ，ｇ，ｈ）および第一の暗号文ｃ１＝（Ｃ１，ａ，Ｃ１，ｂ）および第二の暗号文ｃ２＝（Ｃ２，ａ，Ｃ２，ｂ）を入力として受け取る。次に、Ｃａ＝Ｃ１，ａ＋Ｃ２，ａ，Ｃｂ＝Ｃ１，ｂ＋Ｃ２，ｂを計算する。最後に、準同型演算結果ｃ＝（Ｃａ，Ｃｂ）を出力する。
【０２５３】
メッセージｍ１の暗号文（Ｃ１，ａ＝ｒ・Ｇ，Ｃ１，ｂ＝ｍ１＋ｒ・Ｐ）およびメッセージｍ２の暗号文（Ｃ２，ａ＝ｓ・Ｇ，Ｃ２，ｂ＝ｍ２＋ｓ・Ｐ）に対し、次の２式が成り立つ。
Ｃａ＝（ｒ＋ｓ）・Ｇ
Ｃｂ＝（ｍ１＋ｍ２）＋（ｒ＋ｓ）・Ｐ
【０２５４】
したがって、ｃはｍ１＋ｍ２の暗号文であり、楕円Ｅｌｇａｍａｌ暗号は加法準同型性を有する。
【０２５５】
（本実施例）
第２の実施形態に係る実施例３は、楕円Ｅｌｇａｍａｌ暗号を基礎とし、以下に説明するような修正を加える。以下では、図２から図７に記載の符号を参照しながら、準同型暗号システム２００が実行する実施例の説明を行う。
【０２５６】
鍵生成装置１１０と準同型演算鍵記憶装置１２０と暗号化鍵記憶装置１３０と復号鍵記憶装置１４０は、以下のような処理を行う。
【０２５７】
まず、鍵生成装置１１０の公開パラメータ入力部１１１にセキュリティパラメータκが入力される（ステップＡ１）。
【０２５８】
次に、鍵生成装置１１０の鍵生成部１１２はκビットの素数ｑをランダムに選び、楕円曲線Ｅ上の位数がｑである群の生成元Ｇを選ぶ。次に、１以上ｑ未満の整数ｘを一様ランダムに選択し、Ｐ＝ｘ・Ｇとする。
【０２５９】
次に、鍵生成部１１２が、暗号鍵と復号鍵だけではなく、準同型演算鍵も生成する。具体的には、準同型演算鍵をｈｋ＝（κ，ｑ，Ｅ）、暗号化鍵をｅｋ＝（κ，ｑ，Ｅ，Ｇ，Ｐ）、復号鍵をｄｋ＝（κ，ｑ，Ｅ，Ｇ，Ｐ，ｘ）とする（ステップＡ２）。
【０２６０】
次に、鍵生成装置１１０の準同型演算鍵出力部１１３はステップＡ２で生成した準同型演算鍵ｈｋを出力する（ステップＡ３）。出力された準同型演算鍵ｈｋは、準同型演算鍵記憶装置１２０の準同型演算鍵記憶部１２１に記憶される（ステップＡ４）。
【０２６１】
次に、鍵生成装置１１０の暗号化鍵出力部１１４はステップＡ２で生成した暗号化鍵ｅｋを出力する（ステップＡ５）。出力された暗号化鍵ｅｋは、暗号化鍵記憶装置１３０の暗号化鍵記憶部１３１に記憶される（ステップＡ６）。
【０２６２】
最後に、鍵生成装置１１０の復号鍵出力部１１５はステップＡ２で生成した復号鍵ｄｋを出力する（ステップＡ７）。出力された復号鍵ｄｋは、復号鍵記憶装置１４０の復号鍵記憶部１４１に記憶される（ステップＡ８）。
【０２６３】
暗号化装置１５０は、以下のような処理を行う。
【０２６４】
まず、メッセージ入力部１５１に暗号化対象のメッセージｍが入力される（ステップＢ１）。
【０２６５】
次に、暗号化鍵取得部１５２は暗号化鍵記憶装置１３０の暗号化鍵記憶部１３１に記憶されている暗号化鍵ｅｋ＝（κ，ｑ，Ｅ，Ｇ，Ｐ）を取得する（ステップＢ２）。
【０２６６】
次に、暗号化部１５３は１以上ｑ未満の整数ｒを一様ランダムに選択し、Ｃａ：＝ｒ・Ｇ、Ｃｂ：＝ｍ＋ｒ・Ｐとする（ステップＢ３）。
【０２６７】
最後に、暗号文出力部１５４はステップＢ３で生成した暗号文ｃ＝（Ｃａ，Ｃｂ）を出力する（ステップＢ４）。
【０２６８】
復号装置１６０は、以下のような処理を行う。
【０２６９】
まず、暗号文入力部１６１に復号対象の暗号文ｃが入力される（ステップＣ１）。
【０２７０】
次に、復号鍵取得部１６２は復号鍵記憶装置１４０の復号鍵記憶部１４１に記憶されている復号鍵ｄｋ＝（κ，ｑ，Ｅ，Ｇ，Ｐ，ｘ）を取得する（ステップＣ２）。
【０２７１】
次に、復号部１６３はｍ′＝Ｃｂ−ｘ・Ｃａを計算する（ステップＣ３）。
【０２７２】
最後に、復号結果出力部１６４は、ステップＣ３で生成した復号結果ｍ′を出力する（ステップＣ４）。
【０２７３】
準同型演算装置１７０は、以下のような処理を行う。
【０２７４】
まず、暗号文入力部１７１に準同型演算対象の第一の暗号文ｃ１＝（Ｃ１，ａ，Ｃ１，ｂ）および第二の暗号文ｃ２＝（Ｃ２，ａ，Ｃ２，ｂ）が入力される（ステップＤ１）。
【０２７５】
次に、準同型演算鍵取得部１７２は準同型演算鍵記憶装置１２０の準同型演算鍵記憶部１２１に記憶されている準同型演算鍵ｈｋ＝（κ，ｑ，Ｅ）を取得する（ステップＤ２）。
【０２７６】
次に、準同型演算部１７３はＣａ＝Ｃ１，ａ＋Ｃ２，ａ，Ｃｂ＝Ｃ１，ｂ＋Ｃ２，ｂを計算する（ステップＤ３）。
【０２７７】
最後に、準同型演算結果出力部１７４はステップＤ３で生成した準同型演算結果ｃ＝（Ｃａ，Ｃｂ）を出力する（ステップＤ４）。
【０２７８】
鍵検証装置２８０は、以下のような処理を行う。
【０２７９】
まず、暗号文入力部２８１に検証対象の暗号文ｃ＝（Ｃａ，Ｃｂ）が入力される（ステップＥ１）。
【０２８０】
次に、検証部２８４は、Ｃａ＝０であったらｒｅｓｕｌｔ＝ＮＧ、そうでなければｒｅｓｕｌｔ＝ＯＫとする（ステップＥ２）。
【０２８１】
最後に、検証結果出力部２８５は、ステップＥ２で生成した検証結果ｒｅｓｕｌｔを出力する（ステップＥ３）。
【０２８２】
第２の実施形態に係る実施例３では、準同型演算鍵にはＰが含まれないため、準同型演算鍵のみを用いると、メッセージｍに対する暗号文Ｃａ：＝ｒ・Ｇ、Ｃｂ：＝ｍ＋ｒ・Ｐとして計算することができるのはｒ＝０の場合の暗号文であるｃａ＝０、ｃｂ＝ｍのみである。そこで、鍵検証処理ではｃａ＝０を満たす暗号文であるかどうかを確認し、検証対象の暗号文ｃ＝（ｃａ，ｃｂ）が、暗号化鍵に含まれるＰを知らない攻撃者によって作られたものでないことを確認する。本実施例は暗号化の実行権限と準同型演算の実行権限とが異なり、準同型演算鍵の権限が暗号化鍵よりも弱い。したがって、準同型演算の実行権限ではｒ＝０の場合の暗号文以外の暗号文を生成できない。
【０２８３】
また、第２の実施形態に係る実施例３は、第１の実施形態の場合と同様に、準同型演算鍵は、暗号化鍵の要素のうち、準同型演算に用いない要素を取り除くことで得られる。
【０２８４】
［第３の実施形態］
図８は、第３の実施形態に係る準同型暗号システム３００の構成を示すブロック図である。図８に示されるように、準同型暗号システム３００は、第１の実施形態に係る準同型暗号システム１００の構成に加え、鍵検証装置３８０を備えている。したがって、以下の説明では、鍵生成装置１１０、準同型演算鍵記憶装置１２０、暗号化鍵記憶装置１３０、復号鍵記憶装置１４０、暗号化装置１５０、復号装置１６０、および準同型演算装置１７０の構成の説明は省略する。
【０２８５】
鍵検証装置３８０は、暗号文の入力を受け付ける暗号文入力部３８１と、暗号文入力部３８１に入力された暗号文に対応するメッセージの入力を受け付けるメッセージ入力部３８２と、記憶されている復号鍵を取得する復号鍵取得部３８３と、暗号文がメッセージに対し、復号鍵取得部３８３が取得した暗号化鍵で生成された暗号文であるかどうかの検証結果を生成する検証部３８４と、検証結果を出力する検証結果出力部３８５とを有する。
【０２８６】
鍵検証装置３８０は、次のように鍵検証処理を実行する。図９は鍵検証処理を説明するフロー図である。
【０２８７】
まず、暗号文入力部３８１に検証対象の暗号文が入力され、メッセージ入力部３８２に検証対象の暗号文の復号結果であるメッセージが入力される（ステップＦ１）。
【０２８８】
次に、復号鍵取得部３８３は復号鍵記憶装置１４０の復号鍵記憶部１４１に記憶されている復号鍵を取得する（ステップＦ２）。
【０２８９】
次に、検証部３８４は、ステップＦ１で受け取った暗号文が、ステップＦ２で取得した復号鍵に対応する暗号化鍵で暗号化されたものであるかを検証し、検証結果を生成する（ステップＦ３）。
【０２９０】
最後に、検証結果出力部３８５は、ステップＦ３で生成した検証結果を出力する（ステップＦ４）。
【０２９１】
ただし、以上は処理の例である。例えば、ステップＦ２がステップＦ１より先に実行されても構わない。
【０２９２】
［第３の実施形態に係る実施例１］
次に、Ｏｋａｍｏｔｏ−Ｕｃｈｉｙａｍａ暗号を基礎とした、本実施形態に係る準同型暗号システム３００の処理の一例を説明する。Ｏｋａｍｏｔｏ−Ｕｃｈｉｙａｍａ暗号は、加法準同型性を有する公開鍵暗号の一例である。なお、準同型公開鍵暗号およびＯｋａｍｏｔｏ−Ｕｃｈｉｙａｍａ暗号に関する事項は第１の実施形態の場合と同様なので説明を省略する。
【０２９３】
鍵生成装置１１０と準同型演算鍵記憶装置１２０と暗号化鍵記憶装置１３０と復号鍵記憶装置１４０は、以下のような処理を行う。
【０２９４】
まず、鍵生成装置１１０の公開パラメータ入力部１１１にセキュリティパラメータκが入力される（ステップＡ１）。
【０２９５】
次に、鍵生成装置１１０の鍵生成部１１２はκビットの２つの素数ｐ、ｑをランダムに選び、ｎ＝ｐ２ｑとする。次に、１以上ｎ以下で、ｎと互いに素である（すなわちｎとの最大公約数が１である）整数ｇをランダムに選ぶ。ｇｐ−１  ｍｏｄ  ｐ２＝１であったらｇを選びなおす。次に、ｈ＝ｇｐ（ｐ−１）  ｍｏｄ  ｎを計算する。
【０２９６】
次に、鍵生成部１１２が、暗号鍵と復号鍵だけではなく、準同型演算鍵も生成する。具体的には、準同型演算鍵をｈｋ＝（κ，ｎ，ｇ）、暗号化鍵をｅｋ＝（κ，ｎ，ｇ，ｈ）、復号鍵をｄｋ＝（κ，ｎ，ｇ，ｈ，ｐ，ｑ）とする（ステップＡ２）。
【０２９７】
次に、鍵生成装置１１０の準同型演算鍵出力部１１３はステップＡ２で生成した準同型演算鍵ｈｋを出力する（ステップＡ３）。出力された準同型演算鍵ｈｋは、準同型演算鍵記憶装置１２０の準同型演算鍵記憶部１２１に記憶される（ステップＡ４）。
【０２９８】
次に、鍵生成装置１１０の暗号化鍵出力部１１４はステップＡ２で生成した暗号化鍵ｅｋを出力する（ステップＡ５）。出力された暗号化鍵ｅｋは、暗号化鍵記憶装置１３０の暗号化鍵記憶部１３１に記憶される（ステップＡ６）。
【０２９９】
最後に、鍵生成装置１１０の復号鍵出力部１１５はステップＡ２で生成した復号鍵ｄｋを出力する（ステップＡ７）。出力された復号鍵ｄｋは、復号鍵記憶装置１４０の復号鍵記憶部１４１に記憶される（ステップＡ８）。
【０３００】
暗号化装置１５０は、以下のような処理を行う。
【０３０１】
まず、メッセージ入力部１５１に暗号化対象のメッセージｍが入力される（ステップＢ１）。
【０３０２】
次に、暗号化鍵取得部１５２は暗号化鍵記憶装置１３０の暗号化鍵記憶部１３１に記憶されている暗号化鍵ｅｋ＝（κ，ｎ，ｇ，ｈ）を取得する（ステップＢ２）。
【０３０３】
次に、暗号化部１５３はｎ未満の整数ｒを一様ランダムに選択し、ｃ＝ｇｍ・ｈｒ  ｍｏｄ  ｎとする（ステップＢ３）。
【０３０４】
最後に、暗号文出力部１５４はステップＢ３で生成した暗号文ｃを出力する（ステップＢ４）。
【０３０５】
復号装置１６０は、以下のような処理を行う。
【０３０６】
まず、暗号文入力部１６１に復号対象の暗号文ｃが入力される（ステップＣ１）。
【０３０７】
次に、復号鍵取得部１６２は復号鍵記憶装置１４０の復号鍵記憶部１４１に記憶されている復号鍵ｄｋ＝（κ，ｎ，ｇ，ｈ，ｐ，ｑ）を取得する（ステップＣ２）。
【０３０８】
次に、復号部１６３はｃｐ＝ｃｐ−１  ｍｏｄ  ｐ２とし、さらに、ｃＬ＝（ｃｐ−１）／ｐとする。
【０３０９】
次に、ｇｐ＝ｇｐ−１  ｍｏｄ  ｐ２とし、さらに、ｇＬ＝（ｇｐ−１）／ｐとする。
【０３１０】
次に、ｍ′＝ｃＬ／ｇＬ  ｍｏｄ  ｐを計算する（ステップＣ３）。
【０３１１】
最後に、復号結果出力部１６４は、ステップＣ３で生成した復号結果ｍ′を出力する（ステップＣ４）。
【０３１２】
準同型演算装置１７０は、以下のような処理を行う。
【０３１３】
まず、暗号文入力部１７１に準同型演算対象の第一の暗号文ｃ１および第二の暗号文ｃ２が入力される（ステップＤ１）。
【０３１４】
次に、準同型演算鍵取得部１７２は準同型演算鍵記憶装置１２０の準同型演算鍵記憶部１２１に記憶されている準同型演算鍵ｈｋ＝（κ，ｎ，ｇ）を取得する（ステップＤ２）。
【０３１５】
次に、準同型演算部１７３はｃ＝ｃ１・ｃ２  ｍｏｄ  ｎを計算する（ステップＤ３）。
【０３１６】
最後に、準同型演算結果出力部１７４はステップＤ３で生成した準同型演算結果ｃを出力する（ステップＤ４）。
【０３１７】
鍵検証装置３８０は、以下のような処理を行う。
【０３１８】
まず、暗号文入力部３８１に検証対象の暗号文ｃが入力され、メッセージ入力部３８２に検証対象の暗号文の復号結果であるメッセージｍが入力される（ステップＦ１）。
【０３１９】
次に、復号鍵取得部３８３は復号鍵記憶装置１４０の復号鍵記憶部１４１に記憶されている復号鍵ｄｋ＝（κ，ｎ，ｇ，ｈ，ｐ，ｑ）を取得する（ステップＦ２）。
【０３２０】
次に、検証部３８４は、ｃ′＝ｃ／ｇｍおよびｃ′′＝ｃ′（ｑ−１）／２  ｍｏｄ  ｎを計算する。
【０３２１】
次に、ｃ′′＝１であったらｒｅｓｕｌｔ＝ＯＫ、そうでなければｒｅｓｕｌｔ＝ＮＧとする（ステップＦ３）。
【０３２２】
最後に、検証結果出力部３８５は、ステップＦ３で生成した検証結果ｒｅｓｕｌｔを出力する（ステップＦ４）。
【０３２３】
なお、鍵生成処理のステップＡ２におけるｈの計算方法および鍵検証処理のステップＦ３におけるｃ′′の計算方法は異なっても構わない。ｘｙ  ｍｏｄ  λ（ｎ）＝１（ただし、λはカーマイケル関数を表す）を満たすｘおよびｙに対し、ｈ＝ｇｘ  ｍｏｄ  ｎ、ｃ′′＝ｃ′ｙ  ｍｏｄ  ｎとなっていればよい。例えば、ｈ＝ｇｐ（ｐ−１）／２  ｍｏｄ  ｎ、ｈ＝ｇｐ（ｑ−１）  ｍｏｄ  ｎ，ｈ＝ｇｐ（ｑ−１）／２  ｍｏｄ  ｎとした場合、それぞれｃ′′＝ｃ′（ｑ−１）  ｍｏｄ  ｎ、ｃ′′＝ｃ′（ｐ−１）／２  ｍｏｄ  ｎ、ｃ′′＝ｃ′（ｐ−１）  ｍｏｄ  ｎとすることができる。
【０３２４】
第３の実施形態に係る実施例１では、準同型演算鍵にはｈが含まれないため、準同型演算鍵のみを用いると、メッセージｍに対する暗号文ｃ＝ｇｍ・ｈｒ  ｍｏｄ  ｎとして計算することができるのはｈ＝ｇｐ（ｐ−１）  ｍｏｄ  ｎの代わりにｈ′＝ｇｎ  ｍｏｄ  ｎを用いて計算した暗号文ｃ＝ｇｍ・ｈ′ｒ  ｍｏｄ  ｎである。
【０３２５】
ここで、
ｃ′＝ｃ／ｇｍ＝ｈｒ  ｍｏｄ  ｎ＝ｇｐ（ｐ−１）ｒ  ｍｏｄ  ｎ
ｃ′′＝ｃ′（ｑ−１）／２  ｍｏｄ  ｎ＝ｇｐ（ｐ−１）（ｑ−１）ｒ／２  ｍｏｄ  ｎ＝１
となるが、ｈ′を用いて計算された暗号文は
ｃ′＝ｃ／ｇｍ＝ｈ′ｒ  ｍｏｄ  ｎ＝ｇｐｐｑｒ  ｍｏｄ  ｎ
ｃ′′＝ｃ′（ｑ−１）／２  ｍｏｄ  ｎ＝ｇｐｐｑ（ｑ−１）ｒ／２  ｍｏｄ  ｎ≠１
となる。
【０３２６】
そこで、第３の実施形態に係る実施例１の鍵検証処理では、ｃ′′＝１となるかどうかを確認している。これにより、暗号化鍵に含まれるが準同型演算鍵に含まれない要素を知らない攻撃者によって作られたものでないことを確認する。本実施例は暗号化の実行権限と準同型演算の実行権限とが異なり、準同型演算鍵の権限が暗号化鍵よりも弱い。したがって、準同型演算の実行権限ではｈ＝ｇｐ（ｐ−１）  ｍｏｄ  ｎの代わりにｈ′＝ｇｎ  ｍｏｄ  ｎを用いて計算した場合の暗号文以外の暗号文を生成できない。
【０３２７】
また、第３の実施形態に係る実施例１は、第１の実施形態の場合と同様に、準同型演算鍵は、暗号化鍵の要素のうち、準同型演算に用いない要素を取り除くことで得られる。
【０３２８】
［第４の実施形態］
図１０は、第４の実施形態に係る準同型暗号システム４００の構成を示すブロック図である。第４の実施形態に係る準同型暗号システム４００は、先述の第１の実施形態に係る準同型暗号システム１００の構成を個人認証に応用したものである。したがって、第１の実施形態に記載の各構成は、同一の符号を付すことによって説明を省略する。
【０３２９】
図１０に示すように、準同型暗号システム４００は、認証サーバ４１０と認証端末４２０を備えるサーバクライアントシステムである。
【０３３０】
認証サーバ４１０は、鍵生成装置１１０と暗号化鍵記憶装置１３０と復号鍵記憶装置１４０と復号装置１６０とを備えている。一方、認証端末４２０は、準同型演算鍵記憶装置１２０と暗号化装置１５０と準同型演算装置１７０と登録認証情報記憶装置１９０とを備えている。なお、登録認証情報記憶装置１９０は、暗号化装置１５０で暗号化されたと登録認証情報を記憶しておくための記憶装置である。
【０３３１】
上記構成の準同型暗号システム４００は、以下のように個人認証を行う。
【０３３２】
既述したように、鍵生成装置１１０は、平文から暗号文を生成する権限に係る暗号化鍵と、暗号化されたまま暗号文の準同型演算を実行する権限に係る準同型演算鍵と、暗号文を復号する権限に係る復号鍵とを生成する。生成された暗号化鍵と復号鍵は、それぞれ認証サーバ４１０における暗号化鍵記憶装置１３０と復号鍵記憶装置１４０とに記憶される。一方、生成された準同型演算鍵は、認証端末における準同型演算鍵記憶装置１２０に記憶される。
【０３３３】
認証情報の登録時には、ユーザが登録認証情報を認証端末４２０の暗号化装置１５０に入力する。ここで、認証情報は生体情報やパスワード等の情報である。すると、認証端末４２０の暗号化装置１５０は、認証サーバ４１０の暗号化鍵記憶装置１３０から暗号化鍵を取得し、この暗号化鍵を用いて登録認証情報を暗号化する。暗号化された登録認証情報は、登録認証情報記憶装置１９０に記憶される。
【０３３４】
認証処理の実行時には、ユーザが入力認証情報を認証端末４２０の準同型演算装置１７０に入力する。すると、認証端末４２０の準同型演算装置１７０は、入力された入力認証情報と記憶している登録認証情報との間で認証処理を行う。この時、準同型演算装置１７０は、登録認証情報に対して準同型演算を行うことによって、暗号化されたままで認証処理を行う。準同型演算装置１７０が行う準同型演算には、準同型演算鍵記憶装置１２０に記憶されている準同型演算鍵が用いられる。
【０３３５】
準同型演算装置１７０が行う認証処理は、暗号化されたままで行われるので、認証結果も暗号文である。認証結果の暗号文は、認証サーバ４１０の復号装置１６０に送信され、復号装置１６０が復号鍵を用いて認証結果の暗号文を復号する。これにより、認証サーバは、認証端末４２０に入力された入力認証情報が正当なものであるか否かを判定する。
【０３３６】
上記構成の個人認証では、暗号化鍵が認証端末４２０に保持されないので、悪意を持つ人が認証端末４２０を手に入れた場合でも自身の認証情報を暗号化することができない。したがって、上記構成の個人認証は、なりすましに対する脆弱性が低下する。
【０３３７】
なお、上記構成は本発明の応用の一例であり、第１の実施形態だけではなく、第２の実施形態や第３の実施形態のように、鍵検証装置２８０，３８０を備える構成とすることもできる。また、暗号化装置１５０を認証端末４２０から分離して別個に備える構成とすることもできる。暗号化鍵と準同型演算鍵を別個に管理し、認証処理の実行時には準同型演算鍵のみを用いるような構成であれば、本発明を適切に応用することが可能である。
【０３３８】
［第５の実施形態］
図１１は、第５の実施形態に係る準同型暗号システム５００の構成を示すブロック図である。第５の実施形態に係る準同型暗号システム５００は、先述の第１の実施形態に係る準同型暗号システム１００の構成を秘匿計算に応用したものである。したがって、第１の実施形態に記載の各構成は、同一の符号を付すことによって説明を省略する。
【０３３９】
図１１に示すように、準同型暗号システム５００は、鍵生成装置１１０とデータ提供者装置５１０とデータ分析者装置５２０とデータ利用者装置５３０とを備えている。
【０３４０】
データ提供者装置５１０は、暗号化鍵記憶装置１３０と暗号化装置１５０を備えている。データ分析者装置５２０は、準同型演算鍵記憶装置１２０と準同型演算装置１７０を備えている。データ利用者装置５３０は、復号鍵記憶装置１４０と復号装置１６０とを備えている。
【０３４１】
上記構成の準同型暗号システム４００は、以下のように秘匿計算を行う。
【０３４２】
既述したように、鍵生成装置１１０は、平文から暗号文を生成する権限に係る暗号化鍵と、暗号化されたまま暗号文の準同型演算を実行する権限に係る準同型演算鍵と、暗号文を復号する権限に係る復号鍵とを生成する。生成された暗号化鍵と準同型演算鍵と復号鍵は、それぞれ、データ提供者装置５１０の暗号化鍵記憶装置１３０とデータ分析者装置５２０の準同型演算鍵記憶装置１２０とデータ利用者装置５３０の復号鍵記憶装置１４０とに記憶される。
【０３４３】
秘匿計算では最初に、各ユーザが提供するデータ１からデータｎをデータ提供者装置５１０に入力する。ここで、各ユーザが提供するデータとは、例えば投票得点やプライバシー情報など、他人には知られたくない情報とすることができる。また、データ提供者装置５１０を複数備え、各ユーザが個別のデータ提供者装置５１０にデータを入力するとしてもよい。
【０３４４】
そして、データ提供者装置５１０の暗号化装置１５０が暗号化鍵記憶装置１３０に記憶されている暗号化鍵を用いて、データ１からデータｎを暗号化する。暗号化されたデータ１からデータｎは、データ分析者装置５２０に送信される。
【０３４５】
データ分析者装置５２０では、準同型演算装置１７０が暗号化されたデータ１からデータｎを暗号化されたまま分析する。この分析は、例えば投票得点の合計やプライバシー情報の平均など各種の分析を行うことが可能である。この分析のための準同型演算には、データ分析者装置５２０の準同型演算鍵記憶装置１２０に記憶されている準同型演算鍵が用いられる。
【０３４６】
準同型演算装置１７０が行う分析は、暗号化されたままで行われるので、分析結果も暗号文である。分析結果の暗号文は、データ利用者装置５３０の復号装置１６０に送信され、復号装置１６０が復号鍵を用いて分析結果の暗号文を復号する。これにより、データ利用者装置５３０は、各ユーザが提供するデータ１からデータｎに対する分析結果を知得する。
【０３４７】
上記構成の秘匿計算では、各ユーザが提供するデータ１からデータｎを暗号化したまま分析するので、ユーザが提供する情報の秘密が保持される。その上、データ分析者装置５２０には暗号化鍵が保持されていないので、データ分析者装置５２０を悪意の第３者が使用して、虚偽のデータを暗号化して分析結果に追加するような改竄をすることができない。したがって、データ利用者装置５３０で知得される分析結果の信頼性が高まる。
【０３４８】
なお、上記構成は本発明の応用の一例であり、第１の実施形態だけではなく、第２の実施形態や第３の実施形態のように、鍵検証装置２８０，３８０を備える構成とすることもできる。また、本例では鍵生成装置１１０を分離して別個に備える構成としているが、データ利用者装置５３０に鍵生成装置１１０を備える構成とすることもできる。
【０３４９】
なお、引用した上記の特許文献及び非特許文献等の各開示は、本書に引用をもって織り込むものとする。本発明の全開示（請求の範囲を含む）の枠内において、さらにその基本的技術思想に基づいて、実施形態ないし実施例の変更・調整が可能である。例えば、上記開示と同様の手法が、上述した準同型公開鍵暗号方式以外の準同型公開鍵暗号方式（加法準同型公開鍵暗号方式、乗法準同型公開鍵暗号方式、Ｓｏｍｅｗｈａｔ準同型公開鍵暗号、および完全準同型公開鍵暗号を含む）にも適用可能である。また、本発明の全開示の枠内において種々の開示要素（各請求項の各要素、各実施形態ないし実施例の各要素、各図面の各要素等を含む）の多様な組み合わせ、ないし、選択（少なくとも部分的な非選択を含む）が可能である。すなわち、本発明は、請求の範囲を含む全開示、修正を含むことはもちろんである。特に、本書に記載した数値範囲について、当該範囲内に含まれる任意の数値ないし小範囲が別段の記載のない場合でも具体的に記載されているものと解釈されるべきである。
【産業上の利用可能性】
【０３５０】
本発明は、個人認証や秘匿計算を行うシステムに好適に適用される。
【符号の説明】
【０３５１】
１００  準同型暗号システム
１１０  鍵生成装置
１１１  公開パラメータ入力部
１１２  鍵生成部
１１３  準同型演算鍵出力部
１１４  暗号化鍵出力部
１１５  復号鍵出力部
１２０  準同型演算鍵記憶装置
１２１  準同型演算鍵記憶部
１３０  暗号化鍵記憶装置
１３１  暗号化鍵記憶部
１４０  復号鍵記憶装置
１４１  復号鍵記憶部
１５０  暗号化装置
１５１  メッセージ入力部
１５２  暗号化鍵取得部
１５３  暗号化部
１５４  暗号文出力部
１６０  復号装置
１６１  暗号文入力部
１６２  復号鍵取得部
１６３  復号部
１６４  復号結果出力部
１７０  準同型演算装置
１７１  暗号文入力部
１７２  準同型演算鍵取得部
１７３  準同型演算部
１７４  準同型演算結果出力部
２００  準同型暗号システム
２８０  鍵検証装置
２８１  暗号文入力部
２８４  検証部
２８５  検証結果出力部
３００  準同型暗号システム
３８０  鍵検証装置
３８１  暗号文入力部
３８２  メッセージ入力部
３８３  復号鍵取得部
３８４  検証部
３８５  検証結果出力部
４００  準同型暗号システム
４１０  認証サーバ
４２０  認証端末
５００  準同型暗号システム
５１０  データ提供者装置
５２０  データ分析者装置
５３０  データ利用者装置
【図１】
2020174515.tif 000003
【図２】
2020174515.tif 000004
【図３】
2020174515.tif 000005
【図４】
2020174515.tif 000006
【図５】
2020174515.tif 000007
【図６】
2020174515.tif 000008
【図７】
2020174515.tif 000009
【図８】
2020174515.tif 000010
【図９】
2020174515.tif 000011
【図１０】
2020174515.tif 000012
【図１１】
2020174515.tif 000013
【国際調査報告】
2020174515.tif 000014
2020174515.tif 000015
2020174515.tif 000016