(57)【要約】【構成】入力メッセージｘをアフィン変換し、複数のブロックに分割して、各ブロックＹ１〜Ｙ９をべき乗してＺ１〜Ｚ９とする。多項式Ｒ４〜Ｒ６の各係数をＹ１〜Ｙ３の多項式として、Ｙ１〜Ｙ３により評価し、その値をＺ４〜Ｚ６と排他加算し、Γ４〜Γ６とする。多項式Ｒ７〜Ｒ９の各係数をＹ１〜Ｙ６の多項式として、Ｙ１〜Ｙ６により評価し、その値をＺ７〜Ｚ９と排他加算し、Γ７〜Γ９とする。Ｙ１〜Ｙ３，Γ４〜Γ９をアフィン変換して暗号文Ｋとする。【効果】暗号化、復号処理共に高速で行え、しかも安全性が高い。【選択図】　　図２
2004102096.tif 000002
【特許請求の範囲】
【請求項１】
多次多変数暗号を用いた暗号システムにおいて、
暗号化対象のデータｘを、中間的な暗号データｙ，Ｙ（Ｘ），Ｚ（Ｘ）へ暗号化するための手段と、
得られた中間的な暗号データの少なくとも一部により、秘密の多項式を評価して、新たな多項式Ｒｊ（Ｘ）を得るための手段と、
得られた多項式Ｒｊ（Ｘ）を中間的な暗号データと組み合わせて、暗号文Ｋを得るための手段とを設けたことを特徴とする、暗号システム。
【請求項２】
多次多変数暗号を用いた暗号システムに用いる復号処理装置において、
暗号文Ｋの少なくとも一部を中間的に復号して、中間的な暗号データΓｊ，Ｚｊ（Ｘ），Ｙｊ（Ｘ），ｙを得るための中間復号手段と、
前記中間的な暗号データにより秘密の多項式を評価して、新たな多項式Ｒｊ（Ｘ）を得るための評価手段と、
得られた多項式Ｒｊ（Ｘ）を、暗号文Ｋまたは中間的な暗号データΓｊ，Ｚｊ（Ｘ），Ｙｊ（Ｘ），ｙと組み合わせて復号するための、第２の復号手段とを設けたことを特徴とする、復号処理装置。
【請求項３】
前記秘密の多項式は、前記新たな多項式Ｒｊ（Ｘ）の係数多項式　ｒｉｊ（Ｘ）であることを特徴とする、請求項２の復号処理装置。
【請求項４】
前記評価手段では、得られた中間的な暗号データの一部を用いて前記新たな多項式を得、
前記第２の復号手段では、得られた多項式と中間的な暗号データの他の部分とを用いて、該他の部分をさらに復号するようにしたことを特徴とする、請求項２または３の復号処理装置。
【請求項５】
前記秘密の多項式を複数記憶すると共に、
ａ：　前記評価手段では、中間復号手段で得られた中間的な暗号データの一部を用いて、一部の秘密の多項式に対して新たな多項式を得、
ｂ：　得られた多項式の値と中間的な暗号データの他の部分とを用いて、前記第２の復号手段で、該他の部分をさらに復号し、　かつ
ｃ：　前記処理ｂで他の部分をさらに復号して得られたデータを、前記処理ａでの中間的な暗号データの一部に加えて、前記評価手段で他の秘密の多項式に対して新たな多項式を得、該他の秘密の多項式に対して得られた新たな多項式と、中間的な暗号データの更に他の部分とを用いて、前記第２の復号手段で該更に他の部分をさらに復号することにより、前記ａ，ｂの処理を繰り返して復号を進めるようにしたことを特徴とする、請求項４の復号処理装置。
【請求項６】
前記中間的な復号を、第１中間復号手段と第２中間復号手段の２つの中間復号手段により行い、
第１中間復号手段から得られた第１の中間的な暗号データＹ１により、前記評価手段で、新たな多項式Ｒ２（Ｘ）を得、
かつ前記第２復号手段で、新たな多項式Ｒ２（Ｘ）と、第１の復号手段から得られた中間的な暗号データΓ２（Ｘ）とを組み合わせて、さらに復号した暗号データＺ２（Ｘ）を得、
該暗号データＺ２（Ｘ）を前記第２中間復号手段により更に復号して、第２の中間的な暗号データＹ２を得ることにより、前記ａ，ｂの処理を行い、
作業変数ｊが２以上の場合、
得られた中間的な暗号データＹ１〜Ｙｊにより、前記評価手段で、新たな多項式Ｒｊ＋１（Ｘ）を得、
かつ新たな多項式Ｒｊ＋１（Ｘ）と、第１の復号手段から得られた中間的な暗号データΓｊ＋１（Ｘ）とを組み合わせて、前記第２復号手段でさらに復号した暗号データＺｊ＋１（Ｘ）を得、
暗号データＺｊ＋１（Ｘ）を前記第２中間復号手段により更に復号して、第２の中間的な暗号データＹｊ＋１を得る、
ことにより、前記ａ，ｂの処理を繰り返すようにしたことを特徴とする、請求項２〜５のいずれかの復号処理装置。
ただしｊは、ａ，ｂの処理を１回繰り返す毎に１増加する作業変数である。
【請求項７】
多次多変数暗号を用いた暗号システムに用いる復号プログラムにおいて、
暗号文Ｋの少なくとも一部を中間的に復号して、中間的な暗号データΓｊ，Ｚｊ（Ｘ），Ｙｊ（Ｘ），ｙを得るための中間復号命令と、
前記中間的な暗号データにより秘密の多項式を評価して、新たな多項式Ｒｊ（Ｘ）を得るための評価命令と、
得られた多項式Ｒｊ（Ｘ）を、暗号文Ｋまたは中間的な暗号データΓｊ，Ｚｊ（Ｘ），Ｙｊ（Ｘ），ｙと組み合わせて復号するための第２復号命令、とを備えたことを特徴とする、復号プログラム。
【請求項８】
前記秘密の多項式を複数記憶するための命令を備えると共に、
ａ：　前記評価命令では、中間復号命令で得られた中間的な暗号データの一部を用いて、一部の秘密の多項式に対して新たな多項式を得、
ｂ：　得られた多項式の値と中間的な暗号データの他の部分とを用いて、前記第２の復号命令で、該他の部分をさらに復号し、　かつ
ｃ：　前記処理ｂで他の部分をさらに復号して得られたデータを、前記処理ａでの中間的な暗号データの一部に加えて、前記評価命令で他の秘密の多項式に対して新たな多項式を得、該他の秘密の多項式に対して得られた新たな多項式と、中間的な暗号データの更に他の部分とを用いて、前記第２の復号命令で該更に他の部分をさらに復号することにより、前記ａ，ｂの処理を繰り返して復号を進めるようにしたことを特徴とする、請求項７の復号プログラム。
【請求項９】
多次多変数暗号を用いた暗号システムに用いる復号方法において、
暗号文Ｋの少なくとも一部を中間的に復号して、中間的な暗号データΓｊ，Ｚｊ（Ｘ），Ｙｊ（Ｘ），ｙを得、
前記中間的な暗号データにより秘密の多項式を評価して、新たな多項式Ｒｊ（Ｘ）を得、
得られた多項式Ｒｊ（Ｘ）を、暗号文Ｋまたは中間的な暗号データΓｊ，Ｚｊ（Ｘ），Ｙｊ（Ｘ），ｙと組み合わせて、復号するようにしたことを特徴とする、復号方法。
【請求項１０】
前記秘密の多項式を複数記憶し、
ａ：　前記評価では、中間復号で得られた中間的な暗号データの一部を用いて、一部の秘密の多項式に対して新たな多項式を得、
ｂ：　得られた多項式の値と中間的な暗号データの他の部分とを用いて、前記第２の復号で、該他の部分をさらに復号し、　かつ
ｃ：　前記処理ｂで他の部分をさらに復号して得られたデータを、前記処理ａでの中間的な暗号データの一部に加えて、前記評価で他の秘密の多項式に対して新たな多項式を得、該他の秘密の多項式に対して得られた新たな多項式と、中間的な暗号データの更に他の部分とを用いて、前記第２の復号で該更に他の部分をさらに復号することにより、前記ａ，ｂの処理を繰り返して復号を進めるようにしたことを特徴とする請求項９の復号方法。
【発明の詳細な説明】
【０００１】
【発明の利用分野】
この発明は、多次多変数の暗号システムと、復号処理装置や復号プログラム、復号方法に関し、特に安全性と高速性とを両立させたものに関する。
【０００２】
【従来技術】
【０００３】
【特許文献１】特開２００２−１４９０５９号公報
【０００４】
多次多変数の連立方程式の求解困難性を用いた、暗号システムが知られている。このようなシステムでは、連立方程式にメッセージの値を代入することにより暗号化がなされる。連立方程式は公開鍵として公開され、安全性の基礎は連立方程式の求解困難性である。しかしながらこのような暗号システムでは、安全性の根拠が特殊なクラスに属していることから、充分な安全性を確保することが困難であった。このため発明者は、メッセージを非還元性の非線形符号へ符号化して、縮退した暗号文に暗号化することを提案した（特許文献１）。
【０００５】
【発明の課題】
この発明の課題は、高速で暗号化や復号ができ、しかも安全性の高い、多次多変数多項式を用いた公開鍵暗号システムを提供することにある。
この発明での他の課題は、このような暗号システムに用いる復号処理装置を提供することにある。
この発明での他の課題は、このような復号処理装置に適した復号プログラムを提供することにある。
この発明でのさらに他の課題は、このような暗号システムに適した復号方法を提供することにある。
【０００６】
【用語法他】
この明細書において、紛らわしくない場合、多項式Ｙ（Ｘ）等から変数の表記を省略して多項式Ｙ等のように表記することがある。
特許請求の範囲等での記号は、図面との対象の便宜のためのもので、特許請求の範囲の解釈のためのものではない。
また暗号システムに関する記載は他のカテゴリーの復号処理装置や復号方法、復号プログラムなどにも当てはまり、逆に復号処理装置に関する記載は、暗号システムや復号方法、復号プログラムなどにも当てはまる。
多項式と中間的な暗号データの組み合わせは、実施例での加算に限らず、乗算等でも良い。
【０００７】
【発明の構成】
この発明の暗号システムは、多次多変数暗号を用いた暗号システムにおいて、
暗号化対象のデータｘを、中間的な暗号データｙ，Ｙ（Ｘ），Ｚ（Ｘ）へ暗号化するための手段と、
得られた中間的な暗号データの少なくとも一部により、秘密の多項式を評価して、新たな多項式Ｒｊ（Ｘ）を得るための手段と、
得られた多項式Ｒｊ（Ｘ）を中間的な暗号データと組み合わせて、暗号文Ｋを得るための手段とを設けたことを特徴とする。
【０００８】
この発明の復号処理装置は、多次多変数暗号を用いた暗号システムに用いる復号処理装置において、
暗号文Ｋの少なくとも一部を中間的に復号して、中間的な暗号データΓｊ，Ｚｊ（Ｘ），Ｙｊ（Ｘ），ｙを得るための中間復号手段と、
前記中間的な暗号データにより秘密の多項式を評価して、新たな多項式Ｒｊ（Ｘ）を得るための評価手段と、
得られた多項式Ｒｊ（Ｘ）を、暗号文Ｋまたは中間的な暗号データΓｊ，Ｚｊ（Ｘ），Ｙｊ（Ｘ），ｙと組み合わせて復号するための、第２の復号手段とを設けたことを特徴とする。
【０００９】
好ましくは、前記評価手段では、前記秘密の多項式は、前記新たな多項式Ｒｊ（Ｘ）の係数多項式である。
【００１０】
また好ましくは、前記評価手段では、得られた中間的な暗号データの一部を用いて前記新たな多項式を得、
前記第２の復号手段では、得られた多項式と中間的な暗号データの他の部分とを用いて、該他の部分をさらに復号する。
【００１１】
更に好ましくは、前記秘密の多項式を複数記憶すると共に、
ａ：　前記評価手段では、中間復号手段で得られた中間的な暗号データの一部を用いて、一部の秘密の多項式に対して新たな多項式を得、
ｂ：　得られた多項式の値と中間的な暗号データの他の部分とを用いて、前記第２の復号手段で、該他の部分をさらに復号し、　かつ
ｃ：　前記処理ｂで他の部分をさらに復号して得られたデータを、前記処理ａでの中間的な暗号データの一部に加えて、前記評価手段で他の秘密の多項式に対して新たな多項式を得、該他の秘密の多項式に対して得られた新たな多項式と、中間的な暗号データの更に他の部分とを用いて、前記第２の復号手段で該更に他の部分をさらに復号することにより、前記ａ，ｂの処理を繰り返して復号を進める。
【００１２】
また好ましくは、前記中間的な復号を、第１中間復号手段と第２中間復号手段の２つの中間復号手段により行い、
第１中間復号手段から得られた第１の中間的な暗号データＹ１により、前記評価手段で、新たな多項式Ｒ２（Ｘ）を得、
かつ前記第２復号手段で、新たな多項式Ｒ２（Ｘ）と、第１の復号手段から得られた中間的な暗号データΓ２（Ｘ）とを組み合わせて、さらに復号した暗号データＺ２（Ｘ）を得、
該暗号データＺ２（Ｘ）を前記第２中間復号手段により更に復号して、第２の中間的な暗号データＹ２を得ることにより、前記ａ，ｂの処理を行い、
作業変数ｊが２以上の場合、
得られた中間的な暗号データＹ１〜Ｙｊにより、前記評価手段で、新たな多項式Ｒｊ＋１（Ｘ）を得、
かつ新たな多項式Ｒｊ＋１（Ｘ）と、第１の復号手段から得られた中間的な暗号データΓｊ＋１（Ｘ）とを組み合わせて、前記第２復号手段でさらに復号した暗号データＺｊ＋１（Ｘ）を得、
暗号データＺｊ＋１（Ｘ）を前記第２中間復号手段により更に復号して、第２の中間的な暗号データＹｊ＋１を得る、　ことにより、前記ａ，ｂの処理を繰り返す。
ただしｊは、ａ，ｂの処理を１回繰り返す毎に１増加する作業変数である。
【００１３】
この発明の復号プログラムは、多次多変数暗号を用いた暗号システムに用いる復号プログラムにおいて、
暗号文Ｋの少なくとも一部を中間的に復号して、中間的な暗号データΓｊ，Ｚｊ（Ｘ），Ｙｊ（Ｘ），ｙを得るための中間復号命令と、
前記中間的な暗号データにより秘密の多項式を評価して、新たな多項式Ｒｊ（Ｘ）を得るための評価命令と、
得られた多項式Ｒｊ（Ｘ）を、暗号文Ｋまたは中間的な暗号データΓｊ，Ｚｊ（Ｘ），Ｙｊ（Ｘ），ｙと組み合わせて復号するための第２復号命令、とを備えたことを特徴とする。
【００１４】
好ましくは、前記秘密の多項式を複数記憶するための命令を備えると共に、
ａ：　前記評価命令では、中間復号命令で得られた中間的な暗号データの一部を用いて、一部の秘密の多項式に対して新たな多項式を得、
ｂ：　得られた多項式の値と中間的な暗号データの他の部分とを用いて、前記第２の復号命令で、該他の部分をさらに復号し、　かつ
ｃ：　前記処理ｂで他の部分をさらに復号して得られたデータを、前記処理ａでの中間的な暗号データの一部に加えて、前記評価命令で他の秘密の多項式に対して新たな多項式を得、該他の秘密の多項式に対して得られた新たな多項式と、中間的な暗号データの更に他の部分とを用いて、前記第２の復号命令で該更に他の部分をさらに復号することにより、前記ａ，ｂの処理を繰り返して復号を進める。
【００１５】
この発明の復号方法は、多次多変数暗号を用いた暗号システムに用いる復号方法において、
暗号文Ｋの少なくとも一部を中間的に復号して、中間的な暗号データΓｊ，Ｚｊ（Ｘ），Ｙｊ（Ｘ），ｙを得、
前記中間的な暗号データにより秘密の多項式を評価して、新たな多項式Ｒｊ（Ｘ）を得、
得られた多項式Ｒｊ（Ｘ）を、暗号文Ｋまたは中間的な暗号データΓｊ，Ｚｊ（Ｘ），Ｙｊ（Ｘ），ｙと組み合わせて、復号するようにしたことを特徴とする。
【００１６】
好ましくは、前記秘密の多項式を複数記憶し、
ａ：　前記評価では、中間復号で得られた中間的な暗号データの一部を用いて、一部の秘密の多項式に対して新たな多項式を得、
ｂ：　得られた多項式の値と中間的な暗号データの他の部分とを用いて、前記第２の復号で、該他の部分をさらに復号し、　かつ
ｃ：　前記処理ｂで他の部分をさらに復号して得られたデータを、前記処理ａでの中間的な暗号データの一部に加えて、前記評価で他の秘密の多項式に対して新たな多項式を得、該他の秘密の多項式に対して得られた新たな多項式と、中間的な暗号データの更に他の部分とを用いて、前記第２の復号で該更に他の部分をさらに復号することにより、前記ａ，ｂの処理を繰り返して復号を進める。
【００１７】
【発明の作用と効果】
この発明の暗号システムでは、暗号化の過程をまとめて、公開多項式にメッセージを代入することで実現できる。このため暗号化を高速で行える。また公開多項式からは、秘密の多項式を秘密に保つことができる。この秘密の多項式が暗号化アルゴリズムの中心となるので、暗号強度が高い。復号は、中間的な暗号データの一部を得て、これにより多項式Ｒｊ（Ｘ）を得て、他の部分を中間的な暗号データに戻すことにより行われ、高速で行うことができる。これらのため、暗号化／復号処理とも高速で行え、しかも安全性の高い暗号システムが得られる。
【００１８】
この発明の復号処理装置では、安全性の高い暗号を高速で復号できるので、暗号通信や電子署名、認証などに適している。また比較的少ない計算量で復号できるので、ＩＣカードなどへの実装が容易である。
【００１９】
また秘密の多項式を新たな多項式の係数多項式とすると、新たな多項式が露呈しても秘密の多項式は露呈しにくく安全性が増す。
【００２０】
得られた中間データの一部を用いて新たな多項式を得て、これと中間データの他の部分を組み合わせて、他の部分を更に復号するようにすると、中間データの他の部分の安全性が中間データの一部で強化される。
【００２１】
また、前記秘密の多項式を複数記憶し、
ａ：　前記評価では、中間復号で得られた中間的な暗号データの一部を用いて、一部の秘密の多項式に対して新たな多項式を得、
ｂ：　得られた多項式の値と中間的な暗号データの他の部分とを用いて、前記第２の復号で、該他の部分をさらに復号し、　かつ
ｃ：　前記処理ｂで他の部分をさらに復号して得られたデータを、前記処理ａでの中間的な暗号データの一部に加えて、前記評価で他の秘密の多項式に対して新たな多項式を得、該他の秘密の多項式に対して得られた新たな多項式と、中間的な暗号データの更に他の部分とを用いて、前記第２の復号で該更に他の部分をさらに復号することにより、前記ａ，ｂの処理を繰り返して復号を進めるようにすると、暗号の安全性をさらに高くできる。
【００２２】
特に上記ａ，ｂの処理を、中間的な暗号データの各ブロック毎に繰り返すと、暗号の安全性を極めて高くできる。
【００２３】
この発明の復号プログラムや復号方法を用いると、信頼性の高い公開鍵暗号を高速で復号できる。
【００２４】
【実施例】
図１〜図１１に、実施例とその変形とを示す。これらの図において、２は暗号システムで、４，６は第１及び第２の情報処理装置で、パーソナルコンピュータやセキュリティサーバ、あるいはＩＣカードなどとする。情報処理装置４，６間の入出力は、通信によるものでも、あるいはＩＣカードリーダとＩＣカードとのように、単なる入出力で結ばれたものでも良い。ここでは情報処理装置４に入力メッセージｘが入力され、これを情報処理装置４で暗号文Ｋに変換し、第２の情報処理装置６で復号する場合を説明する。
【００２５】
情報処理装置４，６の構成はは同様とし、８は暗号化処理部で、１０は復号処理部であり、１２は鍵記憶部で、公開鍵である各ｍ次の多項式ｋ１（Ｘ）〜ｋｎ（Ｘ）を記憶し、これ以外に秘密鍵として原始多項式Ｇｊ（Ｘ），ｄ，ｅｊ，正則行列Ａ，Ｂ，秘密の多項式の係数となる多項式ｒｊｉを記憶する。これ以外に実施例では定数Ｊを記憶する。１４は電子署名処理部で、電子署名や認証などに用い、メッセージを暗号化する代わりに、署名や認証すべきデータを暗号化したものを復号する。電子署名や認証では、署名や認証すべきデータを暗号文と見なして、復号処理部１０で復号したものを、電子署名、あるいは認証として出力する。１６はプログラム記憶部で、暗号化のプログラムや復号プログラム並びに鍵の管理に関するプログラムや、電子署名や認証に関するプログラムを、適宜の記憶媒体に記憶させたものである。
【００２６】
表１に、実施例で用いる記号の意味を示す。図２に、変形例での暗号化過程の原理を示す。この変形例での暗号化をやや単純にしたものが実施例である。また図２では、ボックスの数を実際よりも少なく示す。入力メッセージｘをアフィン変換処理部２０でアフィン変換し、出力ｙを例えば９ブロックに分割し、各ブロックを多項式表現して、ボックス２１〜２９に格納する。ボックス２１〜２３のブロックＹ１〜Ｙ３は、そのまま新たな多項式Ｚ１〜Ｚ３として、ボックス３０〜３２に格納する。またボックス２４〜２６の多項式Ｙ４〜Ｙ６を、ボックス３３〜３５に、Ｚ４〜Ｚ６として格納する。同様にボックス２７〜２９の多項式Ｙ７〜Ｙ９を、ボックス３６〜３８に、多項式Ｚ７〜Ｚ９として格納する。
【００２７】
【表１】
2004102096.tif 000003
【００２８】
多項式Ｙ１〜Ｙ３を、秘密の多項式Ｒ４〜Ｒ６の評価手段４０へ入力する。なお評価手段４０は、秘密の多項式Ｒ４〜Ｒ６の各係数を記憶しており、この係数は多項式で、多項式として記憶され、その変数は多項式Ｙ１〜Ｙ３の各係数である。従って、多項式Ｙ１〜Ｙ３を評価手段４０へ入力することにより、秘密の多項式Ｒ４〜Ｒ６の各係数を評価して、新たな多項式Ｒ４（Ｘ）〜Ｒ６（Ｘ）を得ることができる。多項式の係数の値を評価することを、この明細書では多項式を評価する、もしくは多項式の値を求める、多項式を定める等と呼ぶことがある。これは評価後の多項式Ｒ４（Ｘ）〜Ｒ６（Ｘ）の変数Ｘは、多項式表現に伴う形式的な変数だからである。得られた多項式Ｒ４（Ｘ）を排他加算器４１へ出力し、ボックス３３の多項式Ｚ４と排他加算して、ボックス４４に中間暗号文のデータΓ４として出力する。同様に排他加算器４２でＲ５（Ｘ）とＺ５とを排他加算し、ボックス４５にΓ５として記憶する。さらに多項式Ｒ６（Ｘ）とＺ６とを排他加算器４３で排他加算してボックス４６に記憶させる。ここで排他加算としたのは、メッセージｘ等が標数２の体上の元である場合を想定したからで、標数が２でなければ、排他加算以外の演算を用いればよい。
【００２９】
このようにして多項式Ｚ４〜Ｚ６までの処理が終了すると、多項式Ｙ１〜Ｙ６を利用して秘密の多項式Ｒ７〜Ｒ９の各係数を評価し、多項式Ｒ７（Ｘ）〜Ｒ９（Ｘ）を発生させる。４８は秘密の多項式Ｒ７〜Ｒ９の評価手段で、同様に秘密の多項式Ｒ７〜Ｒ９の各係数を記憶する。そして多項式Ｒ７（Ｘ）〜Ｒ９（Ｘ）と、多項式Ｚ７〜Ｚ９とを排他加算器４９〜５１で排他加算し、ボックス５２〜５４に中間的な暗号文Γ７〜Γ９として格納する。
【００３０】
多項式Ｚ１〜Ｚ３を多項式ではなくベクトルと見なし、同様にボックス４４〜４６，５２〜５４のデータΓ４〜Γ９を、多項式ではなくベクトルと見なし、これらを所定の順序で並べて１つのベクトルを構成する。これをアフィン変換処理部５６に入力しアフィン変換する。アフィン変換したベクトルが、暗号文Ｋとなる。暗号文Ｋは入力メッセージｘと等長である。
【００３１】
図３，図４に、実施例での暗号化の原理を示す。また図５に、実施例を変形して暗号強度を高めた変形例を示す。図５の変形例では、図３，図４のアルゴリズムに対する変更部のみを示す。
【００３２】
図３のステップ１で、メッセージｘを入力し、ステップ２で正則行列Ａを用いてアフィン変換する。なおメッセージｘの元の数がｎ個である場合、実施例ではアフィン変換行列Ａもｎ行ｎ列の行列とするが、行列Ａをｎ＋１行×ｎ＋１列の行列とし、メッセージｘの末尾に乱数や定数の項を追加して形式的にｎ＋１次元と見なしても良い。以下同様にデータｙもｎ＋１次元としても良い。また各図において、大文字Ｔは転置を表す。
【００３３】
アフィン変換したメッセージｙをＮ個のブロックに分割し（ステップ３）、原始多項式Ｇｊ（Ｘ）を用いて、各ｙｊ（各ブロック）を多項式表現する（ステップ４）。用いる原始多項式Ｇｊ（Ｘ）はＮ個のブロックに対して共通でも良く、あるいはブロック毎に異ならせても良い。また原始多項式の次数Ｇｊ（Ｘ）は、ｔｊ次以上とする。なおｔｊはｊ番目のブロックの元の数である。そしてステップ５で、秘密の指数ｄを用いて、多項式表現したＹｊ（Ｘ）をＧｊ（Ｘ）を法としてｄ乗する。その結果をＺｊ（Ｘ）とする。
【００３４】
実施例の場合、ｊが１〜Ｊまでの範囲で、Ｚｊ（Ｘ）をΓｊ（Ｘ）に代入する（ステップ６）。続いて結合子▲１▼から図４に移り、多項式Ｒｊ（Ｘ）の各係数ｒｊｉを評価する。係数ｒｊｉはアフィン変換したメッセージｙの一部（ｙ１〜ｙＪ）のｍ次の多項式であり、ブロックＹ１〜ＹＪのｍ次の多項式である。ｒｊｉは多項式Ｒｊ（Ｘ）の例えばｉ次係数を意味し、ｒｊｉは秘密である。そしてＲｊ（Ｘ）は法Ｇｊ（Ｘ）上の多項式なので、その次数は例えばｔｊ−１次以下とする。また係数ｒｊｉをＹ１〜ＹＪの多項式と見なした場合、その次数ｍは例えば２以上５以下が好ましい（ステップ７）。Ｒｊ（Ｘ）が求まると、ステップ８でΓｊ（Ｘ）を求め、ステップ９で中間的な暗号データΓを得る。続いてステップ１０でアフィン変換行列Ｂを用いてアフィン変換すると、ステップ１１の出力暗号文Ｋが得られる。なおＢはｎ行ｎ列の正則行列であるが、行列Ａと同様に、ｎ＋１行×ｎ＋１列の正則行列としても良い。この場合、暗号文Ｋ中のｎ＋１番目の要素は意味のない要素で、削除しても良い。
【００３５】
図５に変形例の処理を示すと、図３の結合子▲２▼から分岐して、ステップ１２でＺ１（Ｘ）をΓ１（Ｘ）とし、Ｙ１を用いて多項式Ｒ２（Ｘ）の各係数を評価して、多項式Ｒ２（Ｘ）を決定する（ステップ１３）。次にＹ１，Ｙ２を用いて、多項式Ｒ３（Ｘ）の各係数を評価し、多項式Ｒ３（Ｘ）を決定する。以下同様にして、Ｙ１〜Ｙｊを用いて多項式Ｒｊ＋１（Ｘ）を決定し、最後の多項式ＲＮ（Ｘ）をＹ１〜ＹＮ−１により決定する（ステップ１５）。次にｊ＝２〜Ｎに対して、Ｚｊ（Ｘ）＋Ｒｊ（Ｘ）＝Γｊ（Ｘ）により、Γｊを決定する。そして結合子▲３▼から、図４のステップ１０に移る。
【００３６】
図６に、メッセージｘから暗号文Ｋまでの暗号化を写像として説明する。アフィン変換Ａを用いて、ｘをｙに変換し、ｙをブロック化し、各ブロックを多項式表現してＹに変換する。なお原始多項式Ｇｊ（Ｘ）の次数は各ブロックの元の数以上である。多項式表現した各ブロックを、秘密の定数ｄでべき乗し、原始多項式Ｇｊ（Ｘ）を法とした多項式をＺＪ（Ｘ）とする。このようにしてＹをＺに変換する。
【００３７】
Ｚ１（Ｘ）〜ＺＮ（Ｘ）を、例えば左半分のＺ１（Ｘ）〜ＺＪ（Ｘ）と右半分のＺＪ＋１（Ｘ）〜ＺＮ（Ｘ）に分割し、左半分のＺ１（Ｘ）〜ＺＪ（Ｘ）をそのままΓ１（Ｘ）〜ΓＪ（Ｘ）とする。なおＮはブロックの数である。そしてＹ１〜ＹＪを用いて、秘密の多項式ＲＪ＋１〜ＲＮを評価し、この秘密の多項式ＲＪ＋１〜ＲＮとＺＪ＋１〜ＺＮとを各々加算して、ΓＪ＋１〜ΓＮを求める。次にΓ１〜ΓＮを集めて１つのベクトルとし、これを行列Ｂによりアフィン変換して出力暗号文Ｋとする。
【００３８】
ここでＹ１〜ＹＪを用いて、秘密の多項式ＲＪ＋１〜ＲＮを一括して評価する代わりに、Ｙ１を用いて多項式Ｒ２を評価し、Ｙ１，Ｙ２を用いて多項式Ｒ３を評価し、以下同様にＹ１〜ＹＮ−１を用いて多項式ＲＮを評価するようにすると、図５の変形例となる。またＹ１〜ＹＮを３分割し、例えばＹ１〜Ｙ３をそのままΓ１〜Γ３とし、同時にＹ１〜Ｙ３で多項式Ｒ４〜Ｒ６を評価し、Ｙ１〜Ｙ６でＲ７〜Ｒ９を評価すると、図２の変形例となる。
【００３９】
図７に、実施例での暗号化の手順を示す。図６の各処理をまとめて１つの合成写像と考えると、これはメッセージｘを変数とする連立多項式と考えることができる。なおデータｙはメッセージｘに対して線形（その要素がメッセージｘの要素の線形和）であり、Ｙを用いて多項式Ｒｊ（Ｘ）等の係数を定めると、メッセージｘを用いて係数を定めたことになる。そこで暗号化の手順を、ｎ個の公開のｍ次多項式ｋ１（ｘ）〜ｋｎ（ｘ）に、メッセージｘを代入することと表現することができる。このため暗号化は簡単かつ高速で行える。
【００４０】
図８に、実施例での復号アルゴリズムを示す。暗号文Ｋをｎ行ｎ列の逆アフィン変換行列Ｂ−１で処理し、中間復号文（中間的な暗号データ）Γに変換する（ステップ２１）。ｉ＝１〜Ｊに対しては、Γｉ（Ｘ）＝Ｚｊ（Ｘ）である（ステップ２２）。アフィン変換Ｂ自体の秘匿強度は低いので、｛Ｚｊ（Ｘ）｝ｅｊ≡Ｙｊ（Ｘ）　ｍｏｄＧｊ（Ｘ）　により　Ｙｊ（Ｘ）に変換し、離散対数問題を利用して中間的な暗号データＹｊ（Ｘ）の安全性を高める（ステップ２３）。次いで、Ｙ１（Ｘ）〜ＹＪ（Ｘ）からＲＪ＋１（Ｘ）〜ＲＮ（Ｘ）を求めて（ステップ２４）、ステップ２５でＺＪ＋１（Ｘ）〜ＺＮ（Ｘ）を復号する。
【００４１】
ステップ２６で、ステップ２３と同様にして、
｛Ｚｊ（Ｘ）｝ｅｊ≡Ｙｊ（Ｘ）　ｍｏｄＧｊ（Ｘ）　によりＹｊ（Ｘ）を求める。Ｎ個のブロックＹ１（Ｘ）〜ＹＮ（Ｘ）を多項式表現からベクトル表現に変更し、要素を順に配列するとベクトルｙが得られる。ベクトルｙに対して、行列Ａ−１　を作用させると、入力メッセージｘを復号できる（ステップ２７）。
【００４２】
図９は、図８のステップ２２〜２６に代わる変形例を示し、ステップ３０で　Γ１（Ｘ）をＺ１（Ｘ）に代入し、ステップ３２でＹ１（Ｘ）を求める。作業変数ｊの初期値を２にセットし（ステップ３２）、Ｙ１（Ｘ）〜Ｙｊ−１（Ｘ）を用いてＲｊ（Ｘ）を決定する（ステップ３３）。ステップ３４でＺｊ（Ｘ）を決定し、ステップ３５でＹｊ（Ｘ）を求め、ステップ３６でｊの値を１増して、全てのブロックＹ１（Ｘ）〜ＹＮ（Ｘ）が得られるまで、処理を繰り返す。次いで結合子▲５▼から図８のステップ２７を実行し、メッセージｘを求める。
【００４３】
実施例ではアフィン変換を用いて、メッセージｘやΓ１〜ΓＮを秘匿し、Ｚｊ（Ｘ）からＹｊ（Ｘ）を秘匿するために離散対数問題を用いた。暗号の信頼性を補強するため、例えば別の多次多項式暗号システムを補助的に用いても良い。図１０，図１１にこのような例を示す。
【００４４】
図１０では、指数ｄでのべき乗に代えて、多次多変数連立多項式への代入を実行する。ブロックＹ１（Ｘ）〜ＹＮ（Ｘ）をベクトル表現したものをｙ１’〜ｙＮ’とし、これをｎ個の多変数多項式に入力して、ベクトルデータＺ１’〜ＺＮ’を得る。なお各ブロックＹ１（Ｘ）〜ＹＮ（Ｘ）の次数をｔｊ−１とすると、各ブロックにｔｊ個の多項式を割り当てる。ベクトルデータＺ１’〜ＺＮ’を多項式表現して、Ｚ１（Ｘ）〜ＺＮ（Ｘ）とする。多次多変数連立多項式の求解は困難なので、復号時には例えばＮ個の復号テーブルを用意し、ベクトルデータＺ１’〜ＺＮ’で復号テーブルを参照し、ｙ１’〜ｙＮ’を求める。
【００４５】
実施例の暗号システムでは、Ｚ１（Ｘ）〜ＺＪ（Ｘ）は多次多変数での処理で秘匿されていないので、Ｚ１（Ｘ）〜ＺＪ（Ｘ）を介しての攻撃が考えられる。Ｚ１（Ｘ）〜ＺＪ（Ｘ）をそのままΓ１（Ｘ）〜ΓＪ（Ｘ）とせずに、多次多変数の連立多項式で補強した例を図１１に示す。Ｚ１（Ｘ）〜ＺＪ（Ｘ）をベクトル表現して、ベクトルデータＺ１’〜ＺＪ’とし、これを多次多変数の連立多項式ｆ１１〜ｆＪｔＪで処理して、多項式Ｚ１’’〜ＺＪ’’とし、これを多項式Γ１〜ΓＪに変換する。この場合、復号時にはＪ枚の復号テーブルを用意してＺ１（Ｘ）〜ＺＪ（Ｘ）へ復号する。またＺ１（Ｘ）のみをそのままΓ内のブロックΓ１に変換する変形例の場合、Ｚ１（Ｘ）をベクトル表現したものを多変数多項式ｆ１に代入してΓ１とし、復号テーブルを１枚用意して、Γ１をＺ１に復号すればよい。この場合は、復号テーブルを記憶するためのスペースを少なくしながら、Ｚ１（Ｘ）の安全性を補強できる。
【００４６】
実施例での暗号化は、公開鍵の連立多変数多項式へのメッセージの入力で実行でき、高速で実行できる。復号処理は、アフィン変換や多項式Ｒｊ（Ｘ）の算出、多項式Ｒｊ（Ｘ）とΓｊ（Ｘ）との排他加算などを、複数のパイプラインで並列処理すると簡単に実行できる。発明者の評価では、共通鍵暗号に匹敵する速度で、復号処理が行えるはずである。
【図面の簡単な説明】
【図１】実施例の暗号システムの構成を示すブロック図
【図２】変形例での暗号化過程の原理を示すブロック図
【図３】実施例での暗号化過程の原理を示すフローチャート
【図４】図３の結合子▲１▼以下のアルゴリズムを示すフローチャート
【図５】暗号化過程の一部を変更した、変形例のアルゴリズムを示すフローチャート
【図６】実施例での暗号化過程を写像として示す図
【図７】実施例での暗号化のアルゴリズムを示す図
【図８】実施例での復号アルゴリズムを示すフローチャート
【図９】変形例の復号アルゴリズムを示すフローチャート
【図１０】他の変形例での暗号化の原理と復号手続の変更箇所を、写像として示す図
【図１１】図１０の変形例を、Ｚ１（Ｘ）〜ＺＪ（Ｘ）の秘匿強度の向上に用いた例を示す図
【符号の説明】
２　　　　　暗号システム
４，６　　　情報処理装置
８　　　　　暗号化処理部
１０　　　　復号処理部
１２　　　　鍵記憶部
１４　　　　電子署名処理部
１６　　　　プログラム記憶部
２０，５６　アフィン変換処理部
２１〜２９　中間的な暗号文Ｙ＝（Ｙ１（Ｘ），…ＹＮ（Ｘ））の各要素Ｙｊを記憶するためのボックス
３０〜３８　中間的な暗号文Ｚ＝（Ｚ１（Ｘ），…ＺＮ（Ｘ））の各要素Ｚｊを記憶するためのボックス
４０，４８　秘密の多項式Ｒ４〜Ｒ６，Ｒ７〜Ｒ９の評価手段
４１〜４３　排他加算器
４９〜５１　排他加算器
４４〜４６　中間的な暗号文Γ４（Ｘ），…Γ６（Ｘ）を記憶するためのボックス
５２〜５４　中間的な暗号文Γ７（Ｘ），…Γ９（Ｘ）を記憶するためのボックス
【図１】
2004102096.tif 000004
【図２】
2004102096.tif 000005
【図３】
2004102096.tif 000006
【図４】
2004102096.tif 000007
【図５】
2004102096.tif 000008
【図６】
2004102096.tif 000009
【図７】
2004102096.tif 000010
【図８】
2004102096.tif 000011
【図９】
2004102096.tif 000012
【図１０】
2004102096.tif 000013
【図１１】
2004102096.tif 000014