(57)【要約】【課題】  群の不変式を用いて暗号化及び復号化を行う暗号システムであって、平文の候補を２つのエンティティ間で共有することを必要とせずに暗号化及び復号化することができる暗号システムを提供する。【解決手段】  群G及び群G1が作用する数学的空間Xと、群G1に関する数学的空間X上の不変式INV1,…,INVnとを共有している第１及び第２のエンティティ間で暗号通信を行うシステムであって、第２エンティティは、平文Zが不変式に対してZ=（INV1(x),…,INVn(x)）となるように数学的空間Xの元xを生成し、これに群G1の元g1と群Gの元である共通キーaとを作用させたz=a＊g1＊xを暗号文として送信し、第１エンティティは、受信した暗号文zに対して共通キーaの逆元を作用させてv= a-1＊zを生成し、不変式にvを代入した値（INV1(v),…,INVn(v)）を復号化された平文Zとする暗号システム。【選択図】          図１
2006101354.tif 000002
【特許請求の範囲】
【請求項１】
第１のエンティティ及び第２のエンティティ間で暗号化された通信を行う暗号システムであって、
第１のエンティティ及び第２のエンティティは、群G及び群G1が作用する数学的空間Xと、群G1に関する数学的空間X上の不変式INV1,INV2,…,INVnとを共有しており、
第２のエンティティは、
暗号化対象である平文Zが、前記不変式に対してZ=（INV1(x),…,INVn(x)）となるように数学的空間Xの元xを生成し、
群G1の元であるg1と群Gの元である共通キーaとを上記で生成した元xに作用させた結果であるz=a＊g1＊xを暗号文として第１のエンティティに送信し、
第１のエンティティは、
受信した暗号文zに対して群Gの元である共通キーaの逆元を作用させてv= a-1＊zを生成し、
生成されたvに対して前記不変式を適用した結果得られる（INV1(v),…,INVn(v)）を復号化された平文Zとすることを特徴とする暗号システム。
【請求項２】
第１のエンティティ及び第２のエンティティ間で暗号化された通信を行う暗号システムであって、
第１のエンティティは、両エンティティ間で共通の群G1の不変式INV1,INV2,…,INVnを保存する手段と、両エンティティ間で共通の数学的空間Xに対する群Gの演算を行う手段と、群Gの元である共通キーaを保存する手段と、前記不変式の値を計算する手段と、送受信手段とを備えており、
第２のエンティティは、両エンティティ間で共通の群G1の不変式INV1,INV2,…,INVnを保存する手段と、両エンティティ間で共通の数学的空間Xに対する群G1の演算を行う手段と、両エンティティ間で共通の数学的空間Xに対する群Gの演算を行う手段と、群Gの元である共通キーaを保存する手段と、両エンティティ間で共通の群G1の元g1を生成する手段と、両エンティティ間で共通の数学的空間Xの元xを生成する手段と、送受信手段とを備えており、
第２のエンティティは、暗号化対象である平文Zが、前記不変式に対してZ=（INV1(x),…,INVn(x)）となるように数学的空間Xの元xを生成し、群G1の元であるg1と群Gの元である共通キーaとを上記で生成した元xに作用させた結果であるz=a＊g1＊xを暗号文として第１のエンティティに送信し、
第１のエンティティは、受信した暗号文zに対して群Gの元である共通キーaの逆元を作用させてv= a-1＊zを生成し、生成されたvに対して前記不変式を適用した結果得られる（INV1(v),…,INVn(v)）を復号化された平文Zとすることを特徴とする暗号システム。
【請求項３】
群G及び群G1が作用する数学的空間Xと、群G1に関する数学的空間X上の不変式INV1,INV2,…,INVnとを共有している第１のエンティティ及び第２のエンティティ間で暗号化された通信を行う方法であって、
第２のエンティティにおいて、暗号化対象である平文Zが、前記不変式に対してZ=（INV1(x),…,INVn(x)）となるように数学的空間Xの元xを生成し、
群G1の元であるg1と群Gの元である共通キーaとを上記で生成した元xに作用させた結果であるz=a＊g1＊xを暗号文として第１のエンティティに送信し、
第１のエンティティにおいて、受信した暗号文zに対して群Gの元である共通キーaの逆元を作用させてv= a-1＊zを生成し、
生成されたvに対して前記不変式を適用した結果得られる（INV1(v),…,INVn(v)）を復号化された平文Zとすることを特徴とする方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、群の不変式を用いて暗号化及び復号化を行う暗号システムに関し、特に、群の要素として与えられた共通キーを用いる暗号システムに関するものである。
【背景技術】
【０００２】
群の不変式を使用した暗号化方法は、ロスアラモス研究所のD. Grigorievによる論文“Public-Key cryptography and invariant Theory”（arXiv:cs.CR/0207080v1）において初めて提唱されたものである。この暗号化方法は、以下のようなものである。
【０００３】
・有限群G1と、その表現（G1,V,P１）において、コンスタントでない不変式ｗを１つ選び、平文としてVの元v0,v1を取る。
・エンティティ１（受信側）では、GL(V)の元aが秘密キーとして与えられており、w(av0)! = w(av1)が成り立っているものとする。
・G1の元giがランダムに生成されており、それに対して公開鍵hi=a-1*P1（gi）*aが与えられているものとする。
・エンティティ２（送信側）では、平文にh1*h2*…*hnをかけることにより暗号化される。例えば、平文v0,v1の暗号化の結果は、u = h1*h2*…*hn(v0)あるいは、u = h1*h2*…*hn(v1)となる。
・エンティティ１（受信側）では、w(au)が、w(av0)に等しいかw(av1)に等しいを判定することによって復号化を行う。
【０００４】
【特許文献１】特開２００４−３２５７４号公報。
【非特許文献１】D. Grigoriev, “Public-key cryptography and invariant theory”,     arXiv:math.cs.CR/0207080. （http://arXiv.org/abs/cs/0207080）
【発明の開示】
【発明が解決しようとする課題】
【０００５】
しかしながら、上記の暗号化方法は不変式wを使用するものではあるが、平文の候補であるv0,v1の選択に依存するところが大きくなってしまう。すなわち、エンティティ１及び２は、不変式による計算結果であるw(v0), w(v1)のみならず、v0, v1をも共有する必要がある。
【０００６】
本発明は、このような実情に鑑みてなされたものであり、群の不変式を用いて暗号化及び復号化を行う暗号システムであって、平文の候補を２つのエンティティ間で共有することを必要とせずに暗号化及び復号化を行うことができる暗号システムを提供しようとするものである。
【課題を解決するための手段】
【０００７】
上記課題を解決すべく本発明は、第１のエンティティ及び第２のエンティティ間で暗号化された通信を行う暗号システムであって、第１のエンティティ及び第２のエンティティは、群G及び群G1が作用する数学的空間Xと、群G1に関する数学的空間X上の不変式INV1,INV2,…,INVnとを共有しており、第２のエンティティは、暗号化対象である平文Zが、前記不変式に対してZ=（INV1(x),…,INVn(x)）となるように数学的空間Xの元xを生成し、群G1の元であるg1と群Gの元である共通キーaとを上記で生成した元xに作用させた結果であるz=a＊g1＊xを暗号文として第１のエンティティに送信し、第１のエンティティは、受信した暗号文zに対して群Gの元である共通キーaの逆元を作用させてv= a-1＊zを生成し、生成されたvに対して前記不変式を適用した結果得られる（INV1(v),…,INVn(v)）を復号化された平文Zとすることを特徴とする暗号システムを提供するものである。
【０００８】
本発明は、また、第１のエンティティ及び第２のエンティティ間で暗号化された通信を行う暗号システムであって、第１のエンティティは、両エンティティ間で共通の群G1の不変式INV1,INV2,…,INVnを保存する手段と、両エンティティ間で共通の数学的空間Xに対する群Gの演算を行う手段と、群Gの元である共通キーaを保存する手段と、前記不変式の値を計算する手段と、送受信手段とを備えており、第２のエンティティは、両エンティティ間で共通の群G1の不変式INV1,INV2,…,INVnを保存する手段と、両エンティティ間で共通の数学的空間Xに対する群G1の演算を行う手段と、両エンティティ間で共通の数学的空間Xに対する群Gの演算を行う手段と、群Gの元である共通キーaを保存する手段と、両エンティティ間で共通の群G1の元g1を生成する手段と、両エンティティ間で共通の数学的空間Xの元xを生成する手段と、送受信手段とを備えており、第２のエンティティは、暗号化対象である平文Zが、前記不変式に対してZ=（INV1(x),…,INVn(x)）となるように数学的空間Xの元xを生成し、群G1の元であるg1と群Gの元である共通キーaとを上記で生成した元xに作用させた結果であるz=a＊g1＊xを暗号文として第１のエンティティに送信し、第１のエンティティは、受信した暗号文zに対して群Gの元である共通キーaの逆元を作用させてv= a-1＊zを生成し、生成されたvに対して前記不変式を適用した結果得られる（INV1(v),…,INVn(v)）を復号化された平文Zとすることを特徴とする暗号システムを提供するものである。
【０００９】
本発明は、また、群G及び群G1が作用する数学的空間Xと、群G1に関する数学的空間X上の不変式INV1,INV2,…,INVnとを共有している第１のエンティティ及び第２のエンティティ間で暗号化された通信を行う方法であって、第２のエンティティにおいて、暗号化対象である平文Zが、前記不変式に対してZ=（INV1(x),…,INVn(x)）となるように数学的空間Xの元xを生成し、群G1の元であるg1と群Gの元である共通キーaとを上記で生成した元xに作用させた結果であるz=a＊g1＊xを暗号文として第１のエンティティに送信し、第１のエンティティにおいて、受信した暗号文zに対して群Gの元である共通キーaの逆元を作用させてv= a-1＊zを生成し、生成されたvに対して前記不変式を適用した結果得られる（INV1(v),…,INVn(v)）を復号化された平文Zとすることを特徴とする方法を提供するものである。
【発明の効果】
【００１０】
以上、説明したように、本発明の不変式を利用した暗号システムによれば、平文の候補を２つのエンティティ間で共有することを必要とせずに暗号化及び復号化を行うことができる。
【発明を実施するための最良の形態】
【００１１】
以下、添付図面を参照しながら、本発明の不変式を利用した暗号システムを実施するための最良の形態を詳細に説明する。図１〜図３は、本発明の実施の形態を例示する図であり、これらの図において、同一の符号を付した部分は同一物を表わし、基本的な構成及び動作は同様であるものとする。
【００１２】
図１は、本発明の一実施形態である暗号システムの概略構成を示すブロック図である。図１に示す暗号システムは、受信側である第１エンティティ１０と送信側である第２のエンティティ２０とから構成されている。第２のエンティティ２０において暗号化されたメッセージが第１のエンティティ１０に送信され、第１のエンティティ１０において復号化されるようになっている。第１エンティティ１０と第２のエンティティ２０とは、通信回線３０によって接続されている。通信回線３０は必ずしもセキュアな回線である必要はなく、インターネット等のような公衆通信網であってよい。
【００１３】
第１のエンティティ１０は、G1の不変式保存装置１１、数学的空間Xに対する群Gの演算装置１３、共通キーa保存装置１４、不変式の値計算装置１５及び送受信装置１６を有している。第２のエンティティ２０は、G1の不変式保存装置２１、数学的空間Xに対する群G1の演算装置２２、数学的空間Xに対する群Gの演算装置２３、共通キーa保存装置２４、群G1の元g1生成装置２５、送受信装置２６及び数学的空間Xの元x生成装置２７を有している。尚、第１のエンティティ１０及び第２のエンティティ２０は、ディスプレイや入力装置等を有するコンピュータ装置として構成することができる。この場合、群G1の不変式保存装置１１、共通キーa保存装置１４及び２４は、コンピュータ装置の外部又は内部に設けられた記憶装置を利用することができる。
【００１４】
群G1の不変式保存装置１１及び２１は、それぞれ、数学的空間Xにおける群G1の作用に関する不変式のシークエンスを保存している。群G1の数学的空間Xへの演算装置２２は、群G1の作用を数学的空間Xへの演算として計算するものである。群Gの数学的空間Xへの演算装置１３及び２３は、それぞれ、群Gの作用を数学的空間Xへの演算として計算するものである。共通キーa保存装置１４及び２４は、それぞれ、Gの元である共通キーaを保存している。このように群の元を共通キーとして生成する方法は、特許文献１などに記載されている。不変式の値計算装置１５は、不変式保存装置１１に保存されている不変式の値を数学的空間Xの元に対して求めるものである。送受信装置１６及び２６は、第１のエンティティと第２のエンティティとの間でのメッセージの送受信を行うものである。群G1の元g1生成装置２５は、群G1の元g1を生成するものである。数学的空間Xの元x生成装置２７は、数学的空間Xの元xを生成するものである。
【００１５】
以上のように構成された本実施形態の暗号システムにおいて、第１のエンティティと第２のエンティティとの間で暗号化したメッセージを送受信する動作について説明する。
【００１６】
図２は、第２のエンティティ２０において平文Zを暗号化し、暗号化した結果であるｚを第の１エンティティ１０に送信するまでの処理の流れを示すフローチャートである。
図２において、第２のエンティティ２０は、数学的空間Xの元x生成装置２７により、暗号化対象である平文Zに対する元xを生成する（ステップ３０）。ここで得られたxの性質は、群G1の不変式保存装置２１の内容が、(INV1,…,INVn)のとき、Z=（INV1(x),……,INVn(x)）となるものである。続いて、群G1の元g1生成装置２５により、群G1の元g1を生成する（ステップ３１）。群G1の数学的空間Xへの演算装置２２により、生成されたg1をxに作用させた結果を求める（ステップ３２）。すなわち、g1＊xを計算し、その結果をyとする。さらに、群Gの数学的空間Xへの演算装置２３により、共通キーa保存装置２４に保存されている群Gの元aをｙに作用させた結果を求める（ステップ３３）。すなわち、a*yを計算し、その結果をzとする。こうして得られた暗号文zを送受信装置２６により第１のエンティティ１０に送信する（ステップ３４）。
【００１７】
図３は、第１のエンティティ１０において受信した暗号文zを復号化して平文Zを得る処理の流れを示すフローチャートである。図３において、第１のエンティティ１０は、送受信装置１６により、第２のエンティティ２０から暗号文zを受信する（ステップ４０）。続いて、共通キーa保存装置１４からaを取得し、群Gの数学的空間Xへの演算装置１３により、aの逆元をｚに作用させた結果を求める（ステップ４１）。すなわち、a-1*zを計算し、その結果をvとする。その後、不変式の値計算装置１５により、不変式のvに対する値を計算すると、平文Zを得ることができる（ステップ４２）。
【実施例】
【００１８】
以下において、上記した実施形態の暗号システムによる暗号化及び復号化の具体的な実施例を示す。特に、図１に示す暗号システムにおける各演算装置行う処理について、具体例を挙げる。
【００１９】
本実施例では、群G1を置換群Sｎとし、Xを複素数C上のn次元ベクトル空間と仮定する。また、群G1の空間Xに対する作用を、適当な空間Xの基底｛x1,x2,x3,…xn｝の自然な置換から生成される群G1の空間X上の表現とする。空間Xの元xをci＊xiの和で表すとき、上記の表現に対して群G1の不変式は次のような交代式となる。
【００２０】
[式１]
INVm＝Σ（Πcij） 
但し、ijは全て異なるm個の添え字であり、Σは全ての(ij)でしかもn >= ij+1 > ij >=1を満足するものであり、m=1〜nである。
式１において、m=1の場合は以下のようになる。
【００２１】
[式２]
INV1=Σci (iは、1〜n) 
式１において、m=2の場合は以下のようになる。
【００２２】
[式３]
INV2=Σci＊cj (i,jは1〜n、i<j) 
式１において、m=nの場合は以下のようになる。
【００２３】
[式４]
INVn=c1＊c2＊c3＊…＊cn 
【００２４】
上記した実施形態の暗号システムにおいて、群G1の不変式保存装置１１及び２１は、これらの代数式のうちいくつかを選択することができるものとする。以下では、式１に示すn個の式を用いる場合について考える。ここで、暗号化対象である平文Zは、長さnの複素数の値の列（Zi）として与えられているとする。そうすると、数学的空間Xの元x生成装置２７が行う演算は、以下の式５に示すciについての方程式を解くことに他ならない。すなわち、式５を満足するベクトル(ci)がxとして求められることになる。
【００２５】
[式５]
Zm＝Σ（Πcij） 
但し、ijは全て異なるm個の添え字であり、Σは、全ての（ij）でしかもｎ>=ij+1> ij>=1を満足するものであり、m=1〜nである。
【００２６】
また、このときに群G1の数学的空間Xへの演算装置２２が行う演算は、群G1の表現を計算することに他ならない。すなわち、式５で求められるベクトル（ci）（上記ではx）に行列を作用させて、新たなベクトル（上記ではz）を得ることに相当する。また、群G1の元g1生成装置２５は、Sn(すなわちG1)のカノ二カルな生成元をランダムに組み合わせることにより、元g1を生成するものであるが、ここでは説明を省略する。
【００２７】
さらに、不変式の値計算装置１５が行う演算は、次の式６の値を求めることに他ならない。式６によって得られた列が暗号文の復号化結果として得られるものであり、もとの平文Zに一致するものである。
【００２８】
[式６]
Σ（Πｚij） 
但し、ijは全て異なるm個の添え字であり、Σは、全ての（ij）でしかもｎ>=ij+1> ij>=1を満足するものであり、m=1〜nである。
【００２９】
また、共通キーaを行列と見なしたとすると、共通キーaの保存装置１４及び２４は行列の保存領域であり、群Gの数学的空間Xへの演算装置が行う演算１３及び２３は、行列の計算に相当する。
【００３０】
尚、本実施例においては、Xを複素数上のn次元ベクトル空間とし、G1を置換群Snとし、Sn(G1)のXへの作用を基底から定義される表現としたが、本発明を実施するにあたってそのように制限されることは全くない。また、共通キーaを行列と見なすことも必須ではない。
【００３１】
以上、本発明の不変式を利用した暗号システムについて、具体的な実施の形態を示して説明したが、本発明はこれらに限定されるものではない。当業者であれば、本発明の要旨を逸脱しない範囲内において、上記各実施形態又は他の実施形態にかかる発明の構成及び機能に様々な変更・改良を加えることが可能である。
【図面の簡単な説明】
【００３２】
【図１】本発明の一実施形態である暗号システムの概略構成を示すブロック図である。
【図２】図１に示す暗号システムにおいて、第２エンティティにおいて平文Zを暗号化し、暗号化した結果であるｚを第１エンティティに送信するまでの処理の流れを示すフローチャートである。
【図３】図１に示す暗号システムにおいて、第１のエンティティにおいて受信した暗号文zを復号化して平文Zを得る処理の流れを示すフローチャートである。
【符号の説明】
【００３３】
１０  第１のエンティティ
１１  群G1の不変式保存装置
１３  数学的空間Xに対する群Gの演算装置
１４  共通キーa保存装置
１５  不変式の値計算装置
１６  送受信装置
２０  第２のエンティティ
２１  群G1の不変式保存装置
２２  数学的空間Xに対する群G1の演算装置
２３  数学的空間Xに対する群Gの演算装置
２４  共通キーa保存装置
２５  群G1の元g1生成装置
２６  送受信装置
２７  数学的空間Xの元x生成装置
【図１】
2006101354.tif 000003
【図２】
2006101354.tif 000004
【図３】
2006101354.tif 000005