(57)【要約】      （修正有）【課題】平文空間が拡張された準同型暗号方式において復号を高速化する。【解決手段】第１要素以外はすべて０のｎ次元ベクトルである暗号文2014102398.tif 000191の入力を受け取るか、または、その第１要素の値ｃの入力を受け取る（ステップＳ１）。そして、秘密鍵であるｎ次正則行列Ｖの逆行列Ｖ−１と、行列Ｖのエルミート標準形であって公開鍵として暗号化に使われる特定式により定義される行列Ｗ＝ｄＶ−１の要素のうちで、平文空間サイズｓと互いに素な要素ｗを取得する（ステップＳ２）。コンピュータはさらに、法ｓのもとでのｗの逆数ｗ−１を取得する（ステップＳ３）。そして、ｃ×ｗ  ｍｏｄ  ｄを範囲［−ｄ／２，ｄ／２）に含まれるように調整した値［ｃ×ｗ］ｄを用いて、平文ｂ＝［ｃ×ｗ］ｄ×ｗ−１  ｍｏｄ  ｓを計算し（ステップＳ４）、出力する（ステップＳ５）。【選択図】図１
2014102398.tif 000002
【特許請求の範囲】
【請求項１】
コンピュータが、
第１要素以外はすべて０のｎ次元ベクトル
2014102398.tif 000175
であって、
ｎ個の整数ｖ０，…，ｖｎ−１を使って準同型暗号方式の秘密鍵として定義されるｎ次正則行列
2014102398.tif 000176
に対応する公開鍵として、前記行列Ｖのエルミート標準形である行列Ｂを用いて、０以上ｓ未満の整数である平文を暗号化した暗号文であるか、もしくは、
各々が０以上ｓ未満の整数である複数の平文を、前記行列Ｂを用いてそれぞれ暗号化して得られる複数の暗号文に対して、当該複数の暗号文を復号せずにある演算を行った結果である暗号文である
ことを特徴とするベクトル
2014102398.tif 000177
の入力を受け取るか、または、当該ベクトル
2014102398.tif 000178
の第１要素である値ｃの入力を受け取り、
前記行列Ｂの行列式ｄと前記行列Ｖの逆行列Ｖ−１により定義される行列Ｗ＝ｄＶ−１の要素のうちでｓと互いに素な要素ｗを取得し、
法ｓのもとでのｗの逆数ｗ−１を取得し、
ｃ×ｗ  ｍｏｄ  ｄを範囲［−ｄ／２，ｄ／２）に含まれるように調整した値［ｃ×ｗ］ｄを用いて、ｂ＝［ｃ×ｗ］ｄ×ｗ−１  ｍｏｄ  ｓを計算し、
計算した値ｂを、入力された前記ベクトル
2014102398.tif 000179
または入力された前記値ｃに対応する平文として、出力する
ことを特徴とする復号方法。
【請求項２】
前記要素ｗを取得する処理は、
前記行列Ｖから前記逆行列Ｖ−１を計算し、
前記逆行列Ｖ−１を用いて、前記行列Ｗ中の少なくとも１行のｎ個の要素を計算するか、または、前記行列Ｗ中の少なくとも１列のｎ個の要素を計算し、
前記行列Ｗ中の計算した前記要素の中から、ｓと互いに素な要素を探して、見つかった要素を前記要素ｗとして取得する
ことを含み、
前記逆数ｗ−１を取得する処理は、見つかった前記要素ｗから前記逆数ｗ−１を計算する処理を含む
ことを特徴とする請求項１に記載の復号方法。
【請求項３】
前記要素ｗを取得する処理は、記憶装置を参照して、当該記憶装置に予め記憶されている前記要素ｗを読み出す処理を含み、
前記逆数ｗ−１を取得する処理は、前記記憶装置を参照して、前記記憶装置に予め記憶されている前記逆数ｗ−１を読み出す処理を含む
ことを特徴とする請求項１に記載の復号方法。
【請求項４】
前記値ｂを計算する処理は、モンゴメリ乗算剰余演算を含むことを特徴とする請求項１から３のいずれか１項に記載の復号方法。
【請求項５】
前記値ｂを計算する処理は、前記値ｃと前記要素ｗとの乗算と、法ｄによる剰余演算と、前記値［ｃ×ｗ］ｄと前記逆数ｗ−１との乗算と、法ｓによる剰余演算を含むことを特徴とする請求項１から３のいずれか１項に記載の復号方法。
【請求項６】
ｓが素数または２の冪乗数であることを特徴とする請求項１から５のいずれか１項に記載の復号方法。
【請求項７】
コンピュータに、
第１要素以外はすべて０のｎ次元ベクトル
2014102398.tif 000180
であって、
ｎ個の整数ｖ０，…，ｖｎ−１を使って準同型暗号方式の秘密鍵として定義されるｎ次正則行列
2014102398.tif 000181
に対応する公開鍵として、前記行列Ｖのエルミート標準形である行列Ｂを用いて、０以上ｓ未満の整数である平文を暗号化した暗号文であるか、もしくは、
各々が０以上ｓ未満の整数である複数の平文を、前記行列Ｂを用いてそれぞれ暗号化して得られる複数の暗号文に対して、当該複数の暗号文を復号せずにある演算を行った結果である暗号文である
ことを特徴とするベクトル
2014102398.tif 000182
の入力を受け取るか、または、当該ベクトル
2014102398.tif 000183
の第１要素である値ｃの入力を受け取り、
前記行列Ｂの行列式ｄと前記行列Ｖの逆行列Ｖ−１により定義される行列Ｗ＝ｄＶ−１の要素のうちでｓと互いに素な要素ｗを取得し、
法ｓのもとでのｗの逆数ｗ−１を取得し、
ｃ×ｗ  ｍｏｄ  ｄを範囲［−ｄ／２，ｄ／２）に含まれるように調整した値［ｃ×ｗ］ｄを用いて、ｂ＝［ｃ×ｗ］ｄ×ｗ−１  ｍｏｄ  ｓを計算し、
計算した値ｂを、入力された前記ベクトル
2014102398.tif 000184
または入力された前記値ｃに対応する平文として、出力する
ことを含む処理を実行させることを特徴とする復号プログラム。
【請求項８】
第１要素以外はすべて０のｎ次元ベクトル
2014102398.tif 000185
であって、
ｎ個の整数ｖ０，…，ｖｎ−１を使って準同型暗号方式の秘密鍵として定義されるｎ次正則行列
2014102398.tif 000186
に対応する公開鍵として、前記行列Ｖのエルミート標準形である行列Ｂを用いて、０以上ｓ未満の整数である平文を暗号化した暗号文であるか、もしくは、
各々が０以上ｓ未満の整数である複数の平文を、前記行列Ｂを用いてそれぞれ暗号化して得られる複数の暗号文に対して、当該複数の暗号文を復号せずにある演算を行った結果である暗号文である
ことを特徴とするベクトル
2014102398.tif 000187
の入力を受け取るか、または、当該ベクトル
2014102398.tif 000188
の第１要素である値ｃの入力を受け取る暗号文受け取り部と、
前記行列Ｂの行列式ｄと前記行列Ｖの逆行列Ｖ−１により定義される行列Ｗ＝ｄＶ−１の要素のうちでｓと互いに素な要素ｗを取得する第１の取得部と、
法ｓのもとでのｗの逆数ｗ−１を取得する第２の取得部と、
ｃ×ｗ  ｍｏｄ  ｄを範囲［−ｄ／２，ｄ／２）に含まれるように調整した値［ｃ×ｗ］ｄを用いて、ｂ＝［ｃ×ｗ］ｄ×ｗ−１  ｍｏｄ  ｓを計算する計算部と、
前記計算部が計算した値ｂを、前記暗号文受け取り部が受け取った前記ベクトル
2014102398.tif 000189
または前記値ｃに対応する平文として出力する平文出力部と、
を備えることを特徴とする復号装置。
【請求項９】
コンピュータが、
ｎ個の整数ｖ０，…，ｖｎ−１を生成し、
生成した前記ｎ個の整数ｖ０，…，ｖｎ−１に関して、
前記ｎ個の整数ｖ０，…，ｖｎ−１により定義されるｎ次正方行列
2014102398.tif 000190
に逆行列Ｖ−１が存在する、という第１の条件と、
１＜ｊ≦ｎなるすべてのｊについて第（１，ｊ）要素が０であり、１＜ｉ≦ｎかつ１＜ｊ≦ｎかつｉ≠ｊなるすべてのｉとｊについて第（ｉ，ｊ）要素が０であり、１＜ｉ≦ｎなるすべてのｉについて第（ｉ，ｉ）要素が１であるようなエルミート標準形の行列Ｂが、前記行列Ｖから導出される、という第２の条件と、
前記行列Ｂの行列式ｄと前記行列Ｖの前記逆行列Ｖ−１により定義される行列Ｗ＝ｄＶ−１のｎ×ｎ個の要素の中に、所定の正整数ｓと互いに素な要素が存在する、という第３の条件と、
が成り立つか否かを判定し、
前記第１の条件と前記第２の条件と前記第３の条件のすべてが成り立つような前記ｎ個の整数ｖ０，…，ｖｎ−１が得られるまで、前記ｎ個の整数ｖ０，…，ｖｎ−１の生成を繰り返し、
前記第１の条件と前記第２の条件と前記第３の条件のすべてが成り立つような前記ｎ個の整数ｖ０，…，ｖｎ−１が得られたら、０以上ｓ未満の整数の集合を平文空間とする準同型暗号方式における公開鍵として、前記行列Ｂを出力する
ことを特徴とする鍵生成方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は準同型暗号方式（homomorphic cryptography）に関する。
【背景技術】
【０００２】
暗号方式（cryptography）には、大別して、共通鍵暗号方式（symmetric-key cryptography）と公開鍵暗号方式（public-key cryptography）がある。共通鍵暗号方式では暗号化鍵（encryption key）と復号鍵（decryption key）が同じである。他方、公開鍵暗号方式では、暗号化と復号とで一対の異なる鍵が用いられる。
【０００３】
多くの公開鍵暗号方式では、暗号化に用いる公開鍵（public key）は予め公開され、復号に用いる秘密鍵（secret key）は秘密情報として保持される。具体的には、例えば、送信者は受信者の公開鍵を用いて平文（plaintext）を暗号化し、暗号文（ciphertext）を送信する。受信者は、受信者自身の秘密鍵を用いて暗号文を復号し、平文を得る。
【０００４】
準同型暗号方式は、データを暗号化したまま処理することを可能とする公開鍵暗号方式の1つである。例えば、ｍ１とｍ２を平文とし、Ｅを暗号化関数とする。任意の２つの平文ｍ１とｍ２に対して以下の式（１）を満たす暗号化関数Ｅは、加算に関して準同型性を持つ。一方、任意の２つの平文ｍ１とｍ２に対して以下の式（２）を満たす暗号化関数Ｅは、乗算に関して準同型性を持つ。
Ｅ（ｍ１）＋Ｅ（ｍ２）＝Ｅ（ｍ１＋ｍ２）        （１）
Ｅ（ｍ１）×Ｅ（ｍ２）＝Ｅ（ｍ１×ｍ２）        （２）
【０００５】
準同型暗号方式を用いれば、暗号文同士の加算や乗算により、暗号文を復号することなく、加算や乗算を行った演算結果の暗号文を得ることができる。この準同型暗号の性質は、例えば、電子投票や電子現金などの分野において有用である。
【０００６】
例えば、Additive El Gamal暗号方式とPaillier暗号方式は、いずれも加算に関して準同型性を持ち、式（１）を満たす。また、ＲＳＡ暗号方式（Rivest-Shamir-Adleman cryptography）は、乗算に関して準同型性を持ち、式（２）を満たす。
【０００７】
近年さらに、加算と乗算の双方に関して準同型な暗号方式（つまり式（１）と式（２）の双方を満たす暗号方式）がGentryにより提案されている。そして、加算と乗算の双方に関して準同型な暗号方式に関しては、理論的提案だけでなく、具体的な実装のための提案もなされている。
【０００８】
例えば、準同型暗号方式に関して提案されている、ある鍵生成装置は、任意値生成部と暗号鍵（cryptographic key）生成部を有する。任意値生成部は、絶対値が所定値以上となるｎ個（ｎは正の整数）の任意値λｉ（ｉ＝０，…，ｎ−１）を生成する。暗号鍵生成部は、ｎ個の任意値λｉ（ｉ＝０，…，ｎ−１）の離散フーリエ変換結果に対応するｎ個の要素をｖｉ（ｉ＝０，…，ｎ−１）とした場合における、ｎ×ｎの巡回行列ｒｏｔ（ｖ）に対して定まるｎ×ｎの行列を、準同型暗号方式の暗号鍵として生成する。
【０００９】
ところで、データを暗号化したままで操作することが可能な演算の種類という観点から、準同型暗号方式における暗号化スキームを分類すると、以下の３種類がある。
・ＨＥ（Homomorphic Encryption）スキーム
・ＳＨＥ（Somewhat Homomorphic Encryption）スキーム
・ＦＨＥ（Fully Homomorphic Encryption）スキーム
【００１０】
ＨＥスキームの例は、上述のAdditive El Gamal暗号方式やPaillier暗号方式などである。ＨＥスキームの暗号方式では、１種類の演算（例えば、加算または乗算）についてのみ、データを暗号化したままで処理することが可能である。ＨＥスキームの暗号方式では、鍵生成、暗号化、復号などの処理を高速に実行することが可能である。
【００１１】
ＳＨＥスキームの暗号方式では、加算とＮ回の乗算を、データを暗号化したままで行うことが可能である。ＳＨＥスキームの暗号方式では、鍵生成、暗号化、復号などの処理をやや高速に実行することが可能である。
【００１２】
ＦＨＥスキームの暗号方式では、任意の種類の演算を、データを暗号化したままで行うことが可能である。しかし、ＦＨＥスキームの暗号方式における鍵生成、暗号化、復号などの処理は非常に低速である。
【００１３】
したがって、複雑な処理を高速に行うためには、ＳＨＥスキームが有利である。また、集合｛０，１｝を平文空間とするＳＨＥスキームだけでなく、集合｛０，１，…，ｓ−１｝を平文空間とするＳＨＥスキーム（すなわち、平文空間が拡張されたＳＨＥスキーム）も提案されている。
【先行技術文献】
【特許文献】
【００１４】
【特許文献１】特開２０１１−１４５５１２号公報
【非特許文献】
【００１５】
【非特許文献１】Craig Gentry, "Fully Homomorphic Encryption Using Ideal Lattices", STOC (Symposium on Theory of Computing) 2009, pp. 169-178, 2009.
【非特許文献２】Craig Gentry and Shai Halevi, "Implementing Gentry's Fully-Homomorphic Encryption Scheme", EUROCRYPT 2011, LNCS (Lecture Notes in Computer Science) 6632, pp. 129-148, 2011.
【非特許文献３】安田雅哉、矢嶋純、下山武司、小暮淳「複数企業が持つ購買履歴データのクラウド秘匿集計」(Secret totalization of purchase histories of companies in cloud) SCIS 2012 (Symposium on Cryptography and Information Security), 3D2-5.
【発明の概要】
【発明が解決しようとする課題】
【００１６】
平文空間が０以上（ｓ−１）以下の整数に拡張された準同型暗号方式では、復号の際にベクトルと行列の乗算が２回行われる。したがって、ベクトルの要素数が多い場合、復号の計算量（computational complexity）も大きく、復号には時間がかかる。
【００１７】
本発明は、１つの側面では、平文空間が拡張された準同型暗号方式において復号を高速化することを目的とする。
【課題を解決するための手段】
【００１８】
一態様による復号方法によれば、コンピュータが、第１要素以外はすべて０のｎ次元ベクトル
2014102398.tif 000003
の入力を受け取るか、または、当該ベクトル
2014102398.tif 000004
の第１要素である値ｃの入力を受け取る。前記ベクトル
2014102398.tif 000005
は、以下のいずれかである。
・ｎ個の整数ｖ０，…，ｖｎ−１を使って準同型暗号方式の秘密鍵として定義されるｎ次正則行列
2014102398.tif 000006
に対応する公開鍵として、前記行列Ｖのエルミート標準形である行列Ｂを用いて、０以上ｓ未満の整数である平文を暗号化した暗号文。
・各々が０以上ｓ未満の整数である複数の平文を、前記行列Ｂを用いてそれぞれ暗号化して得られる複数の暗号文に対して、当該複数の暗号文を復号せずにある演算を行った結果である暗号文。
【００１９】
前記復号方法によれば、前記コンピュータは、さらに、前記行列Ｂの行列式ｄと前記行列Ｖの逆行列Ｖ−１により定義される行列Ｗ＝ｄＶ−１の要素のうちでｓと互いに素な要素ｗを取得する。また、前記コンピュータは、法ｓのもとでのｗの逆数ｗ−１を取得する。
【００２０】
そして、前記コンピュータは、ｃ×ｗ  ｍｏｄ  ｄを範囲［−ｄ／２，ｄ／２）に含まれるように調整した値［ｃ×ｗ］ｄを用いて、ｂ＝［ｃ×ｗ］ｄ×ｗ−１  ｍｏｄ  ｓを計算する。
【００２１】
さらに、前記コンピュータは、計算した値ｂを、入力された前記ベクトル
2014102398.tif 000007
または入力された前記値ｃに対応する平文として、出力する。
【発明の効果】
【００２２】
上記の復号方法によれば、平文空間が拡張された準同型暗号方式において復号が高速化される。
【図面の簡単な説明】
【００２３】
【図１】第１実施形態の復号方法のフローチャートである。
【図２】コンピュータのハードウェア構成図である。
【図３】第３比較例の復号装置のブロック構成図である。
【図４】第３比較例の復号方法のフローチャート（その１）である。
【図５】第３比較例の復号方法のフローチャート（その２）である。
【図６】第３比較例の復号方法のフローチャート（その３）である。
【図７】第２実施形態の情報処理装置のブロック構成図である。
【図８】第２実施形態の情報処理装置が行う処理のフローチャート（その１）である。
【図９】第２実施形態の情報処理装置が行う処理のフローチャート（その２）である。
【図１０】第２実施形態の情報処理装置が行う処理のフローチャート（その３）である。
【図１１】第２実施形態と第３実施形態に共通の復号処理のフローチャートである。
【図１２】第３実施形態の復号装置のブロック構成図である。
【発明を実施するための形態】
【００２４】
以下、実施形態について、図面を参照しながら詳細に説明する。具体的には、まず、図１と２を参照して第１実施形態について説明する。その後、３つの比較例について説明する。このうち第３比較例については、図３〜６も参照する。３つの比較例について説明した後で、これらの比較例に比べた第１実施形態の利点と、第１実施形態の数学的背景についても説明する。
【００２５】
その後、第２実施形態について図７〜１１を参照して説明する。なお、図１１は、第２実施形態と第３実施形態に共通の処理を示す。第３実施形態については、図１１〜１２を参照して説明する。最後に、その他の変形例についても説明する。
【００２６】
図１は、第１実施形態の復号方法のフローチャートである。図１の復号方法を実行するコンピュータは、ステップＳ１で、以下のいずれかの入力を受け取る。
・第１要素以外はすべて０のｎ次元ベクトル
2014102398.tif 000008
。
・ベクトル
2014102398.tif 000009
の第１要素である値ｃ。
【００２７】
ベクトル
2014102398.tif 000010
において第１要素以外の要素はすべて０なので、ベクトル
2014102398.tif 000011
の次元ｎが既知のとき、ベクトル
2014102398.tif 000012
をスカラｃと見なすことができる。よって、ステップＳ１でコンピュータは、ベクトル
2014102398.tif 000013
の入力を受け取ってもよいし、値ｃの入力を受け取ってもよい。
【００２８】
また、コンピュータは、当該コンピュータが有する入力装置（例えばキーボード、ポインティングデバイス、カメラなど）を介してベクトル
2014102398.tif 000014
または値ｃを受け取ってもよい。コンピュータは、ネットワークを介して他の装置からベクトル
2014102398.tif 000015
または値ｃを受け取ってもよい。
【００２９】
ベクトル
2014102398.tif 000016
は、より具体的には、０以上ｓ未満の整数である平文に対応する暗号文であってもよい（ただしｓは２以上の所定の整数）。つまり、ある１つの平文を暗号化することによって得られた暗号文を復号するために、コンピュータが図１の復号方法を実行してもよい。
【００３０】
あるいは、ベクトル
2014102398.tif 000017
は、各々が０以上ｓ未満の整数である複数の平文を、それぞれ暗号化して得られる複数の暗号文に対して、当該複数の暗号文を復号せずにある演算を行った結果であるような、１つの暗号文であってもよい。当該「ある演算」は、例えば、秘匿集計のために行われる演算であってもよい。つまり、個々のデータが暗号化された状態で行われた集計の結果を復号するために、コンピュータが図１の復号方法を実行してもよい。
【００３１】
第１実施形態における暗号化スキームは、ＳＨＥスキームである。よって、上記の「ある演算」は、具体的には以下のいずれかである（ただしＮは１以上の所定の定数）。
・１回以上の加算。
・１回以上Ｎ回以下の乗算。
・１回以上の加算と、１回以上Ｎ回以下の乗算との組み合わせ。
【００３２】
また、第１実施形態では、ｎ個の整数ｖ０，…，ｖｎ−１を使って式（３）のように定義されるｎ次正則行列（n×n invertible matrix）Ｖが、準同型暗号方式の秘密鍵として使われる。
【数１】
2014102398.tif 000018
【００３３】
秘密鍵Ｖに対応する公開鍵としては、行列Ｖのエルミート標準形（Hermite Normal Form; HNF）である行列Ｂが使われる。エルミート標準形とは、整数行列に対して整数上の行基本変形（elementary row operations）を施して得られる、下三角行列または上三角行列である。エルミート標準形が効率的に計算可能であることはよく知られている（例えば、P. Domich, R. Kannan and L. Trotter, "Hermite normal form computation using modulo determinant arithmetic", Math. Oper. Research 12:50-59, 1987などを参照）。
【００３４】
以上のような公開鍵Ｂが使われるので、ベクトル
2014102398.tif 000019
は、より具体的には、以下のいずれかである。
・０以上ｓ未満の整数である平文を、行列Ｂを用いて暗号化することで得られる暗号文。
・各々が０以上ｓ未満の整数である複数の平文を、行列Ｂを用いてそれぞれ暗号化することで得られる複数の暗号文に対して、当該複数の暗号文を復号せずにある演算を行った結果として得られる、１つの暗号文。
【００３５】
なおここで、ｓは上記のとおり２以上の所定の整数であり、ｓにより平文空間が規定される。すなわち、平文空間は集合｛０，１，…，ｓ−１｝である。
【００３６】
そして、以上のごときステップＳ１の次に、ステップＳ２において、コンピュータは、行列Ｂの行列式（determinant）ｄと行列Ｖの逆行列Ｖ−１により定義される行列Ｗ＝ｄＶ−１の要素のうちで、平文空間サイズｓと互いに素な（coprime to s）要素ｗを取得する。定義より、行列Ｗはｎ次正方行列（n×n square matrix）である。
【００３７】
例えば、コンピュータは、ステップＳ２において、行列Ｂから行列式ｄを取得し、行列Ｖから逆行列Ｖ−１を計算し、行列式ｄと逆行列Ｖ−１から行列Ｗを計算してもよい。なお、詳しくは後述するとおり、行列Ｂはある特定の形式なので、行列Ｂの行列式ｄは行列Ｂの第（１，１）要素に等しい。よって、コンピュータは、行列Ｂから容易に行列式ｄを取得することができる。そして、コンピュータは、以上のようにして計算した行列Ｗのｎ×ｎ個の要素の中から、平文空間サイズｓと互いに素な要素を探してもよい。
【００３８】
なお、証明は省略するが、後述の数値例からも理解されるように、行列Ｗには規則性がある。なぜなら、行列Ｖに式（３）のような規則性があるからである。
具体的には、行列Ｗの２行目からｎ行目における各要素の値は、行列Ｗの１行目のいずれかの列の要素の値と同じであるか、または、１行目のいずれかの列の要素の値の−１倍である。よって、コンピュータは、行列Ｗのｎ×ｎ個の要素すべてを調べる必要はない。
【００３９】
コンピュータは、行列Ｗ内の任意の１行のｎ個の要素の中から、所定の整数ｓと互いに素な要素を探すだけで十分である。もちろん、コンピュータは、行列Ｗ内の任意の１列のｎ個の要素の中から、所定の整数ｓと互いに素な要素を探すのでもよい。
【００４０】
よって、コンピュータは、必ずしも上記のように行列式ｄと逆行列Ｖ−１から行列Ｗを計算する必要はない。つまり、コンピュータは、行列Ｗ中の少なくとも１行のｎ個の要素を計算し、計算したｎ個の要素の中から、所定の定数ｓと互いに素な要素を探すだけでも十分である。あるいは、コンピュータは、行列Ｗ中の少なくとも１列のｎ個の要素を計算し、計算したｎ個の要素の中から、所定の定数ｓと互いに素な要素を探すだけでも十分である。
【００４１】
いずれにせよ、コンピュータは、探索の結果として見つかった要素を、上記要素ｗとして取得してもよい。例えば、図１の処理を実行するコンピュータ自体が、秘密鍵Ｖと公開鍵Ｂを生成する鍵生成装置である場合、コンピュータは、以上のような計算と探索により要素ｗを取得してもよい。
【００４２】
また、図１の処理を実行するコンピュータが鍵生成装置でない場合にも、コンピュータは、探索により要素ｗを取得してもよい。例えば、コンピュータは、鍵生成装置から、暗号化されたセキュアな通信路を介して、秘密鍵Ｖを受け取り、受け取った秘密鍵Ｖに基づいて、行列Ｗを計算し、上記のような探索を実行してもよい。すると、コンピュータは、探索の結果として要素ｗを取得することができる。
【００４３】
別の例として、コンピュータは、ステップＳ２において、所定の整数ｓと互いに素な要素ｗを他の装置から受信することにより、要素ｗを取得してもよい。例えば、コンピュータは、秘密鍵Ｖと公開鍵Ｂを生成する鍵生成装置とは別の装置であってもよい。この場合、コンピュータは、暗号化されたセキュアな通信路を介して鍵生成装置と接続されていてもよく、暗号化されたセキュアな通信路を介して鍵生成装置から要素ｗを受信してもよい。
【００４４】
また、図１は１回の復号に対応する。しかし、もちろん、図１の処理を実行するコンピュータは、新たな暗号文ベクトル
2014102398.tif 000020
（またはその第１要素の値ｃ）を受け取るたびに、復号を行ってもよい。
【００４５】
その場合、コンピュータは、１回目の復号におけるステップＳ２で、計算と探索により要素ｗを取得し、取得した要素ｗを記憶装置に記憶してもよい。すると、コンピュータは、２回目以降の復号におけるステップＳ２では、単に記憶装置から要素ｗを読み出すだけで、要素ｗを取得することができる。
【００４６】
同様に、コンピュータは、１回目の復号におけるステップＳ２で、他の装置からの受信により要素ｗを取得し、取得した要素ｗを記憶装置に記憶してもよい。すると、コンピュータは、２回目以降の復号におけるステップＳ２では、単に記憶装置から要素ｗを読み出すだけで、要素ｗを取得することができる。
【００４７】
もちろん、コンピュータは、１回目の復号に先立って、予め計算と探索により要素ｗを取得し、取得した要素ｗを記憶装置に記憶しておいてもよい。同様に、コンピュータは、１回目の復号に先立って、予め他の装置からの受信により要素ｗを取得し、取得した要素ｗを記憶装置に記憶してもよい。すると、コンピュータは、１回目の復号におけるステップＳ２でも、単に記憶装置から要素ｗを読み出すだけで、要素ｗを取得することができる。
【００４８】
いずれにせよ、コンピュータは、ステップＳ２で所定の整数ｓと互いに素な要素ｗを取得する。そして、コンピュータは、ステップＳ３で、法ｓのもとでのｗの逆数ｗ−１（inverse w-1 of w modulo s）を取得する。
【００４９】
例えば、コンピュータは、ステップＳ３において、ステップＳ２で取得した要素ｗから逆数ｗ−１を計算してもよい。例えば、コンピュータは、整数集合を探索することで逆数ｗ−１を取得してもよい。
【００５０】
別の例として、コンピュータは、ステップＳ３において、他の装置（例えば鍵生成装置）から逆数ｗ−１を受信することにより、逆数ｗ−１を取得してもよい。
コンピュータは、１回目の復号におけるステップＳ３で逆数ｗ−１を計算または受信し、計算または受信した逆数ｗ−１を記憶装置に記憶してもよい。すると、コンピュータは、２回目以降の復号におけるステップＳ３では、単に記憶装置から逆数ｗ−１を読み出すだけで、逆数ｗ−１を取得することができる。
【００５１】
もちろん、コンピュータは、１回目の復号に先立って、予め計算または受信により逆数ｗ−１を取得し、取得した逆数ｗ−１を記憶装置に記憶してもよい。すると、コンピュータは、１回目の復号におけるステップＳ３でも、単に記憶装置から逆数ｗ−１を読み出すだけで、逆数ｗ−１を取得することができる。
【００５２】
いずれにせよ、コンピュータは、ステップＳ３で逆数ｗ−１を取得する。なお、上記の要素ｗを取得する方法と逆数ｗ−１を取得する方法によっては、ステップＳ２とステップＳ３の実行順序が逆であってもよい。
【００５３】
また、平文空間サイズｓの値は任意に定められていてよいが、平文空間サイズｓは素数または２の冪乗数であることが好ましい。理由は以下のとおりである。
【００５４】
平文空間サイズｓが素数の場合、２以上の任意の整数は、平文空間サイズｓの倍数でない限り平文空間サイズｓと互いに素である。よって、平文空間サイズｓが素数の場合、平文空間サイズｓと互いに素な要素を行列Ｗの要素の中から探す処理は、「平文空間サイズｓの倍数でない要素を探す」という低負荷の処理である。
【００５５】
また、平文空間サイズｓが２の冪乗数の場合、任意の奇数は平文空間サイズｓと互いに素である。よって、平文空間サイズｓが２の冪乗数の場合、平文空間サイズｓと互いに素な要素を行列Ｗの要素の中から探す処理は、「奇数の要素を探す」というきわめて低負荷の処理である。
【００５６】
以上のように、処理負荷を軽減する効果があるので、平文空間サイズｓは素数または２の冪乗数であることが好ましい。しかし、もちろん、素数でもなく２の冪乗数でもない値が、平文空間サイズｓとして指定されてもよい。
【００５７】
次に、ステップＳ４でコンピュータは、式（４）の値ｂを計算する。
ｂ＝［ｃ×ｗ］ｄ×ｗ−１  ｍｏｄ  ｓ        （４）
【００５８】
なお、式（４）中の“［ｃ×ｗ］ｄ”は、（ｃ×ｗ  ｍｏｄ  ｄ）を、範囲（interval）［−ｄ／２，ｄ／２）に含まれるように調整した値である。なお、“［−ｄ／２，ｄ／２）”は、−ｄ／２以上ｄ／２未満の範囲を示す。すなわち、任意の整数ｚに対して、“［ｚ］ｄ”は、式（５）のように定義される。
【数２】
2014102398.tif 000021
【００５９】
より具体的には、ステップＳ４の処理は、以下の演算を含む処理であってもよい。
・値ｃと値ｗとの乗算。
・法ｄによる剰余演算（modulo operation by d）。
・値［ｃ×ｗ］ｄと逆数ｗ−１との乗算。
・法ｓによる剰余演算。
【００６０】
別の例として、ステップＳ４の処理は、以下の演算を含む処理であってもよい。
・法ｄによるモンゴメリ乗算剰余演算（Montgomery modular multiplication）。
・法ｓによるモンゴメリ乗算剰余演算。
【００６１】
最後に、ステップＳ５でコンピュータは、ステップＳ４で計算した値ｂを、入力されたベクトル
2014102398.tif 000022
または入力された値ｃに対応する平文として、出力する。ステップＳ５での出力は、具体的には、例えば以下のような処理のいずれであってもよい。
・値ｂを、コンピュータの不揮発性記憶装置に書き込む処理。
・値ｂをディスプレイなどの出力装置に表示する処理。
・値ｂを他の装置に送信する処理。
・値ｂを用いた処理を行うためのプログラムモジュールに割り当てられた記憶領域(例えば主記憶上の記憶領域）に、値ｂを記憶する処理。
【００６２】
なお、複数の暗号文に対してある演算を行った結果としての１つの暗号文を復号することで平文ｂが得られた場合においては、得られた平文ｂ自体を秘密にする必要がない場合もあり得る。その場合、コンピュータは、暗号化されていないネットワークを介して他の装置に平文ｂを送信してもよい。もちろん、コンピュータは、暗号化されたセキュアな通信路を介して他の装置に平文ｂを送信することで、平文ｂを秘密状態に保ちながら平文ｂを他の装置に出力してもよい。
【００６３】
なお、式（４）の定義より、値ｂは０以上（ｓ−１）以下の整数である。つまり、値ｂは平文空間に含まれる。また、以上のようにして得られた値ｂが、単に平文空間に含まれるだけでなく、実際に暗号文ベクトル
2014102398.tif 000023
に対応する平文であることについての説明は、後述する。
【００６４】
ところで、図１の処理を実行するコンピュータは、具体的には図２のコンピュータ１００であってもよい。コンピュータ１００は、プロセッサ１０１と、メモリ１０２と、通信インタフェイス１０３と、入力装置１０４と、出力装置１０５と、不揮発性記憶装置１０６を有する。また、コンピュータ１００は、記憶媒体１１０の駆動装置１０７を有する。コンピュータ１００内の各コンポーネントは、バス１０８を介して互いに接続されている。
【００６５】
また、コンピュータ１００はネットワーク１２０に接続されている。ネットワーク１２０は、例えば、ＬＡＮ（Local Area Network）、ＷＡＮ（Wide Area Network）、インターネット、またはその組み合わせである。
【００６６】
ネットワーク１２０には、他のコンピュータ１３０、１４０、および１５０がさらに接続されていてもよい。コンピュータ１３０、１４０、および１５０も、それぞれコンピュータ１００と同様に構成されていてもよい。
【００６７】
ネットワーク１２０には、プログラム提供者１６０がさらに接続されていてもよい。プログラム提供者１６０もコンピュータである。プログラム提供者１６０も、コンピュータ１００と同様に構成されていてもよい。
【００６８】
図２には１つのプロセッサ１０１のみが図示されているが、コンピュータ１００は、複数のプロセッサ１０１を有していてもよい。また、プロセッサ１０１は、シングルコアプロセッサでもよいしマルチコアプロセッサでもよい。
【００６９】
プロセッサ１０１は、具体的には、プログラムを実行する汎用のＣＰＵ（Central Processing Unit）でもよいし、ＡＳＩＣ（Application-Specific Integrated Circuit）などの専用プロセッサであってもよい。また、汎用のＣＰＵと専用プロセッサの双方をコンピュータ１００が有していてもよい。例えば、専用プロセッサの一例として、コンピュータ１００は、多倍長整数（big number integers）同士の乗算回路を有していてもよい。
【００７０】
メモリ１０２は、例えばＤＲＡＭ（Dynamic Random Access Memory）であってもよい。プロセッサ１０１は、プログラムをメモリ１０２にロードし、メモリ１０２をワーキングエリアとしても使いながらプログラムを実行してもよい。
【００７１】
通信インタフェイス１０３は、例えば、有線ＬＡＮインタフェイス回路、無線ＬＡＮインタフェイス回路、またはその組み合わせである。通信インタフェイス１０３は、具体的には、外付けのＮＩＣ（Network Interface Card）でもよいし、オンボード型のネットワークインタフェイスコントローラでもよい。例えば、通信インタフェイス１０３は、物理層の処理を行う「ＰＨＹチップ」と呼ばれる回路と、ＭＡＣ（Media Access Control）副層の処理を行う「ＭＡＣチップ」と呼ばれる回路を含んでいてもよい。
【００７２】
入力装置１０４は、例えば、キーボード、ポインティングデバイス、マイク、カメラ、またはそれらの２つ以上の組み合わせである。ポインティングデバイスは、例えば、マウスでもよいしタッチパッドでもよいしタッチスクリーンでもよい。出力装置１０５は、ディスプレイ、スピーカ、またはその組み合わせである。ディスプレイはタッチスクリーンであってもよい。
【００７３】
不揮発性記憶装置１０６は、例えば、ＨＤＤ（Hard Disk Drive）、ＳＳＤ（Solid-State Drive）、またはその組み合わせである。さらにＲＯＭ（Read-Only Memory）が不揮発性記憶装置１０６として使われてもよい。
【００７４】
記憶媒体１１０の例は、ＣＤ（Compact Disc）やＤＶＤ（Digital Versatile Disk）などの光ディスク、光磁気ディスク、磁気ディスク、フラッシュメモリなどの半導体メモリカードなどである。駆動装置１０７は、具体的には、光ディスク駆動装置、光磁気ディスク駆動装置、または磁気ディスク駆動装置であってもよいし、メモリカード用のリーダおよびライタであってもよい。
【００７５】
ところで、上記のようにプロセッサ１０１がプログラムを実行するＣＰＵである場合、当該プログラムは、予め不揮発性記憶装置１０６にインストールされていてもよい。あるいは、プログラムは、記憶媒体１１０に格納されて提供され、記憶媒体１１０から駆動装置１０７により読み取られて不揮発性記憶装置１０６にコピーされ、その後、メモリ１０２にロードされてもよい。または、プログラムは、ネットワーク１２０上のプログラム提供者１６０から、ネットワーク１２０と通信インタフェイス１０３を介してコンピュータ１００にダウンロードされ、コンピュータ１００にインストールされてもよい。
【００７６】
なお、メモリ１０２、不揮発性記憶装置１０６、記憶媒体１１０は、いずれも、有形の（tangible）記憶媒体の例である。これらの有形の記憶媒体は、信号搬送波のような一時的な（transitory）媒体ではない。
【００７７】
ところで、暗号文であるベクトル
2014102398.tif 000024
またはその第１要素ｃを受け取って、図１の復号処理により平文ｂを得る装置は、復号装置である。また、秘密鍵（つまり行列Ｖ）と公開鍵（つまり行列Ｂ）を生成する装置は、鍵生成装置である。図２においてコンピュータ１００に着目すると、以下の３つの場合があり得る。
・コンピュータ１００が、図１のフローチャートにしたがって復号装置として動作するが、鍵生成装置としては動作しない第１の場合。
・コンピュータ１００が、鍵生成装置として動作するとともに、図１のフローチャートにしたがって復号装置としても動作する第２の場合。
・コンピュータ１００が、鍵生成装置として動作するが、復号装置としては動作しない第３の場合。
【００７８】
上記第１の場合、例えばコンピュータ１３０が鍵生成装置であってもよい。第１の場合において、コンピュータ１００は、鍵生成装置としてのコンピュータ１３０から、ネットワーク１２０を介して、復号に使うための情報を受信してもよい。この場合、ネットワーク１２０を介したコンピュータ１００と１３０の間の通信は、暗号化されたセキュアな通信であるものとする。
【００７９】
復号装置としてのコンピュータ１００は、図１のステップＳ２〜Ｓ４に示すように、行列Ｗ中の要素ｗとその逆数ｗ−１の双方を復号に使う。しかし、復号装置としてのコンピュータ１００は、要素ｗとその逆数ｗ−１の少なくとも一方を鍵生成装置としてのコンピュータ１３０から受信するだけで十分である。なぜなら、要素ｗとその逆数ｗ−１の任意の一方から他方が算出可能だからである。つまり、復号装置としてのコンピュータ１００は、要素ｗとその逆数ｗ−１の一方をコンピュータ１３０からの受信により取得し、他方を計算により取得してもよい。
【００８０】
また、要素ｗは行列Ｗから探し出すことが可能である。よって、復号装置としてのコンピュータ１００は、復号に使うための情報として、要素ｗとその逆数ｗ−１ではなく、行列Ｗを、鍵生成装置としてのコンピュータ１３０から受信してもよい。
【００８１】
もちろん、行列Ｗは、秘密鍵Ｖの逆行列Ｖ−１と、行列Ｂの行列式ｄから算出することが可能である。そして、逆行列Ｖ−１は行列Ｖから算出することが可能であり、行列Ｖは、ｎ個の整数ｖ０，…，ｖｎ−１により規定される。また、行列式ｄは行列Ｂから取得することが可能であり、行列Ｂは行列Ｖから算出することが可能である。
【００８２】
よって、復号装置としてのコンピュータ１００は、復号に使うための情報として、鍵生成装置としてのコンピュータ１３０から、逆行列Ｖ−１、行列Ｖ、または、ｎ個の整数ｖ０，…，ｖｎ−１の組（tuple）のいずれかを受信するだけでもよい。復号装置としてのコンピュータ１００は、付加的に、鍵生成装置としてのコンピュータ１３０から、行列Ｂまたはその行列式ｄを受信してもよい。
【００８３】
復号装置としてのコンピュータ１００は、復号に使うために予めコンピュータ１３０から受信した情報を、不揮発性記憶装置１０６に記憶してもよく、復号の際に不揮発性記憶装置１０６を参照して情報を読み出してもよい。不揮発性記憶装置１０６の少なくとも一部は、耐タンパ性の記憶装置であってもよい。例えば、コンピュータ１００は、図１のステップＳ２で不揮発性記憶装置１０６から要素ｗを取得してもよく、ステップＳ３で不揮発性記憶装置１０６から逆数ｗ−１を取得してもよい。
【００８４】
ところで、復号装置としてのコンピュータ１００は、暗号文ベクトル
2014102398.tif 000025
またはその第１要素の値ｃを、具体的にはコンピュータ１４０からネットワーク１２０を介して受け取ってもよい。あるいは、コンピュータ１００は、ベクトル
2014102398.tif 000026
または値ｃを、コンピュータ１００自体の入力装置１０４を介して受け取ってもよい。換言すれば、復号装置としてのコンピュータ１００において、ベクトル
2014102398.tif 000027
または値ｃの入力を受け取る暗号文受け取り部は、通信インタフェイス１０３により実現されてもよいし、入力装置１０４により実現されてもよい。
【００８５】
また、上記の要素ｗを取得する第１の取得部は、プロセッサ１０１により実現されてもよいし、通信インタフェイス１０３により実現されてもよい。
【００８６】
例えば、プロセッサ１０１は、鍵生成装置としてのコンピュータ１３０から受信された情報を用いた計算により、要素ｗを取得してもよい。それにより、プロセッサ１０１が第１の取得部として動作してもよい。
【００８７】
あるいは、通信インタフェイス１０３は、鍵生成装置としてのコンピュータ１３０から、ネットワーク１２０を介して要素ｗを受信することで要素ｗを取得してもよい。それにより、通信インタフェイス１０３が第１の取得部として動作してもよい。
【００８８】
もちろん、要素ｗは、一旦計算または受信された後で不揮発性記憶装置１０６に記憶されてもよい。この場合、プロセッサ１０１は、要素ｗを不揮発性記憶装置１０６から読み出すことで、要素ｗを取得してもよい。それにより、プロセッサ１０１が第１の取得部として動作してもよい。
【００８９】
同様に、要素ｗの逆数ｗ−１を取得する第２の取得部も、プロセッサ１０１により実現されてもよいし、通信インタフェイス１０３により実現されてもよい。
【００９０】
例えば、プロセッサ１０１は、鍵生成装置としてのコンピュータ１３０から受信した情報を用いた計算により、逆数ｗ−１を取得してもよい。それにより、プロセッサ１０１が第２の取得部として動作してもよい。
【００９１】
あるいは、通信インタフェイス１０３は、鍵生成装置としてのコンピュータ１３０から、ネットワーク１２０を介して逆数ｗ−１を受信することで逆数ｗ−１を取得してもよい。それにより、通信インタフェイス１０３が第２の取得部として動作してもよい。
【００９２】
もちろん、逆数ｗ−１は、一旦計算または受信された後で不揮発性記憶装置１０６に記憶されてもよい。この場合、プロセッサ１０１は、逆数ｗ−１を不揮発性記憶装置１０６から読み出すことで、逆数ｗ−１を取得してもよい。それにより、プロセッサ１０１が第２の取得部として動作してもよい。
【００９３】
なお、復号装置としてのコンピュータ１００において、図１のステップＳ４のように平文ｂを計算する計算部は、プロセッサ１０１により実現される。
【００９４】
また、平文ｂを出力する平文出力部は、例えば、平文を表示する出力装置１０５により実現されてもよいし、通信インタフェイス１０３により実現されてもよいし、不揮発性記憶装置１０６へ平文ｂを書き出すプロセッサ１０１により実現されてもよい。
【００９５】
ところで、上記の第２の場合（つまり、コンピュータ１００が復号装置として動作するだけでなく鍵生成装置としても動作する場合）にも、第１の場合と同様、復号装置内の暗号文受け取り部は、通信インタフェイス１０３または入力装置１０４により実現されてもよい。そして、復号装置内の計算部も、第１の場合と同様に、プロセッサ１０１により実現されてもよい。また、復号装置内の平文出力部も、第１の場合と同様に、出力装置１０５、通信インタフェイス１０３、またはプロセッサ１０１により実現されてもよい。
【００９６】
なお、コンピュータ１００が鍵生成装置としても動作する場合、復号装置としてのコンピュータ１００が復号に使う情報は、コンピュータ１００自身が鍵生成装置として生成した情報から導出される情報である。そのため、コンピュータ１００が鍵生成装置としても動作する第２の場合においては、第１と第２の取得部は、通信インタフェイス１０３ではなく、プロセッサ１０１により実現される。
【００９７】
また、上記の第２の場合または第３の場合において、鍵生成装置としてのコンピュータ１００は、秘密鍵Ｖを規定するｎ個の整数ｖ０，…，ｖｎ−１を生成する生成部を有する。さらに、鍵生成装置としてのコンピュータ１００は、以下の３つの条件が成り立つ（hold true）か否かを判定する判定部も有する。
・第１の条件：生成されたｎ個の整数ｖ０，…，ｖｎ−１により定義されるｎ次正方行列Ｖに、逆行列Ｖ−１が存在する。
・第２の条件：式（６）のような特定の形式のエルミート標準形の行列Ｂが、行列Ｖから導出される。
・第３の条件：行列Ｂの行列式ｄと行列Ｖの逆行列Ｖ−１により定義される行列Ｗ＝ｄＶ−１のｎ×ｎ個の要素の中に、所定の正整数（つまり平文空間サイズ）ｓと互いに素な要素が存在する。
【数３】
2014102398.tif 000028
【００９８】
生成部と判定部は、いずれも、具体的にはプロセッサ１０１により実現される。また、式（６）は以下のことを示す。
・１＜ｊ≦ｎなるすべてのｊについて、行列Ｂの第（１，ｊ）要素は０である。
・１＜ｉ≦ｎかつ１＜ｊ≦ｎかつｉ≠ｊなるすべてのｉとｊについて、行列Ｂの第（ｉ，ｊ）要素は０である。
・１＜ｉ≦ｎなるすべてのｉについて、行列Ｂの第（ｉ，ｉ）要素は１である。
【００９９】
行列Ｂが式（６）の形を持つ場合、行列式の定義から明らかに、行列Ｂの行列式は、行列Ｂの第（１，１）要素に等しい。
【０１００】
さらに、鍵生成装置としてのコンピュータ１００において、生成部としてのプロセッサ１０１は、第１〜第３の条件のすべてが成り立つようなｎ個の整数ｖ０，…，ｖｎ−１が得られるまで、ｎ個の整数ｖ０，…，ｖｎ−１の生成を繰り返す。例えば、プロセッサ１０１は、ｎ個のランダムな整数を上記の整数ｖ０，…，ｖｎ−１として生成してもよい。
【０１０１】
鍵生成装置としてのコンピュータ１００は、さらに、第１〜第３の条件のすべてが成り立つようなｎ個の整数ｖ０，…，ｖｎ−１が得られたら、公開鍵として行列Ｂを出力する公開鍵出力部を有する。公開鍵出力部は、例えば、通信インタフェイス１０３により実現されてもよい。通信インタフェイス１０３は、ネットワーク１２０を介して他の装置（例えばコンピュータ１４０）に行列Ｂを送信することで、公開鍵出力部として動作してもよい。
【０１０２】
公開鍵Ｂは、具体的には、０以上ｓ未満の整数の集合を平文空間とする準同型暗号方式における公開鍵である。つまり、上記の第３の条件における所定の正整数ｓは、平文空間サイズを示す。
【０１０３】
ところで、上記の第３の場合（つまり、コンピュータ１００が鍵生成装置であるが復号装置ではない場合）においては、鍵生成装置としてのコンピュータ１００は、復号に使う情報を復号装置に送信してもよい。例えば、第３の場合における復号装置は、コンピュータ１５０であってもよい。この場合、鍵生成装置としてのコンピュータ１００と復号装置としてのコンピュータ１５０との間のネットワーク１２０を介した通信は、暗号化されたセキュアな通信であるものとする。復号装置が復号に使うための情報として鍵生成装置が復号装置に送信する情報は、第１の場合に関して、コンピュータ１３０からコンピュータ１００への送信を例にして説明したとおりである。
【０１０４】
つまり、第３の場合には、鍵生成装置としてのコンピュータ１００が、復号装置としてのコンピュータ１５０に、要素ｗとその逆数ｗ−１の少なくとも一方を送信してもよい。あるいは、鍵生成装置としてのコンピュータ１００は、行列Ｗを復号装置としてのコンピュータ１５０に送信してもよい。もちろん、鍵生成装置としてのコンピュータ１００は、逆行列Ｖ−１、行列Ｖ、または、ｎ個の整数ｖ０，…，ｖｎ−１の組のいずれかを復号装置としてのコンピュータ１５０に送信するだけでもよい。鍵生成装置としてのコンピュータ１００は、さらに付加的に、行列Ｂまたはその行列式ｄを復号装置としてのコンピュータ１５０に送信してもよい。
【０１０５】
続いて、上述の第１実施形態および後述の第２〜第３実施形態についての理解を助けるため、３つの比較例について説明する。
【０１０６】
第１比較例は、平文空間が集合｛０，１｝の例である。つまり、第１比較例ではｓ＝２である。換言すれば、第１比較例における各平文の長さは１ビットである。
【０１０７】
第１比較例での鍵生成装置は、次元ｎとビット長ｔという２つのパラメタを受け取る。次元ｎとビット長ｔは、いずれも２以上の整数である。
【０１０８】
そして、鍵生成装置は、ｎ個の乱数ｖ０，…，ｖｎ−１を生成する。なお、０≦ｉ≦ｎ−１なる各ｉについて、乱数ｖｉは整数であり、かつ、乱数ｖｉの絶対値｜ｖｉ｜はｔビット以下である。
【０１０９】
鍵生成装置は、生成したｎ個の乱数ｖ０，…，ｖｎ−１により式（３）のように定義される行列Ｖを秘密鍵とする。また、鍵生成装置は、行列Ｖのエルミート標準形である行列Ｂを、秘密鍵Ｖに対応する公開鍵とする。鍵生成装置は、公開鍵Ｂを公開する。
【０１１０】
さて、第１比較例での暗号化装置は、以下のようにして、公開鍵Ｂを用いて１ビットの平文ｂを暗号化する。
【０１１１】
まず、暗号化装置は、各要素が０または１であるｎ次元乱数ベクトル（ノイズベクトルともいう）
2014102398.tif 000029
を選ぶ。以下、乱数ベクトル
2014102398.tif 000030
の各要素を式（７）のように表す。
【数４】
2014102398.tif 000031
【０１１２】
そして、暗号化装置は、乱数ベクトル
2014102398.tif 000032
を用いて、式（８）のベクトル
2014102398.tif 000033
を生成する。以下ではベクトル
2014102398.tif 000034
を「フレッシュ暗号文」（fresh ciphertext）という。
【数５】
2014102398.tif 000035
【０１１３】
なお、式（８）におけるベクトル
2014102398.tif 000036
は、第１要素のみが１で残りの要素がすべて０のｎ次元単位ベクトルである。暗号化装置は、フレッシュ暗号文
2014102398.tif 000037
を用いて、式（９）により、平文ｂに対応する暗号文
2014102398.tif 000038
を生成する。
【数６】
2014102398.tif 000039
【０１１４】
なお、式（９）における“Ｂ−１”は、行列Ｂの逆行列である。
また、任意の有理数ｑに関して、“「ｑ」”は有理数ｑに最も近い整数値を示すものとする。例えば、「１２／５」＝２であり、「１４／５」＝３である。
【０１１５】
演算子“「・」”は、式（９）のように引数がｎ次元ベクトルである場合にも定義される。具体的には、引数がｎ次元ベクトルの場合は、演算子“「・」”による演算結果として、引数ベクトルの第ｉ要素に最も近い整数値を第ｉ要素として持つｎ次元ベクトルが得られる（１≦ｉ≦ｎ）。
【０１１６】
また、第１比較例でも行列Ｂは式（６）の形を持つ。したがって、証明は省略するが、式（９）により得られる暗号文
2014102398.tif 000040
において、第２要素から第ｎ要素はすべて０である。
【０１１７】
さて、第１比較例の復号装置は、秘密鍵Ｖを用いて、以下のようにして暗号文
2014102398.tif 000041
を復号する。
【０１１８】
まず、復号装置は、式（１０）のｎ次元ベクトル
2014102398.tif 000042
を計算する。
【数７】
2014102398.tif 000043
【０１１９】
次に、復号装置は、式（１０）のｎ次元ベクトル
2014102398.tif 000044
の第１要素ａ０’を２で割り、余りを計算する。換言すれば、復号装置は、第１要素ａ０’から最下位ビット（least significant bit; LSB）を復号結果として抽出する。以上のようにして得られた余り（すなわち第１要素ａ０’のＬＳＢ）が、暗号文
2014102398.tif 000045
を復号した結果である。
【０１２０】
以上説明した第１比較例における鍵生成、暗号化、および復号について、以下に数値例を示す。以下の例では、次元ｎが４であり、ビット長ｔが７であるとする。ビット長ｔが７なので、鍵生成装置は、絶対値が１２７（＝２７−１）以下の整数をｎ（＝４）個生成する。例えば、ｖ０＝１１２、ｖ１＝９９、ｖ２＝−１２５、ｖ３＝８１という４つの乱数が得られたとする。
【０１２１】
この場合、秘密鍵Ｖは式（１１）のとおりである。
【数８】
2014102398.tif 000046
【０１２２】
また、鍵生成装置は、行列Ｖから、そのエルミート標準形である行列Ｂを計算する。その結果、式（１２）の行列Ｂが公開鍵として得られる。式（１２）の行列Ｂが式（６）の形であることに注意されたい。
【数９】
2014102398.tif 000047
【０１２３】
続いて、暗号化装置がｂ＝１なる平文を暗号化する処理を説明する。まず、暗号化装置は、４次元乱数ベクトル
2014102398.tif 000048
を生成する。説明の便宜上、式（１３）のような４次元乱数ベクトル
2014102398.tif 000049
が生成されたものとする。
【数１０】
2014102398.tif 000050
【０１２４】
次に、暗号化装置は、得られた４次元乱数ベクトル
2014102398.tif 000051
から、式（８）にしたがって、フレッシュ暗号文
2014102398.tif 000052
を計算する。具体的には、式（１４）のようなフレッシュ暗号文
2014102398.tif 000053
が得られる。
【数１１】
2014102398.tif 000054
【０１２５】
続いて、暗号化装置は、得られたフレッシュ暗号文
2014102398.tif 000055
から、式（９）にしたがって、暗号文
2014102398.tif 000056
を計算する。具体的には、式（１５）のような暗号文
2014102398.tif 000057
が得られる。
【数１２】
2014102398.tif 000058
【０１２６】
そして、暗号文
2014102398.tif 000059
（またはその第１要素）が復号装置に送信される。すると、復号装置は、式（１０）にしたがって４次元ベクトル
2014102398.tif 000060
を計算する。具体的には、式（１６）のような４次元ベクトル
2014102398.tif 000061
が得られる。
【数１３】
2014102398.tif 000062
【０１２７】
すると、復号装置は、４次元ベクトル
2014102398.tif 000063
の第１要素（つまり３という値）を２で割り、余り１を得る。こうして得られた１という値が、復号により得られた値である。以上の数値例では、復号により、ｂ＝１なる元の平文が正しく得られる。
【０１２８】
詳しい説明は省略するが、第１比較例の準同型暗号方式では、式（１４）と式（１６）の計算例が示すように、ベクトル
2014102398.tif 000064
と
2014102398.tif 000065
が一致する。このことは、第１比較例の数学的基盤である整数格子（integer lattice）の性質から導き出されるもので、ベクトル
2014102398.tif 000066
と
2014102398.tif 000067
が一致するので暗号文を復号することができる。
【０１２９】
ところが、第１比較例には、次元ｎが高い場合は特に、式（１０）による復号に時間がかかる（換言すれば復号の処理負荷が高い）という欠点がある。なぜなら、式（１０）に示すとおり、復号においては、ｎ次元ベクトルとｎ×ｎ行列との乗算が２回行われるからである。しかも、ビット長ｔが長い場合、ベクトルの要素と行列の要素との乗算は多倍長演算なので、ますます復号の処理負荷は高い。
【０１３０】
そこで、復号の処理負荷を軽減し、高速に復号を実現することが望ましい。以下に説明する第２比較例は、第１比較例における復号を高速化した例である。第２比較例における鍵生成と暗号化は、第１比較例と同様であるので、説明を省略する。
【０１３１】
第２比較例での復号装置は、暗号文ベクトル
2014102398.tif 000068
の第１要素ｃを用いて、式（１７）により平文ｂを計算する。
ｂ＝［ｃ×ｗ］ｄ  ｍｏｄ  ２        （１７）
【０１３２】
なお、式（１７）におけるｗは、秘密鍵Ｖの逆行列Ｖ−１と、公開鍵Ｂの行列式ｄにより定義される行列Ｗ＝ｄＶ−１の要素のうち、奇数のものである。第２比較例でも公開鍵Ｂは式（６）の形を持つので、公開鍵Ｂの行列式ｄは、行列Ｂの第（１，１）要素に等しい。
【０１３３】
そして、第１実施形態に関して述べたのと同様の理由から、行列Ｗの２行目からｎ行目における各要素の値は、行列Ｗの１行目のいずれかの列の要素の値と同じであるか、または、１行目のいずれかの列の要素の値の−１倍である。よって、式（１７）におけるｗは、行列Ｗの１行目に含まれるいずれかの奇数または当該奇数の−１倍の値である。
【０１３４】
また、式（１７）における“［ｃ×ｗ］ｄ”は、ｃ×ｗ  ｍｏｄ  ｄを範囲［−ｄ／２，ｄ／２）に含まれるように調整した値を示す（詳しくは上述の式（５）を参照）。
【０１３５】
ところで、第１比較例および第２比較例は格子理論に基づいている。そして、式（１０）により得られるｎ次元ベクトル
2014102398.tif 000069
が式（８）のフレッシュ暗号文
2014102398.tif 000070
と等しくなる条件下で、「式（１８）の２つの等号が成り立つ」ということが導き出される。
【数１４】
2014102398.tif 000071
【０１３６】
なお、演算子“［・］ｄ”は、式（１８）のように引数がｎ次元ベクトルの場合にも定義される。具体的には、引数がｎ次元ベクトルの場合、演算子“［・］ｄ”は、引数ベクトルのｎ個の要素にそれぞれ式（５）の演算子“［・］ｄ”を適用することを意味する。したがって、結果としてｎ次元ベクトルが得られる。
【０１３７】
詳しい証明は省略するが、式（１７）は“ｂ＝ａ０’  ｍｏｄ  ２”という式と数学的に等価であり、したがって、式（１７）による復号は正しい。このことは、式（１８）と、暗号文
2014102398.tif 000072
の第２〜第ｎ要素がすべて０であることと、式（８）の定義から導き出される。
【０１３８】
なお、式（１７）から明らかなとおり、第２比較例では復号に際してベクトルと行列の乗算は行われない。式（１７）中の“ｃ×ｗ”は単なるスカラ同士の乗算である。したがって、第２比較例では、復号の処理負荷は第１比較例よりも遥かに低い。換言すれば、第２比較例の復号は第１比較例の復号よりも遥かに高速である。
【０１３９】
ところで、第１比較例と第２比較例のいずれにおいても、平文は１ビットの情報である。１ビットの長さの平文しか利用することができないシステムでは、複雑な情報を表すのに複数の平文が組み合わされ、それぞれの平文が暗号化される。よって、２ビット以上の長さの平文が利用可能なシステムと比べると、例えば集計等の種々の処理が複雑化し、処理時間が長くなってしまう。
【０１４０】
よって、多様な分野への応用のためには、平文空間が拡張されることが望ましい。次に説明する第３比較例は、ｓ＞２の例である。つまり、第３比較例では、第１比較例と比べて平文空間が拡張されている。
【０１４１】
第３比較例における鍵生成（すなわち、秘密鍵としての行列Ｖの生成と、公開鍵としての行列Ｂの生成）は、第１比較例および第２比較例と同様である。よって、鍵生成についての説明は省略する。
【０１４２】
第３比較例の暗号化装置は、第１比較例の暗号化装置と同様に、式（７）のｎ次元乱数ベクトル
2014102398.tif 000073
を生成する。次に、暗号化装置は、式（１９）にしたがってフレッシュ暗号文
2014102398.tif 000074
を生成する。
【数１５】
2014102398.tif 000075
【０１４３】
なお、式（８）と式（１９）を比べると分かるように、式（８）は、式（１９）においてｓ＝２の場合に相当する。
【０１４４】
続いて、暗号化装置は、フレッシュ暗号文
2014102398.tif 000076
を用いて、式（９）により、平文ｂに対応する暗号文
2014102398.tif 000077
を生成する。こうして第３比較例において得られる暗号文
2014102398.tif 000078
においても、第１要素以外はすべて０である。よって、暗号文
2014102398.tif 000079
をその第１要素ｃと見なすこともできる。暗号文
2014102398.tif 000080
とフレッシュ暗号文
2014102398.tif 000081
は１対１に対応する。
【０１４５】
さて、第３比較例の復号装置は、以下のようにして暗号文
2014102398.tif 000082
を復号する。まず、復号装置は、式（１０）のｎ次元ベクトル
2014102398.tif 000083
を計算する。次に、復号装置は、ｎ次元ベクトル
2014102398.tif 000084
の第１要素ａ０’を用いて、式（２０）により平文ｂを計算する。
ｂ＝ａ０’  ｍｏｄ  ｓ      （２０）
【０１４６】
なお、証明は省略するが、第３比較例においても、式（１０）のｎ次元ベクトル
2014102398.tif 000085
は式（１９）のフレッシュ暗号文
2014102398.tif 000086
と一致する。よって、式（２１）が成立する。そのため、式（２０）により正しく平文ｂが得られる。
ａ０’＝ａ０＝ｓ×ｕ０＋ｂ      （２１）
【０１４７】
以上のように、第３比較例では、２ビット以上の長さの平文ｂ（具体的には、０以上（ｓ−１）以下の整数）が利用可能である。しかし、第３比較例での復号は低速である。
【０１４８】
なぜなら、式（１０）から明らかなように、第３比較例の復号においては、ｎ次元ベクトルとｎ×ｎ行列との乗算が２回行われる（換言すれば、スカラ同士の乗算が２×ｎ２回行われる）からである。しかも、ビット長ｔが長い場合、スカラ同士の乗算は多倍長演算なので、ますます復号の処理負荷が高く、したがって、復号にはより長い時間がかかってしまう。
【０１４９】
他方、図１〜２を参照して上述した第１実施形態では、「平文空間が拡張されている」という利点と、「復号の処理負荷が軽いため高速な復号が可能である」という利点が両立している。したがって、第１実施形態は、以上説明した第１〜第３比較例のいずれと比べても有利である。また、後述の第２実施形態と第３実施形態も同様に、第１〜第３比較例のいずれと比べても有利である。
【０１５０】
続いて、第１〜第３実施形態における復号処理の軽減についての理解の助けとするために、第３比較例における復号の詳細について、図３〜６を参照して説明する。
【０１５１】
図３は、第３比較例の復号装置のブロック構成図である。図３に示す復号装置２００は、入出力部２０１と、制御部２０２と、逆行列計算部２０３と、フレッシュ暗号文計算部２０４と、ベクトル・行列乗算部２０５と、スカラ乗算部２０６と、丸め部２０７と、減算部２０８と、モジュロ演算部２０９を有する。
【０１５２】
入出力部２０１は、復号装置２００への入力インタフェイスとして動作し、復号装置２００からの出力インタフェイスとしても動作する。制御部２０２は、入出力部２０１を介して暗号文
2014102398.tif 000087
と秘密鍵Ｖと次元ｎについての入力を受け取り、復号処理を制御し、復号の結果として得られる平文ｂを入出力部２０１に出力する。入出力部２０１と制御部２０２以外の各部の動作については、図４〜６とともに後述する。
【０１５３】
なお、復号装置２００も、例えば図２のコンピュータ１００のようなコンピュータであってもよい。この場合、入出力部２０１は、具体的には、入力装置１０４、出力装置１０５、不揮発性記憶装置１０６、通信インタフェイス１０３のうちの１つ以上の組み合わせにより実現されてもよい。また、この場合、復号装置２００内の入出力部２０１以外の各部は、それぞれ、プロセッサ１０１により実現されてもよい。
【０１５４】
さて、図４〜６は、第３比較例の復号装置２００が実行する復号方法のフローチャートである。
【０１５５】
ステップＳ１０１で制御部２０２が、入出力部２０１から以下の情報を受け取る。
・暗号文であるベクトル
2014102398.tif 000088
・秘密鍵である行列Ｖ
・行列Ｖの次数（dimension）ｎ
【０１５６】
次に、ステップＳ１０２で制御部２０２が、逆行列計算部２０３に行列Ｖと次数ｎを引数として入力する。
【０１５７】
すると、ステップＳ１０３で逆行列計算部２０３が、行列Ｖの逆行列Ｖ−１を計算し、逆行列Ｖ−１を制御部２０２に出力する。逆行列の具体的な計算手法は任意である。例えば、逆行列計算部２０３は、ガウス・ジョルダンの消去法（Gauss-Jordan elimination）により逆行列Ｖ−１を計算してもよい。
【０１５８】
次に、ステップＳ１０４で制御部２０２が、フレッシュ暗号文計算部２０４に以下の情報を引数として入力する。
・入出力部２０１から入力されたベクトル
2014102398.tif 000089
・入出力部２０１から入力された行列Ｖ
・逆行列計算部２０３により計算された逆行列Ｖ−１
・入出力部２０１から入力された次数ｎ
【０１５９】
なお、フレッシュ暗号文計算部２０４は、式（１０）のベクトル
2014102398.tif 000090
を計算するコンポーネントである。上述のとおり、第３比較例では、式（１９）のフレッシュ暗号文
2014102398.tif 000091
と式（１０）のベクトル
2014102398.tif 000092
が等しいので、以下では式（１０）のベクトル
2014102398.tif 000093
のことも「フレッシュ暗号文」ということがある。同じ理由から、式（１０）のベクトル
2014102398.tif 000094
を計算するコンポーネントを、上述のとおり「フレッシュ暗号文計算部」と呼んでいる。
【０１６０】
さて、フレッシュ暗号文計算部２０４は、以上のような入力を受け取ると、まず、式（１０）中のベクトル
2014102398.tif 000095
と逆行列Ｖ−１との積を得るために、ステップＳ１０５で、以下の情報をベクトル・行列乗算部２０５に引数として入力する。
・制御部２０２から入力されたベクトル
2014102398.tif 000096
・制御部２０２から入力された逆行列Ｖ−１
・制御部２０２から入力された次数ｎ
【０１６１】
ところで、ベクトル・行列乗算部２０５は、次数ｎと、ｎ次元行ベクトルと、ｎ次正方行列を入力として受け取ると、入力ベクトルと入力行列の積（すなわちｎ次元行ベクトル）を計算し、計算した積を出力する。以下では説明の便宜上、ベクトル・行列乗算部２０５が出力する出力ベクトルを式（２２）のように表すことにする。
【数１６】
2014102398.tif 000097
【０１６２】
したがって、ステップＳ１０５で上記のごとき入力を受け取ると、ベクトル・行列乗算部２０５は、ベクトル
2014102398.tif 000098
と逆行列Ｖ−１を乗算し、得られた積
2014102398.tif 000099
をフレッシュ暗号文計算部２０４に出力する。具体的には、ベクトル・行列乗算部２０５による乗算と出力は、以下のようにしてステップＳ１０６〜Ｓ１１４において行われる。
【０１６３】
まず、ステップＳ１０６でベクトル・行列乗算部２０５は、インデックス変数ｊを１に初期化する。
【０１６４】
次に、ステップＳ１０７でベクトル・行列乗算部２０５は、出力ベクトル
2014102398.tif 000100
の第ｊ要素を表す変数を０に初期化する。以下では説明の便宜上、この変数も式（２２）の記法を用いて“ｘｊ−１”と示すことにする。
【０１６５】
次に、ステップＳ１０８でベクトル・行列乗算部２０５は、インデックス変数ｉを１に初期化する。
【０１６６】
そして、ステップＳ１０９でベクトル・行列乗算部２０５は、入力ベクトルの第ｉ要素と、入力行列の第（ｉ，ｊ）要素（つまり第ｉ行第ｊ列の要素）を、引数としてスカラ乗算部２０６に入力する。上記のようにステップＳ１０５で暗号文
2014102398.tif 000101
と秘密鍵Ｖの逆行列Ｖ−１がベクトル・行列乗算部２０５に入力される場合、ステップＳ１０９では、暗号文
2014102398.tif 000102
の第i要素と、逆行列Ｖ−１の第（ｉ，ｊ）要素が、スカラ乗算部２０６に入力される。
【０１６７】
スカラ乗算部２０６は、ベクトル・行列乗算部２０５から入力された２つのスカラの積を計算し、計算した積をベクトル・行列乗算部２０５に出力する。すると、ベクトル・行列乗算部２０５は、得られた積を変数ｘｊ−１に足す。
【０１６８】
その後、ステップＳ１１０でベクトル・行列乗算部２０５は、インデックス変数ｉの値が次数ｎに等しいか否かを判定する。
もしｉ≠ｎであれば（具体的にはｉ＜ｎであれば）、出力ベクトル
2014102398.tif 000103
の第ｊ要素ｘｊ−１の計算は完了していない。よって、図４〜６の復号処理はステップＳ１１１へと移行する。
【０１６９】
逆に、もしｉ＝ｎであれば、出力ベクトル
2014102398.tif 000104
の第ｊ要素ｘｊ−１の計算は完了している。よって、復号処理はステップＳ１１２へと移行する。
【０１７０】
ステップＳ１１１でベクトル・行列乗算部２０５は、インデックス変数ｉを１だけインクリメントする。そして、復号処理はステップＳ１０９へと戻る。
【０１７１】
また、ステップＳ１１２でベクトル・行列乗算部２０５は、インデックス変数の値ｊが次数ｎに等しいか否かを判定する。
【０１７２】
もしｊ≠ｎであれば（具体的にはｊ＜ｎであれば）、出力ベクトル
2014102398.tif 000105
の計算は完了していない。よって、復号処理はステップＳ１１３へと移行する。
【０１７３】
逆に、もしｊ＝ｎであれば、出力ベクトル
2014102398.tif 000106
の計算は完了している。よって、復号処理はステップＳ１１４へと移行する。
【０１７４】
ステップＳ１１３でベクトル・行列乗算部２０５は、インデックス変数ｊを１だけインクリメントする。そして、復号処理はステップＳ１０７へと戻る。
【０１７５】
そして、ステップＳ１１４では、ベクトル・行列乗算部２０５が、計算し終わったベクトル
2014102398.tif 000107
をフレッシュ暗号文計算部２０４に出力する。こうしてステップＳ１１４で出力されるベクトルは、具体的には、式（１０）の中の
2014102398.tif 000108
である。
【０１７６】
次に、ステップＳ１１５でフレッシュ暗号文計算部２０４が、以下の情報を丸め部２０７に引数として入力する。
・ステップＳ１１４でベクトル・行列乗算部２０５から出力されたベクトル
・制御部２０２から入力された次数ｎ
【０１７７】
すると、ステップＳ１１６で丸め部２０７は、１≦ｉ≦ｎなる各ｉについて、入力されたｎ次元ベクトルの第ｉ要素に最も近い整数値を第ｉ要素として持つｎ次元ベクトルを計算し、出力する。こうしてステップＳ１１６で出力されるベクトルは、具体的には、式（１０）の中の
2014102398.tif 000109
である。
【０１７８】
次に、フレッシュ暗号文計算部２０４は、式（１０）中の
2014102398.tif 000110
を得るために、ステップＳ１１７で、以下の情報をベクトル・行列乗算部２０５に引数として入力する。
・ステップＳ１１６で丸め部２０７から出力されたｎ次元行ベクトル
2014102398.tif 000111
・制御部２０２から入力された行列Ｖ
・制御部２０２から入力された次数ｎ
【０１７９】
その後のステップＳ１１８〜Ｓ１２６は、ステップＳ１０６〜Ｓ１１４と類似である。具体的には、ステップＳ１１８でベクトル・行列乗算部２０５は、インデックス変数ｊを１に初期化する。
【０１８０】
次に、ステップＳ１１９でベクトル・行列乗算部２０５は、出力ベクトル
2014102398.tif 000112
の第ｊ要素を表す変数を０に初期化する。
【０１８１】
次に、ステップＳ１２０でベクトル・行列乗算部２０５は、インデックス変数ｉを１に初期化する。
【０１８２】
そして、ステップＳ１２１でベクトル・行列乗算部２０５は、入力ベクトルの第ｉ要素と、入力行列の第（ｉ，ｊ）要素（つまり第ｉ行第ｊ列の要素）を、引数としてスカラ乗算部２０６に入力する。スカラ乗算部２０６は、ベクトル・行列乗算部２０５から入力された２つのスカラの積を計算し、計算した積をベクトル・行列乗算部２０５に出力する。すると、ベクトル・行列乗算部２０５は、得られた積を変数ｘｊ−１に足す。
【０１８３】
その後、ステップＳ１２２でベクトル・行列乗算部２０５は、インデックス変数ｉの値が次数ｎに等しいか否かを判定する。もしｉ≠ｎであれば（具体的にはｉ＜ｎであれば）、復号処理はステップＳ１２３へと移行する。逆に、もしｉ＝ｎであれば、復号処理はステップＳ１２４へと移行する。
【０１８４】
ステップＳ１２３でベクトル・行列乗算部２０５は、インデックス変数ｉを１だけインクリメントする。そして、復号処理はステップＳ１２１へと戻る。
【０１８５】
また、ステップＳ１２４でベクトル・行列乗算部２０５は、インデックス変数の値ｊが次数ｎに等しいか否かを判定する。もしｊ≠ｎであれば（具体的にはｊ＜ｎであれば）、復号処理はステップＳ１２５へと移行する。逆に、もしｊ＝ｎであれば、復号処理はステップＳ１２６へと移行する。
【０１８６】
ステップＳ１２５でベクトル・行列乗算部２０５は、インデックス変数ｊを１だけインクリメントする。そして、復号処理はステップＳ１１９へと戻る。
【０１８７】
そして、ステップＳ１２６では、ベクトル・行列乗算部２０５が、計算し終わったベクトル
2014102398.tif 000113
をフレッシュ暗号文計算部２０４に出力する。こうしてステップＳ１２６で出力されるベクトルは、具体的には、式（１０）の中の
2014102398.tif 000114
である。
【０１８８】
すると、ステップＳ１２７でフレッシュ暗号文計算部２０４は、以下の情報を引数として減算部２０８に入力する。
・制御部２０２から入力されたベクトル
2014102398.tif 000115
・ステップＳ１２６でベクトル・行列乗算部２０５から出力されたベクトル（すなわち
2014102398.tif 000116
）
・制御部２０２から入力された次数ｎ
【０１８９】
そして、ステップＳ１２８で減算部２０８は、入力された２つのｎ次元ベクトルの差を算出する。つまり、減算部２０８は、式（１０）のベクトル
2014102398.tif 000117
を算出する。そして、減算部２０８は、算出した
2014102398.tif 000118
をフレッシュ暗号文計算部２０４に出力する。
【０１９０】
なお、上述のように、式（１０）のベクトル
2014102398.tif 000119
はフレッシュ暗号文
2014102398.tif 000120
に等しい。よって、ステップＳ１２８の処理は、換言すれば、減算部２０８がフレッシュ暗号文
2014102398.tif 000121
を計算して出力する処理である。
【０１９１】
そして、ステップＳ１２９では、フレッシュ暗号文計算部２０４が、以上のようにして得られたフレッシュ暗号文
2014102398.tif 000122
を制御部２０２に出力する。
【０１９２】
すると、ステップＳ１３０で制御部２０２が、以下の情報を引数としてモジュロ演算部２０９に入力する。
・フレッシュ暗号文計算部２０４から出力されたフレッシュ暗号文
2014102398.tif 000123
の第１要素ａ０
・平文空間サイズを示す定数ｓ
【０１９３】
すると、ステップＳ１３１でモジュロ演算部２０９は、式（２３）にしたがって平文ｂを計算し、計算した平文ｂを制御部２０２に出力する。なお、上記のとおりａ０’＝ａ０であるから、式（２３）は式（２０）と等価である。
ｂ＝ａ０  ｍｏｄ  ｓ      （２３）
【０１９４】
最後に、ステップＳ１３２で制御部２０２は、入出力部２０１を介して平文ｂを出力する。そして、第３比較例の復号処理は終了する。
【０１９５】
以上のように、第３比較例では、１つの暗号文の復号のたびに、ステップＳ１０９がｎ２回実行され、ステップＳ１２１がｎ２回実行される。つまり、第３比較例では、１つの暗号文の復号のたびに、スカラ乗算部２０６による乗算が２×ｎ２回実行される。したがって、第３比較例による復号の処理負荷は高く、第３比較例による復号には時間がかかる。
【０１９６】
続いて、以上説明した第１〜第３比較例と比べて、図１〜２の第１実施形態の利点について説明する。
第１比較例および第２比較例と比べると、第１実施形態には、「平文空間が拡張されているので、様々な用途への応用がしやすい」という利点がある。
【０１９７】
例えば、近年のクラウドサービスの広がりにともない、個々のデータを暗号化したままの状態でデータの集計を行う秘匿集計が注目されつつある。準同型暗号方式は、例えば秘匿集計などの様々な用途への応用が期待される。よって、平文空間が拡張された（すなわち平文空間サイズｓが２より大きい）第１実施形態は、第１比較例および第２比較例と比べて、応用範囲の広さの点で優れている。
【０１９８】
また、第３比較例と比べると、第１実施形態には、「乗算の回数が大幅に少ないので、高速な復号が可能である」という利点がある。
【０１９９】
具体的には、第３比較例では、上記のとおり１回の復号につきスカラ値同士の乗算が２×ｎ２回実行される。仮に、暗号文
2014102398.tif 000124
の第２〜第ｎ要素がすべて０であることを利用して、０との乗算の実行を省略するように第３比較例を変形するとしても、そのように変形された第３比較例における１回の復号は、それでもやはり（ｎ＋ｎ２）回ものスカラ値同士の乗算を含む。
【０２００】
それに対して、第１実施形態では、図１のステップＳ４で式（４）により平文ｂが計算される。参照の便宜のため、ここに式（４）を再掲する。式（４）に含まれるスカラ値同士の乗算はたったの２回である。
ｂ＝［ｃ×ｗ］ｄ×ｗ−１  ｍｏｄ  ｓ        （４）
【０２０１】
なお、第１実施形態では、式（４）に示すとおり、１回の復号ごとに２回のモジュロ演算が行われる。それに対し、第３比較例では、図６のステップＳ１３１に示すように、１回の復号ごとに行われるモジュロ演算の回数は１回である。そして、モジュロ演算の計算コストは決して低くはない。
【０２０２】
しかし、第３比較例と比べて１回モジュロ演算が増えることによる計算コストの増大の影響はわずかである。復号処理の計算コストを第３比較例と第１実施形態とで比べると、乗算の回数が第１実施形態では大幅に減っていることの影響が支配的である。
【０２０３】
また、第１実施形態のステップＳ２における値ｗの取得にかかるコストと、ステップＳ３における逆数ｗ−１の取得にかかるコストを考慮に入れてもなお、第１実施形態では第３比較例より低い計算コストで復号が可能である。
【０２０４】
上記のとおりステップＳ２とＳ３における取得の具体的方法には様々なものがある。例えば、コンピュータは、ステップＳ２で記憶装置から値ｗを読み出すことにより値ｗを取得してもよく、ステップＳ３で記憶装置から逆数ｗ−１を読み出すことにより逆数ｗ−１を取得してもよい。この場合、ステップＳ２とＳ３の取得コストは、無視しても差し支えないほどに低い。
【０２０５】
別の例として、ステップＳ２でコンピュータは、平文空間サイズｓと互いに素な要素ｗを行列Ｗの中から探すことで、要素ｗを取得してもよい。この場合、上記のとおり、コンピュータは、行列Ｗ中の任意の１行または任意の１列のｎ個の要素の中から平文空間サイズｓと互いに素な要素ｗを探すだけで十分である。つまり、仮に行列Ｗがコンピュータの記憶装置に予め記憶されていないとしても、コンピュータは、ステップＳ２で、行列Ｗ中のｎ個の要素を計算し、それらｎ個の要素の中から平文空間サイズｓと互いに素な要素を探索するだけで十分である。
【０２０６】
そして、Ｗ＝ｄＶ−１であるから、逆行列Ｖ−１が既知の場合には、行列Ｗ中のｎ個の要素の値を計算するためには、コンピュータはスカラ同士の乗算をｎ回行うだけで十分である。明らかに、ｎ回の乗算にかかる時間は、２×ｎ２回の乗算（または（ｎ＋ｎ２）回の乗算）にかかる時間と比べて、十分に短い。
【０２０７】
また、公開鍵として使われる行列Ｂの行列式ｄと平文空間サイズｓが互いに素である場合には、コンピュータは、ステップＳ２で次のようにして値ｗを取得してもよい。すなわち、コンピュータは、行列Ｖ−１中の任意の１行または任意の１列のｎ個の要素の中から、平文空間サイズｓと互いに素な要素を探してもよい。そして、コンピュータは、見つかった要素に上記行列式ｄを乗じることで、値ｗを取得してもよい。この場合、ステップＳ２で生じる乗算の回数は１回だけである。
【０２０８】
つまり、仮にステップＳ２でコンピュータが逆行列Ｖ−１から行列Ｗを計算して行列Ｗの探索により値ｗを取得する場合であっても、ステップＳ２で生じる乗算はｎ回以下である。しかも、ステップＳ２でｎ回の乗算が生じる場合であっても、「１回の復号あたりのコスト」という観点でのステップＳ２の乗算のコストは低い。理由は以下のとおりである。
【０２０９】
第１実施形態で復号に使われる値ｗは、その定義から明らかなとおり、暗号文に依存しない。よって、コンピュータは、仮にある暗号文の復号のために計算と探索により値ｗを取得するとしても、一旦取得した値ｗを記憶装置に記憶して他の暗号文の復号の際には記憶した値ｗを読み出すことで、１回の復号あたりの値ｗの取得コストを下げることができる。同様に、コンピュータは、仮に１回は逆数ｗ−１を計算により取得するのだとしても、一旦取得した逆数ｗ−１を記憶装置に記憶することで、１回の復号あたりの逆数ｗ−１の取得コストを下げることができる。
【０２１０】
他方、第３比較例では、式（１０）および図４〜６から明らかなように、ある暗号文を復号する過程で得られるベクトルは、他の暗号文の復号とは無関係である。つまり、以下に挙げる３つのベクトルは、いずれも、暗号文
2014102398.tif 000125
自体に依存するので、他の暗号文の復号とは無関係であり、したがって、いずれも、他の暗号文の復号のために再利用することはできない。
【数１７】
2014102398.tif 000126
【０２１１】
よって、第３比較例では、仮に逆行列Ｖ−１が事前に計算されていて復号のたびに再利用されるとしても、逆行列Ｖ−１の再利用によって削減可能な１回の復号あたりの計算コストは限られている。つまり、第３比較例では、仮に逆行列Ｖ−１が再利用されるとしても、復号のためには依然としてｎ次元ベクトルとｎ×ｎ行列との乗算が２回行われ、この２回の乗算の計算コストは、計算結果の再利用によって削減できるものではない。
【０２１２】
したがって、第３比較例と第１実施形態とで１回の復号あたりの計算コストを比較する場合、ステップＳ２とＳ３のコストの影響は無視しても差し支えない。そして、ステップＳ４の計算コストは、上記のとおり、第３比較例における復号の計算コストと比べて非常に低い。
【０２１３】
なお、第１実施形態のコンピュータは、計算コストをさらに削減するために、ステップＳ４において、通常の乗算とモジュロ演算の代わりに、モンゴメリ乗算剰余演算を行ってもよい。
【０２１４】
以上から、第１実施形態には、「拡張された平文空間を有する準同型暗号方式において、高速な復号が実現される」という利点がある。
ところで、第１実施形態では、上記のように、式（４）により平文ｂが得られる。第２比較例で使われる式（１７）と式（４）を比べると、式（４）が式（１７）の一般化であることが理解される。つまり、式（４）は任意のｓ≧２について当てはまる式であり、式（１７）はｓ＝２の場合を示す式である。
【０２１５】
参照の便宜のため、ここに式（４）と式（１７）を再掲する。
ｂ＝［ｃ×ｗ］ｄ×ｗ−１  ｍｏｄ  ｓ        （４）
ｂ＝［ｃ×ｗ］ｄ  ｍｏｄ  ２            （１７）
【０２１６】
上記のとおり、式（４）のｗはｓと互いに素である。よって、式（４）においてｓ＝２の場合、式（４）のｗは奇数である。したがって、式（４）においてｓ＝２の場合、式（４）のｗ−１も奇数である（なぜなら、式（４）のｗ−１は、法ｓのもとでのｗの逆数だからである）。そして、ｗ−１が奇数なので、ｓ＝２のとき、式（４）より式（２４）が得られる。
ｂ＝［ｃ×ｗ］ｄ×ｗ−１  ｍｏｄ  ２
＝［ｃ×ｗ］ｄ  ｍｏｄ  ２          （２４）
【０２１７】
こうしてｓ＝２を式（４）に代入することで得られる式（２４）を式（１７）と比較すると分かるとおり、式（４）は式（１７）の一般化である。
【０２１８】
続いて、「第１実施形態において、なぜ式（４）により平文ｂが得られるのか」という理由について説明する。すなわち、「なぜ式（４）は、式（１０）により得られる値ａ０（＝ａ０’）に関する式（２３）と数学的に等価なのか」という理由について、以下に説明する。
【０２１９】
平文空間サイズｓが２より大きい第３比較例においても、上記のとおり、式（１０）はフレッシュ暗号文を示す。つまり、ｓ＞２の場合にも式（２５）が成り立つ。
【数１８】
2014102398.tif 000127
【０２２０】
式（２５）と、上述のＷ＝ｄＶ−１という定義より、式（２６）が導出される。
【数１９】
2014102398.tif 000128
【０２２１】
なお、任意の有理数ｑに対して、“［ｑ］”は、有理数ｑと、有理数ｑに最も近い整数との差を示す。つまり、任意の有理数ｑに対して式（２７）が成り立つ。
［ｑ］＝ｑ−「ｑ」      （２７）
【０２２２】
例えば、「１３／５」＝３であるから、［１３／５］＝１３／５−３＝−２／５である。また、式（２６）のように、演算子“［・］”の引数がｎ次元ベクトルである場合は、ｎ次元ベクトルに対する演算子“［・］”は、引数ベクトルのｎ個の要素にそれぞれ、スカラに対する式（２７）の演算子“［・］”を適用することを意味する。したがって、結果としてｎ次元ベクトルが得られる。
【０２２３】
ここで、式（２６）の両辺に行列Ｗを乗じると、式（２８）が導出される（任意の整数ｚについてｄ×［ｚ／ｄ］＝［ｚ］ｄなので）。なお、式（２８）における“Ｉ”はｎ次単位行列（n×n identity matrix）である。
【数２０】
2014102398.tif 000129
【０２２４】
ところで、第１実施形態の復号方法に対応する暗号化方法は、第３比較例の暗号化方法と同じである。つまり、第１実施形態における暗号化は、次の２つのステップを含む。
・乱数ベクトル
2014102398.tif 000130
を用いた、式（１９）による、フレッシュ暗号文
2014102398.tif 000131
の生成。
・式（９）による、フレッシュ暗号文
2014102398.tif 000132
からの暗号文
2014102398.tif 000133
の生成。
【０２２５】
また、行列Ｖが式（３）のような規則性を持つため、上述のとおり行列Ｗには規則性がある。具体的には、行列Ｗは、式（２９）のような形である。
【数２１】
2014102398.tif 000134
【０２２６】
式（２８）に式（１９）と式（２９）を代入すると、式（３０）が導出される。
【数２２】
2014102398.tif 000135
【０２２７】
他方、暗号文
2014102398.tif 000136
の第２要素から第ｎ要素がすべて０であることに着目すると、式（３１）が得られる。
【数２３】
2014102398.tif 000137
【０２２８】
式（３０）と式（３１）を比較すると、法ｓのもとで式（３２）の等号が成り立つ。
【数２４】
2014102398.tif 000138
【０２２９】
法ｓのもとで式（３２）の等号が成り立つことは、０≦ｉ≦ｎ−１なる任意のｉについて、法ｓのもとで式（３３）の等号が成り立つことを意味する。
【数２５】
2014102398.tif 000139
【０２３０】
ところで、もし、平文空間サイズｓと互いに素であるような要素ｗｉが行列Ｗ中に存在するならば（ただし０≦ｉ≦ｎ−１）、当該要素ｗｉには、法ｓのもとでの逆数ｗｉ−１が存在する。換言すれば、０≦ｉ≦ｎ−１なる任意のｉについて、式（３４）が成り立つ（なお、式（３４）における関数“ｇｃｄ（）”は、２つの引数の最大公約数を示す）。
（ｇｃｄ（ｓ，ｗｉ）＝１）
⇒（∃ｗｉ−１，ｗｉ×ｗｉ−１＝１  （ｍｏｄ  ｓ））    （３４）
【０２３１】
ここで、第１実施形態において図１のステップＳ２で取得される値ｗは、上記のとおり、行列Ｗの要素のうち、平文空間サイズｓと互いに素なものである。よって、式（３４）より、値ｗには法ｓのもとでの逆数ｗ−１が存在する。この逆数ｗ−１が、図１のステップＳ３で取得される。
【０２３２】
行列Ｗには式（２９）のような規則性があるので、第１実施形態のコンピュータは、例えば、ステップＳ２で、行列Ｗの１行目の要素ｗ０，ｗ１，…，ｗｎ−１の中から、平文空間サイズｓと互いに素な要素を探してもよい。
【０２３３】
説明の便宜上、ある要素ｗｉが平文空間サイズｓと互いに素であるものとする（０≦ｉ≦ｎ−１）。また、上記のとおり、０≦ｉ≦ｎ−１なる任意のｉについて、法ｓのもとで式（３３）の等号が成り立つ。したがって、平文空間サイズｓと互いに素な当該要素ｗｉに関して、式（３５）が成り立つ。
【数２６】
2014102398.tif 000140
【０２３４】
式（３５）は、第１実施形態においてステップＳ４で使われる式（４）と同じである。すなわち、以上の説明から明らかなように、第１実施形態での復号は、意味的には（つまり数学的には）、第３比較例における復号と等価である。したがって、第３比較例の復号が正しいのと同様に、式（４）による第１実施形態の復号も正しい。
【０２３５】
しかし、第１実施形態と第３比較例における復号は、数学的には等価であっても、計算量の面で大きく異なる。すなわち、上述したとおり、第１実施形態の復号は、第３比較例の復号と比べて遥かに高速である。したがって、第１実施形態は、第３比較例と比べて優れている。つまり、ある観点から言えば、第１実施形態では、計算量の多い第３比較例における復号が、数学的に等価だが遥かに計算量の少ない復号へと、置き換えられているわけである。
【０２３６】
続いて、第１実施形態のより具体的なバリエーションとして、第２実施形態と第３実施形態について説明する。第１実施形態との共通点については、説明を省略することがある。
【０２３７】
第２実施形態は、復号装置が鍵生成装置を兼ねる実施形態である。換言すれば、第２実施形態は、図１の復号処理を行うコンピュータが、鍵生成装置としても動作し、かつ、復号装置としても動作する場合に対応する。
【０２３８】
他方、第３実施形態は、予め記憶された値ｗと逆数ｗ−１を利用することで復号の計算コストを一層削減する実施形態である。第３実施形態は、復号装置が鍵生成装置を兼ねているか否かに関係なく適用可能である。第３実施形態は、図１のステップＳ２とＳ３の取得が、記憶装置からの読み取り処理により実現される場合に対応する。
【０２３９】
以下、第２実施形態と第３実施形態について、それぞれ具体的に説明する。図７は、第２実施形態の情報処理装置３００のブロック構成図である。
【０２４０】
図７に示す情報処理装置３００は、鍵生成装置でもあり復号装置でもある。情報処理装置３００は、具体的には図２のコンピュータ１００により実現されてもよい。
【０２４１】
情報処理装置３００は、入出力部３０１と制御部３０２を有する。また、情報処理装置３００は、乱数生成部３０３、逆行列計算部３０４、ＨＮＦ（Hermite Normal Form）計算部３０５、スカラ・行列乗算部３０６、スカラ乗算部３０７、探索部３０８、およびＧＣＤ（greatest common divisor；最大公約数）計算部３０９を有する。さらに、情報処理装置３００は、逆元計算部３１０、記憶部３１１、復号部３１２、第１モジュロ演算部３１３、および第２モジュロ演算部３１４を有する。
【０２４２】
入出力部３０１は、情報処理装置３００への入力インタフェイスとして動作し、情報処理装置３００からの出力インタフェイスとしても動作する。例えば、入力インタフェイスとしての入出力部３０１は、通信インタフェイス１０３と入力装置１０４の一方または双方により実現されてもよい。また、出力インタフェイスとしての入出力部３０１は、通信インタフェイス１０３と出力装置１０５の一方または双方により実現されてもよい。場合によっては、不揮発性記憶装置１０６とプロセッサ１０１との間のデータ入出力インタフェイス（例えばディスクコントローラ）により入出力部３０１が実現されてもよい。
【０２４３】
制御部３０２は、鍵生成と復号の双方を制御する。制御部３０２は、例えば、プロセッサ１０１により実現されてもよい。
【０２４４】
第２実施形態では、具体的には、制御部３０２は、ビット長ｔと次数ｎと平文空間サイズｓの入力を入出力部３０１から受け取り、受け取った入力にしたがって鍵生成を制御する。また、制御部３０２は、生成した公開鍵（すなわち行列Ｂ）を、入出力部３０１を介して公開する。
【０２４５】
さらに、制御部３０２は、暗号文として、ベクトル
2014102398.tif 000141
またはその第１要素ｃを、入出力部３０１を介して受け取る。制御部３０２は、暗号文を受け取ると、復号処理を開始する。また、制御部３０２は、復号の結果得られる平文ｂを、入出力部３０１を介して出力する。
【０２４６】
入出力部３０１と制御部３０２以外の各部の詳細については、図８〜１１とともに後述するが、概要は以下のとおりである。
【０２４７】
乱数生成部３０３は秘密鍵の生成に関わり、ＨＮＦ計算部３０５は公開鍵の生成に関わる。逆行列計算部３０４、スカラ・行列乗算部３０６、探索部３０８、およびＧＣＤ計算部３０９は、「秘密鍵が、高速な復号を可能とするための条件を満たすか否か」についての判定に関わる。また、探索部３０８とＧＣＤ計算部３０９は、復号に使うための情報の取得にも関わる。さらに、復号に使うための情報の取得には、逆元計算部３１０も関わる。
【０２４８】
記憶部３１１は、復号に使うための情報を記憶する。記憶部３１１は不揮発性記憶装置１０６により実現されてもよい。
【０２４９】
復号部３１２と第１モジュロ演算部３１３と第２モジュロ演算部３１４は、復号に関わる。なお、スカラ乗算部３０７は、スカラ・行列乗算部３０６と復号部３１２の双方から利用されるモジュールである。
【０２５０】
情報処理装置３００がコンピュータ１００により実現される場合、以下の各部はプロセッサ１０１により実現されてもよい。
・制御部３０２
・乱数生成部３０３
・逆行列計算部３０４
・ＨＮＦ計算部３０５
・スカラ・行列乗算部３０６
・スカラ乗算部３０７
・探索部３０８
・ＧＣＤ計算部３０９
・逆元計算部３１０
・復号部３１２
・第１モジュロ演算部３１３
・第２モジュロ演算部３１４
【０２５１】
さて、図８〜１０は、第２実施形態の情報処理装置３００が行う処理のフローチャートである。
【０２５２】
ステップＳ２０１で制御部３０２は、入出力部３０１から、ビット長ｔと次数ｎと平文空間サイズｓの入力を受け取る。ビット長ｔと次数ｎと平文空間サイズｓは互いに独立な値である。
【０２５３】
例えば、ビット長ｔは、３２でも、６４でも、１２８でも、その他の値でもよい。また、次数ｎとしては、１０２４（＝２１０）、２０４８（＝２１１）、４０９６（＝２１２）、８１９２（＝２１３）、１６３８４（＝２１４）、３２７６８（＝２１５）などの値が好適である。ビット長ｔと次数ｎが大きいほど、秘密鍵が解読（break）されるリスクが低く、したがって、セキュリティが高い。上記に例示したような次数ｎは、セキュリティと処理速度のバランスが良いので好ましい。しかし、もちろん次数ｎは任意である。
【０２５４】
平文空間サイズｓは、例えば、準同型暗号を利用する目的に応じて、適宜決められてよい。第２実施形態でも、第１実施形態と同じく、ｓ＞２である。
【０２５５】
なお、平文空間サイズｓは、２の冪乗数または素数であることが好ましい。なぜなら、平文空間サイズｓが２の冪乗数または素数のとき、平文空間サイズｓと互いに素な要素を探す処理は単純で低負荷だからである。
【０２５６】
つまり、平文空間サイズｓが２の冪乗数のとき、平文空間サイズｓと互いに素な要素を探す処理は、「奇数の要素を探す」という処理（換言すれば「最下位ビット（ＬＳＢ）が１の要素を探す」という処理）であり、この処理は低負荷である。また、平文空間サイズｓが素数のとき、平文空間サイズｓと互いに素な要素を探す処理は、「ｓの倍数ではない要素を探す」という処理であり、この処理も比較的低負荷である。
【０２５７】
さて、次に、ステップＳ２０２で制御部３０２は、乱数生成部３０３にビット長ｔと次数ｎを引数として入力する。
【０２５８】
すると、乱数生成部３０３は、ステップＳ２０３で、ｎ個の乱数ｖ０，ｖ１，…，ｖｎ−１を生成し、生成したｎ個の乱数ｖ０，ｖ１，…，ｖｎ−１を制御部３０２に出力する。より具体的には、０≦ｉ≦ｎ−１なる各ｉについて、乱数ｖｉは整数であり、かつ、乱数ｖｉの絶対値｜ｖｉ｜はｔビット以下である。
【０２５９】
次に、ステップＳ２０４で制御部３０２は、ｎ個の乱数ｖ０，ｖ１，…，ｖｎ−１により式（３）のように定義されるｎ次正方行列Ｖと、次数ｎを、逆行列計算部３０４に引数として入力する。行列Ｖは、秘密鍵の候補である。
【０２６０】
すると、ステップＳ２０５で逆行列計算部３０４は、行列Ｖの逆行列Ｖ−１の計算を試み、結果を制御部３０２に出力する。例えば、逆行列計算部３０４は、ガウス・ジョルダンの消去法により逆行列Ｖ−１の計算を試みてもよい。また、逆行列計算部３０４は、逆行列Ｖ−１の計算のためにスカラ乗算部３０７を呼び出してもよい。
【０２６１】
なお、行列Ｖは上記のように乱数に基づいて定義される。よって、たまたま行列Ｖに逆行列Ｖ−１が存在する場合もあり得るし、たまたま行列Ｖには逆行列Ｖ−１が存在しない場合もあり得る。
【０２６２】
したがって、行列Ｖに逆行列Ｖ−１が存在することが判明した場合は、逆行列計算部３０４は、逆行列Ｖ−１を制御部３０２に出力する。逆に、行列Ｖに逆行列Ｖ−１が存在しないことが判明した場合は、逆行列計算部３０４は、逆行列Ｖ−１が存在しないことを示す返り値またはエラーコードなどを制御部３０２に出力する。
【０２６３】
すると、ステップＳ２０６で制御部３０２は、逆行列計算部３０４からの出力に基づいて、「行列Ｖに逆行列Ｖ−１が存在するか否か」を判定する。ステップＳ２０６の判定は、図２のコンピュータ１００が鍵生成装置として動作する場合についての上記の説明における、「第１の条件が成り立つか否か」の判定に対応する。
【０２６４】
逆行列Ｖ−１が存在しない場合、行列Ｖは秘密鍵として不適切である。よって、逆行列Ｖ−１が存在しない場合、別の新たな行列を秘密鍵の候補として検討するために、処理はステップＳ２０２に戻る。
【０２６５】
逆に、逆行列Ｖ−１が存在する場合は、行列Ｖが秘密鍵として適切か否かに関して、さらに２つの条件（つまり、図２を参照しながら説明した「第２の条件」と「第３の条件」）を調べるために、処理はステップＳ２０７に移行する。
【０２６６】
ステップＳ２０７で制御部３０２は、ＨＮＦ計算部３０５に、行列Ｖと次数ｎを引数として入力する。
【０２６７】
すると、ステップＳ２０８でＨＮＦ計算部３０５は、行列Ｖのエルミート標準形たる行列Ｂを計算し、行列Ｂを制御部３０２に出力する。なお、ＨＮＦ計算部３０５は、行列Ｂの計算のためにスカラ乗算部３０７を呼び出してもよい。
【０２６８】
次に、ステップＳ２０９で制御部３０２は、ＨＮＦ計算部３０５からの出力に基づいて、「行列Ｂが所定の形式（具体的には、式（６）の形式）であるか否か」を判定する。ステップＳ２０９の判定は、図２のコンピュータ１００が鍵生成装置として動作する場合についての上記の説明における、「第２の条件が成り立つか否か」の判定に対応する。
【０２６９】
行列Ｂが式（６）の形式でない場合（換言すれば、式（６）の形式のエルミート標準形が行列Ｖから導出されない場合）、行列Ｖは秘密鍵として不適切である。よって、この場合、別の新たな行列を秘密鍵の候補として検討するために、処理はステップＳ２０２に戻る。
【０２７０】
逆に、行列Ｂが式（６）の形式の場合は、行列Ｖが秘密鍵として適切か否かに関して、さらに残りの１つの条件（つまり、図２を参照しながら説明した「第３の条件」）を調べるために、処理はステップＳ２１０に移行する。
【０２７１】
ステップＳ２１０で制御部３０２は、スカラ・行列乗算部３０６に、以下の情報を引数として入力する。
・逆行列計算部３０４から出力された逆行列Ｖ−１
・入出力部３０１から入力された次数ｎ
・ＨＮＦ計算部３０５から出力された行列Ｂの行列式ｄ（すなわち行列Ｂの第（１，１）要素）
【０２７２】
すると、ステップＳ２１１〜Ｓ２１８でスカラ・行列乗算部３０６は、Ｗ＝ｄＶ−１を計算する。
【０２７３】
具体的には、ステップＳ２１１でスカラ・行列乗算部３０６は、インデックス変数ｉを１に初期化する。
【０２７４】
次に、ステップＳ２１２でスカラ・行列乗算部３０６は、インデックス変数ｊを１に初期化する。
【０２７５】
そして、ステップＳ２１３でスカラ・行列乗算部３０６は、スカラ乗算部３０７に以下の２つの値を引数として入力する。
・制御部３０２から入力された行列式ｄ
・制御部３０２から入力された逆行列Ｖ−１の第（ｉ，ｊ）要素
【０２７６】
すると、ステップＳ２１４でスカラ乗算部３０７は、入力された２つの値を乗算し、乗算の結果として得られた積をスカラ・行列乗算部３０６に出力する。そして、スカラ・行列乗算部３０６は、スカラ乗算部３０７からの出力を、行列Ｗの第（ｉ，ｊ）要素に設定する。
【０２７７】
次に、ステップＳ２１５でスカラ・行列乗算部３０６は、インデックス変数ｊの値が次数ｎに等しいか否かを判定する。
【０２７８】
もしｊ≠ｎであれば（具体的にはｊ＜ｎであれば）、行列Ｗのｉ行目中に値が未定の要素が残っている。よって、処理はステップＳ２１６に移行する。
【０２７９】
逆に、もしｊ＝ｎであれば、行列Ｗのｉ行目のｎ個の要素の値はすべて計算済みである。よって、処理はステップＳ２１７に移行する。
【０２８０】
ステップＳ２１６でスカラ・行列乗算部３０６は、インデックス変数ｊを１だけインクリメントする。そして、処理はステップＳ２１３に戻る。
【０２８１】
また、ステップＳ２１７でスカラ・行列乗算部３０６は、インデックス変数ｉの値が次数ｎに等しいか否かを判定する。
【０２８２】
もしｉ≠ｎであれば（具体的にはｉ＜ｎであれば）、行列Ｗの中に、各要素の値が未定の行が残っている。よって、処理はステップＳ２１８に移行する。
【０２８３】
逆に、もしｉ＝ｎであれば、行列Ｗのｎ×ｎ個の要素の値はすべて計算済みである。よって、処理はステップＳ２１９に移行する。
【０２８４】
ステップＳ２１８でスカラ・行列乗算部３０６は、インデックス変数ｉを１だけインクリメントする。そして、処理はステップＳ２１２に戻る。
【０２８５】
他方、ステップＳ２１９でスカラ・行列乗算部３０６は、制御部３０２に行列Ｗを出力する。
【０２８６】
すると、ステップＳ２２０で制御部３０２は、以下の情報を引数として探索部３０８に入力する。
・スカラ・行列乗算部３０６から出力された行列Ｗ
・入出力部３０１から入力された次数ｎ
・入出力部３０１から入力された平文空間サイズｓ
【０２８７】
続いて、ステップＳ２２１〜Ｓ２２９で探索部３０８は、行列Ｗの要素の中に平文空間サイズｓと互いに素な要素ｗが存在するか否かを判定する。
【０２８８】
具体的には、ステップＳ２２１で探索部３０８は、インデックス変数ｉを１に初期化する。
【０２８９】
次に、ステップＳ２２２で探索部３０８は、インデックス変数ｊを１に初期化する。
【０２９０】
そして、ステップＳ２２３で探索部３０８は、以下の２つの値をＧＣＤ計算部３０９に引数として入力する。
・制御部３０２から入力された行列Ｗの第（ｉ，ｊ）要素
・制御部３０２から入力された平文空間サイズｓ
【０２９１】
すると、ステップＳ２２４でＧＣＤ計算部３０９は、入力された２つの値の最大公約数（ＧＣＤ）を計算し、計算した最大公約数を探索部３０８に出力する。ＧＣＤ計算部３０９は、例えば、ユークリッドの互除法（Euclidean algorithm）により最大公約数を計算してもよい。
【０２９２】
次に、ステップＳ２２５で探索部３０８は、ＧＣＤ計算部３０９から出力された最大公約数が１か否かを判定する。
【０２９３】
最大公約数が１の場合、行列Ｗの第（ｉ，ｊ）要素は平文空間サイズｓと互いに素である。つまり、最大公約数が１の場合、行列Ｗの中には、平文空間サイズｓと互いに素な要素が存在するから、図２を参照しながら説明した「第３の条件」が成立する。よって、この場合、処理はステップＳ２３０に移行する。
【０２９４】
逆に、最大公約数が１でない場合は、平文空間サイズｓと互いに素な要素の探索を続行するために、処理はステップＳ２２６に移行する。
【０２９５】
ステップＳ２２６で探索部３０８は、インデックス変数ｊの値が次数ｎに等しいか否かを判定する。
【０２９６】
もしｊ≠ｎであれば（具体的にはｊ＜ｎであれば）、行列Ｗのｉ行目中には、「平文空間サイズｓと互いに素か否か」に関して未調査の要素が残っている。よって、処理はステップＳ２２７に移行する。
【０２９７】
逆に、もしｊ＝ｎであれば、行列Ｗのｉ行目の要素はどれも平文空間サイズｓと互いに素ではない。よって、処理はステップＳ２２８に移行する。
【０２９８】
ステップＳ２２７で探索部３０８は、インデックス変数ｊを１だけインクリメントする。そして、処理はステップＳ２２３に戻る。
【０２９９】
また、ステップＳ２２８で探索部３０８は、インデックス変数ｉの値が次数ｎに等しいか否かを判定する。
【０３００】
もしｉ≠ｎであれば（具体的にはｉ＜ｎであれば）、行列Ｗの中に、未調査の行が残っている。よって、処理はステップＳ２２９に移行する。
【０３０１】
逆に、もしｉ＝ｎであれば、行列Ｗのｎ×ｎ個の要素はどれも平文空間サイズｓと互いに素ではない。この場合は、第１実施形態の図１のステップＳ４と同様の高速な復号の適用対象外である。つまり、この場合、行列Ｖは、高速な復号を可能とする秘密鍵として適切な行列ではない。したがって、この場合、探索部３０８は、制御部３０２に「平文空間サイズｓと互いに素な要素が行列Ｗ中に存在しない」と通知する。そして、別の新たな行列を秘密鍵の候補として検討するために、処理はステップＳ２０２に戻る。
【０３０２】
ステップＳ２２９で探索部３０８は、インデックス変数ｉを１だけインクリメントする。そして、処理はステップＳ２２２に戻る。
【０３０３】
さて、ステップＳ２３０が実行されるのは、「高速な復号を可能とする秘密鍵として行列Ｖが適切である」ということが判明した場合である。換言すれば、以下の３つの条件がすべて成り立つことが判明した場合に、ステップＳ２３０が実行される。
・第１の条件：生成されたｎ個の整数ｖ０，…，ｖｎ−１により定義されるｎ次正方行列Ｖに、逆行列Ｖ−１が存在する。
・第２の条件：式（６）のようなエルミート標準形の行列Ｂが、行列Ｖから導出される。
・第３の条件：行列Ｗ＝ｄＶ−１のｎ×ｎ個の要素の中に、平文空間サイズｓと互いに素な要素が存在する。
【０３０４】
上記の３つの条件が成り立つ場合、秘密鍵の候補たる行列Ｖは、秘密鍵として適切であり、公開鍵の候補たる行列Ｂは、公開鍵として適切である。よって、制御部３０２は、行列Ｖを秘密鍵と定め、行列Ｂを公開鍵と定める。具体的には、ステップＳ２３０では、以下のような処理が行われる。
【０３０５】
まず、探索部３０８が、行列Ｗの第（ｉ，ｊ）要素ｗを制御部３０２に出力する。つまり、探索部３０８は、平文空間サイズｓと互いに素であることがステップＳ２２５で判明した要素ｗを、制御部３０２に出力する。
【０３０６】
すると、制御部３０２は、以下の２つの値を引数として逆元計算部３１０に入力する。
・探索部３０８から出力された要素ｗ
・入出力部３０１から入力された平文空間サイズｓ
【０３０７】
次に、ステップＳ２３１で逆元計算部３１０は、法ｓのもとでの値ｗの逆数ｗ−１を計算する。ステップＳ２３１が実行される場合、２つの値ｗとｓは互いに素なので、法ｓのもとで値ｗには逆数ｗ−１が存在する。したがって、逆元計算部３１０は、逆数ｗ−１を得ることができる。
【０３０８】
逆元計算部３１０は、逆数ｗ−１を制御部３０２に出力する。すると、制御部３０２は、以下の４つの値を記憶部３１１に記憶する。
・入出力部３０１から入力された平文空間サイズｓ
・ＨＮＦ計算部３０５から出力された行列Ｂの、行列式ｄ（すなわち、公開鍵Ｂの第（１，１）要素）
・探索部３０８から出力された要素ｗ（すなわち、行列Ｗ＝ｄＶ−１中で、平文空間サイズｓと互いに素な要素）
・逆元計算部３１０から出力された逆数ｗ−１
【０３０９】
さらに、次のステップＳ２３２で制御部３０２は、入出力部３０１を介して公開鍵Ｂを公開する。例えば、情報処理装置３００が図２のコンピュータ１００である場合、入出力部３０１が、ネットワーク１２０を介して公開鍵Ｂをコンピュータ１４０に送信することで、公開鍵Ｂを公開してもよい。もちろん、情報処理装置３００は、任意のタイミングで、任意の他の装置からの要求に応じて、公開鍵Ｂを要求元の装置に送信してもよい。
【０３１０】
その後、制御部３０２は、ステップＳ２３３に示すように、暗号文の入力を受け取るまで待つ。そして、制御部３０２が暗号文の入力を受け取ると、処理はステップＳ２３４に移行する。
【０３１１】
ステップＳ２３４では、受け取った暗号文を復号するための復号処理が行われる。復号処理の詳細は図１１とともに後述する。復号処理が終了すると、図８〜１０の処理はステップＳ２３３に戻る。
【０３１２】
なお、制御部３０２が受け取る暗号文は、具体的には、第１要素以外はすべて０のｎ次元ベクトル
2014102398.tif 000142
であってもよいし、当該ｎ次元ベクトル
2014102398.tif 000143
の第１要素ｃであってもよい。制御部３０２は、ｎ次元ベクトルを暗号文として受け取った場合は、第１要素ｃを抽出して、抽出した第１要素ｃを暗号文として用いて、ステップＳ２３４の復号処理を開始する。
【０３１３】
また、制御部３０２が受け取る暗号文は、１つの平文から得られたものでもよいし、複数の平文から得られたものでもよい。
【０３１４】
具体的には、制御部３０２は、ある装置（例えば図２のコンピュータ１４０）が、公開鍵Ｂを用いて、ある１つの平文（具体的には０以上ｓ未満の整数）を暗号化することにより得られた暗号文を、入出力部３０１を介して受け取ってもよい。あるいは、制御部３０２は、複数の暗号文に対するある演算の結果として得られる１つの暗号文を、入出力部３０１を介して受け取ってもよい（第２実施形態における公開鍵Ｂによる暗号化関数が準同型であることに注意されたい）。
【０３１５】
例えば、各々が０以上ｓ未満の整数であるＭ個（Ｍ≧２）の平文を、公開鍵Ｂを用いてそれぞれ暗号化して得られたＭ個の暗号文に対して、それらＭ個の暗号文を復号せずに、ある装置がある演算を行ってもよい。Ｍ個の暗号文は、例えば、１台の装置がＭ個の平文をそれぞれ暗号化することで得られたものであってもよいし、Ｍ台の装置の各々が１つの平文を暗号化することで得られたものであってもよい。
【０３１６】
いずれにせよ、Ｍ個の暗号文が存在する場合、Ｍ個の暗号文に対してある演算が行われてもよい。当該演算は、例えば、加算でもよいし、所定回数以下の乗算でもよいし、加算と所定回数以下の乗算との組み合わせであってもよい。
【０３１７】
また、Ｍ個の暗号文に対して当該演算を行う装置は、平文を暗号化する装置と同じでもよいし、別の装置でもよい。場合によっては、情報処理装置３００自体が、ネットワーク１２０を介してＭ個の暗号文を受信し、Ｍ個の暗号文に対してある演算を実行し、演算結果を制御部３０２に出力してもよい。
【０３１８】
いずれにせよ、Ｍ個の暗号文に対するある演算の結果として、１つの暗号文が得られる場合がある。こうして得られた１つの暗号文を制御部３０２が受け取ってもよい。
【０３１９】
さて、図１１は、図１０のステップＳ２３４の復号処理の詳細を示すフローチャートである。図１１の復号処理は、第２実施形態と第３実施形態に共通である。上記のとおり、図１１の復号処理は、ｎ次元ベクトル
2014102398.tif 000144
の第１要素ｃに対して実行される。
【０３２０】
ステップＳ３０１で制御部３０２は、記憶部３１１から、以下の４つの値を読み出し、読み出した４つの値と暗号文ｃを、復号部３１２に引数として入力する。
・行列Ｗ＝ｄＶ−１中で、平文空間サイズｓと互いに素な要素ｗ
・その逆数ｗ−１
・平文空間サイズｓ
・公開鍵Ｂの行列式ｄ
【０３２１】
次に、ステップＳ３０２で復号部３１２は、スカラ乗算部３０７に以下の２つの値を引数として入力する。
・制御部３０２から入力された暗号文ｃ
・制御部３０２から入力された値ｗ
【０３２２】
すると、ステップＳ３０３でスカラ乗算部３０７は、入力された２つの値の積（ｃ×ｗ）を計算し、計算した積（ｃ×ｗ）を復号部３１２に出力する。
【０３２３】
そして、ステップＳ３０４で復号部３１２は、以下の２つの値を第１モジュロ演算部３１３に引数として入力する。
・スカラ乗算部３０７から出力された値（ｃ×ｗ）
・制御部３０２から入力された値ｄ
【０３２４】
すると、ステップＳ３０５で第１モジュロ演算部３１３は、入力された２つの値から、値［ｃ×ｗ］ｄを計算し、計算した値［ｃ×ｗ］ｄを復号部３１２に出力する。つまり、第１モジュロ演算部３１３は、式（５）のように定義される演算を実行する。
【０３２５】
次に、ステップＳ３０６で復号部３１２は、スカラ乗算部３０７に以下の２つの値を引数として入力する。
・第１モジュロ演算部３１３から出力された値［ｃ×ｗ］ｄ
・制御部３０２から入力された値ｗ−１
【０３２６】
すると、ステップＳ３０７でスカラ乗算部３０７は、入力された２つの値の積（［ｃ×ｗ］ｄ×ｗ−１）を計算し、計算した積（［ｃ×ｗ］ｄ×ｗ−１）を復号部３１２に出力する。
【０３２７】
そして、ステップＳ３０８で復号部３１２は、以下の２つの値を第２モジュロ演算部３１４に引数として入力する。
・スカラ乗算部３０７から出力された値（［ｃ×ｗ］ｄ×ｗ−１）
・制御部３０２から入力された値ｓ
【０３２８】
すると、ステップＳ３０９で第２モジュロ演算部３１４は、入力された２つの値から余りを計算する。第２モジュロ演算部３１４は、任意の２つの整数ｚ１とｚ２の入力を受け取ると（ただしｚ２≠０）、ｚ１の法ｚ２による余りを計算するコンポーネントである。よって、ステップＳ３０９で第２モジュロ演算部３１４は、具体的には、以下に再掲する式（４）の値ｂを計算する。
ｂ＝［ｃ×ｗ］ｄ×ｗ−１  ｍｏｄ  ｓ        （４）
【０３２９】
そして、第２モジュロ演算部３１４は、計算した値ｂを復号部３１２に出力する。すると、ステップＳ３１０で復号部３１２は、値ｂを制御部３０２に出力する。こうして出力される値ｂは、暗号文ｃに対応する平文である。
【０３３０】
最後に、ステップＳ３１１で制御部３０２は、復号部３１２から出力された平文ｂを、入出力部３０１を介して出力する。そして、図１１の復号処理は終了する。
【０３３１】
ところで、以上説明した第２実施形態は、第１実施形態の図１と以下のように対応する。
【０３３２】
第２実施形態では、ステップＳ２０１〜Ｓ２２９での鍵生成の過程（より詳しくは、「第３の条件が成立するか否か」に関するステップＳ２２１〜Ｓ２２９でのチェックの過程）において、値ｗを探索する処理が行われる。そして、見つかった値ｗは、ステップＳ２３１において記憶部３１１に記憶される。
【０３３３】
したがって、第２実施形態では、新たな暗号文が入力されるたびに行われる図１１の復号処理の中で（より具体的には、図１のステップＳ２に対応するステップＳ３０１において）、制御部３０２は、記憶部３１１から値ｗを取得することが可能である。つまり、図１のステップＳ２における値ｗの取得は、直接的には図１１のステップＳ３０１に対応し、間接的にはステップＳ２２０〜Ｓ２２９の処理に基づく。別の観点から見れば、図１のステップＳ２での値ｗの取得は、第２実施形態では、鍵生成フェーズでのステップＳ２２０〜Ｓ２２９の探索処理と、復号フェーズでのステップＳ３０１の読み取り処理を含む。
【０３３４】
また、第２実施形態では、鍵生成が終了すると（換言すれば、第１〜第３の条件を満たす秘密鍵Ｖが見つかると）、ステップＳ２３１で値ｗの逆数ｗ−１が計算され、記憶部３１１に記憶される。
【０３３５】
したがって、第２実施形態では、新たな暗号文が入力されるたびに行われる図１１の復号処理の中で（より具体的には、図１のステップＳ３にも対応するステップＳ３０１において）、制御部３０２は、記憶部３１１から逆数ｗ−１を取得することが可能である。つまり、図１のステップＳ３における逆数ｗ−１の取得は、直接的には図１１のステップＳ３０１に対応し、間接的にはステップＳ２３１での計算に基づく。別の観点から見れば、図１のステップＳ３での逆数ｗ−１の取得は、第２実施形態では、ステップＳ２３１での計算と、ステップＳ３０１の読み取り処理を含む。
【０３３６】
また、第２実施形態では、図１のステップＳ４が、具体的には図１１のステップＳ３０２〜Ｓ３０９に対応する。つまり、第２実施形態では、ステップＳ４の処理が以下の演算を含む。
・ステップＳ３０３での値ｃと値ｗの乗算
・ステップＳ３０５での法ｄによる剰余演算
・ステップＳ３０７での値［ｃ×ｗ］ｄと逆数ｗ−１との乗算
・ステップＳ３０９での法ｓによる剰余演算
【０３３７】
しかし、実施形態によっては、乗算と剰余演算の組み合わせの代わりに、モンゴメリ乗算剰余演算が行われてもよい。例えば、情報処理装置３００は、モンゴメリ乗算剰余演算のためのハードウェア回路を有していてもよい。あるいは、情報処理装置３００がコンピュータ１００により実現され、コンピュータ１００内のプロセッサ１０１が、モンゴメリ乗算剰余演算のためのプログラムモジュールを実行してもよい。
【０３３８】
また、実施形態によっては、制御部３０２は、ステップＳ２３１で値ｗの代わりに、秘密鍵Ｖそのものか、秘密鍵Ｖを規定するｎ個の乱数ｖ０，…，ｖｎ−１の組を記憶部３１１に記憶してもよい。この場合、情報処理装置３００は、新たな暗号文が入力されるたびに、記憶部３１１に記憶されている情報を用いて、以下の処理を実行し、それにより値ｗを取得してもよい。つまり、情報処理装置３００が、復号のたびに、図１のステップＳ２に対応する処理として以下の処理を実行するような実施形態も可能である。
・ステップＳ２０４〜Ｓ２０５と同様の逆行列Ｖ−１の計算。
・ステップＳ２１０〜Ｓ２１９と同様の行列Ｗの計算。
・ステップＳ２２０〜Ｓ２２９と同様の探索。
【０３３９】
また、実施形態によっては、制御部３０２は、ステップＳ２３１で値ｗの代わりに、秘密鍵Ｖの逆行列Ｖ−１を記憶部３１１に記憶してもよい。この場合、情報処理装置３００は、新たな暗号文が入力されるたびに、記憶部３１１に記憶されている逆行列Ｖ−１を用いて、以下の処理を実行し、それにより値ｗを取得してもよい。つまり、情報処理装置３００が、復号のたびに、図１のステップＳ２に対応する処理として以下の処理を実行するような実施形態も可能である。
・ステップＳ２１０〜Ｓ２１９と同様の行列Ｗの計算。
・ステップＳ２２０〜Ｓ２２９と同様の探索。
【０３４０】
また、実施形態によっては、制御部３０２は、ステップＳ２３１で値ｗの代わりに、行列Ｗを記憶部３１１に記憶してもよい。この場合、情報処理装置３００は、新たな暗号文が入力されるたびに、記憶部３１１に記憶されている行列Ｗを用いて、ステップＳ２２０〜Ｓ２２９と同様の探索を実行し、それにより値ｗを取得してもよい。つまり、情報処理装置３００が、復号のたびに、図１のステップＳ２に対応する処理としてステップＳ２２０〜Ｓ２２９と同様の探索を実行するような実施形態も可能である。
【０３４１】
しかし、第２実施形態では、復号処理の効率化および高速化のために、ステップＳ２３１で値ｗが記憶部３１１に記憶され、記憶された値ｗがステップＳ３０１で読み取られる。
【０３４２】
また、逆数ｗ−１がステップＳ２３１で予め計算されないような実施形態も可能である。つまり、新たな暗号文が入力されるたびに、制御部３０２が逆元計算部３１０に逆数ｗ−１の計算を命じてもよく、逆元計算部３１０が逆数ｗ−１を計算してもよい。つまり、情報処理装置３００が、復号のたびに、図１のステップＳ３に対応する処理としてステップＳ２３１と同様の計算を実行するような実施形態も可能である。
【０３４３】
しかし、第２実施形態では、復号処理の効率化および高速化のために、ステップＳ２３１で予め逆数ｗ−１が計算されて記憶部３１１に記憶される。
【０３４４】
ところで、第２実施形態では、ステップＳ２１０〜Ｓ２１９に示すように、行列Ｗのｎ２個の要素がすべて計算される。そして、第２実施形態では、ステップＳ２２０〜Ｓ２２９に示すように、場合によっては、行列Ｗのｎ２個の要素すべてについて、「平文空間サイズｓと互いに素か否か」が判定されることがあり得る。
【０３４５】
しかし、処理の一層の効率化のために、式（２９）に示すような行列Ｗの規則性が利用されてもよい。例えば、制御部３０２は、スカラ・行列乗算部３０６に、行列Ｗの任意の１行のｎ個の要素または任意の１列のｎ個の要素のみを計算させてもよい。そして、制御部３０２は、探索部３０８に、それらの計算されたｎ個の要素の中から平文空間サイズｓと互いに素な要素を探索させてもよい。
【０３４６】
例えば、ステップＳ２１７とＳ２１８が省略されてもよい。その場合、ステップＳ２１５でｊ＝ｎならば、処理はステップＳ２１９に移行する。このような変形により、制御部３０２は、スカラ・行列乗算部３０６に、行列Ｗの第１行のｎ個の要素のみを計算させてもよい。
【０３４７】
そして、ステップＳ２２８とＳ２２９が省略されてもよい。その場合、ステップＳ２２６でｊ＝ｎならば、処理はステップＳ２０２に戻る。このような変形により、制御部３０２は、探索部３０８に、行列Ｗの第１行のｎ個の要素の中から平文空間サイズｓと互いに素な要素を探索させてもよい。
【０３４８】
続いて、第２実施形態に関する数値例を説明する。
図８のステップＳ２０１で、制御部３０２が入出力部３０１から以下のような入力を受け取るものとする。
・ｔ＝７
・ｎ＝４
・ｓ＝５
【０３４９】
また、ステップＳ２０３では、乱数生成部３０３が以下のような乱数を生成するものとする。これらの４つの乱数の絶対値は、いずれも、ｔビット以下である。つまり、これらの４つの乱数の絶対値は、いずれも、１２７（＝２７−１）以下である。
・ｖ０＝１１２
・ｖ１＝９９
・ｖ２＝−１２５
・ｖ３＝８１
【０３５０】
この場合、ステップＳ２０４で逆行列計算部３０４に入力される行列Ｖは、式（３６）のとおりである。
【数２７】
2014102398.tif 000145
【０３５１】
よって、ステップＳ２０５では、逆行列計算部３０４が式（３７）の逆行列Ｖ−１を制御部３０２に出力する。つまり、式（３６）の行列Ｖには逆行列Ｖ−１が存在する。よって、処理はステップＳ２０６からステップＳ２０７へと移行する。
【数２８】
2014102398.tif 000146
【０３５２】
そして、ステップＳ２０８では、ＨＮＦ計算部３０５が式（３８）の行列Ｂを制御部３０２に出力する。式（３８）の行列Ｂは式（６）の形式なので、処理はステップＳ２０９からステップＳ２１０へと移行する。
【数２９】
2014102398.tif 000147
【０３５３】
なお、式（３８）より、ｄ＝１１４３８２１４４９である。よって、ステップＳ２１０での逆行列Ｖ−１と次数ｎと行列Ｂの行列式ｄの入力に応じて、スカラ・行列乗算部３０６は、ステップＳ２１１〜Ｓ２１８で、式（３９）の行列Ｗを計算する。
【数３０】
2014102398.tif 000148
【０３５４】
そして、スカラ・行列乗算部３０６は、ステップＳ２１９で式（３９）の行列Ｗを出力する。例えば式（３９）に例示されるとおり、行列Ｗには式（２９）のような規則性がある。
【０３５５】
その後、ステップＳ２２０での制御部３０２からの命令に応じて、探索部３０８は、行列Ｗ中で平文空間サイズｓ（＝５）と互いに素な要素を探す。式（３９）より、行列Ｗの第（１，１）要素が平文空間サイズｓと互いに素である。
【０３５６】
よって、ｉ＝１かつｊ＝１のときに、処理がステップＳ２２５からステップＳ２３０へと進む。そして、ステップＳ２３０で探索部３０８は、行列Ｗの第（１，１）要素（すなわち、５３５６１８４という値）を制御部３０２に出力する。すると、制御部３０２は、以下の２つの値を逆元計算部３１０に入力する。
・ｗ＝５３５６１８４
・ｓ＝５
【０３５７】
そして、ステップＳ２３１で逆元計算部３１０は、法ｓのもとでの値ｗの逆数ｗ−１を、以下の式（４０）に示すように計算する。
ｗ−１＝４  （ｍｏｄ  ５）      （４０）
【０３５８】
ステップＳ２３１ではさらに、逆元計算部３１０が逆数ｗ−１（＝４）を制御部３０２に出力する。すると、制御部３０２は以下の４つの値を記憶部３１１に記憶する。
・ｓ＝５
・ｄ＝１１４３８２１４４９
・ｗ＝５３５６１８４
・ｗ−１＝４
【０３５９】
また、ステップＳ２３２では式（３８）の行列Ｂが公開鍵として公開される。
【０３６０】
その後、例えば、式（４１）のｎ次元ベクトル
2014102398.tif 000149
が暗号文として入力されたとする。
【数３１】
2014102398.tif 000150
【０３６１】
すると、制御部３０２は式（４１）のベクトル
2014102398.tif 000151
の第１要素ｃ（＝７３９６４０１５）を抽出し、図１１の復号処理を開始する。つまり、図１１のステップＳ３０１では、制御部３０２が復号部３１２に以下の５つの値を入力する。
・ｗ＝５３５６１８４
・ｗ−１＝４
・ｓ＝５
・ｄ＝１１４３８２１４４９
・ｃ＝７３９６４０１５
【０３６２】
すると、ステップＳ３０２では、復号部３１２が、スカラ乗算部３０７に値ｃと値ｗを入力する。そして、ステップＳ３０３では、スカラ乗算部３０７が、式（４２）のように値ｃと値ｗの積（ｃ×ｗ）を計算し、この積を復号部３１２に出力する。
ｃ×ｗ＝７３９６４０１５×５３５６１８４
＝３９６１６４８７３７１８７６０        （４２）
【０３６３】
すると、ステップＳ３０４では、復号部３１２が、式（４２）の値（ｃ×ｗ）と上記の値ｄを第１モジュロ演算部３１３に入力する。そして、ステップＳ３０５では、第１モジュロ演算部３１３が、式（４３）のように値［ｃ×ｗ］ｄを計算し、この値を復号部３１２に出力する。
［ｃ×ｗ］ｄ＝［３９６１６４８７３７１８７６０］１１４３８２１４４９
＝２７２１４７１２                                    （４３）
【０３６４】
すると、ステップＳ３０６では、復号部３１２が、式（４３）の値［ｃ×ｗ］ｄと上記の値ｗ−１をスカラ乗算部３０７に入力する。そして、ステップＳ３０７では、スカラ乗算部３０７が、式（４４）のように値（［ｃ×ｗ］ｄ×ｗ−１）を計算し、この値を復号部３１２に出力する。
［ｃ×ｗ］ｄ×ｗ−１＝２７２１４７１２×４
＝１０８８５８８４８          （４４）
【０３６５】
すると、ステップＳ３０８で復号部３１２が、式（４４）の値（［ｃ×ｗ］ｄ×ｗ−１）と上記の値ｓを第２モジュロ演算部３１４に入力する。そして、ステップＳ３０９では、第２モジュロ演算部３１４が、式（４５）のように値ｂを計算し、値ｂを復号部３１２に出力する。
ｂ＝［ｃ×ｗ］ｄ×ｗ−１  ｍｏｄ  ｓ
＝１０８８５８８４８  ｍｏｄ  ５
＝３                                  （４５）
【０３６６】
そして、平文ｂ（＝３）は、ステップＳ３１０で復号部３１２から制御部３０２に出力され、ステップＳ３１１で制御部３０２から入出力部３０１を介して出力される。
【０３６７】
以上説明したように、第２実施形態でも、第１実施形態と同様に、「平文空間が拡張されている」という利点と、「乗算の回数が少ないので復号が高速である」という利点が両立している。
【０３６８】
続いて、第３実施形態について説明する。図１２は、第３実施形態の復号装置４００のブロック構成図である。
【０３６９】
図１２の復号装置４００は、入出力部４０１、制御部４０２、記憶部４０３、復号部４０４、第１モジュロ演算部４０５、第２モジュロ演算部４０６、およびスカラ乗算部４０７を有する。復号装置４００は、具体的には図２のコンピュータ１００により実現されてもよい。
【０３７０】
入出力部４０１は、復号装置４００への入力インタフェイスとして動作し、復号装置４００からの出力インタフェイスとしても動作する。例えば、入力インタフェイスとしての入出力部４０１は、通信インタフェイス１０３と入力装置１０４の一方または双方により実現されてもよい。また、出力インタフェイスとしての入出力部４０１は、通信インタフェイス１０３と出力装置１０５の一方または双方により実現されてもよい。場合によっては、不揮発性記憶装置１０６とプロセッサ１０１との間のデータ入出力インタフェイス（例えばディスクコントローラ）により入出力部４０１が実現されてもよい。
【０３７１】
制御部４０２は復号を制御する。制御部４０２は、例えば、プロセッサ１０１により実現されてもよい。
【０３７２】
第３実施形態では、具体的には、制御部４０２は、第１要素以外はすべて０のｎ次元ベクトル
2014102398.tif 000152
または当該ベクトル
2014102398.tif 000153
の第１要素ｃを暗号文として受け取る。制御部４０２は、ベクトル
2014102398.tif 000154
を受け取った場合には第１要素ｃを抽出する。そして、制御部４０２は、暗号文として受け取ったか、または上記のようにして抽出した値ｃに対して、図１１の復号処理を開始する。
【０３７３】
記憶部４０３は、第２実施形態の記憶部３１１と類似であり、不揮発性記憶装置１０６により実現されてもよい。具体的には、記憶部４０３は、復号に使うための情報（具体的には以下の４つの値）を記憶する。
・行列Ｗ＝ｄＶ−１中で、平文空間サイズｓと互いに素な要素ｗ
・その逆数ｗ−１
・平文空間サイズｓ
・公開鍵Ｂの行列式ｄ
【０３７４】
第３実施形態では、復号装置４００は、復号装置４００以外の他の装置（例えば、鍵生成装置としての図２のコンピュータ１３０）から、セキュアな暗号化通信路を介して上記の４つの値を受信してもよい。そして、そのようにして復号装置４００が受信した値が、記憶部４０３に記憶されていてもよい。
【０３７５】
あるいは、復号装置４００自身が、一旦、上記の要素ｗの探索と逆数ｗ−１の計算を行ってもよい。例えば、復号装置４００は、鍵生成装置（例えば図２のコンピュータ１３０）から、セキュアな通信路を介して、秘密鍵Ｖ（または秘密鍵Ｖを規定するｎ個の値ｖ０，ｖ１，…，ｖｎ−１）を受信してもよい。そして、復号装置４００は、図７の逆行列計算部３０４、スカラ・行列乗算部３０６、スカラ乗算部３０７、探索部３０８、ＧＣＤ計算部３０９、および逆元計算部３１０と類似のモジュールをさらに有していてもよい。復号装置４００は、それらのモジュールにより、行列Ｗの計算と要素ｗの探索と逆数ｗ−１の計算を行ってもよい。
【０３７６】
上記の４つの値ｗ、ｗ−１、ｓ、ｄがどのような方法により復号装置４００に取得されるにせよ、記憶部４０３は、４つの値ｗ、ｗ−１、ｓ、ｄを記憶する。つまり、記憶部４０３は、図７の記憶部３１１と類似である。
【０３７７】
また、復号部４０４は、図７の復号部３１２と同様である。また、第１モジュロ演算部４０５は、図７の第１モジュロ演算部３１３と同様であり、第２モジュロ演算部４０６は、図７の第２モジュロ演算部３１４と同様である。そして、スカラ乗算部４０７は、図７のスカラ乗算部３０７と同様である。復号部４０４、第１モジュロ演算部４０５、第２モジュロ演算部４０６、およびスカラ乗算部４０７は、いずれも、例えば図２のプロセッサ１０１により実現されてもよい。
【０３７８】
次に、第３実施形態の復号装置４００の動作について、図１１を参照しながら説明する。
【０３７９】
制御部４０２は、ｎ次元ベクトル
2014102398.tif 000155
または当該ベクトル
2014102398.tif 000156
の第１要素ｃを暗号文として受け取ると、図１１の復号処理を開始する。制御部４０２は、ステップＳ３０１で記憶部４０３から４つの値ｗ、ｗ−１、ｓ、ｄを読み出し、それら４つの値と、暗号文としての値ｃを復号部４０４に入力する。
【０３８０】
すると、ステップＳ３０２で復号部４０４がスカラ乗算部４０７に２つの値ｃとｗを入力する。ステップＳ３０３では、スカラ乗算部４０７が乗算を実行し、得られた積を復号部４０４に出力する。
【０３８１】
そして、ステップＳ３０４で復号部４０４が値（ｃ×ｗ）と値ｄを第１モジュロ演算部４０５に入力する。ステップＳ３０５では、第１モジュロ演算部４０５が値［ｃ×ｗ］ｄを計算し、計算結果を復号部４０４に出力する。
【０３８２】
すると、ステップＳ３０６で復号部４０４が２つの値［ｃ×ｗ］ｄとｗ−１をスカラ乗算部４０７に入力する。ステップＳ３０７では、スカラ乗算部４０７が乗算を実行し、得られた積を復号部４０４に出力する。
【０３８３】
そして、ステップＳ３０８で復号部４０４が値（［ｃ×ｗ］ｄ×ｗ−１）と値ｓを第２モジュロ演算部４０６に入力する。ステップＳ３０９では、第２モジュロ演算部４０６が平文ｂを計算し、平文ｂを復号部４０４に出力する。
【０３８４】
すると、平文ｂは、ステップＳ３１０で復号部４０４から制御部４０２に出力され、ステップＳ３１１で制御部４０２から入出力部４０１を介して出力される。
【０３８５】
例えば、ｃ＝７３９６４０１５の場合、第２実施形態についての上記の数値例と同様に、第３実施形態においても、ｂ＝３という平文が出力される。
【０３８６】
以上説明したように、第３実施形態でも、第１〜第２実施形態と同様に、「平文空間が拡張されている」という利点と、「乗算の回数が少ないので復号が高速である」という利点が両立している。
【０３８７】
ところで、本発明は上記の第１〜第３実施形態に限られるものではない。上記の説明においてもいくつかの変形について説明したが、上記の第１〜第３実施形態は、例えば下記のように変形されてもよい。
【０３８８】
例えば、第２実施形態の情報処理装置３００は、鍵生成装置でもあり復号装置でもあるが、実施形態によっては、復号装置とは別の鍵生成装置が以下の処理を行ってもよい。
・ステップＳ２０１〜Ｓ２３２の処理。
・ステップＳ２３１で記憶部に記憶した４つの値ｓ，ｄ，ｗ，ｗ−１を、セキュアな暗号化通信路を介して、適宜のタイミングで復号装置に送信する処理。
【０３８９】
上記のように値ｓ，ｄ，ｗ，ｗ−１を送信する処理は、例えば、ステップＳ２３１の実行直後に行われてもよいし、復号装置からの要求に応じて行われてもよい。また、以上のような鍵生成装置と組み合わされて使われる復号装置は、具体的には、第３実施形態の復号装置４００であってもよい。
【０３９０】
また、鍵生成装置は、上記のように復号装置に値ｗとその逆数ｗ−１の双方を送信する代わりに、以下のいずれかの情報を復号装置に送信してもよい。なぜなら、復号装置は、以下のような情報を受信した場合、受信した情報から値ｗとその逆数ｗ−１の双方を取得することが可能だからである。
・秘密鍵Ｖを規定するｎ個の値ｖ０，ｖ１，…，ｖｎ−１の組
・秘密鍵Ｖ
・秘密鍵Ｖの逆行列Ｖ−１
・行列Ｗ＝ｄＶ−１
・行列Ｗ中の、任意の１行または任意の１列
・値ｗとその逆数ｗ−１のうちの一方
【０３９１】
また、図８〜１１に示したフローチャートにおいて、ステップの実行順序は、矛盾が生じない限り適宜入れ替えられてもよい。入れ替え可能なステップ同士は、並列に実行されてもよい。
【０３９２】
例えば、第２実施形態では、鍵生成の過程において、以下の３つの条件が成り立つか否かがチェックされる。具体的には、図８〜１０のフローチャートによれば、第１の条件がまずチェックされ、次に第２の条件がチェックされる。
・「秘密鍵の候補としての行列Ｖに逆行列Ｖ−１が存在する」という第１の条件。
・「行列Ｖのエルミート標準形たる行列Ｂが、式（６）の所定の形式である」という第２の条件。
・「行列Ｗ＝ｄＶ−１中に、平文空間サイズｓと互いに素な要素ｗが存在する」という第３の条件。
【０３９３】
しかし、実施形態によっては、第２の条件が第１の条件よりも先にチェックされてもよい。また、第１の条件と第２の条件が並列にチェックされてもよい。
【０３９４】
なお、図８〜１０中のいくつかのステップ（例えばステップＳ２０４など）では、次数ｎが引数として与えられる。しかし、情報処理装置３００が実行するプログラムの実装によっては、必ずしも次数ｎが明示的に引数として与えられない場合もあり得る（例えばある種のオブジェクト指向言語が使われる場合など）。
【０３９５】
最後に、上記の種々の実施形態に関して、さらに下記の付記を開示する。
（付記１）
コンピュータが、
第１要素以外はすべて０のｎ次元ベクトル
2014102398.tif 000157
であって、
ｎ個の整数ｖ０，…，ｖｎ−１を使って準同型暗号方式の秘密鍵として定義されるｎ次正則行列
2014102398.tif 000158
に対応する公開鍵として、前記行列Ｖのエルミート標準形である行列Ｂを用いて、０以上ｓ未満の整数である平文を暗号化した暗号文であるか、もしくは、
各々が０以上ｓ未満の整数である複数の平文を、前記行列Ｂを用いてそれぞれ暗号化して得られる複数の暗号文に対して、当該複数の暗号文を復号せずにある演算を行った結果である暗号文である
ことを特徴とするベクトル
2014102398.tif 000159
の入力を受け取るか、または、当該ベクトル
2014102398.tif 000160
の第１要素である値ｃの入力を受け取り、
前記行列Ｂの行列式ｄと前記行列Ｖの逆行列Ｖ−１により定義される行列Ｗ＝ｄＶ−１の要素のうちでｓと互いに素な要素ｗを取得し、
法ｓのもとでのｗの逆数ｗ−１を取得し、
ｃ×ｗ  ｍｏｄ  ｄを範囲［−ｄ／２，ｄ／２）に含まれるように調整した値［ｃ×ｗ］ｄを用いて、ｂ＝［ｃ×ｗ］ｄ×ｗ−１  ｍｏｄ  ｓを計算し、
計算した値ｂを、入力された前記ベクトル
2014102398.tif 000161
または入力された前記値ｃに対応する平文として、出力する
ことを特徴とする復号方法。
（付記２）
前記要素ｗを取得する処理は、
前記行列Ｖから前記逆行列Ｖ−１を計算し、
前記逆行列Ｖ−１を用いて、前記行列Ｗ中の少なくとも１行のｎ個の要素を計算するか、または、前記行列Ｗ中の少なくとも１列のｎ個の要素を計算し、
前記行列Ｗ中の計算した前記要素の中から、ｓと互いに素な要素を探して、見つかった要素を前記要素ｗとして取得する
ことを含み、
前記逆数ｗ−１を取得する処理は、見つかった前記要素ｗから前記逆数ｗ−１を計算する処理を含む
ことを特徴とする付記１に記載の復号方法。
（付記３）
前記要素ｗを取得する処理は、記憶装置を参照して、当該記憶装置に予め記憶されている前記要素ｗを読み出す処理を含み、
前記逆数ｗ−１を取得する処理は、前記記憶装置を参照して、前記記憶装置に予め記憶されている前記逆数ｗ−１を読み出す処理を含む
ことを特徴とする付記１に記載の復号方法。
（付記４）
前記値ｂを計算する処理は、モンゴメリ乗算剰余演算を含むことを特徴とする付記１から３のいずれか１項に記載の復号方法。
（付記５）
前記値ｂを計算する処理は、前記値ｃと前記要素ｗとの乗算と、法ｄによる剰余演算と、前記値［ｃ×ｗ］ｄと前記逆数ｗ−１との乗算と、法ｓによる剰余演算を含むことを特徴とする付記１から３のいずれか１項に記載の復号方法。
（付記６）
ｓが素数または２の冪乗数であることを特徴とする付記１から５のいずれか１項に記載の復号方法。
（付記７）
コンピュータに、
第１要素以外はすべて０のｎ次元ベクトル
2014102398.tif 000162
であって、
ｎ個の整数ｖ０，…，ｖｎ−１を使って準同型暗号方式の秘密鍵として定義されるｎ次正則行列
2014102398.tif 000163
に対応する公開鍵として、前記行列Ｖのエルミート標準形である行列Ｂを用いて、０以上ｓ未満の整数である平文を暗号化した暗号文であるか、もしくは、
各々が０以上ｓ未満の整数である複数の平文を、前記行列Ｂを用いてそれぞれ暗号化して得られる複数の暗号文に対して、当該複数の暗号文を復号せずにある演算を行った結果である暗号文である
ことを特徴とするベクトル
2014102398.tif 000164
の入力を受け取るか、または、当該ベクトル
2014102398.tif 000165
の第１要素である値ｃの入力を受け取り、
前記行列Ｂの行列式ｄと前記行列Ｖの逆行列Ｖ−１により定義される行列Ｗ＝ｄＶ−１の要素のうちでｓと互いに素な要素ｗを取得し、
法ｓのもとでのｗの逆数ｗ−１を取得し、
ｃ×ｗ  ｍｏｄ  ｄを範囲［−ｄ／２，ｄ／２）に含まれるように調整した値［ｃ×ｗ］ｄを用いて、ｂ＝［ｃ×ｗ］ｄ×ｗ−１  ｍｏｄ  ｓを計算し、
計算した値ｂを、入力された前記ベクトル
2014102398.tif 000166
または入力された前記値ｃに対応する平文として、出力する
ことを含む処理を実行させることを特徴とする復号プログラム。
（付記８）
第１要素以外はすべて０のｎ次元ベクトル
2014102398.tif 000167
であって、
ｎ個の整数ｖ０，…，ｖｎ−１を使って準同型暗号方式の秘密鍵として定義されるｎ次正則行列
2014102398.tif 000168
に対応する公開鍵として、前記行列Ｖのエルミート標準形である行列Ｂを用いて、０以上ｓ未満の整数である平文を暗号化した暗号文であるか、もしくは、
各々が０以上ｓ未満の整数である複数の平文を、前記行列Ｂを用いてそれぞれ暗号化して得られる複数の暗号文に対して、当該複数の暗号文を復号せずにある演算を行った結果である暗号文である
ことを特徴とするベクトル
2014102398.tif 000169
の入力を受け取るか、または、当該ベクトル
2014102398.tif 000170
の第１要素である値ｃの入力を受け取る暗号文受け取り部と、
前記行列Ｂの行列式ｄと前記行列Ｖの逆行列Ｖ−１により定義される行列Ｗ＝ｄＶ−１の要素のうちでｓと互いに素な要素ｗを取得する第１の取得部と、
法ｓのもとでのｗの逆数ｗ−１を取得する第２の取得部と、
ｃ×ｗ  ｍｏｄ  ｄを範囲［−ｄ／２，ｄ／２）に含まれるように調整した値［ｃ×ｗ］ｄを用いて、ｂ＝［ｃ×ｗ］ｄ×ｗ−１  ｍｏｄ  ｓを計算する計算部と、
前記計算部が計算した値ｂを、前記暗号文受け取り部が受け取った前記ベクトル
2014102398.tif 000171
または前記値ｃに対応する平文として出力する平文出力部と、
を備えることを特徴とする復号装置。
（付記９）
前記第１の取得部は、
前記行列Ｖから前記逆行列Ｖ−１を計算し、
前記逆行列Ｖ−１を用いて、前記行列Ｗ中の少なくとも１行のｎ個の要素を計算するか、または、前記行列Ｗ中の少なくとも１列のｎ個の要素を計算し、
前記行列Ｗ中の計算した前記要素の中から、ｓと互いに素な要素を探して、見つかった要素を前記要素ｗとして取得し、
前記第２の取得部は、前記第１の取得部が見つけた前記要素ｗから前記逆数ｗ−１を計算することにより、前記逆数ｗ−１を取得する
ことを特徴とする付記８に記載の復号装置。
（付記１０）
前記第１の取得部は、ネットワークを介して前記復号装置と接続された鍵生成装置から前記要素ｗを受信することにより、前記要素ｗを取得し、
前記第２の取得部は、前記鍵生成装置から前記逆数ｗ−１を受信することにより、前記逆数ｗ−１を取得する
ことを特徴とする付記８に記載の復号装置。
（付記１１）
前記復号装置が記憶部をさらに備え、
前記第１の取得部は、
一度取得した前記要素ｗを前記記憶部に記憶し、
前記記憶部に前記要素ｗが記憶済みの場合には、前記記憶部から前記要素ｗを読み出すことにより、前記要素ｗを取得し、
前記第２の取得部は、
一度取得した前記逆数ｗ−１を前記記憶部に記憶し、
前記記憶部に前記逆数ｗ−１が記憶済みの場合には、前記記憶部から前記逆数ｗ−１を読み出すことにより、前記前記逆数ｗ−１を取得する
ことを特徴とする付記９または１０に記載の復号装置。
（付記１２）
コンピュータが、
ｎ個の整数ｖ０，…，ｖｎ−１を生成し、
生成した前記ｎ個の整数ｖ０，…，ｖｎ−１に関して、
前記ｎ個の整数ｖ０，…，ｖｎ−１により定義されるｎ次正方行列
2014102398.tif 000172
に逆行列Ｖ−１が存在する、という第１の条件と、
１＜ｊ≦ｎなるすべてのｊについて第（１，ｊ）要素が０であり、１＜ｉ≦ｎかつ１＜ｊ≦ｎかつｉ≠ｊなるすべてのｉとｊについて第（ｉ，ｊ）要素が０であり、１＜ｉ≦ｎなるすべてのｉについて第（ｉ，ｉ）要素が１であるようなエルミート標準形の行列Ｂが、前記行列Ｖから導出される、という第２の条件と、
前記行列Ｂの行列式ｄと前記行列Ｖの前記逆行列Ｖ−１により定義される行列Ｗ＝ｄＶ−１のｎ×ｎ個の要素の中に、所定の正整数ｓと互いに素な要素が存在する、という第３の条件と、
が成り立つか否かを判定し、
前記第１の条件と前記第２の条件と前記第３の条件のすべてが成り立つような前記ｎ個の整数ｖ０，…，ｖｎ−１が得られるまで、前記ｎ個の整数ｖ０，…，ｖｎ−１の生成を繰り返し、
前記第１の条件と前記第２の条件と前記第３の条件のすべてが成り立つような前記ｎ個の整数ｖ０，…，ｖｎ−１が得られたら、０以上ｓ未満の整数の集合を平文空間とする準同型暗号方式における公開鍵として、前記行列Ｂを出力する
ことを特徴とする鍵生成方法。
（付記１３）
第１要素以外はすべて０のｎ次元ベクトル
2014102398.tif 000173
である暗号文から、０以上ｓ未満の整数である平文を得るための復号に使う情報として、
前記ｎ個の整数ｖ０，…，ｖｎ−１の組、
前記行列Ｖ、
前記逆行列Ｖ−１、
前記行列Ｗ、
前記行列Ｗの前記ｎ×ｎ個の要素の中で前記所定の正整数ｓとは互いに素な要素ｗ、
法ｓのもとでの前記要素ｗの逆数ｗ−１
のうちの少なくとも１つを、前記コンピュータが復号装置に送信する
ことを特徴とする付記１２に記載の鍵生成方法。
（付記１４）
コンピュータに、
ｎ個の整数ｖ０，…，ｖｎ−１を生成し、
生成した前記ｎ個の整数ｖ０，…，ｖｎ−１に関して、
前記ｎ個の整数ｖ０，…，ｖｎ−１により定義されるｎ次正方行列
2014102398.tif 000174
に逆行列Ｖ−１が存在する、という第１の条件と、
１＜ｊ≦ｎなるすべてのｊについて第（１，ｊ）要素が０であり、１＜ｉ≦ｎかつ１＜ｊ≦ｎかつｉ≠ｊなるすべてのｉとｊについて第（ｉ，ｊ）要素が０であり、１＜ｉ≦ｎなるすべてのｉについて第（ｉ，ｉ）要素が１であるようなエルミート標準形の行列Ｂが、前記行列Ｖから導出される、という第２の条件と、
前記行列Ｂの行列式ｄと前記行列Ｖの前記逆行列Ｖ−１により定義される行列Ｗ＝ｄＶ−１のｎ×ｎ個の要素の中に、所定の正整数ｓと互いに素な要素が存在する、という第３の条件と、
が成り立つか否かを判定し、
前記第１の条件と前記第２の条件と前記第３の条件のすべてが成り立つような前記ｎ個の整数ｖ０，…，ｖｎ−１が得られるまで、前記ｎ個の整数ｖ０，…，ｖｎ−１の生成を繰り返し、
前記第１の条件と前記第２の条件と前記第３の条件のすべてが成り立つような前記ｎ個の整数ｖ０，…，ｖｎ−１が得られたら、０以上ｓ未満の整数の集合を平文空間とする準同型暗号方式における公開鍵として、前記行列Ｂを出力する
ことを含む処理を実行させることを特徴とする鍵生成プログラム。
【符号の説明】
【０３９６】
１００、１３０、１４０、１５０  コンピュータ
１０１  プロセッサ
１０２  メモリ
１０３  通信インタフェイス
１０４  入力装置
１０５  出力装置
１０６  不揮発性記憶装置
１０７  駆動装置
１０８  バス
１１０  記憶媒体
１２０  ネットワーク
１６０  プログラム提供者
２００、４００  復号装置
２０１、３０１、４０１  入出力部
２０２、３０２、４０２  制御部
２０３、３０４  逆行列計算部
２０４  フレッシュ暗号文計算部
２０５  ベクトル・行列乗算部
２０６、３０７、４０７  スカラ乗算部
２０７  丸め部
２０８  減算部
２０９  モジュロ演算部
３００  情報処理装置
３０３  乱数生成部
３０５  ＨＮＦ計算部
３０６  スカラ・行列乗算部
３０８  探索部
３０９  ＧＣＤ計算部
３１０  逆元計算部
３１１、４０３  記憶部
３１２、４０４  復号部
３１３、４０５  第１モジュロ演算部
３１４、４０６  第２モジュロ演算部
【図１】
2014102398.tif 000192
【図２】
2014102398.tif 000193
【図３】
2014102398.tif 000194
【図４】
2014102398.tif 000195
【図５】
2014102398.tif 000196
【図６】
2014102398.tif 000197
【図７】
2014102398.tif 000198
【図８】
2014102398.tif 000199
【図９】
2014102398.tif 000200
【図１０】
2014102398.tif 000201
【図１１】
2014102398.tif 000202
【図１２】
2014102398.tif 000203