(57)【特許請求の範囲】
【請求項１】
所定の暗号方式に従い平文を暗号化して暗号文を生成する暗号装置と、前記所定の暗号方式に従い前記暗号文を復号化して復号文を生成する復号装置とを備える暗号システムであって、
前記復号装置は、
整数ｐ、ｑに対し、多項式ｆ、ｇと、Ｆｑ×ｆ＝１（ｍｏｄ  ｑ）となる多項式Ｆｑと（ここでａ（ｍｏｄ  ｂ）は、ａをｂで割った余りを示す。）、Ｆｐ×ｆ＝１（ｍｏｄ  ｐ）となる多項式Ｆｐとを生成し、前記多項式ｇおよび前記多項式Ｆｑの積と法をｑとして合同である多項式ｈを公開鍵として生成し、前記多項式ｆおよび前記多項式Ｆｐを得ることのできる情報を秘密鍵として生成する鍵生成部と、
前記秘密鍵を使用して前記暗号文を復号化して前記復号文を生成する復号化部とを備え、
前記暗号装置は、
前記公開鍵及びランダムに選択した多項式ｒを使用して前記平文を暗号化して前記暗号文を生成する暗号化部を備え、
前記多項式ｆ、前記多項式ｇ、前記多項式ｒ、前記平文であるＮ次元配列のすべての要素は０もしくは１であり、前記整数ｐと前記整数ｑとは互いに素であり、前記整数ｑはｑ＝（２＾ｋ）であり（ただし、２＾ｋは１に２をｋ回掛けた結果である）、
前記多項式ｆは、Ｎ次元配列の値が１となる要素の数を規定する非負整数ｄｆに基づき生成され、
前記多項式ｇは、Ｎ次元配列の値が１となる要素の数を規定する非負整数ｄｇに基づき生成され、
前記多項式ｒは、Ｎ次元配列の値が１となる要素の数を規定する非負整数ｄに基づき選択され、
前記次元Ｎ、前記非負整数ｄｆ、前記非負整数ｄｇ、前記非負整数ｄは、復号エラーが発生しないための条件を表す条件式に基づいており、
前記多項式ｆ、ｇ、ｈ、ｒ、Ｆｐ、Ｆｑは、（Ｎ−１）次以下の多項式であり、多項式の変数をＸとした場合に、多項式の積はＸ＾Ｎ＝１（Ｘ＾ＮはＸのＮ乗）という関係式を用いて演算される
ことを特徴とする暗号システム。
【請求項２】
前記条件式は、Ｍｉｎ（ｄｇ，ｄ）＋ｄｆ＜（ｑ−１）／ｐ（ただし、Ｍｉｎ（ａ，ｂ）はａとｂの小さい方の数を表す）である
ことを特徴とする、請求項１に記載の暗号システム（ただし、Ｍｉｎ（ａ，ｂ）はａとｂの小さい方の数を表す）。
【請求項３】
所定の暗号方式に従い平文を暗号化して暗号文を生成する暗号装置であって、
公開鍵及びランダムに選択した多項式ｒを使用して前記平文を暗号化して前記暗号文を生成する暗号化部を備え、
前記所定の暗号方式は、
整数ｐ、ｑに対し、多項式ｆ、ｇと、Ｆｑ×ｆ＝１（ｍｏｄ  ｑ）となる多項式Ｆｑと、Ｆｐ×ｆ＝１（ｍｏｄ  ｐ）となる多項式Ｆｐとを生成し、前記多項式ｇおよび前記多項式Ｆｑの積と法をｑとして合同である多項式ｈを公開鍵として生成し、前記多項式ｆおよび前記多項式Ｆｐを得ることのできる情報を秘密鍵として生成する鍵生成ステップと、
前記公開鍵及びランダムに選択した多項式ｒを使用して前記平文を暗号化して前記暗号文を生成する暗号化ステップと、
前記秘密鍵を使用して前記暗号文を復号化して復号文を生成する復号化ステップとを含む方法により平文の暗号化および暗号文の復号化が行なわれる暗号方式であり、
前記多項式ｆ、前記多項式ｇ、前記多項式ｒ、前記平文であるＮ次元配列のすべての要素は０もしくは１であり、前記整数ｐと前記整数ｑとは互いに素であり、前記整数ｑはｑ＝（２＾ｋ）であり、
前記多項式ｆは、Ｎ次元配列の値が１となる要素の数を規定する非負整数ｄｆに基づき生成され、
前記多項式ｇは、Ｎ次元配列の値が１となる要素の数を規定する非負整数ｄｇに基づき生成され、
前記多項式ｒは、Ｎ次元配列の値が１となる要素の数を規定する非負整数ｄに基づき選択され、
前記次元Ｎ、前記非負整数ｄｆ、前記非負整数ｄｇ、前記非負整数ｄは、復号エラーが発生しないための条件を表す条件式に基づいており、
前記多項式ｆ、ｇ、ｈ、ｒ、Ｆｐ、Ｆｑは、（Ｎ−１）次以下の多項式であり、多項式の変数をＸとした場合に、多項式の積はＸ＾Ｎ＝１（Ｘ＾ＮはＸのＮ乗）という関係式を用いて演算される
ことを特徴とする、暗号装置。
【請求項４】
前記条件式は、Ｍｉｎ（ｄｇ，ｄ）＋ｄｆ＜（ｑ−１）／ｐ（ただし、Ｍｉｎ（ａ，ｂ）はａとｂの小さい方の数を表す）である
ことを特徴とする請求項３記載の暗号装置。
【請求項５】
所定の暗号方式に従い暗号文を復号化して復号文を生成する復号装置であって、
整数ｐ、ｑに対し、多項式ｆ、ｇと、Ｆｑ×ｆ＝１（ｍｏｄ  ｑ）となる多項式Ｆｑと、Ｆｐ×ｆ＝１（ｍｏｄ  ｐ）となる多項式Ｆｐとを生成し、前記多項式ｇおよび前記多項式Ｆｑの積と法をｑとして合同である多項式ｈを公開鍵として生成し、前記多項式ｆおよび前記多項式Ｆｐを得ることのできる情報を秘密鍵として生成する鍵生成部と、
前記秘密鍵を使用して前記暗号文を復号化して前記復号文を生成する復号化部とを備え、
前記所定の暗号方式は、
整数ｐ、ｑに対し、多項式ｆ、ｇと、Ｆｑ×ｆ＝１（ｍｏｄ  ｑ）となる多項式Ｆｑと、Ｆｐ×ｆ＝１（ｍｏｄ  ｐ）となる多項式Ｆｐとを生成し、前記多項式ｇおよび前記多項式Ｆｑの積と法をｑとして合同である多項式ｈを公開鍵として生成し、前記多項式ｆおよび前記多項式Ｆｐを得ることのできる情報を秘密鍵として生成する鍵生成ステップと、
前記公開鍵及びランダムに選択した多項式ｒを使用して前記平文を暗号化して前記暗号文を生成する暗号化ステップと、
前記秘密鍵を使用して前記暗号文を復号化して前記復号文を生成する復号化ステップとを含む方法により平文の暗号化および暗号文の復号化が行なわれる暗号方式であり、
前記多項式ｆ、前記多項式ｇ、前記多項式ｒ、前記平文であるＮ次元配列のすべての要素は０もしくは１であり、前記整数ｐと前記整数ｑとは互いに素であり、前記整数ｑはｑ＝（２＾ｋ）であり、
前記多項式ｆは、Ｎ次元配列の値が１となる要素の数を規定する非負整数ｄｆに基づき生成され、
前記多項式ｇは、Ｎ次元配列の値が１となる要素の数を規定する非負整数ｄｇに基づき生成され、
前記多項式ｒは、Ｎ次元配列の値が１となる要素の数を規定する非負整数ｄに基づき選択され、
前記次元Ｎ、前記非負整数ｄｆ、前記非負整数ｄｇ、前記非負整数ｄは、復号エラーが発生しないための条件を表す条件式に基づいており、
前記多項式ｆ、ｇ、ｈ、ｒ、Ｆｐ、Ｆｑは、（Ｎ−１）次以下の多項式であり、多項式の変数をＸとした場合に、多項式の積はＸ＾Ｎ＝１（Ｘ＾ＮはＸのＮ乗）という関係式を用いて演算される
ことを特徴とする復号装置。
【請求項６】
前記条件式は、Ｍｉｎ（ｄｇ，ｄ）＋ｄｆ＜（ｑ−１）／ｐ（ただし、Ｍｉｎ（ａ，ｂ）はａとｂの小さい方の数を表す）である
ことを特徴とする、請求項５記載の復号装置。
【請求項７】
コンピュータが、平文を暗号化して暗号文を生成し、かつ前記暗号文を復号化して復号文を生成する暗号方法であって、
コンピュータが、公開鍵と、整数ｐ、ｑに対し、多項式ｆ、ｇと、Ｆｑ×ｆ＝１（ｍｏｄ  ｑ）となる多項式Ｆｑと、Ｆｐ×ｆ＝１（ｍｏｄ  ｐ）となる多項式Ｆｐとを生成し、前記多項式ｇおよび前記多項式Ｆｑの積と法をｑとして合同である多項式ｈを公開鍵として生成し、前記多項式ｆおよび前記多項式Ｆｐを得ることのできる情報を秘密鍵として生成する鍵生成ステップと、
コンピュータが、前記公開鍵及びランダムに選択した多項式ｒを使用して前記平文を暗号化して前記暗号文を生成する暗号化ステップと、
コンピュータが、前記秘密鍵を使用して前記暗号文を復号化して前記復号文を生成する復号化ステップとを含み、
前記多項式ｆ、前記多項式ｇ、前記多項式ｒ、前記平文であるＮ次元配列のすべての要素は０もしくは１であり、前記整数ｐと前記整数ｑとは互いに素であり、前記整数ｑはｑ＝（２＾ｋ）であり（ただし、２＾ｋは１に２をｋ回掛けた結果である）、
前記多項式ｆは、Ｎ次元配列の値が１となる要素の数を規定する非負整数ｄｆに基づき生成され、
前記多項式ｇは、Ｎ次元配列の値が１となる要素の数を規定する非負整数ｄｇに基づき生成され、
前記多項式ｒは、Ｎ次元配列の値が１となる要素の数を規定する非負整数ｄに基づき選択され、
前記次元Ｎ、前記非負整数ｄｆ、前記非負整数ｄｇ、前記非負整数ｄは、復号エラーが発生しないための条件を表す条件式に基づいており、
前記多項式ｆ、ｇ、ｈ、ｒ、Ｆｐ、Ｆｑは、（Ｎ−１）次以下の多項式であり、多項式の変数をＸとした場合に、多項式の積はＸ＾Ｎ＝１（Ｘ＾ＮはＸのＮ乗）という関係式を用いて演算される
ことを特徴とする暗号方法。
【請求項８】
コンピュータを、所定の暗号方式に従い平文を暗号化して暗号文を生成する暗号装置として機能させるためのプログラムであって、
公開鍵及びランダムに選択した多項式ｒを使用して前記平文を暗号化して前記暗号文を生成する暗号化部としてコンピュータを機能させ、
前記所定の暗号方式は、
整数ｐ、ｑに対し、多項式ｆ、ｇと、Ｆｑ×ｆ＝１（ｍｏｄ  ｑ）となる多項式Ｆｑと、Ｆｐ×ｆ＝１（ｍｏｄ  ｐ）となる多項式Ｆｐとを生成し、前記多項式ｇおよび前記多項式Ｆｑの積と法をｑとして合同である多項式ｈを公開鍵として生成し、前記多項式ｆおよび前記多項式Ｆｐを得ることのできる情報を秘密鍵として生成する鍵生成ステップと、
前記公開鍵及びランダムに選択した多項式ｒを使用して前記平文を暗号化して前記暗号文を生成する暗号化ステップと、
前記秘密鍵を使用して前記暗号文を復号化して復号文を生成する復号化ステップとを含む方法により平文の暗号化および暗号文の復号化が行なわれる暗号方式であり、
前記多項式ｆ、前記多項式ｇ、前記多項式ｒ、前記平文であるＮ次元配列のすべての要素は０もしくは１であり、前記整数ｐと前記整数ｑとは互いに素であり、前記整数ｑはｑ＝（２＾ｋ）であり、
前記多項式ｆは、Ｎ次元配列の値が１となる要素の数を規定する非負整数ｄｆに基づき生成され、
前記多項式ｇは、Ｎ次元配列の値が１となる要素の数を規定する非負整数ｄｇに基づき生成され、
前記多項式ｒは、Ｎ次元配列の値が１となる要素の数を規定する非負整数ｄに基づき選択され、
前記次元Ｎ、前記非負整数ｄｆ、前記非負整数ｄｇ、前記非負整数ｄは、復号エラーが発生しないための条件を表す条件式に基づいており、
前記多項式ｆ、ｇ、ｈ、ｒ、Ｆｐ、Ｆｑは、（Ｎ−１）次以下の多項式であり、多項式の変数をＸとした場合に、多項式の積はＸ＾Ｎ＝１（Ｘ＾ＮはＸのＮ乗）という関係式を用いて演算される
ことを特徴とするプログラム。
【請求項９】
コンピュータを、所定の暗号方式に従い暗号文を復号化して復号文を生成する復号装置として機能させるためのプログラムであって、
整数ｐ、ｑに対し、多項式ｆ、ｇと、Ｆｑ×ｆ＝１（ｍｏｄ  ｑ）となる多項式Ｆｑと、Ｆｐ×ｆ＝１（ｍｏｄ  ｐ）となる多項式Ｆｐとを生成し、前記多項式ｇおよび前記多項式Ｆｑの積と法をｑとして合同である多項式ｈを公開鍵として生成し、前記多項式ｆおよび前記多項式Ｆｐを得ることのできる情報を秘密鍵として生成する鍵生成部と、
前記秘密鍵を使用して前記暗号文を復号化して前記復号文を生成する復号化部としてコンピュータを機能させ、
前記所定の暗号方式は、
整数ｐ、ｑに対し、多項式ｆ、ｇと、Ｆｑ×ｆ＝１（ｍｏｄ  ｑ）となる多項式Ｆｑと、Ｆｐ×ｆ＝１（ｍｏｄ  ｐ）となる多項式Ｆｐとを生成し、前記多項式ｇおよび前記多項式Ｆｑの積と法をｑとして合同である多項式ｈを公開鍵として生成し、前記多項式ｆおよび前記多項式Ｆｐを得ることのできる情報を秘密鍵として生成する鍵生成ステップと、
前記公開鍵及びランダムに選択した多項式ｒを使用して前記平文を暗号化して前記暗号文を生成する暗号化ステップと、
前記秘密鍵を使用して前記暗号文を復号化して前記復号文を生成する復号化ステップとを含む方法により平文の暗号化および暗号文の復号化が行なわれる暗号方式であり、
前記多項式ｆ、前記多項式ｇ、前記多項式ｒ、前記平文であるＮ次元配列のすべての要素は０もしくは１であり、前記整数ｐと前記整数ｑとは互いに素であり、前記整数ｑはｑ＝（２＾ｋ）であり、
前記多項式ｆは、Ｎ次元配列の値が１となる要素の数を規定する非負整数ｄｆに基づき生成され、
前記多項式ｇは、Ｎ次元配列の値が１となる要素の数を規定する非負整数ｄｇに基づき生成され、
前記多項式ｒは、Ｎ次元配列の値が１となる要素の数を規定する非負整数ｄに基づき選択され、
前記次元Ｎ、前記非負整数ｄｆ、前記非負整数ｄｇ、前記非負整数ｄは、復号エラーが発生しないための条件を表す条件式に基づいており、
前記多項式ｆ、ｇ、ｈ、ｒ、Ｆｐ、Ｆｑは、（Ｎ−１）次以下の多項式であり、多項式の変数をＸとした場合に、多項式の積はＸ＾Ｎ＝１（Ｘ＾ＮはＸのＮ乗）という関係式を用いて演算される
ことを特徴とするプログラム。
【請求項１０】
所定の暗号方式に従い平文を暗号化して暗号文を生成する集積回路であって、
公開鍵及びランダムに選択した多項式ｒを使用して前記平文を暗号化して前記暗号文を生成する暗号化部を備え、
前記所定の暗号方式は、
整数ｐ、ｑに対し、多項式ｆ、ｇと、Ｆｑ×ｆ＝１（ｍｏｄ  ｑ）となる多項式Ｆｑと、Ｆｐ×ｆ＝１（ｍｏｄ  ｐ）となる多項式Ｆｐとを生成し、前記多項式ｇおよび前記多項式Ｆｑの積と法をｑとして合同である多項式ｈを公開鍵として生成し、前記多項式ｆおよび前記多項式Ｆｐを得ることのできる情報を秘密鍵として生成する鍵生成ステップと、
前記公開鍵及びランダムに選択した多項式ｒを使用して前記平文を暗号化して前記暗号文を生成する暗号化ステップと、
前記秘密鍵を使用して前記暗号文を復号化して復号文を生成する復号化ステップとを含む方法により平文の暗号化および暗号文の復号化が行なわれる暗号方式であり、
前記多項式ｆ、前記多項式ｇ、前記多項式ｒ、前記平文であるＮ次元配列のすべての要素は０もしくは１であり、前記整数ｐと前記整数ｑとは互いに素であり、前記整数ｑはｑ＝（２＾ｋ）であり、
前記多項式ｆは、Ｎ次元配列の値が１となる要素の数を規定する非負整数ｄｆに基づき生成され、
前記多項式ｇは、Ｎ次元配列の値が１となる要素の数を規定する非負整数ｄｇに基づき生成され、
前記多項式ｒは、Ｎ次元配列の値が１となる要素の数を規定する非負整数ｄに基づき選択され、
前記次元Ｎ、前記非負整数ｄｆ、前記非負整数ｄｇ、前記非負整数ｄは、復号エラーが発生しないための条件を表す条件式に基づいており、
前記多項式ｆ、ｇ、ｈ、ｒ、Ｆｐ、Ｆｑは、（Ｎ−１）次以下の多項式であり、多項式の変数をＸとした場合に、多項式の積はＸ＾Ｎ＝１（Ｘ＾ＮはＸのＮ乗）という関係式を用いて演算される
ことを特徴とする集積回路。
【請求項１１】
所定の暗号方式に従い暗号文を復号化して復号文を生成する集積回路であって、
整数ｐ、ｑに対し、多項式ｆ、ｇと、Ｆｑ×ｆ＝１（ｍｏｄ  ｑ）となる多項式Ｆｑと、Ｆｐ×ｆ＝１（ｍｏｄ  ｐ）となる多項式Ｆｐとを生成し、前記多項式ｇおよび前記多項式Ｆｑの積と法をｑとして合同である多項式ｈを公開鍵として生成し、前記多項式ｆおよび前記多項式Ｆｐを得ることのできる情報を秘密鍵として生成する鍵生成部と、
前記秘密鍵を使用して前記暗号文を復号化して前記復号文を生成する復号化部とを備え、
前記所定の暗号方式は、
整数ｐ、ｑに対し、多項式ｆ、ｇと、Ｆｑ×ｆ＝１（ｍｏｄ  ｑ）となる多項式Ｆｑと、Ｆｐ×ｆ＝１（ｍｏｄ  ｐ）となる多項式Ｆｐとを生成し、前記多項式ｇおよび前記多項式Ｆｑの積と法をｑとして合同である多項式ｈを公開鍵として生成し、前記多項式ｆおよび前記多項式Ｆｐを得ることのできる情報を秘密鍵として生成する鍵生成ステップと、
前記公開鍵及びランダムに選択した多項式ｒを使用して前記平文を暗号化して前記暗号文を生成する暗号化ステップと、
前記秘密鍵を使用して前記暗号文を復号化して前記復号文を生成する復号化ステップとを含む方法により平文の暗号化および暗号文の復号化が行なわれる暗号方式であり、
前記多項式ｆ、前記多項式ｇ、前記多項式ｒ、前記平文であるＮ次元配列のすべての要素は０もしくは１であり、前記整数ｐと前記整数ｑとは互いに素であり、前記整数ｑはｑ＝（２＾ｋ）であり、
前記多項式ｆは、Ｎ次元配列の値が１となる要素の数を規定する非負整数ｄｆに基づき生成され、
前記多項式ｇは、Ｎ次元配列の値が１となる要素の数を規定する非負整数ｄｇに基づき生成され、
前記多項式ｒは、Ｎ次元配列の値が１となる要素の数を規定する非負整数ｄに基づき選択され、
前記次元Ｎ、前記非負整数ｄｆ、前記非負整数ｄｇ、前記非負整数ｄは、復号エラーが発生しないための条件を表す条件式に基づいており、
前記多項式ｆ、ｇ、ｈ、ｒ、Ｆｐ、Ｆｑは、（Ｎ−１）次以下の多項式であり、多項式の変数をＸとした場合に、多項式の積はＸ＾Ｎ＝１（Ｘ＾ＮはＸのＮ乗）という関係式を用いて演算される
ことを特徴とする集積回路。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、情報セキュリティ技術としての暗号技術に関し、特に、復号エラーが発生しない暗号に関するものである。
【背景技術】
【０００２】
従来、送信装置と受信装置との間で秘匿通信を実現する方法として、公開鍵暗号を用いた暗号化通信が提案されている。従来の暗号化通信について簡単に説明すると、送信装置が、通信内容を受信装置の公開鍵を用いて暗号化して送信し、受信装置は、暗号化された通信内容を受信し、それを自身の秘密鍵を用いて復号して元の通信内容を得る方法である（例えば、非特許文献１参照）。ここで、公開鍵の値から秘密鍵の値を計算するのは困難である。この方法を用いる一般的な暗号通信システムでは、送信装置及び受信装置は、ともに複数存在する。まず、送信装置は、通信先受信装置の公開鍵を取得する。この公開鍵は、通信先受信装置が有する秘密鍵と対になるものであり当該システムにおいて公開されている。そして、送信装置は、通信すべきデータ内容を上記のように取得した公開鍵で暗号化して送信する。一方、受信装置は、上記のように暗号化された通信内容データを受信する。そして、受信装置は、暗号化された通信内容データを、自身の有する秘密鍵で復号して元の通信内容データを得る。
【０００３】
１９９６年、高速処理が可能な公開鍵暗号として、ＮＴＲＵ（エヌティーアールユー・クリプトシステムズ・インコーポレーテッドの商標）暗号が提案された（例えば、非特許文献２参照）。このＮＴＲＵ暗号は、ある法の下でべき乗剰余演算を行うＲＳＡ（Ｒｉｖｅｓｔ  Ｓｈａｍｉｒ  Ａｄｌｅｍａｎ）暗号や楕円曲線上の点のスカラ倍演算を行う楕円曲線暗号に比べ、高速に演算可能な多項式演算により暗号化と復号化とを行う。このため、従来の公開鍵暗号よりも高速に処理することが可能で、ソフトウェア処理でも実用的な時間で暗号化及び復号化の処理が可能ある。
【０００４】
従って、公開鍵暗号にＮＴＲＵ暗号を用いた暗号通信システムでは、従来の公開鍵暗号を用いた暗号通信システムよりも、送信装置及び受信装置の処理が高速に行えるという利点がある。
【０００５】
このＮＴＲＵ暗号方式については、非特許文献２に詳しく述べられているので、ここでは詳細な説明を省略するが、以下に簡単に説明する。
【０００６】
＜ＮＴＲＵ暗号方式＞
（１）ＮＴＲＵ暗号のパラメータ
ＮＴＲＵ暗号は、非負整数のパラメータ、Ｎ、ｐ、ｑ、ｄｆ、ｄｇ、ｄを持つ。以下に、これらのパラメータの意味を説明する。
【０００７】
（ｉ）パラメータＮ
ＮＴＲＵ暗号は、多項式の演算により暗号化と復号化を行う公開鍵暗号方式である。ＮＴＲＵ暗号で扱う多項式の次元は、上記パラメータＮにより決まる。
【０００８】
ＮＴＲＵ暗号で扱う多項式は、上記パラメータＮに対し、（Ｎ−１）次以下の整数係数多項式であり、例えばＮ＝５のとき、Ｘ＾４＋Ｘ＾３＋１等の多項式である。ここで、「Ｘ＾ａ」はＸのａ乗を意味することとする。また、暗号化時あるいは復号化時に用いられる公開鍵ｈ、秘密鍵ｆ、平文ｍ、乱数ｒ、暗号文ｃはいずれも、（Ｎ−１）次以下の多項式として表現される。
【０００９】
そして、多項式演算は、上記パラメータＮに対し、「Ｘ＾Ｎ＝１」という関係式を用いて、演算結果が常に（Ｎ−１）次以下の多項式になるように演算される。例えば、Ｎ＝５の場合、多項式Ｘ＾４＋Ｘ＾２＋１と多項式Ｘ＾３＋Ｘの積は、多項式と多項式の積を「×」、整数と多項式の積（あるいは整数と整数の積）を「・」とすると、「Ｘ＾５＝１」という関係から、
（Ｘ＾４＋Ｘ＾２＋１）×（Ｘ＾３＋Ｘ）
＝Ｘ＾７＋２・Ｘ＾５＋２・Ｘ＾３＋Ｘ
＝Ｘ＾２×１＋２・１＋２・Ｘ＾３＋Ｘ
＝２・Ｘ＾３＋Ｘ＾２＋Ｘ＋２
というように、常に（Ｎ−１）次元以下の多項式になるように計算される。
【００１０】
（ｉｉ）パラメータｐ、ｑ
ＮＴＲＵ暗号では、２以上の整数であるパラメータｐ、ｑが用いられる。ＮＴＲＵ暗号で出現する多項式の係数は、ｐ、ｑを法とした剰余を取る。非特許文献２に記載の通り、このパラメータｐ、ｑは互いに素となる必要がある。
【００１１】
（ｉｉｉ）パラメータｄｆ、ｄｇ、ｄ
ＮＴＲＵ暗号で扱う秘密鍵の一部である多項式ｆ、公開鍵である多項式ｈを生成するときに多項式ｆと共に用いる多項式ｇ、及び平文を暗号化するときに用いる乱数である多項式ｒの選び方は、それぞれパラメータｄｆ、ｄｇ、及びｄにより決まる。
【００１２】
まず、多項式ｆは、ｄｆ個の係数が１であり、かつ（ｄｆ−１）個の係数が−１であり、かつ他の係数は０となるように選ばれる。すなわち、多項式ｆは（Ｎ−１）次以下の多項式であり、０次（定数項）から（Ｎ−１）次までのＮ個の係数を有する。このＮ個の係数のうち、ｄｆ個の係数が１であり、かつ（ｄｆ−１）個の係数が−１であり、かつ（Ｎ−２ｄｆ＋１）個の係数が０となるように多項式ｆが選ばれる。
【００１３】
そして、多項式ｇは、ｄｇ個の係数が１であり、かつｄｇ個の係数が−１であり、かつ他の係数が０となるように選ばれる。また、乱数である多項式ｒは、ｄ個の係数が１であり、かつｄ個の係数が−１であり、かつ他の係数が０となるように選ばれる。
【００１４】
非特許文献２には、ＮＴＲＵ暗号のパラメータの例として、（Ｎ，ｐ，ｑ，ｄｆ，ｄｇ，ｄ）＝（１０７，３，６４，１５，１２，５）、（Ｎ，ｐ，ｑ，ｄｆ，ｄｇ，ｄ）＝（１６７，３，１２８，６１，２０，１８）、（Ｎ，ｐ，ｑ，ｄｆ，ｄｇ，ｄ）＝（５０３，３，２５６，２１６，７２，５５）の３つの例が挙げられている。
【００１５】
（２）ＮＴＲＵ暗号の鍵生成
ＮＴＲＵ暗号では、上述したように、パラメータｄｆおよびｄｇを用いてランダムに多項式ｆおよび多項式ｇがそれぞれ生成される。そして非特許文献２に記載の通り、Ｆｑ×ｆ＝１（ｍｏｄ  ｑ）なる関係を有する多項式Ｆｑを用いて、
ｈ＝Ｆｑ×ｇ（ｍｏｄ  ｑ）
により、多項式ｈが生成される。ここで、ａ（ｍｏｄ  ｂ）はａをｂで除したときの剰余を示す。
【００１６】
また、ＮＴＲＵ暗号では、秘密鍵を（ｆ，Ｆｐ）、公開鍵をｈとする。
【００１７】
ここで、「ｘ＝ｙ（ｍｏｄ  ｑ）」は、多項式ｙの第ｉ次の係数を剰余が０からｑ−１の範囲に収まるようにするために、法ｑで割ったときの剰余を多項式ｘの第ｉ次の係数とする演算である（０≦ｉ≦Ｎ−１）。すなわち、ｙの各係数を、０から（ｑ−１）の範囲に収まるようにｍｏｄ  ｑ演算（ｑで除したときの剰余を求める演算、法ｑでの剰余演算）を施した多項式を、多項式ｘとする演算である。
【００１８】
（３）ＮＴＲＵ暗号の暗号化
ＮＴＲＵ暗号の暗号化では、平文である多項式ｍを暗号化し、暗号文である多項式ｃを計算する。まず、上述したような多項式である乱数ｒをランダムに生成する。すなわち、乱数ｒは（Ｎ−１）次以下の多項式であり、０次（定数項）から（Ｎ−１）次までＮ個の係数があるが、このＮ個の係数のうち、ｄ個の係数が１であり、かつｄ個の係数が−１であり、かつ（Ｎ−２ｄ）個の係数が０となるように、ランダムに多項式（乱数）ｒを選ぶ。
【００１９】
そして、この乱数ｒと公開鍵ｈとを用いて、係数が０、１もしくは−１である（Ｎ−１）次以下の平文ｍに対し、
ｃ＝ｐ・ｒ×ｈ＋ｍ（ｍｏｄ  ｑ）
により、暗号文ｃを生成する。
【００２０】
この演算は、上述した通り、多項式（ｐ・ｒ×ｈ＋ｍ）の各係数を、０から（ｑ−１）の範囲に収まるようにｍｏｄ  ｑ演算を施した多項式を、多項式ｃとする演算である。
【００２１】
（４）ＮＴＲＵ暗号の復号化
ＮＴＲＵ暗号の復号化では、暗号文である多項式ｃを復号化し、復号文である多項式ｍ'を計算する。復号化時には、まず、暗号文ｃに対し、秘密鍵の一部である多項式ｆを用いて、
ａ＝ｆ×ｃ（ｍｏｄ  ｑ＊）
により多項式ａを計算する。
【００２２】
ここで、（ｍｏｄ  ｑ＊）は、上述の（ｍｏｄ  ｑ）演算と異なり、多項式（ｆ×ｃ）の第ｉ次の係数を、〈−ｑ／２〉＋１から〈ｑ／２〉の範囲に収まるように法ｑで割ったときの剰余を、多項式ａの第ｉ次の係数とする演算である（０≦ｉ≦Ｎ−１）。すなわち、係数が〈ｑ／２〉からｑ−１までの間の値である場合は、係数からｑを減算して、上記範囲に収まるよう調整する。ここで、〈ｘ〉は、ｘ以下の数の中で最も大きい数を示す。例えば、〈−１／２〉＝−１である。
【００２３】
次に、多項式ａに対し、パラメータｐを用いて、
ｂ＝ａ（ｍｏｄ  ｐ）
により、多項式ｂを生成する。
【００２４】
そして、多項式ｂに対し、秘密鍵の一部である多項式Ｆｐを用いて、
ｍ'＝Ｆｐ×ｂ（ｍｏｄ  ｐ＊）
により、復号文ｍ'を計算する。
【００２５】
なお、この（ｍｏｄ  ｐ＊）という演算は、上述した通り、多項式（Ｆｐ×ｂ）の第ｉ次の係数を、〈−ｐ／２〉＋１から〈ｐ／２〉の範囲に収まるように法ｐで割ったときの剰余を、多項式ｍ'の第ｉ次の係数とする演算である。
【００２６】
なお、このＮＴＲＵ暗号に関して、上述のパラメータは全てｐ＝３となるパラメータであるが、このパラメータの他にｐ＝２となるパラメータも開示されている（例えば、非特許文献３参照）。なお、非特許文献２に記載の通り、ｐ＝３の場合は、平文ｍは係数が０、１もしくは−１の３値である多項式であるが、ｐ＝２の場合は、平文ｍは係数が０もしくは１の２値である多項式である。そして、秘密鍵である多項式ｆ、多項式ｇ、乱数ｒは、ｐ＝２かｐ＝３かに関わらず係数が０、１もしくは−１の３値である多項式である。
【００２７】
また、このＮＴＲＵ暗号に関して、鍵生成処理において、
ｈ＝ｐ・Ｆｑ×ｇ（ｍｏｄ  ｑ）
を満たすように、公開鍵ｈを生成し、暗号化処理を
ｃ＝ｒ×ｈ＋ｍ（ｍｏｄ  ｑ）
により行う方法も開示されている（例えば、非特許文献５参照）。
【００２８】
しかしながら、上述したＮＴＲＵ暗号は、公開鍵を用いて平文を暗号化して暗号文を生成し、正規の秘密鍵を用いて暗号文を復号して復号文を生成しても、復号文が元の平文と異なる場合が発生する（例えば、非特許文献２参照）。このことを復号エラー（ｄｅｃｒｙｐｔｉｏｎ  ｆａｉｌｕｒｅ）が発生するという。非特許文献２に記載のＮＴＲＵ暗号は、上述したパラメータの取り方により復号エラーの発生確率が変わるが、当該文献に開示されているパラメータではいずれも、１０＾（−５）程度の確率で復号エラーが発生することが知られている（例えば、非特許文献３参照）。
【００２９】
これに対し、近年、パラメータを後述するパラメータに限定し、復号化時に復号エラー発生確率を低減させる計算を追加することにより、復号エラー確率を２＾（−１００）以下にする新しいＮＴＲＵ暗号方式であるＮＴＲＵＥｎｃｒｙｐｔと呼ばれる方式が提案されている（例えば、非特許文献４参照）。
【００３０】
このＮＴＲＵＥｎｃｒｙｐｔ方式については、非特許文献４に詳しく述べられているので、ここでは詳細な説明を省略するが、以下に簡単に説明する。
【００３１】
＜ＮＴＲＵＥｎｃｒｙｐｔ方式＞
（１）ＮＴＲＵＥｎｃｒｙｐｔのパラメータ
ＮＴＲＵＥｎｃｒｙｐｔでは、非負整数のパラメータ、Ｎ、ｐ、ｑ、ｄｆ、ｄｇ、ｄを持つ。非特許文献４には、ＮＴＲＵＥｎｃｒｙｐｔのパラメータとして（Ｎ，ｐ，ｑ，ｄｆ，ｄｇ，ｄ）＝（２５１，２，２３９，７２，７２，７２）というパラメータのみが開示されている。ＮＴＲＵＥｎｃｒｙｐｔでは、これらのパラメータのうち、パラメータｄｆ、ｄｇ、ｄの意味がＮＴＲＵ暗号と異なる。
【００３２】
以下に、上述のＮＴＲＵ暗号との差異点を中心に、これらのパラメータの意味を説明する。
【００３３】
（ｉ）パラメータＮ
ＮＴＲＵＥｎｃｒｙｐｔは、ＮＴＲＵ暗号と同様、多項式の演算により暗号化と復号化を行う公開鍵暗号方式である。ＮＴＲＵ暗号と同様、ＮＴＲＵＥｎｃｒｙｐｔで扱う多項式は、上記パラメータＮに対し、（Ｎ−１）次以下の整数係数多項式であり、多項式演算は、Ｘ＾Ｎ＝１という関係式を用いて、演算結果が常に（Ｎ−１）次以下の多項式になるように演算される。
【００３４】
（ｉｉ）パラメータｐ、ｑ
ＮＴＲＵＥｎｃｒｙｐｔでは、上述の通りｐ＝２、かつｑ＝２３９となるパラメータｐ、ｑを用いる。このパラメータｐ、ｑは互いに素となっている。
【００３５】
（ｉｉｉ）パラメータｄｆ、ｄｇ、ｄ
ＮＴＲＵＥｎｃｒｙｐｔで扱う秘密鍵の一部である多項式ｆ、公開鍵である多項式ｈを生成するときに多項式ｆと共に用いる多項式ｇ、及び平文を暗号化するときに用いる乱数である多項式ｒの選び方は、それぞれパラメータｄｆ、ｄｇ、ｄにより決まる。
【００３６】
まず、ｄｆ個の係数が１であり、かつ他の係数は０となるような（Ｎ−１）次以下の多項式ｆが選ばれる。
【００３７】
そして、ｄｇ個の係数が１であり、かつ他の係数は０となるような（Ｎ−１）次以下の多項式が選ばれる。また、乱数ｒとして、同様に、ｄ個の係数が１であり、かつ他の係数は０となるような（Ｎ−１）次以下の多項式が選ばれる。
【００３８】
すなわち、ＮＴＲＵ暗号では、多項式ｆ、ｇ、ｒとして、係数が０、１もしくは−１である多項式を選んでいたのに対し、ＮＴＲＵＥｎｃｒｙｐｔでは、多項式ｆ、ｇ、ｒとして、係数が０もしくは１である多項式を選ぶ点がＮＴＲＵ暗号と異なる。
【００３９】
（２）ＮＴＲＵＥｎｃｒｙｐｔの鍵生成
ＮＴＲＵＥｎｃｒｙｐｔでは、上述したように、パラメータｄｆ、ｄｇを用いてランダムに多項式ｆ、ｇを生成する。そして非特許文献４に記載の通り、Ｆｑ×ｆ＝１（ｍｏｄ
ｑ）となる多項式Ｆｑを用いて、
ｈ＝ｐ・Ｆｑ×ｇ（ｍｏｄ  ｑ）
により、多項式ｈを生成する。また、ＮＴＲＵＥｎｃｒｙｐｔでは、秘密鍵を（ｆ，Ｆｐ）、公開鍵を多項式ｈとする。
【００４０】
（３）ＮＴＲＵＥｎｃｒｙｐｔの暗号化
ＮＴＲＵＥｎｃｒｙｐｔでは、まず、上述したような乱数ｒをランダムに生成する。すなわち、パラメータｄを用いてｄ個の係数が１であり、かつ他の係数は０となるような（Ｎ−１）次以下の多項式をランダムに選び、乱数ｒとする。
【００４１】
そして、この乱数ｒと公開鍵ｈを用いて、係数が０もしくは１である（Ｎ−１）次以下の平文ｍに対し、
ｃ＝ｒ×ｈ＋ｍ（ｍｏｄ  ｑ）
により、暗号文ｃを生成する。
【００４２】
この演算は、上述した通り、多項式（ｒ×ｈ＋ｍ）の各係数を、０から（ｑ−１）の範囲に収まるようにｍｏｄ  ｑ演算を施した多項式を、多項式ｃとする演算である。
【００４３】
なお、ＮＴＲＵ暗号の説明で述べた通り、鍵生成処理において、
ｈ＝Ｆｑ×ｇ（ｍｏｄ  ｑ）
を満たすように、公開鍵ｈを生成し、暗号化処理を、
ｃ＝ｐ・ｒ×ｈ＋ｍ（ｍｏｄ  ｑ）
により行っても、暗号文ｃの値は同一となるため、本質的な違いはない。
【００４４】
（４）ＮＴＲＵＥｎｃｒｙｐｔの復号化
復号化時には、まず、暗号文ｃに対し、秘密鍵の一部である多項式ｆを用いて、
ａ＝ｆ×ｃ（ｍｏｄ  ｑ＊＊）
により多項式ａを計算する。
【００４５】
ここで、（ｍｏｄ  ｑ＊＊）は、上述の（ｍｏｄ  ｑ）演算と異なり、多項式（ｆ×ｃ）の第ｉ次の係数を適切な幅ｑの区間に収まるように法ｑで割ったときの剰余を、多項式ａの第ｉ次の係数とする演算である（０≦ｉ≦Ｎ−１）。具体的な演算方法は、非特許文献４に、ｃｅｎｔｅｒ１もしくはｃｅｎｔｅｒ２と呼ばれるアルゴリズムで規定されている。
【００４６】
以下に、ｃｅｎｔｅｒ２のアルゴリズムを示す。
【００４７】
（ｃｅｎｔｅｒ２アルゴリズム）
Ｓｔｅｐ１：Ａ＝ｆ×ｃ（ｍｏｄ  ｑ）とし、Ｉ１＝（Ａ（１）−ｐ×ｄ×ｄｇ）／（ｄｆ＾（−１）  ｍｏｄ  ｑ）  ｍｏｄ  ｑを計算する。ここで、Ａ（１）は多項式Ａの変数ｘに１を代入したときの値を示す。
【００４８】
Ｓｔｅｐ２：Ｉ１が〈（Ｎ―ｑ）／２〉＋１から〈（Ｎ＋ｑ）／２〉の範囲に入るようＩ１にｑの倍数を足して調整したときの値をＩ２とする（当然、Ｉ２＝Ｉ１  ｍｏｄ  ｑを満たす）。
【００４９】
Ｓｔｅｐ３：Ｊ＝ｄｆ×Ｉ２＋ｐ×ｄ×ｄｇを計算する。
【００５０】
Ｓｔｅｐ４：Ａの各係数が〈Ｊ／Ｎ―ｑ／２〉＋１から〈Ｊ／Ｎ＋ｑ／２〉の範囲に入るように、各係数にｑの倍数を足して調整した後の多項式をａ（＝ｆ×ｃ（ｍｏｄ  ｑ＊＊））とする。
【００５１】
この演算は、復号エラー発生確率を減少させるために行う処理である。
【００５２】
次に、多項式ａに対し、パラメータｐを用いて、
ｂ＝ａ（ｍｏｄ  ｐ）
により、多項式ｂを生成する。
【００５３】
そして、多項式ｂに対し、秘密鍵の一部である多項式Ｆｐを用いて、
ｍ'＝Ｆｐ×ｂ（ｍｏｄ  ｐ）
により、復号文ｍ'を生成する。
【００５４】
なお、このＮＴＲＵＥｎｃｒｙｐｔに関して、ｄｆ個の係数が１であり、かつ他の係数は０となるような（Ｎ−１）次以下の多項式Ｆを選び、ｆ＝１＋ｐ・Ｆという式により多項式ｆを構成する方式も開示されている（例えば、非特許文献４参照）。この方式は、非特許文献４に記載の通り、多項式ｆがｆ＝１＋ｐ・Ｆという形であるために、Ｆｐ×ｆ＝１（ｍｏｄ  ｐ）となる多項式ＦｐはＦｐ＝１（ｍｏｄ  ｐ）となるので、復号化処理で行う多項式Ｆｐとの多項式乗算が不要となり、
ｍ'＝ａ（ｍｏｄ  ｐ）
により、復号文ｍ'を生成できる。
【００５５】
このＮＴＲＵＥｎｃｒｙｐｔは、復号化時に復号エラー発生確率を減少させる処理を行うことにより、ＮＴＲＵ暗号よりも復号エラーが発生しにくくした方式ではあるが、その復号エラー発生確率は２＾（−１００）以下ということしか示されておらず、復号エラー発生確率が０、すなわち、復号エラーを全く発生させない方法については知られていない。
【００５６】
なお、ＮＴＲＵ暗号及びＮＴＲＵＥｎｃｒｙｐｔ共に多項式を用いて演算を表現しているが、特許文献１ではこれを一般の環Ｒの元として表現している。具体的には、上記の多項式を環Ｒの元とし、ｐ、ｑを環Ｒのイデアルとしている。
【００５７】
【特許文献１】特表２０００−５１６７３３号公報
【非特許文献１】岡本龍明、山本博資、「現代暗号」、シリーズ／情報科学の数学、産業図書、１９９７．
【非特許文献２】Ｊｅｆｆｅｒｙ  Ｈｏｆｆｓｔｅｉｎ，  Ｊｉｌｌ  Ｐｉｐｈｅｒ，  ａｎｄ  Ｊｏｓｅｐｈ  Ｈ．  Ｓｉｌｖｅｒｍａｎ，  "ＮＴＲＵ：  Ａ  ｒｉｎｇ  ｂａｓｅｄ  ｐｕｂｌｉｃ  ｋｅｙ  ｃｒｙｐｔｏｓｙｓｔｅｍ"，  Ｌｅｃｔｕｒｅ  Ｎｏｔｅｓ  ｉｎ  Ｃｏｍｐｕｔｅｒ  Ｓｃｉｅｎｃｅ，  １４２３，  ｐｐ．２６７−２８８，  Ｓｐｒｉｎｇｅｒ−Ｖｅｒｌａｇ，  １９９８．
【非特許文献３】Ｊｏｓｅｐｈ  Ｈ．  Ｓｉｌｖｅｒｍａｎ，  "ＮＴＲＵ  Ｃｒｙｐｔｏｓｙｓｔｅｍｓ  Ｔｅｃｈｎｉｃａｌ  Ｒｅｐｏｒｔ  ＃０１１，  Ｖｅｒｓｉｏｎ  ２，  Ｗｒａｐｓ，  Ｇａｐｓ，  ａｎｄ  Ｌａｔｔｉｃｅ  Ｃｏｎｓｔａｎｔｓ"，  ［ｏｎｌｉｎｅ］、２００１年３月１５日、［２００３年１２月１５日検索］、インターネット＜ＵＲＬ：  ｈｔｔｐ：／／ｗｗｗ．ｎｔｒｕ．ｃｏｍ／ｃｒｙｐｔｏｌａｂ／ｐｄｆ／ＮＴＲＵＴｅｃｈ０１１＿ｖ２．ｐｄｆ＞
【非特許文献４】Ｊｏｓｅｐｈ  Ｈ．  Ｓｉｌｖｅｒｍａｎ，  Ｗ．  Ｗｈｙｔｅ，  "ＮＴＲＵ  Ｃｒｙｐｔｏｓｙｓｔｅｍｓ  Ｔｅｃｈｎｉｃａｌ  Ｒｅｐｏｒｔ  ＃０１８，  Ｖｅｒｓｉｏｎ  １，  Ｅｓｔｉｍａｔｉｎｇ  Ｄｅｃｒｙｐｔｉｏｎ  Ｆａｉｌｕｒｅ  Ｐｒｏｂａｂｉｌｉｔｉｅｓ  ｆｏｒ  ＮＴＲＵＥｎｃｒｙｐｔ"，  ［ｏｎｌｉｎｅ］、２００３年、［２００３年１２月１５日検索］、インターネット＜ＵＲＬ：  ｈｔｔｐ：／／ｗｗｗ．ｎｔｒｕ．ｃｏｍ／ｃｒｙｐｔｏｌａｂ／ｐｄｆ／ＮＴＲＵＴｅｃｈ０１８．ｐｄｆ＞
【非特許文献５】ＮＴＲＵ  Ｃｒｙｐｔｏｓｙｓｔｅｍｓ，  Ｉｎｃ．，  "Ｔｈｅ  ＮＴＲＵ  Ｐｕｂｌｉｃ  Ｋｅｙ  Ｃｒｙｐｔｏｓｙｓｔｅｍ  −  Ａ  Ｔｕｔｏｒｉａｌ"，  ［ｏｎｌｉｎｅ］、［２００３年１２月１５日検索］、インターネット＜ＵＲＬ：  ｈｔｔｐ：／／ｗｗｗ．ｎｔｒｕ．ｃｏｍ／ｃｒｙｐｔｏｌａｂ／ｐｄｆ／ｎｔｒｕｔｕｔｏｒｉａｌｓ．ｐｄｆ＞
【非特許文献６】Ｎｉｃｋ  Ｈｏｗｇｒａｖｅ−Ｇｒａｈａｍ，  Ｊｏｓｅｐｈ  Ｈ．  Ｓｉｌｖｅｒｍａｎ，  ａｎｄ  Ｗｉｌｌｉａｍ  Ｗｈｙｔｅ，  "ＮＴＲＵ  Ｃｒｙｐｔｏｓｙｓｔｅｍｓ  Ｔｅｃｈｎｉｃａｌ  Ｒｅｐｏｒｔ  ＃００４，  Ｖｅｒｓｉｏｎ  ２，  Ａ  Ｍｅｅｔ−Ｉｎ−Ｔｈｅ−Ｍｉｄｄｌｅ  Ａｔｔａｃｋ  ｏｎ  ａｎ  ＮＴＲＵ  Ｐｒｉｖａｔｅ  Ｋｅｙ"，  ［ｏｎｌｉｎｅ］、２００３年、［２００３年１２月１５日検索］、インターネット＜ＵＲＬ：  ｈｔｔｐ：／／ｗｗｗ．ｎｔｒｕ．ｃｏｍ／ｃｒｙｐｔｏｌａｂ／ｐｄｆ／ＮＴＲＵＴｅｃｈ０１８．ｐｄｆ＞"Ｔｈｅ  ＮＴＲＵ  Ｐｕｂｌｉｃ  Ｋｅｙ  Ｃｒｙｐｔｏｓｙｓｔｅｍ  −  Ａ  Ｔｕｔｏｒｉａｌ"，  ［ｏｎｌｉｎｅ］、［２００３年１２月１５日検索］、インターネット＜ＵＲＬ：  ｈｔｔｐ：／／ｗｗｗ．ｎｔｒｕ．ｃｏｍ／ｃｒｙｐｔｏｌａｂ／ｐｄｆ／ＮＴＲＵＴｅｃｈ００４ｖ２．ｐｄｆ＞
【非特許文献７】Ｊｅｆｆｅｒｙ  Ｈｏｆｆｓｔｅｉｎ，  Ｊｏｓｅｐｈ  Ｈ．  Ｓｉｌｖｅｒｍａｎ，  ａｎｄ  Ｗｉｌｌｉａｍ  Ｗｈｙｔｅ，  "ＮＴＲＵ  Ｃｒｙｐｔｏｓｙｓｔｅｍｓ  Ｔｅｃｈｎｉｃａｌ  Ｒｅｐｏｒｔ  ＃０１２，  Ｖｅｒｓｉｏｎ  ２，  Ｅｓｔｉｍａｔｅｄ  Ｂｒｅａｋｉｎｇ  Ｔｉｍｅｓ  ｆｏｒ  ＮＴＲＵ  Ｌａｔｔｉｃｅｓ  "，  ［ｏｎｌｉｎｅ］、２００３年、［２００３年１２月１５日検索］、インターネット＜ＵＲＬ：  ｈｔｔｐ：／／ｗｗｗ．ｎｔｒｕ．ｃｏｍ／ｃｒｙｐｔｏｌａｂ／ｐｄｆ／ＮＴＲＵＴｅｃｈ０１２ｖ２．ｐｄｆ＞
【発明の開示】
【発明が解決しようとする課題】
【００５８】
しかしながら、上述したＮＴＲＵＥｎｃｒｙｐｔ方式では、ｑが２以外の素数であるため、暗号化処理及び復号化処理で行う多項式係数の法ｑでの剰余演算がＮＴＲＵ暗号方式に比べて容易にできない。このため、ＮＴＲＵ暗号方式と比べて暗号化処理及び復号化処理の処理速度が遅くなる、という課題がある。
【００５９】
また、上述したＮＴＲＵＥｎｃｒｙｐｔ方式では、復号エラー発生確率は０ではないため、送信装置と受信装置の間で暗号化通信を行う暗号通信システムに適用した場合、送信装置が送信したデータ内容が、受信装置で正しく得られない場合がある、という課題がある。
【００６０】
本発明は、前記従来の課題を解決するもので、ＮＴＲＵＥｎｃｒｙｐｔ方式より高速なＮＴＲＵ暗号方式を新たに構成し、新たに構成したＮＴＲＵ暗号方式を暗号システムに適用することで、さらに高速な暗号システムを提供することを第１の目的とする。
【００６１】
また、復号エラーが原理的に発生しないＮＴＲＵ暗号方式を新たに構成し、新たに構成したＮＴＲＵ暗号方式を暗号システムに適用することで、送信装置が送信したデータ内容が、常に受信装置で正しく得られるような暗号システムを提供することを第２の目的とする。
【課題を解決するための手段】
【００６２】
上記目的を達成するために、本発明に係る暗号システムは、所定の暗号方式に従い平文を暗号化して暗号文を生成する暗号装置と、前記所定の暗号方式に従い前記暗号文を復号化して復号文を生成する復号装置とを備える暗号システムであって、前記復号装置は、加算、減算、乗算が定義されたＮ次元配列の集合である環Ｒと、前記環Ｒのイデアルｐ、ｑに対し、前記環Ｒの元ｆ、ｇと、ｆ（ｍｏｄ  ｑ）の逆数である元Ｆｑと（ここでａ（ｍｏｄ  ｂ）は、ａをｂで割った余りを示す。）、ｆ（ｍｏｄ  ｐ）の逆数である元Ｆｐとを生成し、前記元ｇおよび前記元Ｆｑの積と法をｑとして合同である元ｈを公開鍵として生成し、前記元ｆおよび前記元Ｆｐを得ることのできる情報を秘密鍵として生成する鍵生成部と、前記秘密鍵を使用して前記暗号文を復号化して前記復号文を生成する復号化部とを備え、前記暗号装置は、前記公開鍵及び前記環Ｒからランダムに選択した元ｒを使用して前記平文を暗号化して前記暗号文を生成する暗号化部を備え、前記元ｆ、前記元ｇ、前記元ｒ、前記平文であるＮ次元配列のすべての要素は０もしくは１であり、前記イデアルｐと前記イデアルｑとは互いに素であり、前記イデアルｑはｑ＝（２＾ｋ）・Ｒである（ただし、２＾ｋは１に２をｋ回掛けた結果である）ことを特徴とする。
【００６３】
ｑを上述のように、定義している。このため、ｑが整数の場合には、ｑは２のべき乗となり、法ｑでの剰余演算（ｍｏｄ  ｑ演算）をビットマスク演算により行なうことができる。よって、暗号システムは、高速に処理を行なうことができる。
【００６４】
また、前記鍵生成部は、前記元ｆは、Ｎ次元配列の値が１となる要素の数を規定する非負整数ｄｆに基づき生成され、前記元ｇは、Ｎ次元配列の値が１となる要素の数を規定する非負整数ｄｇに基づき生成され、前記元ｒは、Ｎ次元配列の値が１となる要素の数を規定する非負整数ｄに基づき選択され、前記イデアルｐは、前記環Ｒの元ｐｇに対しｐ＝ｐｇ・Ｒであり、前記イデアルｑは、前記環の元ｑｇに対しｑ＝ｑｇ・Ｒであり、前記次元Ｎ、前記元ｐｇ、前記元ｑｇ、前記非負整数ｄｆ、前記非負整数ｄｇ、前記非負整数ｄは、復号エラーが発生しないための条件を表す条件式に基づいていてもよい。具体的には、前記条件式は、Ｍｉｎ（ｄｇ，ｄ）＋ｄｆ＜（ｑｇ−１）／ｐｇ（ただし、Ｍｉｎ（ａ，ｂ）はａとｂの小さい方の数を表す）である。
【００６５】
上述の条件式を満たすようにパラメータを設定すると、実施の形態において後述するように、多項式ｐ・ｒ×ｇ＋ｆ×ｍの全ての係数が０から（ｑ−１）の範囲に収まることになり、復号エラーは発生が発生しない。
【００６６】
なお、本発明は、このような特徴的な手段を備える暗号システムとして実現することができるだけでなく、暗号システムに含まれる特徴的な手段をステップとする暗号方法として実現したり、暗号システムを構成する暗号装置および復号装置に含まれる特徴的な手段としてコンピュータを機能させるプログラムとして実現したりすることもできる。そして、そのようなプログラムは、ＣＤ−ＲＯＭ（Compact Disc-Read Only Memory）等の記録媒体やインターネット等の通信ネットワークを介して流通させることができるのは言うまでもない。
【発明の効果】
【００６７】
本発明によると、従来最速のＮＴＲＵＥｎｃｒｙｐｔ方式よりも高速処理可能なＮＴＲＵ暗号方式を新たに構成し、また、このＮＴＲＵ暗号方式を暗号通信に適用することで、従来よりも高速処理可能な暗号システムを構成することできる。
【００６８】
また、復号エラーが原理的に発生しないＮＴＲＵ暗号方式を構成し、また、このＮＴＲＵ暗号方式を暗号システムに適用することで、暗号装置が送信したデータ内容が、常に復号装置で正しく得られるような暗号システムを構成することできる。
【００６９】
さらに、復号エラーが原理的に発生せず、かつ高速処理可能なＮＴＲＵ暗号方式を構成し、また、このＮＴＲＵ暗号方式を暗号システムに適用することで、暗号装置が送信したデータ内容が、常に復号装置で正しく得られ、従来よりも高速処理可能な暗号システムを構成することできるようになった。
【００７０】
以上により、従来達成できなかった暗号システム、暗号装置及び復号装置を提供することができ、その実用的価値は大きい。
【発明を実施するための最良の形態】
【００７１】
以下本発明の実施の形態について、図面を参照しながら説明する。
【００７２】
（実施の形態１）
本実施の形態１に係る暗号通信システム、暗号装置及び復号装置では、従来において最速であるＮＴＲＵＥｎｃｒｙｐｔ方式よりも高速処理可能なＮＴＲＵ暗号方式を新たに構成し、この新たに構成したＮＴＲＵ暗号方式を用いて暗号化通信を行う（以降、この新たに構成した、従来よりも高速処理可能なＮＴＲＵ暗号方式を「第１の変形ＮＴＲＵ暗号方式」と呼ぶ）。
【００７３】
そのため、最初に高速ＮＴＲＵ暗号方式について説明を行う。
【００７４】
以下、従来のＮＴＲＵＥｎｃｒｙｐｔ方式との差異点を中心に第１の変形ＮＴＲＵ暗号方式について説明する。
【００７５】
＜第１の変形ＮＴＲＵ暗号方式＞
第１の変形ＮＴＲＵ暗号方式は、従来のＮＴＲＵＥｎｃｒｙｐｔよりも高速処理可能となるように改変したものである。
【００７６】
第１の変形ＮＴＲＵ暗号方式は、パラメータとしてｐ＝３、ｑ＝２＾ｋ（ｋ：２以上の整数）となるパラメータを用いつつ、多項式ｆ、ｇ、乱数である多項式ｒ及び平文である多項式ｍとして、係数が０もしくは１の２値である多項式を選ぶ点が従来のＮＴＲＵＥｎｃｒｙｐｔと異なる。なお、パラメータｐは、パラメータｑと互いに素になるような値であればよく、３以外の値であってもよい。
【００７７】
以下、この第１の変形ＮＴＲＵ暗号方式について説明を行う。
【００７８】
（１）第１の変形ＮＴＲＵ暗号方式のパラメータ
第１の変形ＮＴＲＵ暗号方式は、非負整数のパラメータ、Ｎ、ｐ、ｑ、ｄｆ、ｄｇ、ｄを持つ。
【００７９】
これらのパラメータの意味は、従来のＮＴＲＵＥｎｃｒｙｐｔ方式と同じであるが、ｐ＝３かつｑ＝２＾ｋ（ｋ：２以上の整数）となるパラメータを生成し、ｐ＝３としているにも拘わらず、多項式ｆ、ｇ、ｒとして係数が０もしくは１の２値である多項式を用いる点が、従来のＮＴＲＵＥｎｃｒｙｐｔと異なる。
【００８０】
（２）第１の変形ＮＴＲＵ暗号方式の鍵生成
第１の変形ＮＴＲＵ暗号方式では、上述したように、パラメータｄｆ、ｄｇを用いてランダムに多項式ｆ、多項式ｇを生成する。具体的には、ｄｆ個の係数が１であり、それ以外の係数が０である多項式ｆを生成し、ｄｇ個の係数が１であり、それ以外の係数が０である多項式ｇを生成する。そして非特許文献２に記載の通り、Ｆｑ×ｆ＝１（ｍｏｄ  ｑ）となる多項式Ｆｑを用いて、
ｈ＝Ｆｑ×ｇ（ｍｏｄ  ｑ）
により、多項式ｈを生成する。秘密鍵を（ｆ，Ｆｐ）、公開鍵をｈとする。
【００８１】
ここで、ｘ＝ｙ（ｍｏｄ  ｑ）は、多項式ｙの第ｉ次の係数を、剰余が０からｑ−１の範囲に収まるように法ｑで割ったときの剰余を、多項式ｘの第ｉ次の係数とする演算である（０≦ｉ≦Ｎ−１）。すなわち、ｙの各係数を、０から（ｑ−１）の範囲に収まるようにｍｏｄ  ｑ演算を施した多項式を、多項式ｘとする演算である。
【００８２】
（３）第１の変形ＮＴＲＵ暗号方式の暗号化
第１の変形ＮＴＲＵ暗号方式の暗号化では、平文である係数が０もしくは１の２値である多項式ｍを暗号化し、暗号文である多項式ｃを計算する。まず、上述したような乱数である多項式ｒをランダムに生成する。すなわち、乱数ｒは（Ｎ−１）次以下の多項式であり、第０次（定数項）から第（Ｎ−１）次までＮ個の係数があるが、このＮ個の係数のうち、ｄ個の係数が１であり、かつｄ個の係数が−１であり、かつ（Ｎ−２ｄ）個の係数は０となるように、ランダムに乱数ｒを選ぶ。
【００８３】
そして、この乱数ｒと公開鍵ｈを用いて、係数が０、１もしくは−１である（Ｎ−１）次以下の平文ｍに対し、
ｃ＝ｐ・ｒ×ｈ＋ｍ（ｍｏｄ  ｑ）
により、暗号文ｃを生成する。
【００８４】
この演算は、上述した通り、多項式（ｐ・ｒ×ｈ＋ｍ）の各係数を、０から（ｑ−１）の範囲に収まるようにｍｏｄ  ｑ演算を施した多項式を、多項式ｃとする演算である。
【００８５】
第１の変形ＮＴＲＵ暗号方式は、ｐ＝３としているにも拘わらず、係数が０もしくは１の２値である多項式を用いる点が、従来のＮＴＲＵＥｎｃｒｙｐｔと異なる。
【００８６】
（４）第１の変形ＮＴＲＵ暗号方式の復号化
第１の変形ＮＴＲＵ暗号方式の復号化では、暗号文である多項式ｃを復号化し、復号文である多項式ｍ'を計算する。復号化時には、まず、暗号文ｃに対し、秘密鍵の一部である多項式ｆを用いて、
ａ＝ｆ×ｃ（ｍｏｄ  ｑ＊）
により多項式ａを計算する。
【００８７】
ここで、（ｍｏｄ  ｑ＊）は、上述の（ｍｏｄ  ｑ）演算と異なり、多項式（ｆ×ｃ）の第ｉ次の係数を、〈−ｑ／２〉＋１から〈ｑ／２〉の範囲に収まるように法ｑで割ったときの剰余を、多項式ａの第ｉ次の係数とする演算である（０≦ｉ≦Ｎ−１）。すなわち、係数が〈ｑ／２〉からｑ−１である場合は、係数からｑを減算して、上記範囲に収まるよう調整する。ここで、〈ｘ〉は、ｘ以下の数の中で最も大きい数を示す。例えば、〈−１／２〉＝−１である。
【００８８】
次に、多項式ａに対し、パラメータｐを用いて、
ｂ＝ａ（ｍｏｄ  ｐ）
により、多項式ｂを生成する。
【００８９】
そして、多項式ｂに対し、秘密鍵の一部である多項式Ｆｐを用いて、
ｍ'＝Ｆｐ×ｂ（ｍｏｄ  ｐ＊）
により、復号文ｍ'を計算する。
【００９０】
なお、この（ｍｏｄ  ｐ＊）という演算は、上述した通り、多項式（Ｆｐ×ｂ）の第ｉ次の係数を、〈−ｐ／２〉＋１から〈ｐ／２〉の範囲に収まるように法ｐで割ったときの剰余を、多項式ｍ'の第ｉ次の係数とする演算である。
【００９１】
＜従来技術と第１の変形ＮＴＲＵ暗号方式との差異点＞
以下、第１の変形ＮＴＲＵ暗号方式が、従来のＮＴＲＵＥｎｃｒｙｐｔ方式よりも高速処理が可能であることを説明し、従来のＮＴＲＵ暗号及びＮＴＲＵＥｎｃｒｙｐｔ方式との差異について説明する。
【００９２】
（ＮＴＲＵＥｎｃｒｙｐｔとの比較）
ＮＴＲＵＥｎｃｒｙｐｔでは、上述した通り、秘密鍵である多項式ｆ、多項式ｇ、乱数である多項式ｒ、平文である多項式ｍとして、係数が０もしくは１である２値の多項式を用いるが、パラメータとしては、ｐ＝２かつｑ＝２３９となるパラメータしか開示されていない。
【００９３】
今、ＮＴＲＵＥｎｃｒｙｐｔの鍵生成、暗号化及び復号化における主な演算には、例えば、
ｃ＝ｒ×ｈ＋ｍ（ｍｏｄ  ｑ）
というように、多項式の係数のｍｏｄ  ｑ演算を行う演算が含まれる。
【００９４】
この際、ＮＴＲＵＥｎｃｒｙｐｔではｑ＝２３９なのに対し、第１の変形ＮＴＲＵ暗号方式では、ｑ＝２＾ｋ（ｋ：２以上の整数）であるために、第１の変形ＮＴＲＵ暗号方式では、ｍｏｄ  ｑ演算を、ビットマスク演算で高速に処理することができる。
【００９５】
例えば、第１の変形ＮＴＲＵ暗号方式のパラメータｑがｑ＝２５６（＝２＾８）の場合には、係数のｍｏｄ  ｑ演算は、ビットマスク演算にて下位８ビットのみをとる演算で実現できる。
【００９６】
ＮＴＲＵＥｎｃｒｙｐｔでは、ｐ＝２であるが、第１の変形ＮＴＲＵ暗号方式はｐ＝３であり、ｍｏｄ  ｐの計算については、ＮＴＲＵＥｎｃｒｙｐｔの方が高速に行える。しかし、ｍｏｄ  ｐの計算は復号化時のみに行うことと、ＮＴＲＵＥｎｃｒｙｐｔには復号エラー発生確率低減のための計算が必要であるが、第１の変形ＮＴＲＵ暗号方式では不要であるため、ｍｏｄ  ｐの計算量増加と相殺する。
【００９７】
したがって、暗号化及び復号化を含めた全体としては、第１の変形ＮＴＲＵ暗号方式は、ＮＴＲＵＥｎｃｒｙｐｔより高速である。
【００９８】
（従来技術との差異）
従来のＮＴＲＵ暗号では、ｐ＝３となるパラメータに対して、多項式ｆ、ｇ、乱数である多項式ｒ、平文である多項式ｍに、係数が０、１もしくは−１である３値の多項式を用いている（ｐ＝２の場合は、これらの多項式のうち、平文ｍ以外に係数が０、１もしくは−１である３値の多項式を用いる。また、ｐ≠２、３の場合は、多項式ｆ、ｇ、ｒに０、１もしくは−１である３値の多項式を用い、ｍに〈−ｐ／２〉＋１から〈ｐ／２〉の範囲の整数を係数にもつｐ値の多項式を用いる）。
【００９９】
一方、従来のＮＴＲＵＥｎｃｒｙｐｔでは、ｐ＝２となるパラメータに対して、多項式ｆ、ｇ、乱数である多項式ｒ、平文である多項式ｍに、係数が０もしくは１である２値の多項式を用いている。
【０１００】
そのため、ＮＴＲＵ暗号では、ｐ＝３となるパラメータに対しては、多項式ｆ、ｇ、乱数である多項式ｒ、平文である多項式ｍとして、３値の多項式を用いることが通常であり、上述した第１の変形ＮＴＲＵ暗号方式のように、ｐ＝３の場合に、これらの多項式として２値の多項式を用いた場合に、暗号の安全性にどのような影響が生じるかは開示されていなかった。
【０１０１】
しかしながら、今、ｐ＝３となるパラメータに対して、多項式ｆ、ｇ、乱数である多項式ｒ、平文である多項式ｍとして係数が０もしくは１となる２値の多項式を用いても、従来のＮＴＲＵ暗号及びＮＴＲＵＥｎｃｒｙｐｔと同様、パラメータを適切に選択すれば、安全性に問題は起こらない。以下にそのことを説明する。
【０１０２】
ＮＴＲＵ暗号及びＮＴＲＵＥｎｃｒｙｐｔに対する攻撃方法としては、非特許文献２に記載の通り、多項式ｆ、ｇ、ｒに対する総当り攻撃と、ＬＬＬアルゴリズムを用いた攻撃（ｌａｔｔｉｃｅ  ｂａｓｅｄ  ａｔｔａｃｋ）が知られている。
【０１０３】
今、総当り攻撃に対する安全性は、非特許文献２や非特許文献６に記載の通り、多項式ｆ、ｇ、ｒのとり得る値の総数に依存する。そのため、ｐ＝３となるパラメータに対して、これらの多項式として３値の多項式を用いる代わりに、２値の多項式を用いたとしても、これらの多項式のとり得る値の総数が十分大きくなるように、パラメータｄｆ、ｄｇ、ｄを選択すれば安全性に問題は発生しない。
【０１０４】
また、ＬＬＬ攻撃に対する安全性は、多項式ｆ、ｇの０でない係数の数に依存することが、非特許文献７に記載されている。そのため、０でない係数の数が十分大きくなるように、ｄｆ、ｄｇを選択すれば、安全性に問題は発生しない。
【０１０５】
＜変形ＮＴＲＵ暗号方式のパラメータの生成方法＞
ここでは、上述した第１の変形ＮＴＲＵ暗号方式のパラメータの生成方法の一例を挙げる。
【０１０６】
上述した通り、第１の変形ＮＴＲＵ暗号方式のパラメータは、ｐ＝３、かつｑ＝２＾ｋ（ｋ：２以上の整数）となるパラメータを生成すればよい。
【０１０７】
そのため、ここでは、まずｐ＝３とし、係数のｍｏｄ  ｑ演算が、ビットマスク演算にて下位８ビットのみをとる演算で実現可能となるよう、ｑ＝２５６とする。
【０１０８】
そして、ｄｆ＝ｄｇ＝ｄとして、上述した総当り攻撃およびＬＬＬ攻撃に対する安全性が規定の値以上となるように、Ｎ、ｄｆ、ｄｇ、ｄの値を生成する。
【０１０９】
なお、これはパラメータの生成方法の一例であり、ｐ＝３、かつｑ＝２＾ｋ（ｋ：２以上の整数）となるパラメータを生成すれば、他の生成方法でもよい。
【０１１０】
以降では、この生成方法により生成された、（Ｎ，ｐ，ｑ，ｄｆ，ｄｇ，ｄ）＝（２５１，３，２５６，７２，７２，７２）というパラメータを用いた場合の説明を行う。
【０１１１】
以上、第１の変形ＮＴＲＵ暗号方式について説明を行ったが、以降、本実施の形態に係る暗号通信システム、暗号装置及び復号装置について説明を行う。
【０１１２】
＜暗号通信システム１の概要＞
図１は、本発明の実施の形態１における暗号通信システム１の全体構成を示す図である。最初に、同図を用いて暗号通信システム１の概要を説明する。
【０１１３】
この暗号通信システム１は、平文ｍの暗号化通信を行うシステムであり、暗号装置１０と、復号装置２０とから構成されており、暗号装置１０と復号装置２０とは通信路３０を介して相互に接続されている。
【０１１４】
そして、この暗号通信システム１は、暗号装置１０と復号装置２０との間で、第１の変形ＮＴＲＵ暗号方式のパラメータとして、（Ｎ，ｐ，ｑ，ｄｆ，ｄｇ，ｄ）＝（２５１，３，２５６，７２，７２，７２）を共有している。
【０１１５】
この暗号通信システム１において、暗号装置１０は、外部から入力された平文ｍを、上述した、第１の変形ＮＴＲＵ暗号方式を用いて暗号化して暗号文ｃを生成し、通信路３０を介して復号装置２０に送信する。
【０１１６】
そして、復号装置２０は、通信路３０を介して暗号装置１０から受信した暗号文ｃを復号して復号文ｍ'を生成して出力する。
【０１１７】
以上が、暗号通信システム１の概要であるが、以下、暗号通信システム１の構成を述べた後、その動作について説明する。
【０１１８】
＜暗号通信システム１の構成＞
暗号通信システム１は、図１に示すように、暗号装置１０と、復号装置２０とから構成され、暗号装置１０と復号装置２０とは通信路３０を介して相互に接続されている。
【０１１９】
以下、これらの構成要素について詳細に説明を行う。
【０１２０】
＜暗号装置１０の構成＞
暗号装置１０は、図２に示すように、パラメータ記憶部１１と、公開鍵記憶部１２と、暗号化部１３とから構成される。
【０１２１】
（１）パラメータ記憶部１１
パラメータ記憶部１１は、例えばＲＡＭ（Random Access Memory）やＥＥＰＲＯＭ（Electrically Erasable Programmable Read Only Memory）のようなメモリで構成されており、後述する暗号化部１３からアクセス可能なものである。
【０１２２】
パラメータ記憶部１１は、ｐ＝３かつｑ＝２＾ｋ（ｋ：２以上の整数）となるパラメータを予め記憶している。ここでは、上述の通り、パラメータ（Ｎ，ｐ，ｑ，ｄｆ，ｄｇ，ｄ）＝（２５１，３，２５６，７２，７２，７２）を予め記憶しているものとする。
【０１２３】
（２）公開鍵記憶部１２
公開鍵記憶部１２は、例えばマイクロコンピュータ及びＲＡＭのようなメモリで構成されており、後述する暗号化部１３からアクセス可能なものである。
【０１２４】
公開鍵記憶部１２は、予め通信路３０を介して復号装置２０の公開鍵ｈを取得して記憶している。
【０１２５】
（３）暗号化部１３
暗号化部１３は、例えばマイクロコンピュータによって構成されており、パラメータ記憶部１１及び公開鍵記憶部１２にアクセス可能である。
【０１２６】
暗号化部１３は、パラメータ記憶部１１からパラメータＮ、パラメータｑ、パラメータｄを読み取り、公開鍵記憶部１２から、公開鍵ｈを読み取る。
【０１２７】
そして、暗号化部１３は、外部からパラメータＮに対し、（Ｎ−１）次以下の多項式で表される、係数が０もしくは１である平文ｍを受け取る。
【０１２８】
そして、暗号化部１３は、パラメータＮ、パラメータｄを用いて、ｄ個の係数が１であり、かつ他の係数が０となるように、（Ｎ−１）次以下の多項式ｒをランダムに選ぶ。これは、例えば、０からＮ−１までの範囲の重複しないｄ個の乱数値Ｒｉ（１≦ｉ≦ｄ）を選び、第Ｒｉ次（１≦ｉ≦ｄ）の係数を１とし、他の係数は０とすることで実現できる。
【０１２９】
そして、暗号化部１３は、平文ｍに対し、乱数である多項式ｒ、公開鍵ｈ、パラメータＮ、パラメータｑを用いて、第１の変形ＮＴＲＵ暗号方式の暗号化処理を行い、暗号文ｃを生成する。
【０１３０】
そして、暗号化部１３は、生成した暗号文ｃを通信路３０を介して復号装置２０へ送信する。
【０１３１】
＜暗号装置１０の動作＞
ここでは、上述した暗号装置１０の動作について説明する。
【０１３２】
暗号装置１０は、ｐ＝３かつｑ＝２＾ｋ（ｋ：２以上の整数）となるパラメータを予め記憶しており、復号装置２０の公開鍵ｈを公開鍵記憶部１２に予め記憶している。そして、外部から、パラメータＮに対し（Ｎ−１）次以下の多項式で表される平文ｍが入力されると、以下に示す処理を行い、上述した第１の変形ＮＴＲＵ暗号方式を用いて平文ｍを暗号化して暗号文ｃを生成し、通信路３０を介して復号装置２０に送信する。
【０１３３】
以下、図３に示すフローチャートを用いて説明する。
【０１３４】
最初に、暗号化部１３は、外部から平文ｍが入力されると、パラメータ記憶部１１からパラメータＮ、パラメータｑ、パラメータｄを読み取り、公開鍵記憶部１２から、公開鍵ｈを読み取る（ステップＳ１０１）。
【０１３５】
次に、暗号化部１３は、パラメータＮ、パラメータｄを用いて、ｄ個の係数が１であり、かつ他の係数が０となるように、（Ｎ−１）次以下の多項式ｒをランダムに選ぶ（ステップＳ１０２）。
【０１３６】
次に、暗号化部１３は、平文ｍに対し、乱数である多項式ｒ、公開鍵ｈ、パラメータＮ、パラメータｑを用いて、第１の変形ＮＴＲＵ暗号方式の暗号化処理を行い、暗号文ｃを生成する（ステップＳ１０３）。
【０１３７】
次に、暗号化部１３は、生成した暗号文ｃを、通信路３０を介して復号装置２０へ送信して処理を終了する（ステップＳ１０４）。
【０１３８】
＜復号装置２０の構成＞
復号装置２０は、図４に示すように、パラメータ記憶部２１と、鍵生成部２２と、秘密鍵記憶部２３と、復号化部２４とから構成される。
【０１３９】
（１）パラメータ記憶部２１
パラメータ記憶部２１は、例えばＥＥＰＲＯＭのようなメモリで構成されており、後述する鍵生成部２２及び復号化部２４からアクセス可能なものである。
【０１４０】
パラメータ記憶部２１は、暗号装置１０のパラメータ記憶部１１と同一のパラメータ（Ｎ，ｐ，ｑ，ｄｆ，ｄｇ，ｄ）を予め記憶している。ここでは、上述の通り、パラメータ（Ｎ，ｐ，ｑ，ｄｆ，ｄｇ，ｄ）＝（２５１，３，２５６，７２，７２，７２）を予め記憶しているものとする。
【０１４１】
（２）鍵生成部２２
鍵生成部２２は、例えばマイクロコンピュータによって構成されており、第１の変形ＮＴＲＵ暗号方式の秘密鍵（ｆ，Ｆｐ）及び公開鍵ｈを生成する。
【０１４２】
鍵生成部２２は、パラメータ記憶部２１からパラメータＮ、パラメータｑ、パラメータｄｆ、パラメータｄｇを読み取り、パラメータＮ、パラメータｄｆを用いて、ｄｆ個の係数が１であり、かつその他の係数が０となるように、（Ｎ−１）次以下の多項式で表される多項式ｆを選ぶ。これは、例えば、０から（Ｎ−１）までの範囲の重複しないｄｆ個の乱数値Ｒｉ（１≦ｉ≦ｄｆ）を選び、第Ｒｉ次（１≦ｉ≦ｄｆ）の係数を１とし、他の係数は０とすることで実現できる。
【０１４３】
そして、鍵生成部２２は、パラメータＮ、パラメータｄｇを用いて、ｄｇ個の係数が１であり、かつその他の係数は０となるように、（Ｎ−１）次以下の多項式で表される多項式ｇを選ぶ。
【０１４４】
そして、鍵生成部２２は、上述した第１の変形ＮＴＲＵ暗号方式の鍵生成処理を行い、多項式Ｆｐ及びｈを生成する。
【０１４５】
そして、鍵生成部２２は、多項式ｈを公開鍵として公開し、予め暗号装置１０が取得できるようにし、多項式ｆとＦｐの対（ｆ，Ｆｐ）を秘密鍵記憶部２３に記憶する。
【０１４６】
（３）秘密鍵記憶部２３
秘密鍵記憶部２３は、例えばＲＡＭのようなメモリで構成されており、鍵生成部２２及び後述する復号化部２４からアクセス可能なものである。
【０１４７】
秘密鍵記憶部２３は、予め鍵生成部２２が生成した多項式ｆとＦｐの対（ｆ，Ｆｐ）を記憶している。
【０１４８】
（４）復号化部２４
復号化部２４は、例えばマイクロコンピュータによって構成されており、パラメータ記憶部２１及び秘密鍵記憶部２３にアクセス可能である。
【０１４９】
復号化部２４は、パラメータ記憶部２１から、パラメータＮ、パラメータｐ、パラメータｑを読み取り、秘密鍵記憶部２３から、多項式ｆとＦｐの対（ｆ，Ｆｐ）を読み取る。
【０１５０】
そして、復号化部２４は、通信路３０を介して暗号装置１０からパラメータＮに対し、（Ｎ−１）次以下の多項式で表される、暗号文ｃを受け取る。
【０１５１】
そして、復号化部２４は、暗号文ｃに対し、秘密鍵である多項式ｆ及びＦｐ、パラメータＮ、パラメータｐ、パラメータｑを用いて、第１の変形ＮＴＲＵ暗号方式の復号化処理を行い、復号文ｍ'を生成する。
【０１５２】
そして、復号化部２４は、生成した復号文ｍ'を外部へ出力する。
【０１５３】
＜復号装置２０の動作＞
ここでは、上述した復号装置２０の動作について説明する。
【０１５４】
復号装置２０は、暗号装置１０と同一のパラメータを予め記憶しており、復号装置２０の秘密鍵である多項式ｆ及びＦｐの対（ｆ，Ｆｐ）と公開鍵である多項式ｈを生成し、公開鍵ｈを公開して予め暗号装置１０が取得できるようにし、秘密鍵（ｆ，Ｆｐ）を秘密鍵記憶部２３に記憶している。そして、復号装置２０は、通信路３０を介して暗号装置１０から、パラメータＮに対し（Ｎ−１）次以下の多項式で表される暗号文ｃを受信すると、以下に示す処理を行い、上述した高速ＮＴＲＵ暗号方式を用いて復号文ｍ'を生成し、外部へ出力する。
【０１５５】
以下、図５に示すフローチャートを用いて説明する。
【０１５６】
最初に、復号化部２４は、通信路３０を介して暗号装置１０から暗号文多項式ｃを受信すると、パラメータ記憶部２１から、パラメータＮ、パラメータｐ、パラメータｑを読み取り、秘密鍵記憶部２３から、秘密鍵（ｆ，Ｆｐ）を読み取る（ステップＳ１３１）。
【０１５７】
次に、復号化部２４は、暗号文ｃに対し、秘密鍵である多項式ｆ及びＦｐ、パラメータＮ、パラメータｐ、パラメータｑを用いて、第１の変形ＮＴＲＵ暗号方式の復号化処理を行い、復号文ｍ'を生成する（ステップＳ１３２）。
【０１５８】
次に、復号化部２４は、生成した復号文ｍ'を外部へ出力して処理を終了する（ステップＳ１３３）。
【０１５９】
＜暗号通信システム１の動作＞
以上、暗号通信システム１の構成について説明したが、ここでは、暗号通信システム１の全体の動作について、図６に示すフローチャートを用いて説明する。
【０１６０】
最初に、パラメータ記憶部１１及びパラメータ記憶部２１は、ｐ＝３かつｑ＝２＾ｋとなるパラメータを予め記憶している（ステップＳ１６１）。
【０１６１】
次に、鍵生成部２２は、パラメータ記憶部２１からパラメータＮ、パラメータｑ、パラメータｄｆ、パラメータｄｇを読み取り、パラメータＮ、パラメータｄｆを用いて、ｄｆ個の係数が１であり、かつその他の係数が０となるように、（Ｎ−１）次以下の多項式で表される多項式ｆを選ぶ（ステップＳ１６２）。
【０１６２】
次に、鍵生成部２２は、パラメータＮ、パラメータｄｇを用いて、ｄｇ個の係数が１であり、かつその他の係数は０となるように、（Ｎ−１）次以下の多項式で表される多項式ｇを選ぶ（ステップＳ１６３）。
【０１６３】
次に、鍵生成部２２は、上述した第１の変形ＮＴＲＵ暗号方式の鍵生成処理を行い、多項式ｈを生成する（ステップＳ１６４）。
【０１６４】
次に、鍵生成部２２は、多項式ｈを公開鍵として公開し、暗号装置１０が取得できるようにし、多項式ｆ及びＦｐの対（ｆ，Ｆｐ）を秘密鍵として秘密鍵記憶部２３に記憶する（ステップＳ１６５）。
【０１６５】
次に、公開鍵記憶部１２は、通信路３０を介して復号装置２０の公開鍵ｈを取得して記憶する（ステップＳ１６６）。
【０１６６】
次に、暗号化部１３は、外部から係数が０もしくは１である平文ｍが入力されると、パラメータ記憶部１１からパラメータＮ、パラメータｑ、パラメータｄを読み取り、公開鍵記憶部１２から、公開鍵ｈを読み取る（ステップＳ１６７）。
【０１６７】
次に、暗号化部１３は、パラメータＮ、パラメータｄを用いて、ｄ個の係数が１であり、かつ他の係数が０となるように、（Ｎ−１）次元以下の多項式ｒをランダムに選ぶ（ステップＳ１６８）。
【０１６８】
次に、暗号化部１３は、平文ｍに対し、乱数である多項式ｒ、公開鍵ｈ、パラメータＮ、パラメータｑを用いて、第１の変形ＮＴＲＵ暗号方式の暗号化処理を行い、暗号文ｃを生成する（ステップＳ１６９）。
【０１６９】
次に、暗号化部１３は、生成した暗号文ｃを通信路３０を介して復号装置２０へ送信する（ステップＳ１７０）。
【０１７０】
次に、復号化部２４は、通信路３０を介して暗号装置１０から暗号文ｃを受信すると、パラメータ記憶部２１から、パラメータＮ、パラメータｐ、パラメータｑを読み取り、秘密鍵記憶部２３から、秘密鍵（ｆ，Ｆｐ）を読み取る（ステップＳ１７１）。
【０１７１】
次に、復号化部２４は、暗号文ｃに対し、秘密鍵である多項式ｆ及びＦｐ、パラメータＮ、パラメータｐ、パラメータｑを用いて、第１の変形ＮＴＲＵ暗号方式の復号化処理を行い、復号文ｍ'を生成する（ステップＳ１７２）。
【０１７２】
次に、復号化部２４は、生成した復号文ｍ'を外部へ出力して処理を終了する（ステップＳ１７３）。
【０１７３】
＜暗号通信システム１の動作検証＞
まず、暗号装置１０及び復号装置２０は、ステップＳ１６１において、ｐ＝３かつｑ＝２＾ｋ（ｋ：２以上の整数）となるパラメータを記憶している。
【０１７４】
そして、復号装置２０が、予め、このパラメータを用いて、ステップＳ１６２及びステップＳ１６３において、係数が０もしくは１の２値である、多項式ｆ及びｇを生成し、ステップＳ１６４において、これらの多項式を基に公開鍵である多項式ｈを生成している。
【０１７５】
そして、暗号装置１０では、ステップＳ１６８にて、係数が０もしくは１の２値である多項式ｒを生成し、ステップＳ１６９にて、ｐ＝３かつｑ＝２＾ｋ（ｋ：２以上の整数）となるパラメータと公開鍵ｈと乱数ｒを用いて、係数が０もしくは１の２値である平文ｍを暗号化して暗号文ｃを生成している。
【０１７６】
そして、復号装置２０では、ステップＳ１７２において、秘密鍵である多項式ｆ及びＦｐと記憶しているｐ＝３かつｑ＝２＾ｋ（ｋ：２以上の整数）となるパラメータを用いて、復号文ｍ'を生成している。
【０１７７】
かかる構成によれば、ｐ＝３かつｑ＝２＾ｋとなるパラメータに対して、多項式ｆ、ｇ、乱数である多項式ｒ、平文である多項式ｍとして、２値の多項式を用いているので、第１の変形ＮＴＲＵ暗号方式を用いて暗号化通信を行うことができる。
【０１７８】
なお、上述の第１の変形ＮＴＲＵ暗号方式の説明で述べた通り、ＮＴＲＵＥｎｃｒｙｐｔ方式よりも高速処理可能となる。
【０１７９】
これにより、従来のＮＴＲＵＥｎｃｒｙｐｔ方式よりも高速処理可能な第１の変形ＮＴＲＵ暗号方式を新たに構成することができ、また、この第１の変形ＮＴＲＵ暗号方式を暗号通信に適用し、従来よりも高速処理可能な暗号通信システムを提供することができる。
【０１８０】
＜変形例＞
なお、上記に説明した実施の形態は、本発明の実施の形態の一例であり、本発明はこの実施の形態に何ら限定されるものではなく、その主旨を逸脱しない範囲において種々なる態様で実施し得るものである。以下のような場合も本発明に含まれる。
【０１８１】
（１）暗号通信システム１では、第１の変形ＮＴＲＵ暗号方式のパラメータとして、ｐ＝３かつｑ＝２＾ｋ（ｋ：２以上の整数）という条件を満たすパラメータを用いているが、さらに、後述する条件式ＥＦＣ１を満たすパラメータを用いてもよい。
【０１８２】
これにより、後述する通り復号エラーが原理的に発生しなくなるため、暗号装置が送信したデータ内容が、常に復号装置で正しく得られるような暗号通信システムを実現することができる。
【０１８３】
なお、このとき、復号エラーが原理的に発生しないため、ＮＴＲＵＥｎｃｒｙｐｔと異なり、復号エラー発生確率を減少させる処理が不要であるため、以下のように復号化を行ってもよい。
【０１８４】
まず、暗号文ｃに対し、秘密鍵の一部である多項式ｆを用いて、
ａ＝ｆ×ｃ（ｍｏｄ  ｑ）
により多項式ａが計算される。
【０１８５】
そして、この多項式ａに対し、ＮＴＲＵＥｎｃｒｙｐｔと同様にして、復号エラー発生確率を低減させる処理が行なわれ、復号文ｍ'が生成される。
【０１８６】
（２）暗号通信システム１では、第１の変形ＮＴＲＵ暗号方式の秘密鍵の一部である多項式ｆとして、ｄｆ個の係数が１で、かつその他の係数は０である、（Ｎ−１）次以下の多項式を選んでいるが、ＮＴＲＵＥｎｃｒｙｐｔ方式と同様、ｄｆ個の係数が１で、かつその他の係数は０である、（Ｎ−１）次以下の多項式Ｆを用いて、ｆ＝１＋ｐ・Ｆにより多項式ｆを選んでもよい。
【０１８７】
これにより、ＮＴＲＵＥｎｃｒｙｐｔ方式と同様、ＮＴＲＵ暗号の復号化処理で行う、多項式Ｆｐとの多項式乗算が不要となる。また、この場合、秘密鍵の一部である多項式Ｆｐとの多項式乗算が不要であるため、秘密鍵は（ｆ，Ｆｐ）ではなく、多項式ｆとしてもよい。
【０１８８】
（実施の形態２）
本実施の形態２に係る暗号通信システム、暗号装置及び復号装置では、ＮＴＲＵＥｎｃｒｙｐｔ方式を改良して、復号エラーが原理的に発生しないＮＴＲＵ暗号方式を新たに構成し、この新たに構成したＮＴＲＵ暗号方式を用いて暗号化通信を行う（以降、この新たに構成した、復号エラーが原理的に発生しないＮＴＲＵ暗号方式を、「第２の変形ＮＴＲＵ暗号方式」と呼ぶ）。
【０１８９】
そのため、最初に、第２の変形ＮＴＲＵ暗号方式について説明を行う。
【０１９０】
以下、従来のＮＴＲＵＥｎｃｒｙｐｔ方式との差異点を中心に、第２の変形ＮＴＲＵ暗号方式について説明する。
【０１９１】
＜第２の変形ＮＴＲＵ暗号方式＞
変形ＮＴＲＵ暗号２は、従来のＮＴＲＵＥｎｃｒｙｐｔ方式を復号エラーが原理的に発生しないように改変したものである。
【０１９２】
変形ＮＴＲＵ暗号２は、後述する条件式ＥＦＣ１を満たすようにパラメータを生成する点が従来のＮＴＲＵＥｎｃｒｙｐｔと異なる。
【０１９３】
以下、この変形ＮＴＲＵ暗号２について説明を行う。
【０１９４】
（１）第２の変形ＮＴＲＵ暗号方式のパラメータ
変形ＮＴＲＵ暗号２は、非負整数のパラメータ、Ｎ、ｐ、ｑ、ｄｆ、ｄｇ、ｄを持つ。これらのパラメータの意味は、従来のＮＴＲＵＥｎｃｒｙｐｔ方式と同じであるが、以下の条件式ＥＦＣ１を満たすようにパラメータｐ、ｑ、ｄｆ、ｄｇ、ｄを選ぶ点が従来のＮＴＲＵＥｎｃｒｙｐｔ方式と異なる。
【０１９５】
ＥＦＣ１：ｐ・Ｍｉｎ（ｄｇ，ｄ）＋ｄｆ＜ｑ
【０１９６】
この条件式ＥＦＣ１を満たすパラメータを用いれば、後述する通り、復号エラーが原理的に発生しないようにすることができる。
【０１９７】
（２）第２の変形ＮＴＲＵ暗号方式の鍵生成
第２の変形ＮＴＲＵ暗号方式では、上述したように、パラメータｄｆ、ｄｇを用いてランダムに多項式ｆ、多項式ｇを生成する。そして非特許文献２に記載の通り、Ｆｑ×ｆ＝１（ｍｏｄ  ｑ）となる多項式Ｆｑを用いて、
ｈ＝Ｆｑ×ｇ（ｍｏｄ  ｑ）
により、多項式ｈを生成する。ここで、秘密鍵を（ｆ，Ｆｐ）、公開鍵をｈとする。
【０１９８】
（３）第２の変形ＮＴＲＵ暗号方式の暗号化
第２の変形ＮＴＲＵ暗号方式の暗号化では、平文である係数が０もしくは１の２値である多項式ｍを暗号化し、暗号文である多項式ｃを計算する。まず、上述したような多項式ｒをランダムに生成する。すなわち、乱数ｒは（Ｎ−１）次以下の多項式であり、第０次（定数項）から第（Ｎ−１）次までＮ個の係数があるが、このＮ個の係数のうち、ｄ個の係数が１であり、かつｄ個の係数が−１であり、かつ（Ｎ−２ｄ）個の係数は０となるように、ランダムに多項式ｒを選ぶ。
【０１９９】
そして、この乱数ｒと公開鍵ｈを用いて、係数が０、１もしくは−１である（Ｎ−１）次以下の平文ｍに対し、
ｃ＝ｐ・ｒ×ｈ＋ｍ（ｍｏｄ  ｑ）
により、暗号文ｃを生成する。
【０２００】
（４）第２の変形ＮＴＲＵ暗号方式の復号化
第２の変形ＮＴＲＵ暗号方式では、後述する通り、復号エラーが原理的に発生しないため、ＮＴＲＵＥｎｃｒｙｐｔと異なり、復号エラー発生確率を減少させる処理が不要である。
【０２０１】
そのため、以下のように復号化を行う。
【０２０２】
第２の変形ＮＴＲＵ暗号方式の復号化では、暗号文である多項式ｃを復号化し、復号文である多項式ｍ'を計算する。復号化時には、まず、暗号文ｃに対し、秘密鍵の一部である多項式ｆを用いて、
ａ＝ｆ×ｃ（ｍｏｄ  ｑ＊）
により多項式ａを計算する。
【０２０３】
次に、多項式ａに対し、パラメータｐを用いて、
ｂ＝ａ（ｍｏｄ  ｐ）
により、多項式ｂを生成する。
【０２０４】
そして、多項式ｂに対し、秘密鍵の一部である多項式Ｆｐを用いて、
ｍ'＝Ｆｐ×ｂ（ｍｏｄ  ｐ＊）
により、復号文ｍ'を計算する。
【０２０５】
以上のように、第２の変形ＮＴＲＵ暗号方式では、従来のＮＴＲＵＥｎｃｒｙｐｔ方式と異なり、非特許文献４に記載のｃｅｎｔｅｒ１もしくはｃｅｎｔｅｒ２と呼ばれるアルゴリズムのような復号エラー発生確率を減少させる処理は行わない。
【０２０６】
＜復号エラーが原理的に発生しない理由＞
以下、第２の変形ＮＴＲＵ暗号方式は復号エラーが原理的に発生しないことを説明する。
【０２０７】
まず、復号エラーが発生しないための条件について述べた後、上述した条件式ＥＦＣ１を満たすパラメータを用いる第２の変形ＮＴＲＵ暗号方式は、復号エラーが原理的に発生しないことを説明する。
【０２０８】
（復号エラーが発生しないための条件）
第２の変形ＮＴＲＵ暗号方式は、従来のＮＴＲＵＥｎｃｒｙｐｔ方式を復号エラーが原理的に発生しないように改変したものである。
【０２０９】
今、ＮＴＲＵＥｎｃｒｙｐｔにおいて復号エラーが発生しないための条件は開示されていない。しかしながら、多項式ｐ・ｒ×ｇ＋ｆ×ｍの全ての係数が０から（ｑ−１）の範囲に収まっていれば、正しく復号処理を行うことができ、復号エラーは発生しない。
【０２１０】
以下に、その理由を説明する。
【０２１１】
（ｉ）ＮＴＲＵ暗号方式の場合
ＮＴＲＵＥｎｃｒｙｐｔにおいて復号エラーが発生しないための条件を説明するため、まず非特許文献２に記載のＮＴＲＵ暗号において復号エラーが発生しないための条件について述べる。
【０２１２】
ＮＴＲＵ暗号に関しては、非特許文献２に、復号処理時において計算される多項式（ｐ・ｒ×ｇ＋ｆ×ｍ）の係数すべてが、−ｑ／２からｑ／２の範囲に収まっていれば、正しく復号処理を行うことができ、復号エラーが発生しないことが記載されている。これは以下の理由による。
【０２１３】
今、非特許文献２に記載のＮＴＲＵ暗号の復号処理では、まず暗号文ｃに対し、秘密鍵の一部である多項式ｆを用いて、
ａ＝ｃ×ｆ（ｍｏｄ  ｑ＊）
により多項式ａを演算する。ここで（ｍｏｄ  ｑ＊）は、多項式ｃ×ｆの第ｉ次の係数を、剰余が〈−ｑ／２〉＋１から〈ｑ／２〉の範囲に収まるように法ｑで割ったときの剰余を、多項式ａの第ｉ次の係数とする演算である。すなわち、多項式ｃと多項式ｆの乗算結果の多項式を求め、その各係数を、〈−ｑ／２〉＋１から〈ｑ／２〉の範囲に収まるようにｍｏｄ  ｑ演算を施した多項式を、多項式ａとする演算である。
【０２１４】
このとき、この多項式ａの値は、非特許文献２に記載の通り、平文ｍと暗号文ｃの関係式及び秘密鍵の一部である多項式ｆと公開鍵ｈの関係式から、
ａ＝ｃ×ｆ（ｍｏｄ  ｑ＊）
＝（ｐ・ｒ×ｈ＋ｍ）×ｆ（ｍｏｄ  ｑ＊）
＝ｐ・ｒ×ｇ＋ｆ×ｍ（ｍｏｄ  ｑ＊）
となる。すなわち、多項式ａは、多項式ｐ・ｒ×ｇ＋ｆ×ｍの各係数を−ｑ／２からｑ／２の範囲に収まるようにｍｏｄ  ｑ演算を施した多項式となっている。
【０２１５】
ここで、ＮＴＲＵ暗号では、乱数ｒ、多項式ｆ、ｇ及び平文ｍは、係数が０、１もしくは−１となる多項式である。そのため、ｐ・ｒ×ｇ＋ｆ×ｍは、その係数が負の値となる可能性がある多項式である。
【０２１６】
今、この負の係数値を取り得る多項式ｐ・ｒ×ｇ＋ｆ×ｍの全ての係数が−ｑ／２からｑ／２の範囲に収まっていれば、多項式ｐ・ｒ×ｇ＋ｆ×ｍ（ｍｏｄ  ｑ＊）の値は、多項式ｐ・ｒ×ｇ＋ｆ×ｍの値と等しくなるため、多項式ａの値は、
ａ＝ｐ・ｒ×ｇ＋ｆ×ｍ（ｍｏｄ  ｑ＊）
＝ｐ・ｒ×ｇ＋ｆ×ｍ
となる。すると、非特許文献２に記載の通り、その後の復号処理において正しく平文ｍを復元することができるので、復号エラーは発生しない。
【０２１７】
（ｉｉ）ＮＴＲＵＥｎｃｒｙｐｔ方式の場合
一方、ＮＴＲＵＥｎｃｒｙｐｔでは、復号エラーが発生しないための条件は開示されていないが、上述した通り、多項式ｐ・ｒ×ｇ＋ｆ×ｍの全ての係数が０から（ｑ−１）の範囲に収まっていれば、正しく復号処理を行うことができ、復号エラーは発生しない。これは、以下の理由による。
【０２１８】
今、復号アルゴリズムＤでは、非特許文献４に記載の通り、まず、暗号文ｃに対し、秘密鍵の一部である多項式ｆを用いて、
ａ＝ｃ×ｆ（ｍｏｄ  ｑ）
により多項式ａを演算する。この演算は、多項式ｃと多項式ｆの乗算結果の多項式を求め、その各係数を、０から（ｑ−１）の範囲に収まるようにｍｏｄ  ｑ演算を施した多項式を、多項式ａとする演算である。
【０２１９】
このとき、この多項式ａの値は、非特許文献４に記載の通り、平文ｍと暗号文ｃの関係式及び秘密鍵の一部である多項式ｆと公開鍵ｈの関係式から、
ａ＝ｃ×ｆ（ｍｏｄ  ｑ）
＝ｐ・ｒ×ｇ＋ｆ×ｍ（ｍｏｄ  ｑ）
となる。すなわち、多項式ａは、多項式ｐ・ｒ×ｇ＋ｆ×ｍの各係数を０から（ｑ−１）の範囲に収まるようにｍｏｄ  ｑ演算を施した多項式となっている。
【０２２０】
ここで、ＮＴＲＵＥｎｃｒｙｐｔでは、乱数である多項式ｒ、多項式ｆ、ｇ及び平文である多項式ｍは、係数が０もしくは１となる多項式である。そのため、ｐ・ｒ×ｇ＋ｆ×ｍは、その係数が０もしくは正の値となる多項式である。
【０２２１】
今、この多項式ｐ・ｒ×ｇ＋ｆ×ｍの全ての係数が０から（ｑ−１）の範囲に収まっていれば、多項式ｐ・ｒ×ｇ＋ｆ×ｍ（ｍｏｄ  ｑ）の値は、多項式ｐ・ｒ×ｇ＋ｆ×ｍの値と等しくなるため、多項式ａの値は、
ａ＝ｐ・ｒ×ｇ＋ｆ×ｍ（ｍｏｄ  ｑ）
＝ｐ・ｒ×ｇ＋ｆ×ｍ
となる。すると、非特許文献２に記載のＮＴＲＵ暗号と同様に、その後の復号処理において正しく平文ｍを復元することができるので、復号エラーは発生しない。
【０２２２】
（条件式ＥＦＣ１を満たすパラメータを用いれば復号エラーが発生しなくなる理由）
第２の変形ＮＴＲＵ暗号方式は、条件式ＥＦＣ１を満たすようにパラメータを設定するよう、従来のＮＴＲＵＥｎｃｒｙｐｔ方式を改変し、復号エラーが原理的に発生しないようにしたものである。
【０２２３】
以下、条件式ＥＦＣ１を満たすようにパラメータを設定すれば、多項式ｐ・ｒ×ｇ＋ｆ×ｍの全ての係数が、０から（ｑ−１）の範囲に収まり、復号エラーは発生しなくなることを説明する。
【０２２４】
まず、多項式ｐ・ｒ×ｇを考える。
【０２２５】
ここで、多項式ｒ×ｇのｋ次の係数は、多項式ａのｋ次の係数をａ（ｋ）で表すと、
（ｒ×ｇ）（ｋ）
＝ｒ（０）・ｇ（ｋ）＋ｒ（１）・ｇ（ｋ−１）＋．．．
＋ｒ（Ｎ−１）・ｇ（ｋ−（Ｎ−１）（ｍｏｄ  Ｎ））
である（多項式と多項式の乗算方法については、例えば、非特許文献２参照）。
【０２２６】
上述した通り、乱数ｒは、ｄ個の係数が１であり、かつ他の係数は０となる多項式であり、多項式ｇは、ｄｇ個の係数が１であり、かつ他の係数は０となる多項式である。
【０２２７】
すると、多項式ｒ×ｇの係数（ｒ×ｇ）（ｋ）の値は、
ｒ×ｇ（ｋ）
＝ｒ（０）・ｇ（ｋ）＋ｒ（１）・ｇ（ｋ−１）＋．．．
＋ｒ（Ｎ−１）・ｇ（ｋ−（Ｎ−１）（ｍｏｄ  Ｎ））
＝１・ｇ（ｉ１）＋１・ｇ（ｉ２）＋．．．＋１・ｇ（ｉｄ）
＋０・ｇ（ｊ１）＋０・ｇ（ｊ２）＋．．．＋０・ｇ（ｊ（Ｎ−ｄ））
＝１・ｇ（ｉ１）＋１・ｇ（ｉ２）＋．．．＋１・ｇ（ｉｄ）
というように、ｄ個の１・ｇ（ｉｎ）という項（１≦ｎ≦ｄ）で表される。
【０２２８】
今、ｄ≦ｄｇの場合、ｇ（ｉｎ）が全て１である場合が考えられ（１≦ｎ≦ｄ≦ｄｇ）、このとき（ｒ×ｇ）（ｋ）は最大値を取り、その値は高々ｄである。
【０２２９】
なお、ｄ＞ｄｇの場合、ｇ（ｉｎ）が全て１である場合はあり得ないため、ｇ（ｉｎ）のうちｄｇ個が１であり、（ｄ−ｄｇ）個が０である場合に（ｒ×ｇ）（ｋ）は最大値を取り、その値は高々ｄｇである。
【０２３０】
以上により、多項式ｒ×ｇの係数の最大値はＭｉｎ（ｄｇ，ｄ）である。
【０２３１】
従って、多項式ｐ・ｒ×ｇの係数の最大値は、多項式ｒ×ｇの係数の最大値にｐを乗じたものとなるので、ｐ・Ｍｉｎ（ｄｇ，ｄ）となる。
【０２３２】
次に、多項式ｆ×ｍを考える。
【０２３３】
ここで、多項式ｆ×ｍの第ｋ次の係数を考えると、多項式ｆはｄｆ個の係数が１であり、かつ他の係数は０となる多項式であるので、上述の議論と同様に、
ｆ×ｍ（ｋ）
＝ｆ（０）・ｍ（ｋ）＋ｆ（１）・ｍ（ｋ−１）＋．．．
＋ｆ（Ｎ−１）・ｍ（ｋ−（Ｎ−１）（ｍｏｄ  Ｎ））
＝１・ｍ（ｉ１）＋１・ｍ（ｉ２）＋．．．＋１・ｍ（ｉｄｆ）
というように、ｄｆ個の１・ｍ（ｉｎ）という項（１≦ｎ≦ｄｆ）で表される。
【０２３４】
今、平文である多項式ｍは係数が０もしくは１であるので、ｍ（ｉｎ）が全て１である場合が考えられ（１≦ｎ≦ｄｆ）、このとき（ｆ×ｍ）（ｋ）は最大値を取り、その値は高々ｄｆである。
【０２３５】
以上により、多項式ｆ×ｍの係数の最大値はｄｆである。
【０２３６】
以上をまとめると、多項式ｐ・ｒ×ｇ＋ｆ×ｍの係数の最大値は高々、
ｐ・Ｍｉｎ（ｄｇ，ｄ）＋ｄｆ
である。
【０２３７】
そして、係数の最大値がｑ−１以下であれば、多項式ｐ・ｒ×ｇ＋ｆ×ｍの全ての係数が０から（ｑ−１）の範囲に収まっていることになるので、復号エラーは発生しない。
【０２３８】
すなわち、復号エラーが原理的に発生しないためには、
ｐ・Ｍｉｎ（ｄｇ，ｄ）＋ｄｆ＜ｑ
となるようにすればよく、下記条件式ＥＦＣ１が導かれる。
【０２３９】
ＥＦＣ１：ｐ・Ｍｉｎ（ｄｇ，ｄ）＋ｄｆ＜ｑ
【０２４０】
＜第２の変形ＮＴＲＵ暗号方式のパラメータ生成方法＞
ここでは、上述した第２の変形ＮＴＲＵ暗号方式のパラメータの生成方法の一例を挙げる。
【０２４１】
上述した通り、第２の変形ＮＴＲＵ暗号方式のパラメータは、上述した条件式ＥＦＣ１を満たすパラメータを生成すればよい。
【０２４２】
そのため、ここでは、まずｐ＝２とし、ｐと互いに素となるよう、ｑ＝２３９とする。
【０２４３】
そして、ｄｆ＝ｄｇ＝ｄとして、上述した条件式ＥＦＣ１を満たすように、ｄｆ、ｄｇ、ｄの値を生成する。そして、上述した総当り攻撃およびＬＬＬ攻撃に対する安全性が規定の値以上となるように、Ｎの値を生成する。
【０２４４】
なお、これはパラメータの生成方法の一例であり、条件式ＥＦＣ１を満たすようにパラメータを生成すれば、他の生成方法でもよい。
【０２４５】
以降では、この生成方法により生成された、（Ｎ，ｐ，ｑ，ｄｆ，ｄｇ，ｄ）＝（２５１，２，２３９，６３，６３，６３）というパラメータを用いた場合の説明を行う。
【０２４６】
以上、第２の変形ＮＴＲＵ暗号方式について説明を行ったが、以降、本実施の形態に係る暗号通信システム、暗号装置及び復号装置について説明を行う。
【０２４７】
＜暗号通信システム１ｂの概要＞
図７は、本発明の実施の形態２における暗号通信システム１ｂの全体構成を示す図である。最初に、同図を用いて暗号通信システム１ｂの概要を説明する。
【０２４８】
この暗号通信システム１ｂは、平文ｍの暗号化通信を行うシステムであり、暗号装置１０ｂと、復号装置２０ｂとから構成されており、暗号装置１０ｂと復号装置２０ｂとは通信路３０を介して相互に接続されている。
【０２４９】
そして、この暗号通信システム１ｂは、暗号装置１０ｂと復号装置２０ｂとの間で、第２の変形ＮＴＲＵ暗号方式のパラメータとして、（Ｎ，ｐ，ｑ，ｄｆ，ｄｇ，ｄ）＝（２５１，２，２３９，６３，６３，６３）を共有している。
【０２５０】
この暗号通信システム１ｂにおいて、暗号装置１０ｂは、外部から入力された平文ｍを、上述した、第２の変形ＮＴＲＵ暗号方式を用いて暗号化して暗号文ｃを生成し、通信路３０を介して復号装置２０ｂに送信する。
【０２５１】
そして、復号装置２０ｂは、通信路３０を介して暗号装置１０ｂから受信した暗号文ｃを復号して復号文ｍ'を生成して出力する。
【０２５２】
以上が、暗号通信システム１ｂの概要であるが、以下、暗号通信システム１との差異点を中心に、その構成及び動作について説明する。
【０２５３】
＜暗号通信システム１ｂの構成＞
暗号通信システム１ｂは、図７に示すように、暗号装置１０ｂと、復号装置２０ｂとから構成され、暗号装置１０ｂと復号装置２０ｂとは通信路３０を介して相互に接続されている。
【０２５４】
以下、これらの構成要素について暗号通信システム１との差異点を中心に説明する。
【０２５５】
＜暗号装置１０ｂの構成＞
暗号装置１０ｂは、図８に示すように、パラメータ記憶部１１ｂと、公開鍵記憶部１２と、暗号化部１３ｂとから構成される。
【０２５６】
以下、これらの構成要素について、暗号装置１０との差異点を中心に説明する。
【０２５７】
（１）パラメータ記憶部１１ｂ
パラメータ記憶部１１ｂは、例えばＲＡＭやＥＥＰＲＯＭのようなメモリで構成されており、後述する暗号化部１３ｂからアクセス可能なものである。
【０２５８】
パラメータ記憶部１１ｂは、上述した条件式ＥＦＣ１を満たすようなパラメータを予め記憶している。ここでは、上述の通り、パラメータ（Ｎ，ｐ，ｑ，ｄｆ，ｄｇ，ｄ）＝（２５１，２，２３９，６３，６３，６３）を予め記憶しているものとする。
【０２５９】
（２）暗号化部１３ｂ
暗号化部１３ｂは、例えばマイクロコンピュータによって構成されており、パラメータ記憶部１１ｂ及び公開鍵記憶部１２にアクセス可能である。
【０２６０】
暗号化部１３ｂは、第１の変形ＮＴＲＵ暗号方式の暗号化処理を行う代わりに、第２の変形ＮＴＲＵ暗号方式の暗号化処理を行い、暗号文ｃを生成する点が、暗号化部１３と異なる。
【０２６１】
＜復号装置２０ｂの構成＞
復号装置２０ｂは、図９に示すように、パラメータ記憶部２１ｂと、鍵生成部２２ｂと、秘密鍵記憶部２３と、復号化部２４ｂとから構成される。
【０２６２】
以下、これらの構成要素について、復号装置２０との差異点を中心に説明する。
【０２６３】
（１）パラメータ記憶部２１ｂ
パラメータ記憶部２１ｂは、例えばＲＡＭやＥＥＰＲＯＭのようなメモリで構成されており、後述する鍵生成部２２ｂ及び復号化部２４ｂからアクセス可能なものである。
【０２６４】
パラメータ記憶部２１ｂは、暗号装置１０ｂのパラメータ記憶部１１ｂと同一のパラメータ（Ｎ，ｐ，ｑ，ｄｆ，ｄｇ，ｄ）を予め記憶している。ここでは、上述の通り、パラメータ（Ｎ，ｐ，ｑ，ｄｆ，ｄｇ，ｄ）＝（２５１，２，２３９，６３，６３，６３）を予め記憶しているものとする。
【０２６５】
（２）鍵生成部２２ｂ
鍵生成部２２ｂは、例えばマイクロコンピュータによって構成されており、エラーフリーＮＴＲＵ暗号の秘密鍵ｆ及び公開鍵ｈを生成する。
【０２６６】
鍵生成部２２ｂは、第１の変形ＮＴＲＵ暗号方式の鍵生成処理を行う代わりに、第２の変形ＮＴＲＵ暗号方式の鍵生成処理を行う点が、鍵生成部２２と異なる。
【０２６７】
（３）復号化部２４ｂ
復号化部２４ｂは、例えばマイクロコンピュータによって構成されており、パラメータ記憶部２１ｂ及び秘密鍵記憶部２３にアクセス可能である。
【０２６８】
復号化部２４ｂは、第１の変形ＮＴＲＵ暗号方式の復号化処理を行う代わりに、第２の変形ＮＴＲＵ暗号方式の復号化処理を行い、復号文ｍ'を生成する点が、復号化部２４と異なる。
【０２６９】
＜暗号通信システム１ｂの動作＞
以上、暗号通信システム１ｂの構成について説明したが、ここでは、暗号通信システム１ｂの全体の動作について、図１０に示すフローチャートを用いて説明する。
【０２７０】
最初に、パラメータ記憶部１１ｂ及びパラメータ記憶部２１ｂは、条件式ＥＦＣ１を満たすパラメータを予め記憶している（ステップＳ２６１）。
【０２７１】
次に、鍵生成部２２ｂは、パラメータ記憶部２１ｂからパラメータＮ、パラメータｑ、パラメータｄｆ、パラメータｄｇを読み取り、パラメータＮ、パラメータｄｆを用いて、ｄｆ個の係数が１であり、かつその他の係数が０となるように、（Ｎ−１）次以下の多項式で表される多項式ｆを選ぶ（ステップＳ２６２）。
【０２７２】
次に、鍵生成部２２ｂは、パラメータＮ、パラメータｄｇを用いて、ｄｇ個の係数が１であり、かつその他の係数は０となるように、（Ｎ−１）次以下の多項式で表される多項式ｇを選ぶ（ステップＳ２６３）。
【０２７３】
次に、鍵生成部２２ｂは、上述した第２の変形ＮＴＲＵ暗号方式の鍵生成処理を行い、多項式Ｆｐ及びｈを生成する（ステップＳ２６４）。
【０２７４】
次に、鍵生成部２２ｂは、多項式ｈを公開鍵として公開し、暗号装置１０ｂが取得できるようにし、多項式ｆとＦｐの対（ｆ，Ｆｐ）を秘密鍵として秘密鍵記憶部２３に記憶する（ステップＳ２６５）。
【０２７５】
次に、公開鍵記憶部１２は、通信路３０を介して復号装置２０ｂの公開鍵ｈを取得して記憶する（ステップＳ２６６）。
【０２７６】
次に、暗号化部１３ｂは、外部から係数が０もしくは１である平文ｍが入力されると、パラメータ記憶部１１ｂからパラメータＮ、パラメータｑ、パラメータｄを読み取り、公開鍵記憶部１２から、公開鍵ｈを読み取る（ステップＳ２６７）。
【０２７７】
次に、暗号化部１３ｂは、パラメータＮ、パラメータｄを用いて、ｄ個の係数が１であり、かつ他の係数が０となるように、（Ｎ−１）次以下の多項式ｒをランダムに選ぶ（ステップＳ２６８）。
【０２７８】
次に、暗号化部１３ｂは、平文ｍに対し、乱数ｒ、公開鍵ｈ、パラメータＮ、パラメータｑを用いて、第２の変形ＮＴＲＵ暗号方式の暗号化処理を行い、暗号文ｃを生成する（ステップＳ２６９）。
【０２７９】
次に、暗号化部１３ｂは、生成した暗号文ｃを通信路３０を介して復号装置２０ｂへ送信する（ステップＳ２７０）。
【０２８０】
次に、復号化部２４ｂは、通信路３０を介して暗号装置１０ｂから暗号文ｃを受信すると、パラメータ記憶部２１ｂから、パラメータＮ、パラメータｐ、パラメータｑを読み取り、秘密鍵記憶部２３から、秘密鍵（ｆ，Ｆｐ）を読み取る（ステップＳ２７１）。
【０２８１】
次に、復号化部２４ｂは、暗号文ｃに対し、秘密鍵である多項式ｆ及びＦｐ、パラメータＮ、パラメータｐ、パラメータｑを用いて、第２の変形ＮＴＲＵ暗号方式の復号化処理を行い、復号文ｍ'を生成する（ステップＳ２７２）。
【０２８２】
次に、復号化部２４ｂは、生成した復号文ｍ'を外部へ出力して処理を終了する（ステップＳ２７３）。
【０２８３】
＜暗号通信システム１ｂの動作検証＞
まず、暗号装置１０ｂ及び復号装置２０ｂは、ステップＳ２６１において、条件式ＥＦＣ１を満たすようなパラメータを記憶している。
【０２８４】
そして、復号装置２０ｂが、予め、このパラメータを用いて、ステップＳ２６２及びステップＳ２６３において、係数が０もしくは１の２値である、多項式ｆ及びｇを生成し、ステップＳ２６４において、これらの多項式を基に公開鍵である多項式ｈを生成している。
【０２８５】
そして、暗号装置１０ｂでは、ステップＳ２６７にて、係数が０もしくは１の２値である多項式ｒを生成し、ステップＳ２６８にて、条件式ＥＦＣ１を満たすようなパラメータと公開鍵ｈと乱数ｒを用いて、係数が０もしくは１の２値の多項式である平文ｍを暗号化して暗号文ｃを生成している。
【０２８６】
そして、復号装置２０ｂでは、ステップＳ２７１において、秘密鍵である多項式ｆ及びＦｐと記憶している条件式ＥＦＣ１を満たすようなパラメータを用いて、復号文ｍ'を生成している。
【０２８７】
かかる構成によれば、条件式ＥＦＣ１を満たすパラメータを、暗号装置１０ｂと復号装置２０ｂとの間で共有し、このパラメータを用いて暗号化通信を行っているため、上述の条件式ＥＦＣ１の説明で述べた通り、復号エラーは原理的に起こらず、復号文ｍ'は必ず平文ｍと同一となる。
【０２８８】
これにより、復号エラーが原理的に発生しない第２の変形ＮＴＲＵ暗号方式を構成することができ、また、第２の変形ＮＴＲＵ暗号方式を暗号通信システムに適用し、暗号装置が送信したデータ内容が、常に復号装置で正しく得られるような暗号通信システムを提供することができる。
【０２８９】
＜変形例＞
なお、上記に説明した実施の形態は、本発明の実施の形態の一例であり、本発明はこの実施の形態に何ら限定されるものではなく、その主旨を逸脱しない範囲において種々なる態様で実施し得るものである。以下のような場合も本発明に含まれる。
【０２９０】
（１）暗号通信システム１ｂでは、第２の変形ＮＴＲＵ暗号方式のパラメータとしてｐ＝２となるパラメータを用いているが、条件式ＥＦＣ１を満たせば他のパラメータでもよく、たとえば、ｐ＝３となるパラメータを用いてもよい。また、上述の実施の形態では、条件式ＥＦＣ１を満たすパラメータとしてパラメータ（Ｎ，ｐ，ｑ，ｄｆ，ｄｇ，ｄ）＝（２５１，２，２３９，６３，６３，６３）を用いて説明を行なったが、ＮＴＲＵＥｎｃｒｙｐｔ方式で採用されているパラメータ（Ｎ，ｐ，ｑ，ｄｆ，ｄｇ，ｄ）＝（２５１，２，２３９，７２，７２，７２）であっても、条件式ＥＦＣ１を満たすため、このパラメータを用いてもよい。
【０２９１】
（２）暗号通信システム１ｂでは、第２の変形ＮＴＲＵ暗号方式の秘密鍵の一部である多項式ｆとして、ｄｆ個の係数が１で、かつその他の係数は０である、（Ｎ−１）次以下の多項式を選んでいるが、ＮＴＲＵＥｎｃｒｙｐｔ方式と同様、ｄｆ個の係数が１で、かつその他の係数は０である、（Ｎ−１）次元以下の多項式Ｆを用いて、ｆ＝１＋ｐ・Ｆにより秘密鍵ｆを選び、後述する条件式ＥＦＣ２を満たすようなパラメータを生成するようにしてもよい。この場合は、秘密鍵を（ｆ，Ｆｐ）ではなく、多項式ｆとしてもよい。
【０２９２】
これにより、ＮＴＲＵＥｎｃｒｙｐｔ方式と同様、ＮＴＲＵ暗号の復号化処理で行う、多項式Ｆｐとの多項式乗算が不要となる。なお、後述する通り条件式ＥＦＣ２を満たすようなパラメータが生成されるので、復号エラーが原理的に発生せず、実施の形態２と同様に、暗号装置が送信したデータ内容が、常に復号装置で正しく得られるような暗号通信システムを実現することができる。
【０２９３】
（実施の形態３）
本実施の形態３に係る暗号通信システム、暗号装置及び復号装置では、ＮＴＲＵＥｎｃｒｙｐｔ方式を改良して、復号エラーが原理的に発生せず、かつ高速処理可能なＮＴＲＵ暗号方式を新たに構成し、この新たに構成したＮＴＲＵ暗号方式を用いて暗号化通信を行う（以降、この新たに構成した、復号エラーが原理的に発生しないＮＴＲＵ暗号方式を、「第３の変形ＮＴＲＵ暗号方式」と呼ぶ）。
【０２９４】
そのため、最初に、第３の変形ＮＴＲＵ暗号方式について説明を行う。
【０２９５】
以下、従来のＮＴＲＵＥｎｃｒｙｐｔ方式との差異点を中心に、第３の変形ＮＴＲＵ暗号方式について説明する。
【０２９６】
＜第３の変形ＮＴＲＵ暗号方式＞
第３の変形ＮＴＲＵ暗号方式は、従来のＮＴＲＵＥｎｃｒｙｐｔ方式を復号エラーが原理的に発生せず、かつ高速処理可能なように改変したものである。
【０２９７】
第３の変形ＮＴＲＵ暗号方式は、パラメータとしてｐ＝３、ｑ＝２＾ｋ（ｋ：２以上の整数）となるパラメータを用いつつ、多項式ｆ、ｇ、乱数である多項式ｒ及び平文である多項式ｍとして、係数が０もしくは１の２値である多項式を選ぶ点、及び後述する条件式ＥＦＣ２を満たすようにパラメータを生成する点が従来のＮＴＲＵＥｎｃｒｙｐｔと異なる。
【０２９８】
以下、この第３の変形ＮＴＲＵ暗号方式について説明を行う。
【０２９９】
（１）第３の変形ＮＴＲＵ暗号方式のパラメータ
第３の変形ＮＴＲＵ暗号方式は、非負整数のパラメータ、Ｎ、ｐ、ｑ、ｄｆ、ｄｇ、ｄを持つ。これらのパラメータの意味は、従来のＮＴＲＵＥｎｃｒｙｐｔ方式と同じであるが、ｐ＝３かつｑ＝２＾ｋ（ｋ：２以上の整数）となるパラメータを生成し、ｐ＝３としているにも拘わらず、多項式ｆ、ｇ、乱数である多項式ｒとして係数が０もしくは１の２値である多項式を用いる点、及び以下の条件式ＥＦＣ２を満たすようにパラメータｐ、ｑ、ｄｆ、ｄｇ、ｄを選ぶ点が従来のＮＴＲＵＥｎｃｒｙｐｔ方式と異なる。
【０３００】
ＥＦＣ２：Ｍｉｎ（ｄｇ，ｄ）＋ｄｆ＜（ｑ−１）／ｐ
【０３０１】
このように、ｐ＝３というパラメータを用いるにも拘わらず、多項式ｆ、ｇ、乱数である多項式ｒとして係数が０もしくは１の２値である多項式を用いることで、従来のＮＴＲＵＥｎｃｒｙｐｔよりも高速処理可能となるようにできる。
【０３０２】
また、この条件式ＥＦＣ２を満たすパラメータを用いれば、後述する通り、復号エラーが原理的に発生しないようにすることができる。
【０３０３】
（２）第３の変形ＮＴＲＵ暗号方式の鍵生成
第３の変形ＮＴＲＵ暗号方式では、上述したように、パラメータｄｆ、ｄｇを用いてランダムに多項式ｆ、多項式ｇを生成する。ここで、多項式ｆは、ｄｆ個の係数が１で、かつその他の係数は０である、（Ｎ−１）次以下の多項式Ｆを用いて、ｆ＝１＋ｐ・Ｆにより多項式ｆを選ぶ。
【０３０４】
そして非特許文献２に記載の通り、Ｆｑ×ｆ＝１（ｍｏｄ  ｑ）となる多項式Ｆｑを用いて、
ｈ＝Ｆｑ×ｇ（ｍｏｄ  ｑ）
により、多項式ｈを生成する。ここで、秘密鍵を多項式ｆ、公開鍵をｈとする。
【０３０５】
（３）第３の変形ＮＴＲＵ暗号方式の暗号化
第３の変形ＮＴＲＵ暗号方式の暗号化では、平文である係数が０もしくは１の２値である多項式ｍを暗号化し、暗号文である多項式ｃを計算する。まず、上述したような多項式ｒをランダムに生成する。すなわち、乱数ｒは（Ｎ−１）次以下の多項式であり、第０次（定数項）から第（Ｎ−１）次までＮ個の係数があるが、このＮ個の係数のうち、ｄ個の係数が１であり、かつｄ個の係数が−１であり、かつ（Ｎ−２ｄ）個の係数は０となるように、ランダムに多項式ｒを選ぶ。
【０３０６】
そして、この乱数ｒと公開鍵ｈを用いて、係数が０、１もしくは−１である（Ｎ−１）次以下の平文ｍに対し、
ｃ＝ｐ・ｒ×ｈ＋ｍ（ｍｏｄ  ｑ）
により、暗号文ｃを生成する。
【０３０７】
（４）第３の変形ＮＴＲＵ暗号方式の復号化
第３の変形ＮＴＲＵ暗号方式では、後述する通り、復号エラーが原理的に発生しないため、ＮＴＲＵＥｎｃｒｙｐｔと異なり、復号エラー発生確率を減少させる処理が不要である。
【０３０８】
そのため、以下のように復号化を行う。
【０３０９】
第３の変形ＮＴＲＵ暗号方式の復号化では、暗号文である多項式ｃを復号化し、復号文である多項式ｍ'を計算する。復号化時には、まず、暗号文ｃに対し、秘密鍵の一部である多項式ｆを用いて、
ａ＝ｆ×ｃ（ｍｏｄ  ｑ＊）
により多項式ａを計算する。
【０３１０】
次に、多項式ａに対し、パラメータｐを用いて、
ｂ＝ａ（ｍｏｄ  ｐ）
により、多項式ｂを生成する。
【０３１１】
そして、非特許文献４に記載の通り、秘密鍵である多項式ｆがｆ＝１＋ｐ・Ｆという形であるために、Ｆｐ×ｆ＝１（ｍｏｄ  ｐ）となる多項式ＦｐはＦｐ＝１（ｍｏｄ  ｐ）となるので、復号化処理で行う、多項式Ｆｐとの多項式乗算が不要となるので、
ｍ'＝ａ（ｍｏｄ  ｐ＊）
により、復号文ｍ'を生成する。
【０３１２】
以上のように、第３の変形ＮＴＲＵ暗号方式では、従来のＮＴＲＵＥｎｃｒｙｐｔ方式と異なり、非特許文献４に記載のｃｅｎｔｅｒ１もしくはｃｅｎｔｅｒ２と呼ばれるアルゴリズムのような復号エラー発生確率を減少させる処理は行わない。
【０３１３】
＜復号エラーが原理的に発生しない理由＞
以下、上述した条件式ＥＦＣ２を満たすパラメータを用いる第３の変形ＮＴＲＵ暗号方式は、復号エラーが原理的に発生しないことを説明する。
【０３１４】
（条件式ＥＦＣ２を満たすパラメータを用いれば復号エラーが発生しなくなる理由）
第３の変形ＮＴＲＵ暗号方式は、条件式ＥＦＣ２を満たすようにパラメータを設定するよう、従来のＮＴＲＵＥｎｃｒｙｐｔ方式を改変し、復号エラーが原理的に発生しないようにしたものである。
【０３１５】
以下、条件式ＥＦＣ２を満たすようにパラメータを設定すれば、多項式ｐ・ｒ×ｇ＋ｆ×ｍの全ての係数が、０から（ｑ−１）の範囲に収まり、復号エラーは発生しなくなることを説明する。
【０３１６】
まず、多項式ｐ・ｒ×ｇを考えると、上述した通り、多項式ｐ・ｒ×ｇの係数の最大値は、ｐ・Ｍｉｎ（ｄｇ，ｄ）となる。
【０３１７】
次に、多項式ｆ×ｍを考える。
【０３１８】
今、秘密鍵である多項式ｆはｆ＝１＋ｐ・Ｆなので、
ｆ×ｍ
＝（１＋ｐ・Ｆ）×ｍ
＝ｍ＋ｐ・Ｆ×ｍ
である。
【０３１９】
ここで、多項式Ｆ×ｍの第ｋ次の係数を考えると、多項式Ｆはｄｆ個の係数が１であり、かつ他の係数は０となる多項式であるので、上述の議論と同様に、
Ｆ×ｍ（ｋ）
＝Ｆ（０）・ｍ（ｋ）＋Ｆ（１）・ｍ（ｋ−１）＋．．．
＋Ｆ（Ｎ−１）・ｍ（ｋ−（Ｎ−１）（ｍｏｄ  Ｎ））
＝１・ｍ（ｉ１）＋１・ｍ（ｉ２）＋．．．＋１・ｍ（ｉｄｆ）
というように、ｄｆ個の１・ｍ（ｉｎ）という項（１≦ｎ≦ｄｆ）で表される。
【０３２０】
今、平文である多項式ｍは係数が０もしくは１であるので、ｍ（ｉｎ）が全て１である場合が考えられ（１≦ｎ≦ｄｆ）、このとき（Ｆ×ｍ）（ｋ）は最大値を取り、その値は高々ｄｆである。
【０３２１】
以上により、多項式Ｆ×ｍの係数の最大値はｄｆである。
【０３２２】
従って、平文である多項式ｍの係数の最大値は１であり、ｐ・Ｆ×ｍの係数の最大値は、ｐ・ｄｆとなるので、多項式ｆ×ｍ（＝ｍ＋ｐ・Ｆ×ｍ）の係数の最大値は、１＋ｐ・ｄｆとなる。
【０３２３】
以上をまとめると、多項式ｐ・ｒ×ｇ＋ｆ×ｍの係数の最大値は高々、
ｐ・Ｍｉｎ（ｄｇ，ｄ）＋１＋ｐ・ｄｆ
である。
【０３２４】
そして、係数の最大値がｑ−１以下であれば、多項式ｐ・ｒ×ｇ＋ｆ×ｍの全ての係数が０から（ｑ−１）の範囲に収まっていることになるので、復号エラーは発生しない。
【０３２５】
すなわち、復号エラーが原理的に発生しないためには、
ｐ・Ｍｉｎ（ｄｇ，ｄ）＋１＋ｐ・ｄｆ＜ｑ
となるようにすればよく、この式を変形すると、下記条件式ＥＦＣ２が導かれる。
【０３２６】
ＥＦＣ２：Ｍｉｎ（ｄｇ，ｄ）＋ｄｆ＜（ｑ−１）／ｐ
＜第３の変形ＮＴＲＵ暗号方式のパラメータ生成方法＞
ここでは、上述した第３の変形ＮＴＲＵ暗号方式のパラメータの生成方法の一例を挙げる。
【０３２７】
上述した通り、第３の変形ＮＴＲＵ暗号方式のパラメータは、ｐ＝３かつｑ＝２＾ｋ（ｋ：２以上の整数）とし、上述した条件式ＥＦＣ２を満たすパラメータを生成すればよい。
【０３２８】
そのため、ここでは、まずｐ＝３とし、ｐと互いに素となりかつ係数のｍｏｄ  ｑ演算が、ビットマスク演算にて下位８ビットのみをとる演算で実現可能となるよう、ｑ＝２５６とする。
【０３２９】
そして、ｄｆ＝ｄｇ＝ｄとして、上述した条件式ＥＦＣ２を満たすように、ｄｆ、ｄｇ、ｄの値を生成する。そして、上述した総当り攻撃およびＬＬＬ攻撃に対する安全性が規定の値以上となるように、Ｎの値を生成する。
【０３３０】
なお、これはパラメータの生成方法の一例であり、条件式ＥＦＣ２を満たすようにパラメータを生成すれば、他の生成方法でもよい。
【０３３１】
以降では、この生成方法により生成された、（Ｎ，ｐ，ｑ，ｄｆ，ｄｇ，ｄ）＝（２５１，３，２５６，４２，４２，４２）というパラメータを用いた場合の説明を行う。
【０３３２】
以上、第３の変形ＮＴＲＵ暗号方式について説明を行ったが、以降、本実施の形態に係る暗号通信システム、暗号装置及び復号装置について説明を行う。
【０３３３】
＜暗号通信システム１ｃの概要＞
図１１は、本発明の実施の形態３における暗号通信システム１ｃの全体構成を示す図である。最初に、同図を用いて暗号通信システム１ｃの概要を説明する。
【０３３４】
この暗号通信システム１ｃは、平文ｍの暗号化通信を行うシステムであり、暗号装置１０ｃと、復号装置２０ｃとから構成されており、暗号装置１０ｃと復号装置２０ｃとは通信路３０を介して相互に接続されている。
【０３３５】
そして、この暗号通信システム１ｃは、暗号装置１０ｃと復号装置２０ｃとの間で、第３の変形ＮＴＲＵ暗号方式のパラメータとして、（Ｎ，ｐ，ｑ，ｄｆ，ｄｇ，ｄ）＝（２５１，３，２５６，４２，４２，４２）を共有している。
【０３３６】
この暗号通信システム１ｃにおいて、暗号装置１０ｃは、外部から入力された平文ｍを、上述した、第３の変形ＮＴＲＵ暗号方式を用いて暗号化して暗号文ｃを生成し、通信路３０を介して復号装置２０ｃに送信する。
【０３３７】
そして、復号装置２０ｃは、通信路３０を介して暗号装置１０ｃから受信した暗号文ｃを復号して復号文ｍ'を生成して出力する。
【０３３８】
以上が、暗号通信システム１ｃの概要であるが、以下、暗号通信システム１との差異点を中心に、その構成及び動作について説明する。
【０３３９】
＜暗号通信システム１ｃの構成＞
暗号通信システム１ｃは、図１１に示すように、暗号装置１０ｃと、復号装置２０ｃとから構成され、暗号装置１０ｃと復号装置２０ｃとは通信路３０を介して相互に接続されている。
【０３４０】
以下、これらの構成要素について暗号通信システム１との差異点を中心に説明する。
【０３４１】
＜暗号装置１０ｃの構成＞
暗号装置１０ｃは、図１２に示すように、パラメータ記憶部１１ｃと、公開鍵記憶部１２と、暗号化部１３ｃとから構成される。
【０３４２】
以下、これらの構成要素について、暗号装置１０との差異点を中心に説明する。
【０３４３】
（１）パラメータ記憶部１１ｃ
パラメータ記憶部１１ｃは、例えばＲＡＭやＥＥＰＲＯＭのようなメモリで構成されており、後述する暗号化部１３ｃからアクセス可能なものである。
【０３４４】
パラメータ記憶部１１ｃは、上述したように、ｐ＝３かつｑ＝２＾ｋ（ｋ：２以上の整数）とし、条件式ＥＦＣ２を満たすようなパラメータを予め記憶している。ここでは、上述の通り、パラメータ（Ｎ，ｐ，ｑ，ｄｆ，ｄｇ，ｄ）＝（２５１，３，２５６，４２，４２，４２）を予め記憶しているものとする。
【０３４５】
（２）暗号化部１３ｃ
暗号化部１３ｃは、例えばマイクロコンピュータによって構成されており、パラメータ記憶部１１ｃ及び公開鍵記憶部１２にアクセス可能である。
【０３４６】
暗号化部１３ｃは、第１の変形ＮＴＲＵ暗号方式の暗号化処理を行う代わりに、第３の変形ＮＴＲＵ暗号方式の暗号化処理を行い、暗号文ｃを生成する点が、暗号化部１３と異なる。
【０３４７】
＜復号装置２０ｃの構成＞
復号装置２０ｃは、図１３に示すように、パラメータ記憶部２１ｃと、鍵生成部２２ｃと、秘密鍵記憶部２３と、復号化部２４ｃとから構成される。
【０３４８】
以下、これらの構成要素について、復号装置２０との差異点を中心に説明する。
【０３４９】
（１）パラメータ記憶部２１ｃ
パラメータ記憶部２１ｃは、例えばＲＡＭやＥＥＰＲＯＭのようなメモリで構成されており、後述する鍵生成部２２ｃ及び復号化部２４ｃからアクセス可能なものである。
【０３５０】
パラメータ記憶部２１ｃは、暗号化部１０ｃのパラメータ記憶部１１ｃと同一のパラメータ（Ｎ，ｐ，ｑ，ｄｆ，ｄｇ，ｄ）を予め記憶している。ここでは、上述の通り、パラメータ（Ｎ，ｐ，ｑ，ｄｆ，ｄｇ，ｄ）＝（２５１，３，２５６，４２，４２，４２）を予め記憶しているものとする。
【０３５１】
（２）鍵生成部２２ｃ
鍵生成部２２ｃは、例えばマイクロコンピュータによって構成されており、第３の変形ＮＴＲＵ暗号方式の秘密鍵である多項式ｆ及び公開鍵である多項式ｈを生成する。
【０３５２】
鍵生成部２２ｃは、第１の変形ＮＴＲＵ暗号方式の鍵生成処理を行う代わりに、第３の変形ＮＴＲＵ暗号方式の鍵生成処理を行う点が、鍵生成部２２と異なる。
【０３５３】
（３）復号化部２４ｃ
復号化部２４ｃは、例えばマイクロコンピュータによって構成されており、パラメータ記憶部２１ｃ及び秘密鍵記憶部２３にアクセス可能である。
【０３５４】
復号化部２４ｃは、第１の変形ＮＴＲＵ暗号方式の復号化処理を行う代わりに、第３の変形ＮＴＲＵ暗号方式の復号化処理を行い、復号文ｍ'を生成する点が、復号化部２４と異なる。
【０３５５】
＜暗号通信システム１ｃの動作＞
以上、暗号通信システム１ｃの構成について説明したが、ここでは、暗号通信システム１ｃの全体の動作について、図１４に示すフローチャートを用いて説明する。
【０３５６】
最初に、パラメータ記憶部１１ｃ及びパラメータ記憶部２１ｃは、ｐ＝３かつｑ＝２＾ｋ（ｋ：２以上の整数）であり、条件式ＥＦＣ２を満たすパラメータを予め記憶している（ステップＳ３６１）。
【０３５７】
次に、鍵生成部２２ｃは、パラメータ記憶部２１ｃからパラメータＮ、パラメータｑ、パラメータｄｆ、パラメータｄｇを読み取り、パラメータＮ、パラメータｄｆを用いて、ｄｆ個の係数が１であり、かつその他の係数が０となるように、（Ｎ−１）次以下の多項式で表される多項式Ｆを選び、ｆ＝１＋ｐ・Ｆにより秘密鍵ｆを生成する（ステップＳ３６２）。
【０３５８】
次に、鍵生成部２２ｃは、パラメータＮ、パラメータｄｇを用いて、ｄｇ個の係数が１であり、かつその他の係数は０となるように、（Ｎ−１）次以下の多項式で表される多項式ｇを選ぶ（ステップＳ３６３）。
【０３５９】
次に、鍵生成部２２ｃは、上述した第３の変形ＮＴＲＵ暗号方式の鍵生成処理を行い、公開鍵である多項式ｈを生成する（ステップＳ３６４）。
【０３６０】
次に、鍵生成部２２ｃは、多項式ｈを公開鍵として公開し、暗号装置１０ｃが取得できるようにし、多項式ｆを秘密鍵として秘密鍵記憶部２３に記憶する（ステップＳ３６５）。
【０３６１】
次に、公開鍵記憶部１２は、通信路３０を介して復号装置２０ｃの公開鍵ｈを取得して記憶する（ステップＳ３６６）。
【０３６２】
次に、暗号化部１３ｃは、外部から係数が０もしくは１である平文ｍが入力されると、パラメータ記憶部１１ｃからパラメータＮ、パラメータｑ、パラメータｄを読み取り、公開鍵記憶部１２から、公開鍵ｈを読み取る（ステップＳ３６７）。
【０３６３】
次に、暗号化部１３ｃは、パラメータＮ、パラメータｄを用いて、ｄ個の係数が１であり、かつ他の係数が０となるように、（Ｎ−１）次以下の多項式ｒをランダムに選ぶ（ステップＳ３６８）。
【０３６４】
次に、暗号化部１３ｃは、平文ｍに対し、乱数ｒ、公開鍵ｈ、パラメータＮ、パラメータｑを用いて、第３の変形ＮＴＲＵ暗号方式の暗号化処理を行い、暗号文ｃを生成する（ステップＳ３６９）。
【０３６５】
次に、暗号化部１３ｃは、生成した暗号文ｃを通信路３０を介して復号装置２０ｃへ送信する（ステップＳ３７０）。
【０３６６】
次に、復号化部２４ｃは、通信路３０を介して暗号装置１０ｃから暗号文ｃを受信すると、パラメータ記憶部２１ｃから、パラメータＮ、パラメータｐ、パラメータｑを読み取り、秘密鍵記憶部２３から、秘密鍵ｆを読み取る（ステップＳ３７１）。
【０３６７】
次に、復号化部２４ｃは、暗号文ｃに対し、秘密鍵ｆ、パラメータＮ、パラメータｐ、パラメータｑを用いて、第３の変形ＮＴＲＵ暗号方式の復号化処理を行い、復号文ｍ'を生成する（ステップＳ３７２）。
【０３６８】
次に、復号化部２４ｃは、生成した復号文ｍ'を外部へ出力して処理を終了する（ステップＳ３７３）。
【０３６９】
＜暗号通信システム１ｃの動作検証＞
まず、暗号装置１０ｃ及び復号装置２０ｃは、ステップＳ３６１において、ｐ＝３かつｑ＝２＾ｋ（ｋ：２以上の整数）であり、条件式ＥＦＣ２を満たすようなパラメータを記憶している。
【０３７０】
そして、復号装置２０ｃが、予め、このパラメータを用いて、ステップＳ３６２及びステップＳ３６３において、係数が０もしくは１の２値である、秘密鍵ｆ及び多項式ｇを生成し、ステップＳ３６４において、これらの多項式を基に公開鍵ｈを生成している。
【０３７１】
そして、暗号装置１０ｃでは、ステップＳ３６８にて、係数が０もしくは１の２値である多項式ｒを生成し、ステップＳ３６９にて、ｐ＝３かつｑ＝２＾ｋ（ｋ：２以上の整数）であり、条件式ＥＦＣ２を満たすようなパラメータと公開鍵ｈと乱数ｒを用いて、係数が０もしくは１の２値である平文ｍを暗号化して暗号文ｃを生成している。
【０３７２】
そして、復号装置２０ｃでは、ステップＳ３７２において、秘密鍵ｆと記憶しているｐ＝３かつｑ＝２＾ｋ（ｋ：２以上の整数）であり条件式ＥＦＣ２を満たすようなパラメータを用いて、復号文ｍ'を生成している。
【０３７３】
かかる構成によれば、ｐ＝３かつｑ＝２＾ｋ（ｋ：２以上の整数）であり、条件式ＥＦＣ２を満たすパラメータを、暗号装置１０ｃと復号装置２０ｃとの間で共有し、このパラメータを用いて暗号化通信を行っているため、上述した通り、従来のＮＴＲＵＥｎｃｒｙｐｔよりも高速処理可能となるようにできる。また、上述の条件式ＥＦＣ２の説明で述べた通り、復号エラーは原理的に起こらず、復号文ｍ'は必ず平文ｍと同一となる。
【０３７４】
これにより、復号エラーが原理的に発生せず、かつ高速処理可能な第３の変形ＮＴＲＵ暗号方式を構成することができ、また、第３の変形ＮＴＲＵ暗号方式を暗号通信システムに適用し、暗号装置が送信したデータ内容が、常に復号装置で正しく得られ、従来よりも高速処理可能な暗号通信システムを提供することができる。
【０３７５】
（その他の変形例）
なお、上記に説明した実施の形態は、本発明の実施の形態の一例であり、本発明はこの実施の形態に何ら限定されるものではなく、その主旨を逸脱しない範囲において種々なる態様で実施し得るものである。上述した変形例に加え、以下のような場合も本発明に含まれる。
【０３７６】
（１）暗号通信システム１、１ｂ、１ｃにおいては、パラメータ生成方法の一例、及びこのパラメータ生成方法により生成したパラメータの具体例を示しているが、これは、パラメータ生成方法の説明で述べた通り、他の生成方法でもよく、また、条件を満たせば他のパラメータでもよく、これに限定されない。
【０３７７】
（２）暗号通信システム１では、暗号装置１０と復号装置２０との間で、同一のパラメータとして、（Ｎ，ｐ，ｑ，ｄｆ，ｄｇ，ｄ）＝（２５１，３，２５６，４２，４２，４２）を共有しているが、暗号装置１０で、このパラメータのうち、暗号化処理に必要なもののみを保持するようにしてもよいし、復号装置２０で、鍵生成処理及び復号化処理に必要なもののみを保持するようにしてもよい。
【０３７８】
（３）暗号通信システム１では、復号装置２０が鍵生成処理を行っていたが、さらに専用通信路を介して暗号装置１０及び復号装置２０と通信可能な鍵生成装置を備え、復号装置２０が鍵生成処理を行うのに代えて、鍵生成装置が鍵生成処理を行い、暗号装置１０が、鍵生成装置から専用通信路を介して、公開鍵ｈを取得して公開鍵記憶部１２に予め記憶しておき、復号装置２０が、鍵生成装置から専用通信路を介して、秘密鍵の一部または秘密鍵そのものである多項式ｆを取得して秘密鍵記憶部２３に予め記憶しておいてもよい。なお、専用通信路に代えて通信路３０を用いてもよい。
【０３７９】
（４）実施の形態１から３では、多項式を用いて演算を表現しているが、特許文献１のようにこれを一般の環Ｒの元として表現してもよい。具体的には、多項式を環Ｒの元とし、ｐ、ｑを環Ｒのイデアルとしてもよい。さらに実施の形態１から３のｐ、ｑをイデアルｐ＝ｐｇ・Ｒ、ｑ＝ｑｇ・Ｒとしてもよい。具体的には、実施の形態１から３において、ｐ＝３、ｑ＝２＾ｋである場合に、ｐ＝３・Ｒ、ｑ＝（２＾ｋ）・Ｒであってもよい。このとき、２は環Ｒにおける２であり、環Ｒにおける加法群の零元０に乗法群の単位元１を２回足したものである。同様に３は零元０に単位元１を３回足したものである。さらに、２＾ｋは乗法群の単位元１に２をｋ回掛けたものである。
【０３８０】
また、ｄｇ、ｄを元ｇ、ｒをＮ次元配列で表現したときの要素が１である個数、ｄｆをｆまたはＦをＮ次元配列で表現したときの要素が１である個数とし、復号エラーが発生しない条件式をｐｇ×Ｍｉｎ（ｄｇ，ｄ）＋１＋ｐｇ×ｄｆ＜ｑｇとしてもよい。
【０３８１】
（５）本発明は、上記に示す方法であるとしてもよい。また、これらの方法をコンピュータにより実現するコンピュータプログラムであるとしてもよいし、前記コンピュータプログラムからなるデジタル信号であるとしてもよい。
【０３８２】
また、本発明は、前記コンピュータプログラム又は前記デジタル信号をコンピュータ読み取り可能な記録媒体、例えば、半導体メモリ、ハードディスクドライブ、ＣＤ−ＲＯＭ、ＤＶＤ−ＲＯＭ、ＤＶＤ−ＲＡＭ等に記録したものとしてもよい。
【０３８３】
（６）上記実施の形態及び変形例をそれぞれ組み合わせるとしてもよい。
【０３８４】
（７）また、ブロック図（図２や図４など）の各機能ブロックは典型的には集積回路であるＬＳＩとして実現される。これらは個別に１チップ化されても良いし、一部又は全てを含むように１チップ化されても良い。
【０３８５】
なお、ＬＳＩは集積度の違いにより、ＩＣ、システムＬＳＩ、スーパーＬＳＩ、ウルトラＬＳＩと呼称されることもある。
【０３８６】
また、集積回路化の手法はＬＳＩに限るものではなく、専用回路又は汎用プロセッサで実現してもよい。ＬＳＩ製造後に、プログラムすることが可能なＦＰＧＡ（Field Programmable Gate Array）や、ＬＳＩ内部の回路セルの接続や設定を再構成可能なリコンフィギュラブル・プロセッサを利用しても良い。
【０３８７】
さらには、半導体技術の進歩又は派生する別技術によりＬＳＩに置き換わる集積回路化の技術が登場すれば、当然、その技術を用いて機能ブロックの集積化を行ってもよい。別技術としてバイオ技術等が可能性としてありえる。
【産業上の利用可能性】
【０３８８】
本発明にかかる暗号通信システム、暗号装置及び復号装置は、従来よりも高速処理可能であるという効果、あるいは、復号エラーを原理的に発生させないようにできるという効果を有し、鍵配送やコンテンツ配信等の暗号通信システム等として有用である。
【図面の簡単な説明】
【０３８９】
【図１】図１は、本発明の実施の形態１に係る暗号通信システムの構成を示すブロック図である。
【図２】図２は、実施の形態１に係る暗号装置の構成を示すブロック図である。
【図３】図３は、実施の形態１に係る暗号装置の動作を示すフローチャートである。
【図４】図４は、実施の形態１に係る復号装置の構成を示すブロック図である。
【図５】図５は、実施の形態１に係る復号装置の動作を示すフローチャートである。
【図６】図６は、実施の形態１に係る暗号通信システム全体の動作を示すフローチャートである。
【図７】図７は、本発明の実施の形態２に係る暗号通信システムの構成を示すブロック図である。
【図８】図８は、実施の形態２に係る暗号装置の構成を示すブロック図である。
【図９】図９は、実施の形態２に係る復号装置の構成を示すブロック図である。
【図１０】図１０は、実施の形態２に係る暗号通信システム全体の動作を示すフローチャートである。
【図１１】図１１は、実施の形態３に係る暗号通信システムの構成を示すブロック図である。
【図１２】図１２は、実施の形態３に係る暗号装置の構成を示すブロック図である。
【図１３】図１３は、実施の形態３に係る復号装置の構成を示すブロック図である。
【図１４】図１４は、実施の形態３に係る暗号通信システム全体の動作を示すフローチャートである。
【符号の説明】
【０３９０】
１，１ｂ，１ｃ    暗号通信システム
１０，１０ｂ，１０ｃ    暗号装置
１１，１１ｂ，１１ｃ，２１，２１ｂ，２１ｃ    パラメータ記憶部
１２    公開鍵記憶部
１３，１３ｂ，１３ｃ    暗号化部
２０，２０ｂ，２０ｃ    復号装置
２２，２２ｂ，２２ｃ    鍵生成部
２３    秘密鍵記憶部
２４，２４ｂ，２４ｃ    復号化部
３０    通信路
【図１】
0004786531.tif 000002
【図２】
0004786531.tif 000003
【図３】
0004786531.tif 000004
【図４】
0004786531.tif 000005
【図５】
0004786531.tif 000006
【図６】
0004786531.tif 000007
【図７】
0004786531.tif 000008
【図８】
0004786531.tif 000009
【図９】
0004786531.tif 000010
【図１０】
0004786531.tif 000011
【図１１】
0004786531.tif 000012
【図１２】
0004786531.tif 000013
【図１３】
0004786531.tif 000014
【図１４】
0004786531.tif 000015