(57)【要約】      （修正有）【課題】並列度を上げて、計算の効率を向上させた共通鍵準同型暗号を提供する。【解決手段】共通鍵暗号装置は、記憶部、平文受付部、平文多項式生成部、マスク多項式生成部及び暗号化部を備えている。前記記憶部は、第１の多項式環の複数の要素で構成される共通鍵を記憶する。前記平文受付部は、平文情報の入力を受け付ける。前記平文多項式生成部は、前記入力を受け付けた平文情報を前記第１の多項式環の部分空間の多項式の少なくとも一つの項に埋め込むことにより、平文多項式を生成する。前記マスク多項式生成部は、前記第１の多項式環上で定義される第２の可換環に基づいて、前記共通鍵を解に含むマスク多項式を生成する。前記暗号化部は、前記平文多項式と前記マスク多項式とを用いて、暗号文を生成する。【選択図】図１
2015114629.tif 000002
【特許請求の範囲】
【請求項１】
第１の多項式環の複数の要素で構成される共通鍵を記憶する記憶部と、
平文情報の入力を受け付ける平文受付部と、
前記入力を受け付けた平文情報を前記第１の多項式環の部分空間の多項式の少なくとも一つの項に埋め込むことにより、平文多項式を生成する平文多項式生成部と、
前記第１の多項式環上で定義される第２の可換環に基づいて、前記共通鍵を解に含むマスク多項式を生成するマスク多項式生成部と、
前記平文多項式と前記マスク多項式とを用いて、暗号文を生成する暗号化部と、
を備える共通鍵暗号装置。
【請求項２】
請求項１に記載の共通鍵暗号装置において、
前記平文多項式生成部は、前記平文情報を複数の部分情報に加法的に分割し、前記複数の部分情報を前記平文多項式の各項の係数として埋め込む、共通鍵暗号装置。
【請求項３】
請求項１に記載の共通鍵暗号装置において、
前記平文多項式生成部、前記マスク多項式生成部及び前記暗号化部によって２つの平文多項式から個別に２つの暗号文が生成されたとき、当該２つの暗号文を互いに加算する準同型演算処理により、新たな暗号文を生成する準同型演算部を備え、
前記共通鍵に基づいて前記新たな暗号文を復号した結果は、前記２つの平文多項式を互いに加算した結果と等しい、共通鍵暗号装置。
【請求項４】
請求項１に記載の共通鍵暗号装置において、
前記マスク多項式は、前記多項式環上で定義される代数曲面を表す代数曲面多項式であり、
前記代数曲面は、ｘ，ｙの２変数を含む前記代数曲面多項式で表される零点の集合であり、前記ｘ，ｙがｔでパラメタライズされた曲線が存在し、
前記共通鍵は、前記曲線を表すセクション多項式である、共通鍵暗号装置。
【請求項５】
第１の多項式環の部分空間の多項式の少なくとも一つの項に平文情報を埋め込むことにより生成された平文多項式と、前記第１の多項式環の複数の要素で構成される共通鍵を解に含むマスク多項式であって前記第１の多項式環上で定義される第２の可換環に基づいて生成された前記マスク多項式と、を用いて生成された暗号文の入力を受け付ける暗号文受付部と、
前記共通鍵を記憶する記憶部と、
前記記憶部内の前記共通鍵に基づいて、前記暗号文から平文多項式を復号する平文多項式復号部と、
前記復号した平文多項式から前記平文情報を復号する復号部と、
を備える共通鍵復号装置。
【請求項６】
請求項５に記載の共通鍵復号装置において、
前記平文情報は複数の部分情報に加法的に分割され、前記複数の部分情報が前記平文多項式の各項に係数として埋め込まれており、
前記復号部は、前記復号された平文多項式の各項の係数を前記複数の部分情報として抽出し、当該複数の部分情報の総和を計算することにより前記平文情報を復号する、共通鍵復号装置。
【請求項７】
請求項５に記載の共通鍵復号装置において、
前記入力を受け付けた暗号文は、２つの平文多項式から個別に生成された２つの暗号文を互いに加算する準同型演算処理により生成されており、
前記復号部により復号された結果は、前記２つの平文多項式を互いに加算した結果と等しい、共通鍵復号装置。
【請求項８】
請求項５に記載の共通鍵復号装置において、
前記マスク多項式は、前記多項式環上で定義される代数曲面を表す代数曲面多項式であり、
前記代数曲面は、ｘ，ｙの２変数を含む前記代数曲面多項式で表される零点の集合であり、前記ｘ，ｙがｔでパラメタライズされた曲線が存在し、
前記共通鍵は、前記曲線を表すセクション多項式である、共通鍵復号装置。
【請求項９】
コンピュータを
第１の多項式環の複数の要素で構成される共通鍵を記憶する記憶手段と、
平文情報の入力を受け付ける平文受付手段と、
前記入力を受け付けた平文情報を前記第１の多項式環の部分空間の多項式の少なくとも一つの項に埋め込むことにより、平文多項式を生成する平文多項式生成手段と、
前記第１の多項式環上で定義される第２の可換環に基づいて、前記共通鍵を解に含むマスク多項式を生成するマスク多項式生成手段と、
前記平文多項式と前記マスク多項式とを用いて、暗号文を生成する暗号化手段
として機能させる共通鍵暗号プログラム。
【請求項１０】
コンピュータを、
第１の多項式環の部分空間の多項式の少なくとも一つの項に平文情報を埋め込むことにより生成された平文多項式と、前記第１の多項式環の複数の要素で構成される共通鍵を解に含むマスク多項式であって前記第１の多項式環上で定義される第２の可換環に基づいて生成された前記マスク多項式と、を用いて生成された暗号文の入力を受け付ける暗号文受付手段と、
前記共通鍵を記憶する記憶手段と、
前記記憶部内の前記共通鍵に基づいて、前記暗号文から平文多項式を復号する平文多項式復号手段と、
前記復号した平文多項式から前記平文情報を復号する復号手段
として機能させる共通鍵復号プログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明の実施形態は、共通鍵暗号装置及びプログラム、並びに、共通鍵復号装置及びプログラムに関する。
【背景技術】
【０００２】
通信内容を秘匿するために暗号化技術が用いられる。暗号化技術には、共通鍵暗号方式（Symmetric Encryption Scheme）及び公開鍵暗号（Asymmetric Encryption Scheme）がある。共通鍵暗号方式は、暗号化処理と復号処理において対称の秘密鍵を使用する。公開鍵暗号は、暗号化処理と復号処理において非対称な鍵（相異なる公開鍵及び秘密鍵）を使用する。
【０００３】
代表的な共通鍵暗号方式には、ＡＥＳ（Advanced Encryption Standard）がある。ＡＥＳは、高速に処理できるラウンド関数を繰り返し処理することで安全性の強度を高めている。但し、ＡＥＳは、後述する準同型性を有しない。
【０００４】
共通鍵暗号化方式Ｅｎｃは、以下を満たすときに準同型暗号（Homomorphic Encryption）と呼ばれる。秘密鍵sk及び２つの平文（plaintext）ｍ1，ｍ2に対応する２つの暗号文をｃ1＝Ｅｎｃ（sk，ｍ1）とｃ2＝Ｅｎｃ（sk，ｍ2）とする。平文ｍ1，ｍ2を復元することなく、２つの暗号文ｃ1，ｃ2から新たな暗号文ｃ’＝ｃ1（＊）ｃ2＝Ｅｎｃ（ｍ1（＋）ｍ2）を計算できるとき、暗号化方式Ｅｎｃは準同型暗号と呼ばれる。但し、（＊）と（＋）は演算子を表す。
【０００５】
演算子（＋）が加算を表すとき、暗号化方式Ｅｎｃは、加法的準同型暗号（Additive Homomorphic Encryption）と呼ばれる。演算子（＋）が乗算を表すとき、暗号化方式Ｅｎｃは、乗法的準同型暗号（Multiplicative Homomorphic Encryption）と呼ばれる。加法的及び乗法的の準同型性を実現する２種類の暗号文演算（＊）を有するとき、暗号化方式Ｅｎｃは、（ある程度）完全準同型暗号（（Somewhat） Fully Homomorphic Encryption）と呼ばれる。
【先行技術文献】
【非特許文献】
【０００６】
【非特許文献１】Michal Hojsik, Veronika Pulpanova, “A Fully Homomorphic Cryptosystem with Approximate Perfect Secrecy”, CT-RSA 2013, pp.375-388, LNCS 7779, Springer-Verlag
【発明の概要】
【発明が解決しようとする課題】
【０００７】
しかしながら、以上のような共通鍵暗号方式は、通常は特に問題ないが、本発明者の検討によれば、並列度を上げて、計算の効率を向上できる余地があると考えられる。
【０００８】
本発明が解決しようとする課題は、並列度を上げて、計算の効率を向上し得る共通鍵暗号装置及びプログラム、並びに、共通鍵復号装置及びプログラムを提供することである。
【課題を解決するための手段】
【０００９】
実施形態の共通鍵暗号装置は、記憶部、平文受付部、平文多項式生成部、マスク多項式生成部及び暗号化部を備えている。
【００１０】
前記記憶部は、第１の多項式環の複数の要素で構成される共通鍵を記憶する。
【００１１】
前記平文受付部は、平文情報の入力を受け付ける。
【００１２】
前記平文多項式生成部は、前記入力を受け付けた平文情報を前記第１の多項式環の部分空間の多項式の少なくとも一つの項に埋め込むことにより、平文多項式を生成する。
【００１３】
前記マスク多項式生成部は、前記第１の多項式環上で定義される第２の可換環に基づいて、前記共通鍵を解に含むマスク多項式を生成する。
【００１４】
前記暗号化部は、前記平文多項式と前記マスク多項式とを用いて、暗号文を生成する。
【図面の簡単な説明】
【００１５】
【図１】第１の実施形態に係る共通鍵暗号装置の構成を示す模式図である。
【図２】同実施形態における共通鍵復号装置の構成を示す模式図である。
【図３】同実施形態における暗号化処理を説明するためのフローチャートである。
【図４】同実施形態における復号処理を説明するためのフローチャートである。
【図５】第１の実施形態の変形例２に用いられる準同型演算装置の構成を示す模式図である。
【図６】同変形例２における準同型演算処理を説明するためのフローチャートである。
【図７】第２の実施形態に係る共通鍵暗号装置の構成を示す模式図である。
【図８】同実施形態における共通鍵復号装置の構成を示す模式図である。
【図９】同実施形態における暗号化処理を説明するためのフローチャートである。
【図１０】同実施形態における復号処理を説明するためのフローチャートである。
【発明を実施するための形態】
【００１６】
以下、各実施形態について図面を用いて説明する。なお、以下の各装置は、それぞれハードウェア構成、又はハードウェア資源とソフトウェアとの組合せ構成のいずれでも実施可能となっている。組合せ構成のソフトウェアとしては、予めネットワーク又はコンピュータ読み取り可能な記憶媒体からコンピュータにインストールされ、当該コンピュータのプロセッサに実行されることにより、各装置の機能を当該コンピュータに実現させるためのプログラムが用いられる。
【００１７】
＜第１の実施形態の概要＞
第１の実施形態の概要について、記法、暗号化処理及び復号処理の順に説明する。
【００１８】
始めに、本実施形態に用いられる記法を述べる。
【００１９】
Ａを可換環(commutative ring)とする。Ｓ＝Ａ［ｔ1, …, ｔm’］＝｛Σｃi1, i2, …, im’ｔ1i1ｔ2i2…ｔm’im’｜ｃi1, i2, …, im’∈Ａ｝を、ｔ1, …, ｔm’を変数とするｍ’変数多項式環(polynomial ring)とする（Ｓを第１の可換環とも呼ぶ）。
【００２０】
Ｒ＝Ｓ［ｘ1, …, ｘm］を、多項式を要素とする可換環とする（Ｒを第２の可換環とも呼ぶ）。例えば、Ｓは、整数環(integer ring)Ｚ＝｛０，±１，±２，…｝の要素を係数とし、ｍ’≧１に対してｔ1, …, ｔm’を変数とする多項式環Ｚ［ｔ1, …, ｔm’］としてもよい。可換環Ｒは、この多項式環Ｓ＝Ｚ［ｔ1, …, ｔm’］を係数とする多項式環（Ｚ［ｔ1, …, ｔm’］）［ｘ1, …, ｘm］としても良い。
【００２１】
これら、可換環Ｒ及び多項式環Ｓは、システムにおける公開パラメータとしても良いし、共通鍵を共有する通信者間での秘密情報としても良い。
【００２２】
秘密鍵skは、多項式環Ｓのｎ個の要素（ｓ1，ｓ2, …, ｓn）で構成される。例えば、秘密鍵skの各成分ｓiは変数ｔ1, …, ｔm’を変数に持つ多項式ｓi（ｔ1, …, ｔm’）として、sk＝（ｓ1（ｔ1, …, ｔm’）, …, ｓn（ｔ1, …, ｔm’））としても良い。ここで、ｓiは、変数ｔ1, …, ｔm’に関する次数が予め定められた値（次数をｄとする）以下となる多項式とする。あるいは、秘密鍵skの各成分ｓiは変数ｔを変数に持つ多項式ｓi（ｔ）として、sk＝（ｓ1（ｔ）, …, ｓn（ｔ））としても良い。この場合には、ｓiは、変数ｔに関する次数が予め定められた値（次数をｄとする）以下となる多項式とする。
【００２３】
本実施形態において、暗号化対象文書である平文（plaintext）情報msgは、多項式環Ｓの部分空間Ｍの要素にエンコードされる。以下、平文情報を平文と呼ぶ。
【００２４】
部分空間Ｍは、多項式を要素として含む集合である。多項式の各項を基底と呼び、部分空間Ｍは、二つ以上の基底からなる多項式を要素に含む集合であるものとする。
【００２５】
平文msgから部分空間Ｍの要素ｅへのエンコード処理をｅ＝Ｅｃｄ（msg）で表す。ここで、エンコード結果ｅは可換環Ａの要素を係数とし、ｔjを変数とする多項式である。
【００２６】
一方、環Ｓの部分空間Ｍの要素ｅから復号文msg’へのデコード処理をmsg’＝Ｄｃｄ（ｅ）で表す。ＥｃｄあるいはＤｃｄは、平文msgあるいはエンコード結果ｅのほかに、秘密鍵skを入力として受け付け、エンコード処理ｅ＝Ｅｃｄ（sk，msg）あるいはデコード処理msg’＝Ｄｃｄ（sk，ｅ）を実行してもよい。ＥｃｄとＤｃｄは、msg＝Ｄｃｄ（Ｅｃｄ（msg））となるように設計する（必要に応じてＥｃｄとＤｃｄの入力に秘密鍵skを追加する）。
【００２７】
例えば、多項式環Ｓ＝Ｚ［ｔ1, …, ｔm’］の場合に、エンコード処理Ｅｃｄは、平文msgをビット表現してｍ’個のビット列msg1｜｜msg2｜｜…｜｜msgm’に分割し（ここで｜｜はビット連結を表す）、平文多項式ｅ＝Σmsgiｔiを出力してもよい。この場合、デコード処理Ｄｃｄ（sk，ｅ）により、ビット列msg1｜｜msg2｜｜…｜｜msgm’＝msgを復元できる。ここで、ｍ’は、前述の次数ｄと後述する次数ｗに対して、ｍ’≦ｄｗ−１をみたす値とする。
【００２８】
あるいは、例えば、多項式環Ｓ＝Ｚ［ｔ］の場合に、エンコード処理Ｅｃｄは、平文msgをビット表現してｍ個のビット列msg1｜｜msg2｜｜…｜｜msgmに分割し、ｔを変数とするｍ−１次の平文多項式ｅ＝Σmsgiｔi-1を出力してもよい。この場合、デコード処理Ｄｃｄ（sk，ｅ）により、ビット列msg1｜｜msg2｜｜…｜｜msgm＝msgを復元できる。ここで、ｍは、前述の次数ｄと後述する次数ｗに対して、ｍ≦ｄｗ−１をみたす値とする。
【００２９】
なお、ここでは、平文msgをビット分割する例を記載したが、これに限らず、平文msgをｌ進展開して（例えばｌ＝２16＝６５５３６）、ｌ進展開して得られる各桁をビット列msgiに対応付けても良い。その際、デコードはｌ進展開された値を２進数あるいは１０進数など所定の形式に変換して平文msgを復元する。
【００３０】
また、ここではエンコード結果を平文msgに対して確定的に計算する例を記載したが、これに限らず、ビット列msgiのうちのいくつかをランダムな整数rndiとし、エンコード結果を平文msgに対して確率的に計算しても良い。その際、デコード処理は、ランダムな整数rndiを除くビット列msgiを取り出して、平文msgを復元する。
【００３１】
これら各処理Ｅｃｄ，Ｄｃｄは、システムにおける公開パラメータとしても良いし、共通鍵を共有する通信者間での秘密情報としても良い。
【００３２】
次に、本実施形態における暗号化と復号処理の概要を説明する。
【００３３】
暗号文（ciphertext）の送信者と受信者は、多項式環Ｓのｎ個の要素からなる秘密鍵sk＝（ｓ1, …, ｓn）を共通鍵として共有している。ここで、送信者は、後述する共通鍵暗号装置に対応する。受信者は、後述する共通鍵復号装置に対応する。
【００３４】
暗号文の送信者は、平文msgをエンコードして、平文多項式ｅ＝Ｅｃｄ（msg）を計算する。
【００３５】
送信者は可換環ＲあるいはＲ＝Ｓ［ｘ1, …, ｘn］の部分集合からｗ次以下の多項式ｆ（ｘ1, …, ｘn）をランダムに生成する。ここで、ｆ（ｘ1, …, ｘn）の次数は、ｘ1, …, ｘnを変数としてｆ（ｘ1, …, ｘn）の各項の次数を計算し、その最大値で定義する。
【００３６】
Ｓ＝Ａ［ｔ1, …, ｔm’］である場合には、ｆはｘ1, …, ｘnに加えてｔ1, …, ｔm’を変数とする多項式として表現される。以下では、誤解のない限り、ｆはｘ1, …, ｘnを変数とする多項式として表現する。後述するｃ（ｘ1, …, ｘn），ｇ（ｘ1, …, ｘn）についても同様である。
【００３７】
送信者は、暗号文ｃ（ｘ1, …, ｘn）＝ｅ＋ｆ（ｘ1, …, ｘn）−ｆ（ｓ1, …, ｓn）を計算して、受信者に送信する。
【００３８】
暗号文の受信者は、受信した暗号文ｃ（ｘ1, …, ｘn）に秘密鍵（ｓ1, …, ｓn）を代入して、次式のように平文多項式ｅを計算する。
【００３９】
ｃ（ｓ1, …, ｓn）＝ｅ
しかる後、受信者は、平文多項式ｅに基づいてデコード処理msg’＝Ｄｃｄ（ｅ）を実行し、平文msg＝msg’を復元する。
【００４０】
＜第１の実施形態の具体的な構成＞
以下、第１の実施形態について具体的に説明する。
【００４１】
図１は第１の実施形態に係る共通鍵暗号装置の構成を示す図であり、図２は同実施形態における共通鍵復号装置の構成を示す図である。
【００４２】
ここで、共通鍵暗号装置１００は、パラメータ記憶部１０１、入出力部１０２及び暗号化処理部１０３を備えている。
【００４３】
パラメータ記憶部（記憶部）１０１は、暗号化処理部１０３から読出可能なメモリであり、第１の多項式環Ｓの複数の要素（ｓ1, …, ｓn）で構成される秘密鍵sk（共通鍵）と、安全性のパラメータ（security parameter）とを記憶する。パラメータ記憶部１０１は、可換環Ｒ及び多項式環Ｓの情報を記憶してもよい。また、パラメータ記憶部１０１は、エンコード処理Ｅｃｄの情報を記憶してもよい。
【００４４】
入出力部１０２は、暗号化対象文書の平文msg（平文情報）の入力を受け付け、暗号化処理部１０３で計算した暗号文ｃ（ｘ1, …, ｘn）を出力する。このような入出力部１０２は、平文受付部及び出力部を構成している。
【００４５】
暗号化処理部１０３は、入出力部１０２で入力を受け付けた平文msgとパラメータ記憶部１０１が記憶する情報に基づいて、暗号文ｃ（ｘ1, …, ｘn）を計算する。
【００４６】
例えば、暗号化処理部１０３は、以下の機能(f103-1)〜(f103-3)をもっている。
【００４７】
(f103-1)  入力を受け付けた平文msgを第１の多項式環Ｓの部分空間Ｍの多項式の少なくとも一つの項に埋め込むことにより、平文多項式ｅを生成する平文多項式生成機能。
【００４８】
なお、平文多項式生成機能(f103-1)は、平文msgを複数の部分情報msg1, ..., msgi, ..., msgmに加法的に分割し、複数の部分情報msg1, ..., msgi, ..., msgmを平文多項式ｅの各項の係数として埋め込む機能(f103-1-1)を有していてもよい。ここで、ｍは、前述の次数ｄとｗに対して、ｍ≦ｄｗ−１をみたす値とする。
【００４９】
(f103-2)  第１の多項式環Ｓ上で定義される第２の可換環Ｒに基づいて、秘密鍵sk（共通鍵）を解に含むマスク多項式ｇ（ｘ1, …, ｘn）を生成するマスク多項式生成機能。
【００５０】
(f103-3)  平文多項式ｅとマスク多項式ｇ（ｘ1, …, ｘn）とを用いて、暗号文ｃ（ｘ1, …, ｘn）を生成する暗号化機能。
【００５１】
また、暗号化処理部１０３は、以下の機能(f103-4)を備えていてもよい。
【００５２】
(f103-4)  平文多項式生成機能(f103-1)、マスク多項式生成機能(f103-2)及び暗号化機能(f103-3)によって２つの平文多項式ｅ(1)，ｅ(2)から２つの暗号文ｃ(1)（ｘ1, …, ｘn），ｃ(2)（ｘ1, …, ｘn）が個別に生成されたとき、当該２つの暗号文を互いに加算又は乗算する準同型演算処理により、新たな暗号文ｃ(hom)（ｘ1, …, ｘn）を生成する準同型演算機能。
【００５３】
ここで、当該２つの暗号文を互いに加算する場合、秘密鍵skに基づいて新たな暗号文ｃ(hom)（ｘ1, …, ｘn）を復号した結果は、２つの平文多項式ｅ(1)，ｅ(2)を互いに加算した結果と等しい。
【００５４】
また、２つの暗号文を互いに乗算する場合、秘密鍵skに基づいて新たな暗号文ｃ(hom)（ｘ1, …, ｘn）を復号した結果は、２つの平文多項式ｅ(1)，ｅ(2)を互いに乗算した結果と等しい。
【００５５】
このような暗号化処理部１０３は、平文多項式生成部、マスク多項式生成部及び暗号化部を構成している。また、暗号化処理部１０３は、準同型演算部を構成してもよい。
【００５６】
一方、共通鍵復号装置２００は、図２に示すように、パラメータ記憶部２０１、入出力部２０２及び復号処理部２０３を備えている。
【００５７】
パラメータ記憶部（記憶部）２０１は、復号処理部２０３から読出可能なメモリであり、多項式環Ｓの複数の要素（ｓ1, …, ｓn）で構成される秘密鍵sk（共通鍵）と、安全性のパラメータとを記憶する。パラメータ記憶部２０１は、可換環Ｒ及び多項式環Ｓの情報を記憶してもよい。また、パラメータ記憶部２０１は、デコード処理Ｄｃｄの情報を記憶してもよい。
【００５８】
入出力部２０２は、暗号文ｃ（ｘ1, …, ｘn）を入力として受け付け、復号結果msg’を出力する。このような入出力部２０２は、暗号文受付部及び出力部を構成している。
【００５９】
ここで、暗号文ｃ（ｘ1, …, ｘn）は、平文多項式ｅと、マスク多項式ｇ（ｘ1, …, ｘn）と、を用いて生成されている。
【００６０】
平文多項式ｅは、第１の多項式環Ｓの部分空間Ｍの多項式の少なくとも一つの項に平文msgを埋め込むことにより生成されている。なお、平文msgは、複数の部分情報に加法的に分割され、複数の部分情報が平文多項式ｅの各項に係数として埋め込まれていてもよい。この場合、後述する復号機能(f203-2)は、平文多項式復号機能(f203-1)により復号された平文多項式ｅの各項の係数を複数の部分情報として抽出し、当該複数の部分情報の総和を計算することにより平文msgを復号することが可能である。
【００６１】
マスク多項式ｇ（ｘ1, …, ｘn）は、秘密鍵skを解に含む。このマスク多項式ｇ（ｘ1, …, ｘn）は、第１の多項式環Ｓ上で定義される第２の可換環Ｒに基づいて生成されている。
【００６２】
復号処理部２０３は、入出力部３０１で入力を受け付けた暗号文ｃ（ｘ1, …, ｘn）とパラメータ記憶部２０１が記憶する情報に基づいて暗号文ｃ（ｘ1, …, ｘn）を復号して復号結果msg’を得る。
【００６３】
例えば、復号処理部２０３は、以下の機能(f203-1)〜(f203-2)をもっている。
【００６４】
(f203-1)  パラメータ記憶部２０１内の秘密鍵skに基づいて、暗号文ｃ（ｘ1, …, ｘn）から平文多項式ｅを復号する平文多項式復号機能。
【００６５】
(f203-2)  復号した平文多項式ｅから平文msgを復号する復号機能。
【００６６】
なお、入力を受け付けた暗号文が、２つの平文多項式ｅ(1)，ｅ(2)から個別に生成された２つの暗号文ｃ(1)（ｘ1, …, ｘn），ｃ(2)（ｘ1, …, ｘn）を互いに加算又は乗算する準同型演算処理により生成されている場合について述べる。
【００６７】
当該２つの暗号文を互いに加算する場合、復号機能(f203-2)により復号された結果は、２つの平文多項式ｅ(1)，ｅ(2)を互いに加算した結果と等しい。
【００６８】
また、２つの暗号文を互いに乗算する場合、復号機能(f203-2)により復号された結果は、２つの平文多項式ｅ(1)，ｅ(2)を互いに乗算した結果と等しい。
【００６９】
このような復号処理部２０３は、平文多項式復号部及び復号部を構成している。
【００７０】
次に、以上のように構成された共通鍵暗号装置及び共通鍵復号装置の動作について図３及び図４のフローチャートを用いて説明する。
【００７１】
共通鍵暗号装置１００では、図３に示すように、入出力部１０２が、平文msgの入力を受け付ける（ＳＴ１）。また、パラメータ記憶部１０１内のパラメータ（例えば、Ｓ，Ｒ，sk等）は、適宜、暗号化処理部１０３に読み出される。
【００７２】
暗号化処理部１０３は、入出力部１０２により入力を受け付けた平文msgを多項式環Ｓの部分空間Ｍの多項式の各項に埋め込むようにエンコード処理を実行し、平文多項式ｅ＝Ｅｃｄ（msg）を計算する（ＳＴ２）。
【００７３】
暗号化処理部１０３は、多項式環Ｓ上で定義される可換環Ｒに基づいて、秘密鍵（ｓ1, …, ｓn）を解に含むマスク多項式ｇ（ｘ1, …, ｘn）を生成する。例えば、暗号化処理部１０３は、マスク多項式ｇ（ｘ1, …, ｘn）を可換環Ｒからランダムに選択する（ＳＴ３〜ＳＴ５）。なお、マスク多項式ｇ（ｘ1, …, ｘn）は、平文多項式ｅに加算されて平文多項式ｅを隠蔽する。
【００７４】
具体的には、暗号化処理部１０３は、例えば、可換環Ｒから多項式ｆ（ｘ1, …, ｘn）をランダムに選択する（ＳＴ３）。多項式ｆ（ｘ1, …, ｘn）は、ランダム多項式ｆ（ｘ1, …, ｘn）と呼んでもよい。
【００７５】
暗号化処理部１０３は、多項式ｆ（ｘ1, …, ｘn）の変数ｘ1, …, ｘnに秘密鍵skを代入した多項式ｆ（ｓ1, …, ｓn）を計算し（ＳＴ４）、マスク多項式ｇ（ｘ1, …, ｘn）＝ｆ（ｘ1, …, ｘn）−ｆ（ｓ1, …, ｓn）を設定する（ＳＴ５）。
【００７６】
ここで、＋は可換環Ｒで定義される加法であり、−は加法逆元の加法である。
【００７７】
また、マスク多項式ｇ（ｘ1, …, ｘn）や多項式ｆ（ｘ1, …, ｘn）は可換環Ｒから選ばれるのではなく、可換環Ｒの部分集合から選ばれても良い。
【００７８】
あるいは、マスク多項式ｇ（ｘ1, …, ｘn）や多項式ｆ（ｘ1, …, ｘn）はランダムに選ばれるのではなく、暗号化を処理する日時や秘密鍵sk、あるいは平文msgなどに依存して選ばれても良い。また、ステップＳＴ３〜ＳＴ５は、ステップＳＴ１が実行される前に、予め実行されても良い。
【００７９】
暗号化処理部１０３は、平文多項式ｅとマスク多項式ｇ（ｘ1, …, ｘn）とを加算する処理により、暗号文ｃ（ｘ1, …, ｘn）＝ｅ＋ｇ（ｘ1, …, ｘn）を生成する（ＳＴ６）。
【００８０】
共通鍵暗号装置１００は、暗号文ｃ（ｘ1, …, ｘn）を入出力部１０１から出力する（ＳＴ７）。
【００８１】
以上が共通鍵暗号装置１００の動作である。続いて、共通鍵復号装置２００の動作を説明する。
【００８２】
共通鍵復号装置２００は、図４に示すように、入出力部２０２が暗号文ｃ（ｘ1, …, ｘn）の入力を受け付ける（ＳＴ１１）。
【００８３】
復号処理部２０３は、パラメータ記憶部２０１内の秘密鍵sk＝（ｓ1, …, ｓn）に基づいて、暗号文ｃ（ｘ1, …, ｘn）から平文多項式ｅを復号する。例えば、復号処理部２０３は、秘密鍵sk＝（ｓ1, …, ｓn）を暗号文ｃ（ｘ1, …, ｘn）に代入し、次式に示すように、平文多項式ｅを計算する（ＳＴ１２）。
【００８４】
ｃ（ｓ1, …, ｓn）＝ｅ＋ｇ（ｓ1, …, ｓn）＝ｅ
復号処理部２０３は、復号した平文多項式ｅから平文msgを復号する。すなわち、復号処理部２０３は、平文多項式ｅをデコードして、復号結果msg’＝Ｄｃｄ（ｅ）を計算する（ＳＴ１３）。
【００８５】
例えば、前述したように、多項式環Ｓ＝Ａ［ｔ1, …, ｔn］，エンコード処理Ｅｃｄ（msg）＝ｅ＝Σmsgiｔi、但し、平文msg＝msg1｜｜msg2｜｜…｜｜msgn、の場合には、ステップＳＴ１２で計算される多項式ｃ（ｓ1, …, ｓn）は、ｔiを変数とする平文多項式ｅ＝Σmsgiｔiである。
【００８６】
この場合、平文多項式ｅ＝Σmsgiｔiにおいて、変数ｔiの係数を平文のビット列msg’iに割り当てて復号結果msg’＝msg’1｜｜msg’2｜｜…｜｜msg’nと設定することにより、平文msg＝msg’を復号することができる。
【００８７】
あるいは、多項式環Ｓ＝Ｆq［ｔ］，エンコード処理Ｅｃｄ（msg）＝ｅ＝Σmsgiｔi、但し、平文msg＝msg1｜｜msg2｜｜…｜｜msgm’、の場合には、ステップＳＴ１２で計算される多項式ｃ（ｓ1, …, ｓn）は、ｔを変数とする平文多項式ｅ＝Σmsgiｔiである。
【００８８】
この場合、平文多項式ｅ＝Σmsgiｔiにおいて、ｔiの係数を平文のビット列msg’iに割り当てて復号結果msg’＝msg’1｜｜msg’2｜｜…｜｜msg’nと設定することにより、平文msg＝msg’を復号することができる。
【００８９】
あるいは、多項式環Ｓ＝Ｆq［ｔ］，エンコード処理Ｅｃｄ（msg）＝ｅ＝Σmsgiｔi、但し、平文msg＝Σmsgiｌiの場合には、ステップＳＴ１２で計算される多項式ｃ（ｓ1, …, ｓn）は、ｔを変数とする平文多項式ｅ＝Σmsgiｔiである。
【００９０】
この場合、平文多項式ｅ＝Σmsgiｔiにおいて、ｔiの係数をビット列msg’iに割り当てて復号結果msg’＝Σmsgiｌiと設定することにより、平文msg＝msg’を復号することができる。
【００９１】
最後に、共通鍵復号装置２００は、入出力部２０２から平文msg＝msg’を出力する（ＳＴ１４）。
【００９２】
上述したように本実施形態によれば、平文msgを多項式環Ｓの部分空間Ｍの多項式の各項に埋め込むことにより平文多項式ｅを生成し、平文多項式ｅと、共通鍵（sk）を解に含むマスク多項式ｇ（ｘ1, …, ｘn）とを加算する処理により、暗号文ｃ（ｘ1, …, ｘn）を生成する構成により、並列度を上げて、計算の効率を向上させることができる。なお、多項式同士を加算する処理においては、同類項同士の係数を加算する処理を並列に実行できる。従って、本実施形態は、平文多項式ｅとマスク多項式ｇ（ｘ1, …, ｘn）とを加算する処理において、並列度を上げることができる。また、本実施形態は、平文msgを多項式の各項に埋め込む処理を並列に実行できる点からも、並列度を上げることができる。
【００９３】
また、本実施形態によれば、このように生成された暗号文ｃ（ｘ1, …, ｘn）の入力を受け付けると、共通鍵（sk）に基づいて、当該暗号文ｃ（ｘ1, …, ｘn）から平文多項式ｅを復号し、当該復号した平文多項式ｅから平文msgを復号する構成により、並列度を上げて、計算の効率を向上させることができる。なお、共通鍵（sk）に基づいて暗号文ｃ（ｘ1, …, ｘn）から平文多項式ｅを復号する処理においては、例えば、同類項毎に係数を復元する等のように、多項式の各項毎に平文msgの一部を復元する処理を並列に実行できる。従って、本実施形態は、暗号文ｃ（ｘ1, …, ｘn）から平文多項式ｅを復号する処理において、並列度を上げることができる。また、本実施形態は、平文多項式ｅの各項から平文msgの一部を復号する処理を並列に実行できる点からも、並列度を上げることができる。
【００９４】
また、共通鍵暗号装置１００では、エンコード処理Ｅｃｄにより、平文msgを二つ以上の基底の和で表現される要素を含む可換環に対応付ける。そのため、平文情報をＭの要素の二つ以上の基底に埋め込むことにより、一つの暗号文に多倍長精度の平文を埋め込むことができる。そのため、多倍長演算を行うことなくＣＰＵの処理単位よりも大きいサイズの平文を暗号化することができる。
【００９５】
例えば、完全準同型性を有する共通鍵暗号方式としては、非特許文献１記載の技術が知られている。
【００９６】
しかしながら、非特許文献１記載の技術は、復号においてＦp＝｛０，１, …, ｐ−１｝の整数値が計算されるため、１つの暗号文には単一の平文しか埋め込めない。そのため、非特許文献１記載の技術では、ＣＰＵの処理単位よりも大きなサイズの平文を暗号化処理するためには多倍長演算（data processing with multi precision）を行わなければならない。また、非特許文献１記載の技術では、複数の種類の平文を暗号化するためには、複数の暗号文を計算しなければならない。
【００９７】
これに対し、本実施形態によれば、平文情報を多項式の各項に埋め込む構成により、１つの暗号文に多倍長精度の平文、あるいは複数の種類の平文を埋め込むことができる。
【００９８】
＜第１の実施形態の変形例１：拡大体＞
第１の実施形態では、Ｍが多項式環Ｓの部分集合となる共通鍵暗号装置の構成を示した。変形例１では、多項式環Ｓの部分集合Ｍを体Ｌ（field L）の部分集合とする例を説明する。以降では、体Ｌは、体Ｆpあるいは体Ｋにαを添加した拡大体を例に説明するが、体Ｆpあるいは体Ｋにα1, …, αm’を添加した拡大体を用いても良い。前者は第１の実施形態における多項式環Ｓ＝Ａ［ｔ］に相当し、後者は第１の実施形態における多項式環Ｓ＝Ａ［ｔ1, …, ｔm’］に相当する。
【００９９】
変形例１を実現する共通鍵暗号装置の構成は、前述した共通鍵暗号装置１００と同様である。
【０１００】
次に、変形例１を説明するための記法を説明する。
【０１０１】
第１の実施形態では、Ｓをｔiを変数とする多項式環とした。変形例１ではＳ⊆Ｌを、体Ｆp＝｛０，１, …, ｐ−１｝のｍ次拡大体（extension field of Fp of degree m）Ｌ＝｛Σ0≦i≦m-1ｃiαi｜ｃi∈Ｆp、αはＦpを係数とするｍ次既約多項式の根、ｍ≧２｝の部分体（Subfield）とする。あるいは、部分体Ｓは、体Ｆpとは異なる任意の体Ｋの拡大体としても良い。
【０１０２】
可換環Ｒ＝Ｓ［ｘ1, …, ｘn］は、部分体Ｓの要素を係数とする多項式環とする。
【０１０３】
秘密鍵skは、例えば、部分体Ｓの要素の組sk＝（ｓ1, …, ｓn）、但し、ｓi＝Σ0≦j≦m-1ｃjαiは部分体Ｓの要素、とする。
【０１０４】
エンコード処理は、平文msgを部分体Ｓの部分集合Ｍの要素に割り当てる。前述の基底は、部分集合Ｍの要素であるΣｃiαiの各ｃiαiに相当する。
【０１０５】
例えば、秘密鍵sk＝（ｓ1, …, ｓn）∈Ｓn，可換環Ｒ＝Ｓ［ｘ1, …, ｘn］の場合には、エンコード処理Ｅｃｄは、平文msgをビット表現してｍ個のビット列msg1｜｜msg2｜｜…｜｜msgmに分割し（ここで｜｜はビット連結を表す）、平文多項式ｅ＝Σmsgiαi-1を出力してもよい。
【０１０６】
このとき、第１の実施形態と同様に、デコード処理Ｄｃｄ（sk，ｅ）により、ｍ個のビット列msg1, msg2, …, msgmを連結し、次式に示すように平文msgを復元できる。
【０１０７】
msg1｜｜msg2｜｜…｜｜msgm＝msg
あるいは、平文msgをｌ進展開して（例えばｌ＝２16＝６５５３６）、各桁をビット列msgiに対応付けても良い。その際、デコード処理はｌ進展開された値を２進数あるいは１０進数など所定の形式に変換して平文msgを復元する。
【０１０８】
さらに、ビット列msgiのうちのいくつかをランダムな整数rndiとし、エンコード処理を平文msgに対して確率的に計算しても良い。
【０１０９】
その際、デコード処理は、ランダムな整数rndiを除くビット列msgiを取り出して、平文msgを復元する。
【０１１０】
ここで、ビット列msgiの代わりにランダムな整数rndiを用いる箇所を示すインデックスｉ（すなわち、実際の平文msgを埋め込むビット列msgjのインデックスｊ）は、システムにおける公開パラメータとしても良いし、共通鍵を共有する通信者間での秘密情報としても良い。
【０１１１】
変形例１の共通鍵暗号装置及び共通鍵復号装置の処理は、前述した共通鍵暗号装置１００及び共通鍵復号装置２００と同様である。具体的には、各装置の処理は、第１の実施形態のｔijをαijに置換したものであるため、詳細な説明を省略する。
【０１１２】
上述したように本変形例１によれば、多項式環Ｓの部分集合Ｍを体Ｌの部分集合とした場合であっても、第１の実施形態を同様に実施して同様の効果を得ることができる。
【０１１３】
＜第１の実施形態の変形例２：準同型演算＞
第１の実施形態及び変形例１では、共通鍵暗号装置の構成を示した。第１の実施形態及び変形例１において、エンコードがＥｃｄ（msg(1)）＋Ｅｃｄ（msg(2)）＝Ｅｃｄ（msg(1)＋msg(2)）あるいはＥｃｄ（msg(1)）＊Ｅｃｄ（msg(2)）＝Ｅｃｄ（msg(1)＊msg(2)）を満たすとき、準同型性を有する共通鍵暗号装置を構成できる。
【０１１４】
このような性質を満たすエンコードとして、例えば上述したように、平文msgをビット列msg1｜｜msg2｜｜…｜｜msgmのように分割し、Ｅｃｄ（msg）＝ｅ＝Σmsgiｘni-1やＥｃｄ（msg）＝ｅ＝Σmsgiαi-1とする方法がある。
【０１１５】
あるいは、平文msgをΣmsg(l)iｌiのようにｌ進展開して、平文多項式ｅ＝Ｅｃｄ（msg）＝Σmsg(l)iｘiとしても良い。
【０１１６】
あるいは、上述のビット列msgiのうちのいくつかをランダムな整数rndiとし、エンコード結果を平文msgに対して確率的に計算して、Ｅｃｄ（msg）＝ｅ＝Σ1≦irndiｘni-1+msgやＥｃｄ（msg）＝ｅ＝Σ1≦irndiαi-1+msgとしても良い。
【０１１７】
変形例２の共通鍵暗号装置の構成は、前述した共通鍵暗号装置１００の構成と同一であり、エンコードの方法のみが異なる。以降では、変形例２の共通鍵暗号装置による準同型演算処理を説明する。
【０１１８】
図５は第１の実施形態の変形例２に用いられる準同型演算装置の構成を示す図である。準同型演算装置３００は、パラメータ記憶部３０１、入出力部３０２及び準同型演算部３０３を備えている。
【０１１９】
パラメータ記憶部３０１は、安全性のパラメータを記憶する。パラメータ記憶部３０１は、可換環Ｒ及び多項式環Ｓの情報を記憶してもよい。また、パラメータ記憶部３０１は、エンコード処理Ｅｃｄの情報を記憶してもよい。
【０１２０】
入出力部３０２は、共通鍵暗号装置１００から２つの暗号文ｃ(1)（ｘ1, …, ｘn），ｃ(2)（ｘ1, …, ｘn）を入力として受け付け、準同型演算結果ｃ(hom)（ｘ1, …, ｘn）を共通鍵暗号装置１００に出力する。
【０１２１】
準同型演算部３０３は、入出力部３０２で受け付けた各暗号文ｃ(1)（ｘ1, …, ｘn），ｃ(2)（ｘ1, …, ｘn）とパラメータ記憶部３０１が記憶する情報に基づいて準同型演算結果ｃ(hom)（ｘ1, …, ｘn）を計算する。
【０１２２】
なお、前述した共通鍵暗号装置１００が準同型演算装置３００の機能を更に備えてもよい。
【０１２３】
図６を用いて、変形例２の準同型演算処理を説明する。
【０１２４】
準同型演算装置３００は、入出力部３０２が、２つの暗号文ｃ(1)（ｘ1, …, ｘn），ｃ(2)（ｘ1, …, ｘn）の入力を受け付ける（ＳＴ２１）。なお、第１の暗号文ｃ(1)（ｘ1, …, ｘn）は、第１の平文多項式ｅ(1)から生成されたものとする。第２の暗号文ｃ(2)（ｘ1, …, ｘn）は、第２の平文多項式ｅ(2)から生成されたものとする。
【０１２５】
準同型演算装置３００は、２つの暗号文に対し、加法演算又は乗法演算を示す演算の種類を決定する（ＳＴ２２）。演算の種類は、準同型演算装置３００に対して予め決定されていても良いし、暗号文ｃ(1)（ｘ1, …, ｘn），ｃ(2)（ｘ1, …, ｘn）を入力として受け付ける際に、外部から準同型演算装置３００に指定されても良い。
【０１２６】
２つの暗号文ｃ(1)（ｘ1, …, ｘn），ｃ(2)（ｘ1, …, ｘn）の加法演算を行う場合、準同型演算装置３００は、次式に示すように、当該２つの暗号文を互いに加算する準同型演算処理により、新たな暗号文ｃ(Add)（ｘ1, …, ｘn）を生成する（ＳＴ２３Ａ）。
【０１２７】
ｃ(Add)（ｘ1, …, ｘn）＝ｃ(1)（ｘ1, …, ｘn）＋ｃ(2)（ｘ1, …, ｘn）  
＝ｅ(1)＋ｅ(2)＋ｇ(1)（ｘ1, …, ｘn）＋ｇ(2)（ｘ1, …, ｘn）
２つの暗号文の乗法演算を行う場合、準同型演算装置３００は、次式に示すように、当該２つの暗号文を互いに乗算する準同型演算処理により、新たな暗号文ｃ(Mul)（ｘ1, …, ｘn）を生成する（ＳＴ２３Ｍ）。
【０１２８】
ｃ(Mul)（ｘ1, …, ｘn）＝ｃ(1)（ｘ1, …, ｘn）＊ｃ(2)（ｘ1, …, ｘn）  
＝ｅ(1)＊ｅ(2)＋ｇ(1)（ｘ1, …, ｘn）ｇ(2)（ｘ1, …, ｘn）＋ｇ(1)（ｘ1, …, ｘn）ｅ(2)＋ｇ(2)（ｘ1, …, ｘn）ｅ(1) 
準同型演算装置３００は、ステップＳＴ２３Ａ又はＳＴ２３Ｍで得られた準同型演算結果を入出力部３０２から共通鍵暗号装置１００に出力する（ＳＴ２４）。
【０１２９】
共通鍵暗号装置１００は、準同型演算を行った後の暗号文が、意図した準同型演算を行った平文に対応することを確認した後、当該暗号文を共通鍵復号装置２００に送信する。なお、この準同型演算の確認は、共通鍵復号装置２００が実行してもよい。
【０１３０】
加法演算に関しては、次式に示すように、秘密鍵sk＝（ｓ1, …, ｓn）に基づいて新たな暗号文ｃ(Add)（ｘ1, …, ｘn）を復号した結果は、２つの平文多項式ｅ(1)，ｅ(2)を互いに加算した結果と等しい。
【０１３１】
ｃ(Add)（ｓ1, …, ｓn）＝ｃ(1)（ｓ1, …, ｓn）＋ｃ(2)（ｓ1, …, ｓn）＝ｅ(1)＋ｅ(2)＋ｇ(1)（ｓ1, …, ｓn）＋ｇ(2)（ｓ1, …, ｓn）＝ｅ(1)＋ｅ(2) 
すなわち、共通鍵復号装置２００が準同型演算結果ｃ(Add)（ｘ1, …, ｘn）に秘密鍵skを代入すると、正しく平文多項式の和（ｅ(1)＋ｅ(2)）が復号される。
【０１３２】
乗法演算に関しては、次式に示すように、秘密鍵sk＝（ｓ1, …, ｓn）に基づいて新たな暗号文ｃ(Mul)（ｘ1, …, ｘn）を復号した結果は、２つの平文多項式ｅ(1)，ｅ(2)を互いに乗算した結果と等しい。
【０１３３】
ｃ(Mul)（ｓ1, …, ｓn）＝ｃ(1)（ｓ1, …, ｓn）＊ｃ(2)（ｓ1, …, ｓn）＝ｅ(1)＊ｅ(2)＋ｇ(1)（ｓ1, …, ｓn）ｇ(2)（ｓ1, …, ｓn）＋ｇ(1)（ｓ1, …, ｓn）ｅ(2)＋ｇ(2)（ｓ1, …, ｓn）ｅ(1)＝ｅ(1)＊ｅ(2) 
このため、共通鍵復号装置２００が準同型演算結果ｃ(Mul)（ｘ1, …, ｘn）に秘密鍵skを代入すると、正しく平文多項式の積（ｅ(1)＊ｅ(2)）が復号される。
【０１３４】
上述したように本変形例２によれば、２つの平文多項式ｅ(1)，ｅ(2)から個別に２つの暗号文ｃ(1)（ｘ1, …, ｘn），ｃ(2)（ｘ1, …, ｘn）が生成されたとき、当該２つの暗号文を互いに加算又は乗算する準同型演算処理により、新たな暗号文を生成する。
【０１３５】
加算の場合、共通鍵に基づいて新たな暗号文を復号した結果が２つの平文多項式を互いに加算した結果と等しいので、加法的準同型演算を実現することができる。
【０１３６】
乗算の場合、共通鍵に基づいて新たな暗号文を復号した結果が２つの平文多項式を互いに乗算した結果と等しいので、乗法的準同型演算を実現することができる。
【０１３７】
また、本変形例２によれば、加法的及び乗法的準同型演算を実現できるので、第１の実施形態の効果に加え、完全準同型演算を実現することができる。
【０１３８】
（第１の実施形態のその他の変形例：エンコード処理Ｅｃｄ）
上述した第１の実施形態及び変形例１，２において、以下の（１）〜（７）に説明するエンコード処理Ｅｃｄを使用することも可能である。
【０１３９】
（１）平文msgをｌ進展開した後にビット列に分割したエンコード処理
上述では、平文msgをビット列msg1｜｜…｜｜msgmあるいはｌ進展開msg＝Σmsgiｌi-1のように表現し、エンコード処理をＥｃｄ（msg）＝ｅ＝Σmsgiｔi-1またはＥｃｄ（msg）＝ｅ＝Σmsgiαi-1とする例を説明した。ただし、ｍは、前述の次数ｄとｗに対して、ｍ≦ｄｗ−１をみたす値とする。
【０１４０】
これらエンコード処理Ｅｃｄを用いる共通鍵暗号方式は、加法及び乗法に関する準同型性を満たす。
【０１４１】
（２）平文msgを分割しないエンコード処理
平文msgを分割せず、１つの係数ｃ0に平文msgを設定し（ｃ0＝msg）、ｍ−１個の他の係数ｃ1, …, ｃm-1に乱数を設定して、エンコード処理をＥｃｄ（msg）＝ｅ＝ΣｃiｔiまたはＥｃｄ（msg）＝ｅ＝Σｃiαiと設定しても良い。ここで、ｍは、前述の次数ｄとｗに対して、ｍ≦ｄｗ−１をみたす値とする。
【０１４２】
このようなエンコード処理Ｅｃｄを用いる場合には、共通鍵暗号方式は加法及び乗法に関する準同型性を満たす。
【０１４３】
（３）平文msgを加法的に分割したエンコード処理
エンコード処理Ｅｃｄは、平文msgを複数の部分情報msg1, ..., msgi, ..., msgmに加法的に分割し、複数の部分情報msg1, ..., msgi, ..., msgmを平文多項式ｅの各項の係数として埋め込むように実行してもよい。ここで、ｍは、前述の次数ｄとｗに対して、ｍ≦ｄｗ−１をみたす値とする。
【０１４４】
例えば、平文msgを、msg＝Σmsgiやmsg＝Σmsgi  ｍｏｄ  ｐ（ｐは整数）のように加法的に分割して、エンコード処理をＥｃｄ（msg）＝ｅ＝Σmsgiｔi-1またはＥｃｄ（msg）＝ｅ＝Σmsgiαi-1としても良い。ここで、加法的に分割して得られるmsgiの数は、前述の次数ｄとｗに対して、（ｄｗ−１）個以下とする。
【０１４５】
対応するデコード処理Ｄｃｄは、復号された平文多項式ｅの各項の係数を複数の部分情報として抽出し、当該複数の部分情報の総和を計算することにより平文msgを復号するように実行してもよい。
【０１４６】
例えば、平文多項式ｅ＝Σmsg’iｔi-1あるいは平文多項式ｅ＝Σmsg’iαi-1に対して、復号結果msg’＝Σmsg’iなどにより平文msg＝msg’を復号する。この（３）の場合、上記（１）とは異なり、全ての部分情報msg’iが正しいときのみ、部分情報msg’iの総和を計算することにより、平文msgを復号できる。すなわち、この（３）の場合、上記（１）とは異なり、平文msgの部分情報msgiを秘密分散した場合と同様の効果を得ることができる。
【０１４７】
このようなエンコード処理Ｅｃｄを用いる場合には、共通鍵暗号方式は加法に関する準同型性を満たす。
【０１４８】
（４）平文msgを解にしたエンコード処理
また、平文msgを加法的に分割するだけでなく、平文msgが多項式ｅ＝Σｃiｔi-1あるいは多項式ｅ＝Σｃiαi-1の係数ｃiから導出される方程式の解となるように平文msgをエンコード処理Ｅｃｄしても良い。
【０１４９】
例えば、ｘとｙを変数とする２元１次連立方程式を考え、ｃ0ｘ＋ｃ1ｙ＝ｃ2，ｃ3ｘ＋ｃ4ｙ＝ｃ5の解がｘ＝msgとなるように係数ｃ0〜ｃ5を定めてエンコード処理Ｅｃｄしても良い。
【０１５０】
あるいは、ｘを変数とする２次方程式を考え、ｃ0＋ｃ1ｘ＋ｃ2ｘ2＝０の解がｘ＝msgとなるように係数ｃ0〜ｃ2を定めてエンコード処理Ｅｃｄしても良い。この場合には、方程式から２つの解が導かれるため、一意復号性を保つために、方程式が平文msgを重解に持つようにしても良い。
【０１５１】
あるいは、もう一つの解は平文msgよりも大きな（あるいは小さな）値となるように係数ｃ0〜ｃ2を定め、２次方程式を解いた後に小さな（あるいは大きな）値を平文msgとして選択しても良い。
【０１５２】
（５）可換環へのエンコード処理
平文msgがエンコードされる空間をＳの部分空間Ｍに限らず、多項式環Ｓ［ｘ1, …, ｘn］の部分空間とすることもできる。このとき、エンコード結果はｘ1, …, ｘnを変数とする多項式ｅ（ｘ1, …, ｘn）となる。
【０１５３】
例えば、秘密鍵sk＝（ｓ1, …, ｓn），degt ｓi＞Σi>j≧0 degt ｓjとし、エンコード処理をＥｃｄ（msg）＝msg1,1, …, 1ｘ1ｘ2…ｘn＋msg0,1, …, 1ｘ2…ｘn＋…＋msg0,0, …, 1ｘn＋msg0,0, …, 0、とすることができる。
【０１５４】
但し、degt ｓiは多項式ｓiのｔに関する次数を表す。  
平文msgは、msg＝msg1,1, …, 1｜｜msg0,1, …, 1｜｜…｜｜msg0,0, …, 0とする。
【０１５５】
復号処理におけるデコード処理Ｄｃｄでは、暗号文ｃ（ｘ1, …, ｘn）に秘密鍵skを代入し、次式のように平文多項式ｅ（ｓ1, …, ｓn）が計算される。
【０１５６】
ｃ（ｓ1, …, ｓn）＝ｅ（ｓ1, …, ｓn）
得られた平文多項式ｅ（ｓ1, …, ｓn）のｔに関する最高次の係数からビット列msg1,1, …, 1が復元される。
【０１５７】
次に、平文多項式ｅ（ｓ1, …, ｓn）−msg1,1, …, 1ｓ1ｓ2…ｓnの最高次の係数からビット列msg0,1, …, 1が復元される。
【０１５８】
同様にして、各ビット列msg0,0, …, 1，…，msg0,0, …, 0を順番に復元し、各ビット列から平文msg＝msg1,1, …, 1｜｜msg0,1, …, 1｜｜…｜｜msg0,0, …, 0を復元することができる。
【０１５９】
（６）複数の種類の平文に対するエンコード処理
エンコード処理Ｅｃｄは単一の平文msgのみでなく、例えば身長と体重など、複数の種類の平文msg(1), …, msg(m)を部分空間Ｍの要素に変換しても良い。
【０１６０】
この場合、エンコード処理Ｅｃｄは、例えば、Ｅｃｄ（msg(1), …, msg(m)）＝ｅ＝Σmsg(i)ｔi-1やＥｃｄ（msg(1), …, msg(m)）＝ｅ＝Σmsg(i)αi-1としても良い。ここで、エンコードされるmsg(i)の数は、前述の次数ｄとｗに対して、（ｄｗ−１）個以下とする。
【０１６１】
このようなエンコード処理Ｅｃｄを用いる場合には、共通鍵暗号方式はそれぞれの平文msgの種類（例えばmsg(1)に身長を割り当ててmsg(2)に体重を割り当てる場合には、その各々）について加法に関する準同型性を満たす。
【０１６２】
また、上述と同様に、平文msg(i)のそれぞれを更にビット列msg(i)1｜｜…｜｜msg(i)mなどと分割して、エンコード処理をＥｃｄ（msg(1), …, msg(m)）＝ｅ＝Σmsg(i)jｔm*i+j-1又はＥｃｄ（msg(1), …, msg(m)）＝ｅ＝Σmsg(i)jαm*i+j-1としても良い。
【０１６３】
また、共通鍵暗号方式に乗法に関する準同型性を要求する場合、暗号文の乗算結果を因数分解することにより、例えば、乗算結果がいずれの暗号文に基づくかなどの情報が漏洩する可能性がある。
【０１６４】
そのため、乗法の準同型性を損なわない範囲で、暗号文の乗算結果に部分空間Ｍの要素を加算しても良い。
【０１６５】
例えば、部分空間Ｍを多項式環Ｓ＝Ａ［ｔ］の部分集合とするとき、係数ｃ0＝msgと設定し、他の係数ｃ1, …, ｃm-1に乱数を設定するエンコード処理Ｅｃｄ（msg）＝ｅ＝Σｃiｔiを用いるとする。
【０１６６】
この場合、暗号文の乗算結果のうち、乗法の準同型性に影響を与える項は定数項（ｔ0）であり、ｔ, …, ｔ2(m-1)の項は乗法の準同型性には影響を与えない。そこで、係数ｃ0＝０と設定し、係数ｃ1, …, ｃ2(m-1)をランダムに設定したランダム多項式Σｃiｔiを作成し、当該ランダム多項式Σｃiｔiを暗号文の乗算結果に加算しても良い。このランダム多項式Σｃiｔiはマスク多項式と呼んでもよい。
【０１６７】
（７）共通鍵の更新を行うためのエンコード処理
エンコード処理Ｅｃｄは、平文msgを多項式環Ｓの部分集合Ｍの要素（多項式）に変換する。上述のmsgiやrndiの代わりに、共通鍵の更新用の情報ksiとして利用しても良い。送信者と受信者は、予め定められた手順で、ksiに基づき共通鍵skjを更新する。
【０１６８】
エンコード処理の方法は、上述の（１）から（７）に限定されるものではなく、それら二つ以上を組み合わせた方法を用いても良い。
【０１６９】
上述した第１の実施形態および変形例では、秘密鍵skを解に含むマスク多項式ｇ（ｘ1, …, ｘn）を使用して、ｃ（ｘ1, …, ｘn）＝ｇ（ｘ1, …, ｘn）＋ｅにより暗号化処理を行った。このとき、部分空間Ｍの中で可逆な要素Ｄ（たとえばＤ＝１）を使用して、暗号化処理をｃ（ｘ1, …, ｘn）＝［ｇ（ｘ1, …, ｘn）＋Ｄ］＊ｅとして計算してもよい。ここで、「＊」はＲ内の乗算をあらわす。この場合、暗号文ｃ（ｘ1, …, ｘn）は、秘密鍵skを入力して、ｃ（ｓ1, …, ｓn）＝［ｇ（ｓ1, …, ｓn）＋Ｄ］＊ｅ＝Ｄ＊ｅを計算し、Ｄ＊ｅをＤで割り算してｅを計算してもよい。
【０１７０】
＜第２の実施形態の概要＞
次に、第２の実施形態の概要を説明する。
【０１７１】
第１の実施形態では、可換環Ｒ及びＳの要素を用いる共通鍵暗号装置の構成を示した。  第２の実施形態では、第１の実施形態におけるマスク多項式ｇ（ｘ1, …, ｘn）と秘密鍵sk＝（ｓ1, …, ｓn）として、代数曲面多項式Ｘ（ｘ，ｙ）とそのセクション（ｕx（ｔ），ｕy（ｔ））を用いている。ここで、マスク多項式ｇ（ｘ1, …, ｘn）は、多項式環Ｓ上で定義される代数曲面を表す代数曲面多項式Ｘ（ｘ，ｙ）である。当該代数曲面は、ｘ，ｙの２変数を含む代数曲面多項式Ｘ（ｘ，ｙ）で表される零点の集合であり、ｘ，ｙがｔでパラメタライズされた曲線が存在する。秘密鍵（共通鍵）skは、当該曲線を表すｄ次のセクション多項式（ｕx（ｔ），ｕy（ｔ））である。
【０１７２】
具体的には、Ｆq＝｛０，１，２, …, ｑ−１｝をｑ元体とする。ｑ元体Ｆq上で定義されてｔを変数とする１変数多項式が存在する空間をＦq［ｔ］とする。
【０１７３】
空間Ｆq［ｔ］＝｛Σｃiｔi｜ｃi∈Ｆq｝上の代数曲面とはｘ，ｙに関する次数がｗ次の２変数多項式Ｘ（ｘ，ｙ）∈（Ｆq［ｔ］）［ｘ，ｙ］で表される零点の集合であり、Ｘ（ｕx（ｔ），ｕy（ｔ））＝０を満たす代数曲線（ｕx（ｔ），ｕy（ｔ））∈（Ｆq［ｔ］）2を代数曲面多項式Ｘ（ｘ，ｙ）＝０のセクションという。なお、ｕx（ｔ），ｕy（ｔ）は、ｘ，ｙがｔでパラメタライズされた多項式である。
【０１７４】
代数曲線（ｕx（ｔ），ｕy（ｔ））が与えられたときに、代数曲線（ｕx（ｔ），ｕy（ｔ））をセクションにもつような代数曲面多項式Ｘ（ｘ，ｙ）＝０を構成することは容易である。しかしながら、代数曲面多項式Ｘ（ｘ，ｙ）＝０が与えられたときに、特定のＸ（ｘ，ｙ）を除けば、代数曲面多項式Ｘ（ｘ，ｙ）＝０のセクション（ｕx（ｔ），ｕy（ｔ））を求める方法は知られていない。このため、第２の実施形態では、共通鍵暗号方式の秘密鍵skとして、代数曲面のセクションを用いている。
【０１７５】
第２の実施形態の記法では、第１の実施形態における多項式環Ｓ，可換環Ｒ，マスク多項式ｇ（ｘ1…，ｘn），暗号文ｃ（ｘ1…，ｘn），秘密鍵skを、それぞれ、空間Ｆq［ｔ］，空間（Ｆq［ｔ］）［ｘ，ｙ］，代数曲面多項式Ｘ（ｘ，ｙ），暗号文ｃ（ｘ，ｙ），セクション（ｕx（ｔ），ｕy（ｔ））と設定したものと見做すことができる。なお、体は環でもあるので、ｑ元体Ｆqは多項式環Ｓ及び可換環Ｒを含む。
【０１７６】
あるいは、第２の実施形態の記法では、第１の実施形態における可換環Ｒ，代数曲面多項式Ｘ（ｘ，ｙ）∈（Ｆq［ｔ］）［ｘ，ｙ］，暗号文ｃ（ｘ1…，ｘn）∈（Ｆq［ｔ］）［ｘ，ｙ］を、それぞれ、空間Ｆq［ｘ，ｙ，ｔ］，代数曲面多項式Ｘ（ｘ，ｙ，ｔ）∈Ｆq［ｘ，ｙ，ｔ］，暗号文ｃ（ｘ，ｙ，ｔ）∈Ｆq［ｘ，ｙ，ｔ］と見做すこともできる。
【０１７７】
以降の説明では、誤解のない限り、前者の記法を用いている。
【０１７８】
これらｑ元体Ｆq及び位数ｑは、システムにおける公開パラメータとしても良いし、共通鍵を共有する通信者間での秘密情報としても良い。
【０１７９】
続いて、第２の実施形態を説明するための記法を詳細に説明する。
【０１８０】
秘密鍵skは、Ｆq［ｔ］の２個の要素（ｕx（ｔ），ｕy（ｔ））で構成される。
【０１８１】
第２の実施形態においては、平文msgはエンコード処理Ｅｃｄにより、Ｆq［ｔ］の部分集合Ｍの要素にエンコードされる。ここで、平文msgから部分集合Ｍの要素ｅへのエンコード処理をｅ＝Ｅｃｄ（msg）で表す。
【０１８２】
一方、部分集合Ｍの要素ｅからデコード結果msg’へのデコード処理をmsg’＝Ｄｃｄ（ｅ）で表す。
【０１８３】
エンコード処理Ｅｃｄあるいはデコード処理Ｄｃｄは平文msgあるいは要素ｅのほかに、秘密鍵skを入力として受け付け、ｅ＝Ｅｃｄ（sk，msg）あるいはmsg’＝Ｄｃｄ（sk，ｅ）を演算してもよい。エンコード処理Ｅｃｄとデコード処理Ｄｃｄは、平文msg＝Ｄｃｄ（Ｅｃｄ（msg））となるように設計する（必要に応じてエンコード処理Ｅｃｄとデコード処理Ｄｃｄの入力に秘密鍵skを追加する）。
【０１８４】
例えば、エンコード処理Ｅｃｄは、平文msgをビット表現してｎ個のビット列msg1｜｜msg2｜｜…｜｜msgnに分割し（ここで｜｜はビット連結を表す）、平文多項式ｅ＝Σmsgiｔi-1を出力してもよい。ここで、ｎは、前述の次数ｄとｗに対して、ｎ≦ｄｗ−１をみたす値である。この場合、デコード処理Ｄｃｄ（sk，ｅ）により、平文多項式ｅからｎ個のビット列msg1｜｜msg2｜｜…｜｜msgnを抽出し、平文msg＝msg1｜｜msg2｜｜…｜｜msgnを復元できる。
【０１８５】
あるいは、平文msgをｌ進展開して（例えばｌ＝２16＝６５５３６）、各桁を各ビット列msgiに対応付けても良い。その際、デコード処理は、ｌ進展開された値を２進数あるいは１０進数など所定の形式に変換して平文msgを復元する。
【０１８６】
さらに、上述ではエンコード処理を平文msgに対して確定的に計算する例を記載したが、各ビット列msgiのうちのいくつかをランダムな整数rndiとし、エンコード処理を平文msgに対して確率的に計算しても良い。その際、デコード処理はランダムな整数rndiを除く各ビット列msgiを取り出して、平文msgを復元する。
【０１８７】
これら、エンコード処理Ｅｃｄ及びデコード処理Ｄｃｄは、システムにおける公開パラメータとしても良いし、共通鍵を共有する通信者間での秘密情報としても良い。
【０１８８】
＜第２の実施形態の具体的な構成＞
以下、第２の実施形態について具体的に説明する。
【０１８９】
図７は第２の実施形態に係る共通鍵暗号装置の構成を示す図であり、図８は同実施形態における共通鍵復号装置の構成を示す図である。
【０１９０】
ここで、共通鍵暗号装置４００は、パラメータ記憶部４０１、入出力部４０２及び暗号化処理部４０３を備えている。
【０１９１】
パラメータ記憶部４０１は、前述した秘密鍵skのほかに、安全性のパラメータを記憶する。パラメータ記憶部４０１は、空間Ｆq［ｔ］及び空間（Ｆq［ｔ］）［ｘ，ｙ］の情報を記憶してもよい。また、パラメータ記憶部４０１は、エンコード処理Ｅｃｄの情報を記憶してもよい。
【０１９２】
入出力部４０２は、平文msgの入力を受け付け、暗号化処理部４０３で計算した暗号文ｃ（ｘ，ｙ）を出力する。
【０１９３】
暗号化処理部４０３は、入出力部４０２で入力を受け付けた平文msgとパラメータ記憶部４０１が記憶する情報に基づいて、暗号文ｃ（ｘ，ｙ）を計算する。
【０１９４】
一方、共通鍵復号装置５００は、図８に示すように、パラメータ記憶部５０１、入出力部５０２及び復号処理部５０３を備えている。
【０１９５】
パラメータ記憶部５０１は、秘密鍵skのほかに、安全性のパラメータを記憶する。パラメータ記憶部５０１は、空間Ｆq［ｔ］及び空間（Ｆq［ｔ］）［ｘ，ｙ］の情報を記憶してもよい。また、パラメータ記憶部５０１は、デコード処理Ｄｃｄの情報を記憶してもよい。
【０１９６】
入出力部５０２は、暗号文ｃ（ｘ，ｙ）を入力として受け付け、平文msg＝msg’を出力する。
【０１９７】
復号処理部５０３は、入出力部５０２で受け付けた暗号文ｃ（ｘ，ｙ）とパラメータ記憶部５０１が記憶する情報に基づいて暗号文ｃ（ｘ，ｙ）を復号し、復号結果msg’である平文msg＝msg’を得る。
【０１９８】
次に、以上のように構成された共通鍵暗号装置及び共通鍵復号装置の動作について図９及び図１０のフローチャートを用いて説明する。
【０１９９】
共通鍵暗号装置４００は、図９に示すように、入出力部４０２が、平文msgの入力を受け付ける（ＳＴ３１）。また、パラメータ記憶部４０１内のパラメータは、適宜、暗号化処理部４０３に読み出される。パラメータは、例えば、セクション（ｕx（ｔ），ｕy（ｔ））及び空間（Ｆq［ｔ］）［ｘ，ｙ］等である。
【０２００】
暗号化処理部４０３は、平文msgを空間Ｆq［ｔ］の部分空間Ｍの多項式の各項に埋め込むようにエンコード処理を実行し、平文多項式ｅ＝Ｅｃｄ（msg）を計算する（ＳＴ３２）。
【０２０１】
暗号化処理部４０３は、空間Ｆq［ｔ］上で定義される空間（Ｆq［ｔ］）［ｘ，ｙ］に基づいて、セクション多項式（ｕx（ｔ），ｕy（ｔ））を解に含む代数曲面多項式Ｘ（ｘ，ｙ）を生成する。例えば、暗号化処理部４０３は、代数曲面多項式Ｘ（ｘ，ｙ）を空間（Ｆq［ｔ］）［ｘ，ｙ］からランダムに選択する（ＳＴ３３〜ＳＴ３５）。なお、代数曲面多項式Ｘ（ｘ，ｙ）は、平文多項式ｅに加算されて平文多項式ｅを隠蔽する。
【０２０２】
具体的には、暗号化処理部４０３は、空間（Ｆq［ｔ］）［ｘ，ｙ］から多項式ｆ（ｘ，ｙ）をランダムに選択する（ＳＴ３３）。多項式ｆ（ｘ，ｙ）は、ランダム多項式ｆ（ｘ，ｙ）と呼んでもよい。
【０２０３】
暗号化処理部４０３は、多項式ｆ（ｘ，ｙ）の２変数ｘ，ｙに秘密鍵（ｕx（ｔ），ｕy（ｔ））を代入した多項式ｆ（ｕx（ｔ），ｕy（ｔ））を計算し（ＳＴ３４）、代数曲面多項式Ｘ（ｘ，ｙ）＝ｆ（ｘ，ｙ）−ｆ（ｕx（ｔ），ｕy（ｔ））を設定する（ＳＴ３５）。
【０２０４】
ここで、代数曲面多項式Ｘ（ｘ，ｙ）や多項式ｆ（ｘ，ｙ）は、空間（Ｆq［ｔ］）［ｘ，ｙ］から選ばれるのではなく、空間（Ｆq［ｔ］）［ｘ，ｙ］の部分集合から選ばれても良い。
【０２０５】
あるいは、代数曲面多項式Ｘ（ｘ，ｙ）や多項式ｆ（ｘ，ｙ）は、ランダムに選ばれるのではなく、暗号化を処理する日時や秘密鍵、あるいは平文などに依存して選ばれても良い。また、ステップＳＴ３３〜ＳＴ３５は、ステップＳＴ３１が実行される前に予め実行されても良い。
【０２０６】
暗号化処理部４０３は、平文多項式ｅと代数曲面多項式Ｘ（ｘ，ｙ）とを加算する処理により、暗号文ｃ（ｘ，ｙ）＝ｅ＋Ｘ（ｘ，ｙ）を計算する（ＳＴ３６）。
【０２０７】
共通鍵暗号装置４００は、暗号文ｃ（ｘ，ｙ）を入出力部４０２から出力する（ＳＴ３７）。
【０２０８】
以上が共通鍵暗号装置４００の動作である。続いて、共通鍵復号装置５００の動作を説明する。
【０２０９】
共通鍵復号装置５００は、図１０に示すように、入出力部５０２が、暗号文ｃ（ｘ，ｙ）の入力を受け付ける（ＳＴ４１）。
【０２１０】
復号処理部５０３は、パラメータ記憶部５０１内の秘密鍵sk＝（ｕx（ｔ），ｕy（ｔ））に基づいて、暗号文ｃ（ｘ，ｙ）から平文多項式ｅを復号する。例えば、復号処理部５０３は、秘密鍵sk＝（ｕx（ｔ），ｕy（ｔ））を暗号文ｃ（ｘ，ｙ）に代入し、次式に示すように、平文多項式ｅを計算する（ＳＴ４２）。
【０２１１】
ｃ（ｕx（ｔ），ｕy（ｔ））＝ｅ＋Ｘ（ｕx（ｔ），ｕy（ｔ））＝ｅ
復号処理部５０３は、復号した平文多項式ｅから平文msgを復号する。すなわち、復号処理部５０３は、平文多項式ｅをデコードして、復号結果msg’＝Ｄｃｄ（ｅ）を計算する（ＳＴ４３）。
【０２１２】
例えば、前述したように、Ｅｃｄ（msg）＝ｅ＝Σmsgiｔi-1、但し、平文msg＝msg1｜｜msg2｜｜…｜｜msgn、の場合には、ステップＳＴ４２で計算される多項式ｃ（ｕx（ｔ），ｕy（ｔ））は、ｔを変数とする平文多項式ｅ＝Σmsgiｔi-1である。従って、平文多項式ｅ＝Σmsgiｔi-1において、ｔiの係数をビット列msg’iに割り当てて復号結果msg’＝msg’1｜｜msg’2｜｜…｜｜msg’nと設定することにより、平文msg＝msg’を復元することができる。
【０２１３】
最後に、共通鍵復号装置５００は、入出力部５０２から平文mgs＝msg’を出力する（ＳＴ４４）。
【０２１４】
上述したように本実施形態によれば、第１の実施形態におけるマスク多項式として、空間Ｆq［ｔ］（多項式環Ｓ）上で定義される代数曲面を表す代数曲面多項式Ｘ（ｘ，ｙ）を用いる。この代数曲面は、ｘ，ｙの２変数を含む当該代数曲面多項式Ｘ（ｘ，ｙ）で表される零点の集合であり、ｘ，ｙがｔでパラメタライズされた曲線が存在する。第１の実施形態における秘密鍵sk（共通鍵）として、当該曲線を表すセクション多項式（ｕx（ｔ），ｕy（ｔ））を用いる。このような構成により、第１の実施形態と同様の効果を得ることができる。
【０２１５】
すなわち、本実施形態によれば、平文msgを空間Ｆq［ｔ］の部分空間の多項式の各項に埋め込むことにより平文多項式ｅを生成し、平文多項式ｅと、セクション多項式（共通鍵）を解に含む代数曲面多項式（マスク多項式）とを加算する処理により、暗号文ｃ（ｘ，ｙ）を生成する構成により、並列度を上げて、計算の効率を向上させることができる。
【０２１６】
また、本実施形態によれば、このように生成された暗号文ｃ（ｘ，ｙ）の入力を受け付けると、共通鍵（セクション多項式）に基づいて、当該暗号文ｃ（ｘ，ｙ）から平文多項式ｅを復号し、当該復号した平文多項式ｅから平文msgを復号する構成により、並列度を上げて、計算の効率を向上させることができる。
【０２１７】
従って、前述同様に、一つの暗号文に多倍長精度の平文を埋め込むことができ、多倍長演算を行うことなくＣＰＵの処理単位よりも大きいサイズの平文を暗号化できる。
【０２１８】
＜第２の実施形態の変形例＞
第２の実施形態に関しても、第１の実施形態の変形例２及びその他の変形例と同様に、準同型演算及びエンコード処理（１）〜（７）に関する変形例を構成することができる。  第１の実施形態と同様に、上述した第２の実施形態および変形例では、秘密鍵skを解に含むマスク多項式Ｘ（ｘ,ｙ）を使用して、ｃ（ｘ,ｙ）＝Ｘ（ｘ,ｙ）＋ｅにより暗号化処理を行った。このとき、部分空間Ｍの中で可逆な要素Ｄ（たとえばＤ＝１）を使用して、暗号化処理をｃ（ｘ,ｙ）＝［Ｘ（ｘ,ｙ）＋Ｄ］＊ｅとして計算してもよい。ここで、「＊」はＲ内の乗算をあらわす。この場合、暗号文ｃ（ｘ,ｙ）は、秘密鍵skを入力して、ｃ（ｕx（ｔ）,ｕy（ｔ））＝［Ｘ（ｘ,ｙ）＋Ｄ］＊ｅ＝Ｄ＊ｅを計算し、Ｄ＊ｅをＤで割り算してｅを計算してもよい。
【０２１９】
以上説明した少なくとも一つの実施形態によれば、平文情報を多項式環の部分空間の多項式の各項に埋め込むことにより平文多項式を生成し、平文多項式と、共通鍵を解に含むマスク多項式とを加算する処理により、暗号文を生成する構成により、並列度を上げて、計算の効率を向上させることができる。
【０２２０】
また、このように生成された暗号文の入力を受け付けると、共通鍵に基づいて、当該暗号文から平文多項式を復号し、当該復号した平文多項式から平文情報を復号する構成により、並列度を上げて、計算の効率を向上させることができる。
【０２２１】
なお、上記の各実施形態に記載した手法は、コンピュータに実行させることのできるプログラムとして、磁気ディスク（フロッピー（登録商標）ディスク、ハードディスクなど）、光ディスク（ＣＤ−ＲＯＭ、ＤＶＤなど）、光磁気ディスク（ＭＯ）、半導体メモリなどの記憶媒体に格納して頒布することもできる。
【０２２２】
また、この記憶媒体としては、プログラムを記憶でき、かつコンピュータが読み取り可能な記憶媒体であれば、その記憶形式は何れの形態であっても良い。
【０２２３】
そして、記憶媒体からコンピュータにインストールされたプログラムの指示に基づきコンピュータ上で稼働しているＯＳ（オペレーティングシステム）や、データベース管理ソフト、ネットワークソフト等のＭＷ（ミドルウェア）等が上記実施形態を実現するための各処理の一部を実行しても良い。
【０２２４】
さらに、各実施形態における記憶媒体は、コンピュータと独立した媒体に限らず、ＬＡＮやインターネット等により伝送されたプログラムをダウンロードして記憶または一時記憶した記憶媒体も含まれる。
【０２２５】
また、記憶媒体は１つに限らず、複数の媒体から上記の各実施形態における処理が実行される場合も本発明における記憶媒体に含まれ、媒体構成は何れの構成であっても良い。
【０２２６】
なお、各実施形態におけるコンピュータは、記憶媒体に記憶されたプログラムに基づき、上記の各実施形態における各処理を実行するものであって、パソコン等の１つからなる装置、複数の装置がネットワーク接続されたシステム等の何れの構成であっても良い。
【０２２７】
また、各実施形態におけるコンピュータとは、パソコンに限らず、情報処理機器に含まれる演算処理装置、マイコン等も含み、プログラムによって本発明の機能を実現することが可能な機器、装置を総称している。
【０２２８】
なお、本発明のいくつかの実施形態を説明したが、これらの実施形態は、例として提示したものであり、発明の範囲を限定することは意図していない。これら新規な実施形態は、その他の様々な形態で実施されることが可能であり、発明の要旨を逸脱しない範囲で、種々の省略、置き換え、変更を行うことができる。これら実施形態やその変形は、発明の範囲や要旨に含まれるとともに、特許請求の範囲に記載された発明とその均等の範囲に含まれる。
【符号の説明】
【０２２９】
１００，４００…共通鍵暗号装置、１０１，２０１，３０１，４０１，５０１…パラメータ記憶部、１０２，２０２，３０２，４０２，５０２…入出力部、１０３，４０３…暗号化処理部、２００，５００…共通鍵復号装置、２０３，５０３…復号処理部、３００…準同型演算装置、３０３…準同型演算部。
【図１】
2015114629.tif 000003
【図２】
2015114629.tif 000004
【図３】
2015114629.tif 000005
【図４】
2015114629.tif 000006
【図５】
2015114629.tif 000007
【図６】
2015114629.tif 000008
【図７】
2015114629.tif 000009
【図８】
2015114629.tif 000010
【図９】
2015114629.tif 000011
【図１０】
2015114629.tif 000012