耐量子コンピュータ性をもつ鍵共有方式
【課題】従来の鍵共有方式の安全性は、素因数分解問題や乗法群上の離散対数問題の計算量上の困難さに依存するものであり、量子コンピュータが実用化するといずれの問題も多項式時間で解読可能と予想されている。
【解決手段】鍵共有方式の安全性をＮＰ完全問題の１つである高次多変数連立代数方程式の解法の困難さに依存する方式を採用することにより、耐量子コンピュータ性を持つ鍵共有方式を提供する。
【解決手段】鍵共有方式の安全性をＮＰ完全問題の１つである高次多変数連立代数方程式の解法の困難さに依存する方式を採用することにより、耐量子コンピュータ性を持つ鍵共有方式を提供する。
【発明の詳細な説明】
【技術分野】
【０００１】
この発明は高次多変数連立代数方程式を利用した、耐量子コンピュータ性をもつ鍵共有方式に関するものである。
【背景技術】
【０００２】
通信者双方が秘密の鍵を共有する共通鍵暗号方式は、歴史も長く一般にも広く使われているが、その共通の鍵を初めに通信者同士が交換しなければならない。そこで共通鍵の交換に使われるのが、ＲＳＡ暗号に代表される公開鍵暗号系である。ＲＳＡ暗号は素因数分解の計算量的観点からの困難性を根拠にしているが、同じように計算量的困難性を根拠にしている暗号に、Ｄｉｆｆｉｅ−Ｈｅｌｌｍａｎ問題（以下、ＤＨ問題という）（″Ｎｅｗ ｄｉｒｅｃｔｉｏｎｓ ｉｎ ｃｒｙｐｔｏｇｒａｐｈｙ″，Ｗ．Ｄｉｆｆｉｅ ａｎｄ Ｍ．Ｅ．Ｈｅｌｌｍａｎ，ＩＥＥＥ Ｔｒａｎｓａｃｔｉｏｎｓ ｏｎ Ｉｎｆｏｒｍａｔｉｏｎ Ｔｈｅｏｒｙ，ＩＴ−２２：６４４−６５４，１９７６）を利用した公開鍵暗号がある。
【０００３】
西岡は素因数分解問題の困難性やＤＨ問題の困難性を利用した共通鍵配送方法を発表している。西岡方式では、送信者は受信者の公開鍵を用いて送信者側装置内で暗号文を作成し，通信回線を介して受信者側装置に送信し，受信者は秘密鍵を用いて暗号文の復号化を行う公開鍵暗号による暗号通信方法であって，素因数分解問題の困難性を前提に選択平文攻撃に対して一方向であるＲａｂｉｎ暗号と，Ｄｉｆｆｉｅ−Ｈｅｌｌｍａｎ決定問題の困難性を前提に選択平文攻撃に対して強秘匿であるＥｌＧａｍａｌ暗号の双方の安全性の特徴を併せ持つように，暗号化および復号化のための手順を構築している。さらに，共通鍵暗号の鍵配送に使用する目的の下で，真の平文空間を秘密にしながら，平文空間の大きさを小さくする。これにより、より困難な問題を前提に安全性の証明が可能であり，かつ，暗復号化のための計算において効率性の高い処理ができる公開鍵暗号方法とそれを用いた鍵共有方法を提供している。
【先行技術文献】
【特許文献】
【０００４】
【特許文献１】特許出願２０００−５９６６９４ 公開鍵暗号及び鍵共有方法 株式会社日立製作所西岡 玄次 特願平１１−２１２５４、特願平１１−２３９１７７
【非特許文献】
【０００５】
【非特許文献１】Ｗ．Ｄｉｆｆｉｅ ａｎｄ Ｍ．Ｅ．Ｈｅｌｌｍａｎ，″Ｎｅｗ ｄｉｒｅｃｔｉｏｎｓ ｉｎ ｃｒｙｐｔｏｇｒａｐｈｙ″，ＩＥＥＥ Ｔｒａｎｓａｃｔｉｏｎｓ ｏｎ Ｉｎｆｏｒｍａｔｉｏｎ Ｔｈｅｏｒｙ，ＩＴ−２２：６４４−６５４，１９７６
【発明の概要】
【発明が解決しようとする課題】
【０００６】
西岡方式の安全性は、素因数分解問題や乗法群上の離散対数問題の計算量上の困難さに依存することであり、量子コンピュータが実用化するといずれの問題も多項式時間で解読可能と予想されている。
【０００７】
このように西岡方式等、従来の方式は、耐量子コンピュータ性がなく、量子コンピュータが実用化すると多項式時間で解読されてしまうと予想されている。本発明は、安全性をＮＰ完全問題の１つである高次多変数連立代数方程式の解法の困難さに依存する方式を採用することにより、耐量子コンピュータ性を持つ鍵共有方式を提供することを目的とする。
【課題を解決するための手段】
【０００８】
請求項１の発明によれば、システムセンタは奇素数ｑおよび３つの整数［ｄ，ｒ，ｍ］を選び公開する。利用者Ｕは、システム加入時に、秘密鍵［Ａｉ（ｉ＝１，．．，ｍ）］を選ぶ。ここで、Ａｉ（ｉ＝１，．．，ｍ）をＦｑ上の四元数環Ｈ上の任意のｍ個の要素とする。１つの要素ＡｉはＦｑ上の４つの要素から成り立っている四元数であり、全てのＡｉはＦｑ上の四元数環Ｈ上で逆数Ａｉ−１を持つ。利用者Ｕは公開されている３つのシステムパラメータ［ｄ，ｒ，ｍ］と秘密鍵［Ａｉ（ｉ＝１，．．，ｍ）］から、公開鍵である四元数環上の高次関数である暗号化関数Ｆ（Ｘ）を以下のように生成する。
【０００９】
【数１】
【００１０】
利用者Ｕは暗号化関数Ｆ（Ｘ）を展開して、展開式の各係数ｆｊｅ０ｅ１ｅ２ｅ３を求め、その集合｛ｆｊｅ０ｅ１ｅ２ｅ３｝をシステムセンタに利用者Ｕの公開鍵ＰＫとして利用者Ｕの識別情報ＩＤとともに送る。四元数Ｆ（Ｘ）の要素表現形式を（ｆ０，ｆ１，ｆ２，ｆ３）とすると、
【数２】
ここで、
Ｘ＝（ｘ０，ｘ１，ｘ２，ｘ３）∈Ｈ，
ｘｉ∈Ｆｑ（ｉ＝０，．．，３）
であり、また１＋ｒ＋・・・＋ｒｄ＝ｓとして、
ｅ０，ｅ１，ｅ２，ｅ３は非負の整数でｅ０＋ｅ１＋ｅ２＋ｅ３＝ｓを満足する。上式右辺のｆｊｅ０ｅ１ｅ２ｅ３の総数ｎは、
【数３】
となる。
【００１１】
システムパラメータｍの値はシステムセンタにて以下のように決定されている。
【数４】
【００１２】
利用者Ｖは利用者Ｕと利用者Ｖ間の共通鍵Ｋｖ１，Ｋｖ２を以下のように生成する。
利用者Ｖは、四元数環Ｈ上の逆数をもつ任意のｍ個の要素Ｒｉ（ｉ＝１，．．，ｍ）を選ぶ。Ｒｉ（ｉ＝１，．．，ｍ）を利用者Ｖの一時秘密鍵ＴＳＫと呼ぶ。
【００１３】
利用者Ｖは要素Ｒｉ（ｉ＝１，．．，ｍ）を用いて、Ｆｑ上の四元数環上の高次関数である一時暗号化関数Ｔ（Ｘ）を以下のように生成する。
【数５】
【００１４】
利用者ＶはＴ（Ｘ）を展開して、展開式の各係数ｔｊｅ０ｅ１ｅ２ｅ３を求め、その集合｛ｔｊｅ０ｅ１ｅ２ｅ３｝を利用者Ｖの一時公開鍵ＴＫとする。
四元数Ｔ（Ｘ）の要素表現形式を（ｔ０，ｔ１，ｔ２，ｔ３）とすると
【数６】
ここで、ｅ０，ｅ１，ｅ２，ｅ３は非負の整数でｅ０＋ｅ１＋ｅ２＋ｅ３＝ｓを満足する。上記ｔｊｅ０ｅ１ｅ２ｅ３の総数ｎは、
【数７】
となる。
【００１５】
利用者Ｖは｛ｔｊｅ０ｅ１ｅ２ｅ３｝を利用者Ｕに送る。
【００１６】
利用者Ｖはシステムセンタの公開鍵管理簿から入手した利用者Ｕの公開鍵｛ｆｊｅ０ｅ１ｅ２ｅ３｝と利用者Ｖの一時秘密鍵Ｒｉ（ｉ＝１，．．，ｍ）から共通鍵Ｋｖ１，Ｋｖ２を以下の手順で生成する。
【数８】
ここで、
Ｒｉ＝（Ｒｉ０，Ｒｉ１，Ｒｉ２，Ｒｉ３），（ｉ＝０，．．，ｍ）
である。
ｅ０，ｅ１，ｅ２，ｅ３は非負整数でｅ０＋・・・＋ｅ３＝ｓを満足する．
ＲｒｉとＴｖ２ｉｊを以下に定める。
【数９】
ｅ０，ｅ１，ｅ２，ｅ３は非負整数でｅ０＋・・・＋ｅ３＝ｓを満足する．
Ｋｖ２を以下の式で与える。
【数１０】
【００１７】
一方、利用者Ｕは以下のように共通鍵Ｋｕ１，Ｋｕ２を生成する。
まず、Ｋｕ１，Ｋｕ２の要素表現を以下に定める。
Ｋｕ１＝（Ｋｕ１０，Ｋｕ１１，Ｋｕ１２，Ｋｕ１３）
Ｋｕ２＝（Ｋｕ２０，Ｋｕ２１，Ｋｕ２２，Ｋｕ２３）．
【００１８】
Ａｒｉの要素表現を用いてＴｕ１ｉｊを計算する。
【数１１】
ｅ０，ｅ１，ｅ２，ｅ３は非負整数でｅ０＋・・・＋ｅ３＝ｓを満足する．
Ｔｕ１ｉｊを用いて、四元数演算を実行してＫｕ１を求める。
【数１２】
【００１９】
Ｋｕ２ｊは［数６］のｔｊの式のｘ０，ｘ１，ｘ２，ｘ３にＡｉ０，Ａｉ２，Ａｉ３をそれぞれ代入して計算できる。
【数１３】
ｅ０，ｅ１，ｅ２，ｅ３は非負整数でｅ０＋・・・＋ｅ３＝ｓを満足する．
【００２０】
Ｋｕ１＝Ｋｖ１，
Ｋｕ２＝Ｋｖ２
であることを以下に示す。
【数１４】
同様にして
Ｋｕ２＝Ｋｖ２．
が示せる。この証明は、発明者の論文（Ｍａｓａｈｉｒｏ Ｙａｇｉｓａｗａ，″Ｋｅｙ Ａｇｒｅｅｍｅｎｔ Ｐｒｏｔｏｃｏｌｓ Ｂａｓｅｄ ｏｎ Ｍｕｌｔｉｖａｒｉａｔｅ Ａｌｇｅｂｒａｉｃ Ｅｑｕａｔｉｏｎｓ ｏｎ Ｑｕａｔｅｒｎｉｏｎ Ｒｉｎｇ″，Ｃｒｙｐｔｏｌｏｇｙ ｅＰｒｉｎｔ Ａｒｃｈｉｖｅ，Ｒｅｐｏｒｔ２０１０／３７７，（２０１０−０７）．）に示されている。
【００２１】
利用者Ｕと利用者Ｖの共通鍵は［Ｋｕ１，Ｋｕ２］となる。
【００２２】
公開される集合｛ｆｊｅ０ｅ１ｅ２ｅ３｝の値から秘密鍵［Ａｉ（ｉ＝１，．．，ｍ）］を求めることが高次多変数連立代数方程式の解法に帰結される。この解法問題はＮＰ完全問題の一つである。
【００２３】
請求項２の発明によれば、システムセンタは奇素数ｑおよび２つの整数［ｄ，ｍ］を選び公開する。利用者Ｕは、システム加入時に、秘密鍵［Ａｉｊ（ｉ＝１，．．，ｍ；ｊ＝１，．．，ｄ）］を選ぶ。ここで、Ａｉｊ（ｉ＝１，．．，ｍ；ｊ＝１，．．，ｄ）をＦｑ上の四元数環Ｈ上の任意のｍｄ個の要素とする。１つの要素ＡｉｊはＦｑ上の４つの要素から成り立っている四元数である。利用者Ａは公開されている３つのシステムパラメータ［ｑ，ｄ，ｍ］と秘密鍵［Ａｉｊ（ｉ＝１，．．，ｍ；ｊ＝１，．．，ｄ）］から、公開鍵である四元数環上の高次関数である暗号化関数Ｆ（Ｘ）を以下のように生成する。
【数１５】
【００２４】
利用者Ｕは暗号化関数Ｆ（Ｘ）を展開して、展開式の各係数ｆｊｅ１０．．ｅｄ３を求め、その集合｛ｆｊｅ１０．．ｅｄ３｝をシステムセンタに利用者Ｕの公開鍵として利用者Ｕの識別情報ＩＤとともに送る。四元数Ｆ（Ｘ）の展開表現を（ｆ０，ｆ１，ｆ２，ｆ３）とすると、
【数１６】
ｅｉｊ∈｛０，１｝（ｉ＝１，．．，ｄ；ｊ＝０，．．，３）は
ｅｉ０＋．．＋ｅｉ３＝１（ｉ＝１，．．，ｄ）．
であり、
ｅ１０＋．．＋ｅ１３＋・・・＋ｅｄ０＋．．＋ｅｄ３＝ｄ
を満足する。｛ｆｊｅ１０．．ｅｄ３｝はｆｊｅ１０．．ｅｄ３．全てを含む集合とする。ｆｊｅ１０．．ｅｄ３の個数はｎで与えられる。
【数１７】
【００２５】
システムパラメータｍの値はシステムセンタにて以下のように決定されている。
【数１８】
【００２６】
利用者Ｖは利用者Ｕと利用者Ｖ間の共通鍵Ｋｖ１，Ｋｖ２を以下のように生成する。
利用者Ｖは、四元数環Ｈのｍｄ個の任意の要素Ｂｉｊ（ｉ＝１，．．，ｍ；ｊ＝１，．．，ｄ）を選ぶ。Ｂｉｊ（ｉ＝１，．．，ｍ）を利用者Ｖの一時秘密鍵ＴＳＫと呼ぶ。
【００２７】
利用者Ｖは要素Ｂｉｊ（ｉ＝１，．．，ｍ；ｊ＝１，．．，ｄ）を用いて、Ｆｑ上の四元数環上の高次関数である一時暗号化関数Ｔ（Ｘ１，．．，Ｘｄ）を以下のように生成する。
【数１９】
【００２８】
利用者ＶはＴ（Ｘ）を展開して、展開式の各係数ｔｊｅ１０．．ｅｄ３を求め、その集合｛ｔｊｅ１０．．ｅｄ３｝である一時公開鍵ＴＫを求める。各係数ｔｊｅ１０．．ｅｄ３は以下のような形をしている。四元数Ｔ（Ｘ）の要素表現形式を（ｔ０，ｔ１，ｔ２，ｔ３）とすると
【数２０】
ここで、ｅｉｊ∈｛０，１｝（ｉ＝１，．．，ｄ；ｊ＝０，．．，３）は
ｅｉ０＋．．＋ｅｉ３＝１（ｉ＝１，．．，ｄ）．
であり、
ｅ１０＋．．＋ｅ１３＋・・・＋ｅｄ０＋．．＋ｅｄ３＝ｄ
を満足する。｛ｔｊｅ１０．．ｅｄ３｝はｔｊｅ１０．．ｅｄ３．全てを含む集合とする。ｔｊｅ１０．．ｅｄ３の個数はｎで与えられる。
【数２１】
【００２９】
利用者Ｖは｛ｔｊｅ１０．．ｅｄ３｝を利用者Ｕに送る。
【００３０】
利用者Ｖはシステムセンタの公開鍵管理簿から入手した利用者Ｕの公開鍵｛ｆｊｅ１０．．ｅｄ３｝と利用者Ｖの一時秘密鍵Ｂｉｊ（ｉ＝１，．．，ｍ；ｊ＝１，．．，ｄ）から共通鍵Ｋｖ１，Ｋｖ２を以下の手順で生成する。
【数２２】
したがって、Ｋｖ１ｊ（ｊ＝０，．．，３）は以下の形をしている。
（Ｖｉｊ０，Ｖｉｊ１，Ｖｉｊ２，Ｖｉｊ３）＝Ｂｉｊ（ｉ＝１，．．，ｍ；ｊ＝１，．．，ｄ），
ｅｉｊ∈｛０，１｝（ｉ＝１，．．，ｄ；ｊ＝０，．．，３）は
ｅｉ０＋・・・＋ｅｉ３＝１（ｉ＝１，．．，ｄ）
であり、
ｅ１０＋．．＋ｅ１３・・・＋ｅｄ０＋．．＋ｅｄ３＝ｄ
を満足する。
【数２３】
したがって、Ｋｖ２ｊ（ｊ＝０，．．，３）は以下の形をしている。
ここで、
（Ｖｉｊ０，Ｖｉｊ１，Ｖｉｊ２，Ｖｉｊ３）＝Ｂｉｊ，（ｉ＝１，．．，ｍ；ｊ＝１，．．，ｄ）．
係数ｆ’ｊｅ１０．．ｅｄ３はＦｑの要素である。
ｅｉｊ∈｛０．１｝（ｉ＝１，．．，ｄ；ｊ＝０，．．，３）は
ｅｉ０＋・・・＋ｅｉ３＝１（ｉ＝１，．．，ｄ）
であり、
ｅ１０＋．．＋ｅ１３＋・・・＋ｅｄ０＋．．＋ｅｄ３＝ｄ
を満足する。
【００３１】
利用者Ｕは以下のように共通鍵Ｋｕ１，Ｋｕ２を計算する。
まず、Ｋｕ１，Ｋｕ２の要素表現を以下に定める。
【数２４】
したがって、Ｋｖ１ｊ（ｊ＝０，．．，３）は以下の形をしている。
ここで、（Ｕｉｊ０，Ｕｉｊ１，Ｕｉｊ２，Ｕｉｊ３）＝Ａｉｊ，（ｉ＝１，．．，ｍ；ｊ＝１，．．，ｄ），
係数ｔ’ｊｅ１０．．ｅｄ３はＦｑの要素である。
ｅｉｊ∈｛０，１｝（ｉ＝１，．．，ｄ；ｊ＝０，．．，３）は
ｅｉ０＋・・・＋ｅｉ３＝１（ｉ＝１，．．，ｄ）
であり、
ｅ１０＋．．＋ｅ１３＋・・・＋ｅｄ０＋．．＋ｅｄ３＝ｄ
を満足する。
【数２５】
したがって、Ｋｖ２ｊ（ｊ＝０，．．，３）は以下の形をしている。
ここで、（Ｕｉｊ０，Ｕｉｊ１，Ｕｉｊ２，Ｕｉｊ３）＝Ａｉｊ，（ｉ＝１，．．，ｍ；ｊ＝１，．．，ｄ），
ｅｉｊ∈｛０，１｝（ｉ＝１，．．，ｄ；ｊ＝０，．．，３）は
ｅｉ０＋・・・＋ｅｉ３＝１（ｉ＝１，．．，ｄ）
であり、
ｅ１０＋．．＋ｅ１３＋・・・＋ｅｄ０＋．．ｅｄ３＝ｄ
を満足する。
【００３２】
［数２２］と［数２４］から
Ｋｕ１＝Ｋｖ１，
［数２３］と［数２５］から
Ｋｕ２＝Ｋｖ２．
であることがわかる。
利用者Ｕと利用者Ｖの共通鍵ＫはＫ＝［Ｋｕ１，Ｋｕ２］＝［Ｋｖ１，Ｋｖ２］で与えられる。
【００３３】
公開される利用者Ｕの公開鍵｛ｆｊｅ１０．．ｅｄ３｝の値から利用者Ｕの秘密鍵［Ａｉｊ（ｉ＝１，．．，ｍ；ｊ＝１，．．，ｄ）］を求めることは高次多変数連立代数方程式の解法に帰結される。この解法問題はＮＰ完全問題の一つである。
【００３４】
請求項３の発明によれば、システムセンタは奇素数ｑおよび２つの整数［ｄ，ｍ］を選び公開する。利用者Ｕは、システム加入時に、利用者Ｕの秘密鍵ＳＫ＝［Ａｉ＝（ａｉ０，ａｉ１，ａｉ２，ａｉ３）（ｉ＝１，．．，ｍ）］を選ぶ。ここで、Ａｉ（ｉ＝１，．．，ｍ）をＦｑ上の四元数環Ｈ上の任意のｍ個の要素とする。１つの要素ＡｉはＦｑ上の４つの要素から成り立っている四元数である。利用者Ｕは公開されている３つのシステムパラメータ［ｑ，ｄ，ｍ］と秘密鍵ＳＫから、公開鍵である四元数環上の高次関数である暗号化関数Ｆ（Ｘ）を以下のように生成する。
【数２６】
【００３５】
利用者Ｕは暗号化関数Ｆ（Ｘ）を展開して、展開式の各係数ｆｊｅ０ｅ１ｅ２ｅ３を求め、その集合｛ｆｊｅ０ｅ１ｅ２ｅ３｝をシステムセンタに利用者Ｕの公開鍵ＰＫとして利用者Ｕの識別情報ＩＤとともに送る。四元数Ｆ（Ｘ）の要素表現形式を（ｆ０，ｆ１，ｆ２，ｆ３）とすると、
【数２７】
ここで、ｅ０，ｅ１，ｅ２，ｅ３は非負の整数でｅ０＋ｅ１＋ｅ２＋ｅ３＝ｄを満足する。上式右辺のｆｊｅ０ｅ１ｅ２ｅ３（ｊ＝０，１，２，３）の総数ｎは、
【数２８】
となる。
｛ｆｊｅ０ｅ１ｅ２ｅ３｝はｆｊｅ０ｅ１ｅ２ｅ３全てを含む集合とする。
【００３６】
システムパラメータｍの値はシステムセンタにて以下のように決定されている。
【数２９】
【００３７】
利用者Ｖは利用者Ｕと利用者Ｖ間の共通鍵Ｋｖを以下のように生成する。
利用者Ｖは、四元数環Ｈのｍ個の任意の要素Ｂｉ＝（ｂｉ０，ｂｉ１，ｂｉ２，ｂｉ３）（ｉ＝１，．．，ｍ）を選ぶ。Ｂｉ（ｉ＝１，．．，ｍ）を利用者Ｖの一時秘密鍵ＴＳＫと呼ぶ。
【００３８】
利用者Ｖは要素Ｂｉ（ｉ＝１，．．，ｍ）を用いて、Ｆｑ上の四元数環上の高次関数である一時暗号化関数Ｔ（Ｘ）を以下のように生成する。
【数３０】
【００３９】
利用者ＶはＴ（Ｘ）を展開して、展開式の各係数ｔｊｅ０ｅ１ｅ２ｅ３を求め、その集合｛ｔｊｅ０ｅ１ｅ２ｅ３｝を求める。
四元数Ｔ（Ｘ）の要素表現形式を（ｔ０，ｔ１，ｔ２，ｔ３）とすると
【数３１】
【００４０】
ここで、ｅ０，ｅ１，ｅ２，ｅ３は非負の整数でｅ０＋ｅ１＋ｅ２＋ｅ３＝ｄを満足する。上記ｔｊｅ０ｅ１ｅ２ｅ３総数ｎは、
【数３２】
となる。
｛ｔｊｅ０ｅ１ｅ２ｅ３｝はｔｊｅ０ｅ１ｅ２ｅ３全てを含む集合であり、利用者Ｖの一時公開鍵ＴＫと呼ぶ。
【００４１】
利用者Ｖは｛ｔｊｅ０ｅ１ｅ２ｅ３｝を利用者Ｕに送る。
【００４２】
利用者Ｖはシステムセンタの公開鍵管理簿から入手した利用者Ｕの公開鍵ＰＫと利用者Ｖの一時秘密鍵Ｂｉ（ｉ＝１，．．，ｍ）から共通鍵Ｋｖを以下の手順で生成する。
【数３３】
Ｋｖｊ（ｊ＝０，１，２，３）は以下で与えられる。
【数３４】
ｅ０，ｅ１，ｅ２，ｅ３は非負整数でｅ０＋・・・＋ｅ３＝ｄを満足する．
【００４３】
利用者Ｕは以下のように共通鍵Ｋｕを計算する。まず、Ｋｕの要素表現を以下に定める。
【数３５】
【００４４】
Ｋｕｉ（ｉ＝１，０，１，２，３）は以下で与えられる。
【数３６】
ｅ０，ｅ１，ｅ２，ｅ３は非負整数でｅ０＋・・・＋ｅ３＝ｄを満足する．
【００４５】
［数３３］、［数３５］から
Ｋｕ＝Ｋｖ，
であることが分かる。利用者Ｕと利用者Ｖの共通鍵はＫｕまたはＫｖである。
【００４６】
公開される利用者Ｕの公開鍵｛ｆｊｅ０ｅ１ｅ２ｅ３｝の値から利用者Ｕの秘密鍵［Ａｉ（ｉ＝１，．．，ｍ）］を求めることは高次多変数連立代数方程式の解法に帰結される。この解法問題はＮＰ完全問題の一つである。
【００４７】
請求項４の発明によれば、システムセンタは素数ｑおよび３つの整数［ｄ，ｍ，ｎ］を選び公開する。
利用者Ｕは、システム加入時に、利用者Ｕの秘密鍵ＳＫ＝［ｋｉ，ａｉｉ（ｉ＝１，．．，ｍ；ｊ＝１，．．，ｎ）］を選ぶ。ここで、，ｋｉａｉｊ（ｉ＝１，．．，ｍ；ｊ＝１，．．，ｎ）をＦｑ上の任意の要素とする。利用者Ｕは公開されている３つのシステムパラメータ［ｑ，ｄ，ｍ］と利用者Ｕの秘密鍵ＳＫから、公開鍵であるｎ変数多項式環Ｆｑ［ｘ１，．．，ｘｎ］上の暗号化関数Ｆ（Ｘ）を以下のように生成する。
【数３７】
ここで、
Ａｉ（Ｘ）＝ａｉ１Ｘ１＋・・・＋ａｉｎＸｎ，（ｉ＝１，．．，ｍ）
変数；Ｘ＝（Ｘ１，．．，Ｘｎ）Ｔ∈Ｆｑ［ｘ１，．．，ｘｎ］ｎ
【００４８】
利用者Ｕは暗号化関数Ｆ（Ｘ）を展開して、展開式の各係数ｆｊｅ０．．ｅｎを求め、その集合｛ｆｊｅ０．．ｅｎ｝をシステムセンタに利用者Ｕの公開鍵ＰＫとして利用者Ｕの識別情報ＩＤとともに送る。各係数もｆｊｅ０．．ｅｎは以下のような形をしている。
【数３８】
ここで、ｅ０，．．，ｅｎは非負の整数でｅｉ１＋．．＋ｅｉｎ＝ｉを満足する。上式右辺のｆｉｅｉ１．．ｅｉｎ数Ｎは、
となる。
｛ｆｉｅｉ１．．ｅｉｎ｝はｆｉｅｉ１．．ｅｉｎ全てを含む集合とする。
【００４９】
システムパラメータｍの値はシステムセンタにて以下のように決定されている。
【数３９】
【００５０】
利用者Ｖは利用者Ｕと利用者Ｖ間の共通鍵Ｋｖ（Ｘ）を以下のように生成する。
利用者Ｖは、ｈｉ，ｂｉｊ∈Ｆｑ，（ｉ＝１，．．，ｍ；ｊ＝１，．．，ｎ）を任意に選ぶ。［ｈｉ，ｂｉｊ∈Ｆｑ，（ｉ＝１，．．，ｍ；ｊ＝１，．．，ｎ）］を利用者Ｖの一時秘密鍵ＴＳＫと呼ぶ。
【００５１】
利用者Ｖは［ｈｉ，ｂｉｊ∈Ｆｑ，（ｉ＝１，．．，ｍ；ｊ＝１，．．，ｎ）］を用いて、Ｆｑ上の一時暗号化関数Ｔ（Ｘ）を以下のように生成する。
【数４０】
ここで、
Ｂｉ（Ｘ）＝ｂｉ１ｘ１＋・・・＋ｂｉｎｘｎ，（ｉ＝１，．．，ｍ）．
【００５２】
利用者ＶはＴ（Ｘ）を展開して、展開式の各係数ｔｉｅｉ１．．ｅｉｎを求め、その集合｛ｔｉｅｉ１．．ｅｉｎ｝を求める。
【数４１】
【００５３】
ここで、ｅ０，．．，ｅｎは非負の整数でｅｉ１＋．．＋ｅｉｎ＝ｉを満足する。ｔｉｅｉ１．．ｅｉｎの総数Ｎ’は、Ｎに等しい。
｛ｔｉｅｉ１．．ｅｉｎ｝はｔｉｅｉ１．．ｅｉｎをすべて含む集合であり、利用者Ｖの一時公開鍵ＴＫと呼ぶ。
【００５４】
利用者Ｖは｛ｔｉｅｉ１．．ｅｉｎ｝を利用者Ｕに送る。
【００５５】
利用者Ｖはシステムセンタの公開鍵管理簿から入手した利用者Ｕの公開鍵ＰＫと利用者Ｖの一時秘密鍵ＴＳＫから共通鍵Ｋｖを以下の手順で生成する。
【数４２】
［数３７］から
【数４３】
また、［数３８］から
【数４４】
が得られる。
ここで、ｅ０，．．，ｅｎは非負の整数でｅｉ１＋．．＋ｅｉｎ＝ｉ（ｉ＝１，．．，ｄ）を満足する。
【００５６】
一方、利用者Ｕは以下のように共通鍵Ｋｕを計算する。
【数４５】
［数４０］から
【数４６】
また、［数４１］から
【数４７】
が得られる。
ここで、ｅ０，．．，ｅｎは非負の整数でｅｉ１＋．．＋ｅｉｎ＝ｉ（ｉ＝１，．．，ｄ）を満足する。
【００５７】
［数４３］、［数４６］から
【数４８】
であることが分かる。利用者Ｕと利用者Ｖの共通鍵はＫｕ（Ｘ）またはＫｖ（Ｘ）である。
【００５８】
公開される利用者Ｕの公開鍵｛ｆｉｅｉ１．．ｅｉｎ｝の値から秘密鍵［ｈｉ，ｂｉ１∈Ｆｑ，（ｉ＝１，．．，ｍ；ｊ＝１，．．，ｎ）］を求めることは高次多変数連立代数方程式の解法に帰結される。この解法問題はＮＰ完全問題の一つである。
【００５９】
ところで、西岡方式の安全性は、乗法群や楕円曲線上の離散対数問題の困難さに依存する。
【００６０】
一方、本発明方式の安全性は、有限体Ｆｑ上の高次多変数連立代数方程式の解法の困難さに依存する。次数を大きくし、変数の数を多くすることにより、耐量子コンピュータ性をもつ鍵共有方式である。
【発明の効果】
【００６１】
西岡方式の安全性は、乗法群や楕円曲線上の離散対数問題の困難さに依存するので、量子コンピュータが出現すると、多項式時間で解読可能となる恐れがある。
【００６２】
一方、請求項１、請求項２、請求項３および請求項４の発明において、有限体Ｆｑ上の高次多変数連立代数方程式の解法の困難さに依存する鍵共有方式では、高次多変数連立代数方程式の解法がＮＰ完全問題の１つとなるので、量子コンピュータに耐えうる鍵共有方式を提供できる。
【００６３】
従ってこの発明によれば安全性を高く保持するものとなる。
【００６４】
なお、本発明は、上記において説明した実施形態に限定されるものではなく、その主旨を逸脱しない範囲において種々変更可能であり、それらも本発明の範囲内に包含されるものであることは言うまでもない。
【図面の簡単な説明】
【００６５】
【図１】本発明に係る鍵共有方法の実施形態例を示す概念図である。
【図２】図１中の利用者Ｕの通信装置の一例のブロック図である。
【図３】図１中の利用者Ｖの通信装置の一例のブロック図である。
【図４】図１中のシステムセンタの一例のブロック図である。
【符号の説明】
【００６６】
１００…システムセンタ
２００…利用者Ｕの通信装置
３００…利用者Ｖの通信装置
４００…安全でない通信路
１０１…システムセンタ公開鍵管理簿
２０１…乱数発生器
２０２…暗号化関数Ｆ（Ｘ）
２０３…共通鍵生成器
２０４…記憶装置
２０５…結合器
３０１…乱数発生器
３０２…一時暗号化関数Ｔ（Ｘ）
３０３…共通鍵生成器
３０４…記憶装置
【発明を実施するための形態】
【実施例】
【００６７】
請求項１の発明の一実施例について説明する。図１はこの発明の第１、第２、第３、第４の実施形態例を示す概念図である。利用者Ｕが事前にシステムセンタに登録しておいた利用者Ｕの公開鍵と利用者Ｖが発生する乱数をもとに生成する利用者Ｖの一時公開鍵を用いて、利用者Ｕと利用者Ｖがそれぞれ共通鍵を生成する場合を示している。
【００６８】
図２に利用者Ｕの通信装置の一例を示す。まず、システムに加入した利用者Ｕは、システムセンタ１００から入手したシステムパラメータと乱数発生器２０１から発生させた乱数である秘密鍵ＳＫから暗号化関数Ｆ（Ｘ）を作成し、Ｆ（Ｘ）を展開してその係数の集合である公開鍵ＰＫを生成し、公開鍵ＰＫを利用者Ｕの識別情報ＩＤと結合器にて対にして、システムセンタ１００の公開鍵管理簿１０１に登録する。
【００６９】
次に、利用者Ｕが共通鍵Ｋを生成する手順について説明する。利用者Ｕはシステムセンタ１００から入手したシステムパラメータと利用者Ｕの秘密鍵ＳＫと利用者Ｖから受信した利用者Ｖの一時公開鍵ＴＫから共通鍵生成器により共通鍵Ｋｕを生成する。
【００７０】
図３に利用者Ｖの通信装置を示す。利用者Ｖは乱数生成器３０１を用いて乱数である一時秘密鍵ＴＳＫを発生し、一時秘密鍵ＴＳＫとシステムセンタ１００から入手したシステムパラメータを用いて一時暗号関数Ｔ（Ｘ）を作成し、Ｔ（Ｘ）を展開して、その係数の集合である一時公開鍵ＴＫとを利用者Ｕに送信する。利用者Ｖはシステムセンタにアクセスして利用者Ｕの公開鍵ＰＫを入手して、利用者Ｖの一時秘密鍵ＴＳＫと利用者Ｕの公開鍵ＰＫから共通鍵Ｋｖを生成する。
【００７１】
図４にシステムセンタの一例を示す。
まず、システムセンタはシステムパラメータを公開する。次に利用者Ｕの公開鍵ＰＫとＩＤを受信して公開鍵管理簿に登録し公開する。
【００７２】
なお、本発明は、上記において説明した実施形態に限定されるものではなく、その主旨を逸脱しない範囲において種々変更可能であり、それらも本発明の範囲内に包含されるものであることは言うまでもない。
【産業上の利用可能性】
【００７３】
この発明は通信者同士がお互いに同一の秘密情報を持たずに共通鍵を確保できる鍵共有方式に関し、高次多変数連立代数方程式を利用して、特に安全性が高く、耐量子コンピュータ性をもつ鍵共有方式を提供するものである。
【技術分野】
【０００１】
この発明は高次多変数連立代数方程式を利用した、耐量子コンピュータ性をもつ鍵共有方式に関するものである。
【背景技術】
【０００２】
通信者双方が秘密の鍵を共有する共通鍵暗号方式は、歴史も長く一般にも広く使われているが、その共通の鍵を初めに通信者同士が交換しなければならない。そこで共通鍵の交換に使われるのが、ＲＳＡ暗号に代表される公開鍵暗号系である。ＲＳＡ暗号は素因数分解の計算量的観点からの困難性を根拠にしているが、同じように計算量的困難性を根拠にしている暗号に、Ｄｉｆｆｉｅ−Ｈｅｌｌｍａｎ問題（以下、ＤＨ問題という）（″Ｎｅｗ ｄｉｒｅｃｔｉｏｎｓ ｉｎ ｃｒｙｐｔｏｇｒａｐｈｙ″，Ｗ．Ｄｉｆｆｉｅ ａｎｄ Ｍ．Ｅ．Ｈｅｌｌｍａｎ，ＩＥＥＥ Ｔｒａｎｓａｃｔｉｏｎｓ ｏｎ Ｉｎｆｏｒｍａｔｉｏｎ Ｔｈｅｏｒｙ，ＩＴ−２２：６４４−６５４，１９７６）を利用した公開鍵暗号がある。
【０００３】
西岡は素因数分解問題の困難性やＤＨ問題の困難性を利用した共通鍵配送方法を発表している。西岡方式では、送信者は受信者の公開鍵を用いて送信者側装置内で暗号文を作成し，通信回線を介して受信者側装置に送信し，受信者は秘密鍵を用いて暗号文の復号化を行う公開鍵暗号による暗号通信方法であって，素因数分解問題の困難性を前提に選択平文攻撃に対して一方向であるＲａｂｉｎ暗号と，Ｄｉｆｆｉｅ−Ｈｅｌｌｍａｎ決定問題の困難性を前提に選択平文攻撃に対して強秘匿であるＥｌＧａｍａｌ暗号の双方の安全性の特徴を併せ持つように，暗号化および復号化のための手順を構築している。さらに，共通鍵暗号の鍵配送に使用する目的の下で，真の平文空間を秘密にしながら，平文空間の大きさを小さくする。これにより、より困難な問題を前提に安全性の証明が可能であり，かつ，暗復号化のための計算において効率性の高い処理ができる公開鍵暗号方法とそれを用いた鍵共有方法を提供している。
【先行技術文献】
【特許文献】
【０００４】
【特許文献１】特許出願２０００−５９６６９４ 公開鍵暗号及び鍵共有方法 株式会社日立製作所西岡 玄次 特願平１１−２１２５４、特願平１１−２３９１７７
【非特許文献】
【０００５】
【非特許文献１】Ｗ．Ｄｉｆｆｉｅ ａｎｄ Ｍ．Ｅ．Ｈｅｌｌｍａｎ，″Ｎｅｗ ｄｉｒｅｃｔｉｏｎｓ ｉｎ ｃｒｙｐｔｏｇｒａｐｈｙ″，ＩＥＥＥ Ｔｒａｎｓａｃｔｉｏｎｓ ｏｎ Ｉｎｆｏｒｍａｔｉｏｎ Ｔｈｅｏｒｙ，ＩＴ−２２：６４４−６５４，１９７６
【発明の概要】
【発明が解決しようとする課題】
【０００６】
西岡方式の安全性は、素因数分解問題や乗法群上の離散対数問題の計算量上の困難さに依存することであり、量子コンピュータが実用化するといずれの問題も多項式時間で解読可能と予想されている。
【０００７】
このように西岡方式等、従来の方式は、耐量子コンピュータ性がなく、量子コンピュータが実用化すると多項式時間で解読されてしまうと予想されている。本発明は、安全性をＮＰ完全問題の１つである高次多変数連立代数方程式の解法の困難さに依存する方式を採用することにより、耐量子コンピュータ性を持つ鍵共有方式を提供することを目的とする。
【課題を解決するための手段】
【０００８】
請求項１の発明によれば、システムセンタは奇素数ｑおよび３つの整数［ｄ，ｒ，ｍ］を選び公開する。利用者Ｕは、システム加入時に、秘密鍵［Ａｉ（ｉ＝１，．．，ｍ）］を選ぶ。ここで、Ａｉ（ｉ＝１，．．，ｍ）をＦｑ上の四元数環Ｈ上の任意のｍ個の要素とする。１つの要素ＡｉはＦｑ上の４つの要素から成り立っている四元数であり、全てのＡｉはＦｑ上の四元数環Ｈ上で逆数Ａｉ−１を持つ。利用者Ｕは公開されている３つのシステムパラメータ［ｄ，ｒ，ｍ］と秘密鍵［Ａｉ（ｉ＝１，．．，ｍ）］から、公開鍵である四元数環上の高次関数である暗号化関数Ｆ（Ｘ）を以下のように生成する。
【０００９】
【数１】
【００１０】
利用者Ｕは暗号化関数Ｆ（Ｘ）を展開して、展開式の各係数ｆｊｅ０ｅ１ｅ２ｅ３を求め、その集合｛ｆｊｅ０ｅ１ｅ２ｅ３｝をシステムセンタに利用者Ｕの公開鍵ＰＫとして利用者Ｕの識別情報ＩＤとともに送る。四元数Ｆ（Ｘ）の要素表現形式を（ｆ０，ｆ１，ｆ２，ｆ３）とすると、
【数２】
ここで、
Ｘ＝（ｘ０，ｘ１，ｘ２，ｘ３）∈Ｈ，
ｘｉ∈Ｆｑ（ｉ＝０，．．，３）
であり、また１＋ｒ＋・・・＋ｒｄ＝ｓとして、
ｅ０，ｅ１，ｅ２，ｅ３は非負の整数でｅ０＋ｅ１＋ｅ２＋ｅ３＝ｓを満足する。上式右辺のｆｊｅ０ｅ１ｅ２ｅ３の総数ｎは、
【数３】
となる。
【００１１】
システムパラメータｍの値はシステムセンタにて以下のように決定されている。
【数４】
【００１２】
利用者Ｖは利用者Ｕと利用者Ｖ間の共通鍵Ｋｖ１，Ｋｖ２を以下のように生成する。
利用者Ｖは、四元数環Ｈ上の逆数をもつ任意のｍ個の要素Ｒｉ（ｉ＝１，．．，ｍ）を選ぶ。Ｒｉ（ｉ＝１，．．，ｍ）を利用者Ｖの一時秘密鍵ＴＳＫと呼ぶ。
【００１３】
利用者Ｖは要素Ｒｉ（ｉ＝１，．．，ｍ）を用いて、Ｆｑ上の四元数環上の高次関数である一時暗号化関数Ｔ（Ｘ）を以下のように生成する。
【数５】
【００１４】
利用者ＶはＴ（Ｘ）を展開して、展開式の各係数ｔｊｅ０ｅ１ｅ２ｅ３を求め、その集合｛ｔｊｅ０ｅ１ｅ２ｅ３｝を利用者Ｖの一時公開鍵ＴＫとする。
四元数Ｔ（Ｘ）の要素表現形式を（ｔ０，ｔ１，ｔ２，ｔ３）とすると
【数６】
ここで、ｅ０，ｅ１，ｅ２，ｅ３は非負の整数でｅ０＋ｅ１＋ｅ２＋ｅ３＝ｓを満足する。上記ｔｊｅ０ｅ１ｅ２ｅ３の総数ｎは、
【数７】
となる。
【００１５】
利用者Ｖは｛ｔｊｅ０ｅ１ｅ２ｅ３｝を利用者Ｕに送る。
【００１６】
利用者Ｖはシステムセンタの公開鍵管理簿から入手した利用者Ｕの公開鍵｛ｆｊｅ０ｅ１ｅ２ｅ３｝と利用者Ｖの一時秘密鍵Ｒｉ（ｉ＝１，．．，ｍ）から共通鍵Ｋｖ１，Ｋｖ２を以下の手順で生成する。
【数８】
ここで、
Ｒｉ＝（Ｒｉ０，Ｒｉ１，Ｒｉ２，Ｒｉ３），（ｉ＝０，．．，ｍ）
である。
ｅ０，ｅ１，ｅ２，ｅ３は非負整数でｅ０＋・・・＋ｅ３＝ｓを満足する．
ＲｒｉとＴｖ２ｉｊを以下に定める。
【数９】
ｅ０，ｅ１，ｅ２，ｅ３は非負整数でｅ０＋・・・＋ｅ３＝ｓを満足する．
Ｋｖ２を以下の式で与える。
【数１０】
【００１７】
一方、利用者Ｕは以下のように共通鍵Ｋｕ１，Ｋｕ２を生成する。
まず、Ｋｕ１，Ｋｕ２の要素表現を以下に定める。
Ｋｕ１＝（Ｋｕ１０，Ｋｕ１１，Ｋｕ１２，Ｋｕ１３）
Ｋｕ２＝（Ｋｕ２０，Ｋｕ２１，Ｋｕ２２，Ｋｕ２３）．
【００１８】
Ａｒｉの要素表現を用いてＴｕ１ｉｊを計算する。
【数１１】
ｅ０，ｅ１，ｅ２，ｅ３は非負整数でｅ０＋・・・＋ｅ３＝ｓを満足する．
Ｔｕ１ｉｊを用いて、四元数演算を実行してＫｕ１を求める。
【数１２】
【００１９】
Ｋｕ２ｊは［数６］のｔｊの式のｘ０，ｘ１，ｘ２，ｘ３にＡｉ０，Ａｉ２，Ａｉ３をそれぞれ代入して計算できる。
【数１３】
ｅ０，ｅ１，ｅ２，ｅ３は非負整数でｅ０＋・・・＋ｅ３＝ｓを満足する．
【００２０】
Ｋｕ１＝Ｋｖ１，
Ｋｕ２＝Ｋｖ２
であることを以下に示す。
【数１４】
同様にして
Ｋｕ２＝Ｋｖ２．
が示せる。この証明は、発明者の論文（Ｍａｓａｈｉｒｏ Ｙａｇｉｓａｗａ，″Ｋｅｙ Ａｇｒｅｅｍｅｎｔ Ｐｒｏｔｏｃｏｌｓ Ｂａｓｅｄ ｏｎ Ｍｕｌｔｉｖａｒｉａｔｅ Ａｌｇｅｂｒａｉｃ Ｅｑｕａｔｉｏｎｓ ｏｎ Ｑｕａｔｅｒｎｉｏｎ Ｒｉｎｇ″，Ｃｒｙｐｔｏｌｏｇｙ ｅＰｒｉｎｔ Ａｒｃｈｉｖｅ，Ｒｅｐｏｒｔ２０１０／３７７，（２０１０−０７）．）に示されている。
【００２１】
利用者Ｕと利用者Ｖの共通鍵は［Ｋｕ１，Ｋｕ２］となる。
【００２２】
公開される集合｛ｆｊｅ０ｅ１ｅ２ｅ３｝の値から秘密鍵［Ａｉ（ｉ＝１，．．，ｍ）］を求めることが高次多変数連立代数方程式の解法に帰結される。この解法問題はＮＰ完全問題の一つである。
【００２３】
請求項２の発明によれば、システムセンタは奇素数ｑおよび２つの整数［ｄ，ｍ］を選び公開する。利用者Ｕは、システム加入時に、秘密鍵［Ａｉｊ（ｉ＝１，．．，ｍ；ｊ＝１，．．，ｄ）］を選ぶ。ここで、Ａｉｊ（ｉ＝１，．．，ｍ；ｊ＝１，．．，ｄ）をＦｑ上の四元数環Ｈ上の任意のｍｄ個の要素とする。１つの要素ＡｉｊはＦｑ上の４つの要素から成り立っている四元数である。利用者Ａは公開されている３つのシステムパラメータ［ｑ，ｄ，ｍ］と秘密鍵［Ａｉｊ（ｉ＝１，．．，ｍ；ｊ＝１，．．，ｄ）］から、公開鍵である四元数環上の高次関数である暗号化関数Ｆ（Ｘ）を以下のように生成する。
【数１５】
【００２４】
利用者Ｕは暗号化関数Ｆ（Ｘ）を展開して、展開式の各係数ｆｊｅ１０．．ｅｄ３を求め、その集合｛ｆｊｅ１０．．ｅｄ３｝をシステムセンタに利用者Ｕの公開鍵として利用者Ｕの識別情報ＩＤとともに送る。四元数Ｆ（Ｘ）の展開表現を（ｆ０，ｆ１，ｆ２，ｆ３）とすると、
【数１６】
ｅｉｊ∈｛０，１｝（ｉ＝１，．．，ｄ；ｊ＝０，．．，３）は
ｅｉ０＋．．＋ｅｉ３＝１（ｉ＝１，．．，ｄ）．
であり、
ｅ１０＋．．＋ｅ１３＋・・・＋ｅｄ０＋．．＋ｅｄ３＝ｄ
を満足する。｛ｆｊｅ１０．．ｅｄ３｝はｆｊｅ１０．．ｅｄ３．全てを含む集合とする。ｆｊｅ１０．．ｅｄ３の個数はｎで与えられる。
【数１７】
【００２５】
システムパラメータｍの値はシステムセンタにて以下のように決定されている。
【数１８】
【００２６】
利用者Ｖは利用者Ｕと利用者Ｖ間の共通鍵Ｋｖ１，Ｋｖ２を以下のように生成する。
利用者Ｖは、四元数環Ｈのｍｄ個の任意の要素Ｂｉｊ（ｉ＝１，．．，ｍ；ｊ＝１，．．，ｄ）を選ぶ。Ｂｉｊ（ｉ＝１，．．，ｍ）を利用者Ｖの一時秘密鍵ＴＳＫと呼ぶ。
【００２７】
利用者Ｖは要素Ｂｉｊ（ｉ＝１，．．，ｍ；ｊ＝１，．．，ｄ）を用いて、Ｆｑ上の四元数環上の高次関数である一時暗号化関数Ｔ（Ｘ１，．．，Ｘｄ）を以下のように生成する。
【数１９】
【００２８】
利用者ＶはＴ（Ｘ）を展開して、展開式の各係数ｔｊｅ１０．．ｅｄ３を求め、その集合｛ｔｊｅ１０．．ｅｄ３｝である一時公開鍵ＴＫを求める。各係数ｔｊｅ１０．．ｅｄ３は以下のような形をしている。四元数Ｔ（Ｘ）の要素表現形式を（ｔ０，ｔ１，ｔ２，ｔ３）とすると
【数２０】
ここで、ｅｉｊ∈｛０，１｝（ｉ＝１，．．，ｄ；ｊ＝０，．．，３）は
ｅｉ０＋．．＋ｅｉ３＝１（ｉ＝１，．．，ｄ）．
であり、
ｅ１０＋．．＋ｅ１３＋・・・＋ｅｄ０＋．．＋ｅｄ３＝ｄ
を満足する。｛ｔｊｅ１０．．ｅｄ３｝はｔｊｅ１０．．ｅｄ３．全てを含む集合とする。ｔｊｅ１０．．ｅｄ３の個数はｎで与えられる。
【数２１】
【００２９】
利用者Ｖは｛ｔｊｅ１０．．ｅｄ３｝を利用者Ｕに送る。
【００３０】
利用者Ｖはシステムセンタの公開鍵管理簿から入手した利用者Ｕの公開鍵｛ｆｊｅ１０．．ｅｄ３｝と利用者Ｖの一時秘密鍵Ｂｉｊ（ｉ＝１，．．，ｍ；ｊ＝１，．．，ｄ）から共通鍵Ｋｖ１，Ｋｖ２を以下の手順で生成する。
【数２２】
したがって、Ｋｖ１ｊ（ｊ＝０，．．，３）は以下の形をしている。
（Ｖｉｊ０，Ｖｉｊ１，Ｖｉｊ２，Ｖｉｊ３）＝Ｂｉｊ（ｉ＝１，．．，ｍ；ｊ＝１，．．，ｄ），
ｅｉｊ∈｛０，１｝（ｉ＝１，．．，ｄ；ｊ＝０，．．，３）は
ｅｉ０＋・・・＋ｅｉ３＝１（ｉ＝１，．．，ｄ）
であり、
ｅ１０＋．．＋ｅ１３・・・＋ｅｄ０＋．．＋ｅｄ３＝ｄ
を満足する。
【数２３】
したがって、Ｋｖ２ｊ（ｊ＝０，．．，３）は以下の形をしている。
ここで、
（Ｖｉｊ０，Ｖｉｊ１，Ｖｉｊ２，Ｖｉｊ３）＝Ｂｉｊ，（ｉ＝１，．．，ｍ；ｊ＝１，．．，ｄ）．
係数ｆ’ｊｅ１０．．ｅｄ３はＦｑの要素である。
ｅｉｊ∈｛０．１｝（ｉ＝１，．．，ｄ；ｊ＝０，．．，３）は
ｅｉ０＋・・・＋ｅｉ３＝１（ｉ＝１，．．，ｄ）
であり、
ｅ１０＋．．＋ｅ１３＋・・・＋ｅｄ０＋．．＋ｅｄ３＝ｄ
を満足する。
【００３１】
利用者Ｕは以下のように共通鍵Ｋｕ１，Ｋｕ２を計算する。
まず、Ｋｕ１，Ｋｕ２の要素表現を以下に定める。
【数２４】
したがって、Ｋｖ１ｊ（ｊ＝０，．．，３）は以下の形をしている。
ここで、（Ｕｉｊ０，Ｕｉｊ１，Ｕｉｊ２，Ｕｉｊ３）＝Ａｉｊ，（ｉ＝１，．．，ｍ；ｊ＝１，．．，ｄ），
係数ｔ’ｊｅ１０．．ｅｄ３はＦｑの要素である。
ｅｉｊ∈｛０，１｝（ｉ＝１，．．，ｄ；ｊ＝０，．．，３）は
ｅｉ０＋・・・＋ｅｉ３＝１（ｉ＝１，．．，ｄ）
であり、
ｅ１０＋．．＋ｅ１３＋・・・＋ｅｄ０＋．．＋ｅｄ３＝ｄ
を満足する。
【数２５】
したがって、Ｋｖ２ｊ（ｊ＝０，．．，３）は以下の形をしている。
ここで、（Ｕｉｊ０，Ｕｉｊ１，Ｕｉｊ２，Ｕｉｊ３）＝Ａｉｊ，（ｉ＝１，．．，ｍ；ｊ＝１，．．，ｄ），
ｅｉｊ∈｛０，１｝（ｉ＝１，．．，ｄ；ｊ＝０，．．，３）は
ｅｉ０＋・・・＋ｅｉ３＝１（ｉ＝１，．．，ｄ）
であり、
ｅ１０＋．．＋ｅ１３＋・・・＋ｅｄ０＋．．ｅｄ３＝ｄ
を満足する。
【００３２】
［数２２］と［数２４］から
Ｋｕ１＝Ｋｖ１，
［数２３］と［数２５］から
Ｋｕ２＝Ｋｖ２．
であることがわかる。
利用者Ｕと利用者Ｖの共通鍵ＫはＫ＝［Ｋｕ１，Ｋｕ２］＝［Ｋｖ１，Ｋｖ２］で与えられる。
【００３３】
公開される利用者Ｕの公開鍵｛ｆｊｅ１０．．ｅｄ３｝の値から利用者Ｕの秘密鍵［Ａｉｊ（ｉ＝１，．．，ｍ；ｊ＝１，．．，ｄ）］を求めることは高次多変数連立代数方程式の解法に帰結される。この解法問題はＮＰ完全問題の一つである。
【００３４】
請求項３の発明によれば、システムセンタは奇素数ｑおよび２つの整数［ｄ，ｍ］を選び公開する。利用者Ｕは、システム加入時に、利用者Ｕの秘密鍵ＳＫ＝［Ａｉ＝（ａｉ０，ａｉ１，ａｉ２，ａｉ３）（ｉ＝１，．．，ｍ）］を選ぶ。ここで、Ａｉ（ｉ＝１，．．，ｍ）をＦｑ上の四元数環Ｈ上の任意のｍ個の要素とする。１つの要素ＡｉはＦｑ上の４つの要素から成り立っている四元数である。利用者Ｕは公開されている３つのシステムパラメータ［ｑ，ｄ，ｍ］と秘密鍵ＳＫから、公開鍵である四元数環上の高次関数である暗号化関数Ｆ（Ｘ）を以下のように生成する。
【数２６】
【００３５】
利用者Ｕは暗号化関数Ｆ（Ｘ）を展開して、展開式の各係数ｆｊｅ０ｅ１ｅ２ｅ３を求め、その集合｛ｆｊｅ０ｅ１ｅ２ｅ３｝をシステムセンタに利用者Ｕの公開鍵ＰＫとして利用者Ｕの識別情報ＩＤとともに送る。四元数Ｆ（Ｘ）の要素表現形式を（ｆ０，ｆ１，ｆ２，ｆ３）とすると、
【数２７】
ここで、ｅ０，ｅ１，ｅ２，ｅ３は非負の整数でｅ０＋ｅ１＋ｅ２＋ｅ３＝ｄを満足する。上式右辺のｆｊｅ０ｅ１ｅ２ｅ３（ｊ＝０，１，２，３）の総数ｎは、
【数２８】
となる。
｛ｆｊｅ０ｅ１ｅ２ｅ３｝はｆｊｅ０ｅ１ｅ２ｅ３全てを含む集合とする。
【００３６】
システムパラメータｍの値はシステムセンタにて以下のように決定されている。
【数２９】
【００３７】
利用者Ｖは利用者Ｕと利用者Ｖ間の共通鍵Ｋｖを以下のように生成する。
利用者Ｖは、四元数環Ｈのｍ個の任意の要素Ｂｉ＝（ｂｉ０，ｂｉ１，ｂｉ２，ｂｉ３）（ｉ＝１，．．，ｍ）を選ぶ。Ｂｉ（ｉ＝１，．．，ｍ）を利用者Ｖの一時秘密鍵ＴＳＫと呼ぶ。
【００３８】
利用者Ｖは要素Ｂｉ（ｉ＝１，．．，ｍ）を用いて、Ｆｑ上の四元数環上の高次関数である一時暗号化関数Ｔ（Ｘ）を以下のように生成する。
【数３０】
【００３９】
利用者ＶはＴ（Ｘ）を展開して、展開式の各係数ｔｊｅ０ｅ１ｅ２ｅ３を求め、その集合｛ｔｊｅ０ｅ１ｅ２ｅ３｝を求める。
四元数Ｔ（Ｘ）の要素表現形式を（ｔ０，ｔ１，ｔ２，ｔ３）とすると
【数３１】
【００４０】
ここで、ｅ０，ｅ１，ｅ２，ｅ３は非負の整数でｅ０＋ｅ１＋ｅ２＋ｅ３＝ｄを満足する。上記ｔｊｅ０ｅ１ｅ２ｅ３総数ｎは、
【数３２】
となる。
｛ｔｊｅ０ｅ１ｅ２ｅ３｝はｔｊｅ０ｅ１ｅ２ｅ３全てを含む集合であり、利用者Ｖの一時公開鍵ＴＫと呼ぶ。
【００４１】
利用者Ｖは｛ｔｊｅ０ｅ１ｅ２ｅ３｝を利用者Ｕに送る。
【００４２】
利用者Ｖはシステムセンタの公開鍵管理簿から入手した利用者Ｕの公開鍵ＰＫと利用者Ｖの一時秘密鍵Ｂｉ（ｉ＝１，．．，ｍ）から共通鍵Ｋｖを以下の手順で生成する。
【数３３】
Ｋｖｊ（ｊ＝０，１，２，３）は以下で与えられる。
【数３４】
ｅ０，ｅ１，ｅ２，ｅ３は非負整数でｅ０＋・・・＋ｅ３＝ｄを満足する．
【００４３】
利用者Ｕは以下のように共通鍵Ｋｕを計算する。まず、Ｋｕの要素表現を以下に定める。
【数３５】
【００４４】
Ｋｕｉ（ｉ＝１，０，１，２，３）は以下で与えられる。
【数３６】
ｅ０，ｅ１，ｅ２，ｅ３は非負整数でｅ０＋・・・＋ｅ３＝ｄを満足する．
【００４５】
［数３３］、［数３５］から
Ｋｕ＝Ｋｖ，
であることが分かる。利用者Ｕと利用者Ｖの共通鍵はＫｕまたはＫｖである。
【００４６】
公開される利用者Ｕの公開鍵｛ｆｊｅ０ｅ１ｅ２ｅ３｝の値から利用者Ｕの秘密鍵［Ａｉ（ｉ＝１，．．，ｍ）］を求めることは高次多変数連立代数方程式の解法に帰結される。この解法問題はＮＰ完全問題の一つである。
【００４７】
請求項４の発明によれば、システムセンタは素数ｑおよび３つの整数［ｄ，ｍ，ｎ］を選び公開する。
利用者Ｕは、システム加入時に、利用者Ｕの秘密鍵ＳＫ＝［ｋｉ，ａｉｉ（ｉ＝１，．．，ｍ；ｊ＝１，．．，ｎ）］を選ぶ。ここで、，ｋｉａｉｊ（ｉ＝１，．．，ｍ；ｊ＝１，．．，ｎ）をＦｑ上の任意の要素とする。利用者Ｕは公開されている３つのシステムパラメータ［ｑ，ｄ，ｍ］と利用者Ｕの秘密鍵ＳＫから、公開鍵であるｎ変数多項式環Ｆｑ［ｘ１，．．，ｘｎ］上の暗号化関数Ｆ（Ｘ）を以下のように生成する。
【数３７】
ここで、
Ａｉ（Ｘ）＝ａｉ１Ｘ１＋・・・＋ａｉｎＸｎ，（ｉ＝１，．．，ｍ）
変数；Ｘ＝（Ｘ１，．．，Ｘｎ）Ｔ∈Ｆｑ［ｘ１，．．，ｘｎ］ｎ
【００４８】
利用者Ｕは暗号化関数Ｆ（Ｘ）を展開して、展開式の各係数ｆｊｅ０．．ｅｎを求め、その集合｛ｆｊｅ０．．ｅｎ｝をシステムセンタに利用者Ｕの公開鍵ＰＫとして利用者Ｕの識別情報ＩＤとともに送る。各係数もｆｊｅ０．．ｅｎは以下のような形をしている。
【数３８】
ここで、ｅ０，．．，ｅｎは非負の整数でｅｉ１＋．．＋ｅｉｎ＝ｉを満足する。上式右辺のｆｉｅｉ１．．ｅｉｎ数Ｎは、
となる。
｛ｆｉｅｉ１．．ｅｉｎ｝はｆｉｅｉ１．．ｅｉｎ全てを含む集合とする。
【００４９】
システムパラメータｍの値はシステムセンタにて以下のように決定されている。
【数３９】
【００５０】
利用者Ｖは利用者Ｕと利用者Ｖ間の共通鍵Ｋｖ（Ｘ）を以下のように生成する。
利用者Ｖは、ｈｉ，ｂｉｊ∈Ｆｑ，（ｉ＝１，．．，ｍ；ｊ＝１，．．，ｎ）を任意に選ぶ。［ｈｉ，ｂｉｊ∈Ｆｑ，（ｉ＝１，．．，ｍ；ｊ＝１，．．，ｎ）］を利用者Ｖの一時秘密鍵ＴＳＫと呼ぶ。
【００５１】
利用者Ｖは［ｈｉ，ｂｉｊ∈Ｆｑ，（ｉ＝１，．．，ｍ；ｊ＝１，．．，ｎ）］を用いて、Ｆｑ上の一時暗号化関数Ｔ（Ｘ）を以下のように生成する。
【数４０】
ここで、
Ｂｉ（Ｘ）＝ｂｉ１ｘ１＋・・・＋ｂｉｎｘｎ，（ｉ＝１，．．，ｍ）．
【００５２】
利用者ＶはＴ（Ｘ）を展開して、展開式の各係数ｔｉｅｉ１．．ｅｉｎを求め、その集合｛ｔｉｅｉ１．．ｅｉｎ｝を求める。
【数４１】
【００５３】
ここで、ｅ０，．．，ｅｎは非負の整数でｅｉ１＋．．＋ｅｉｎ＝ｉを満足する。ｔｉｅｉ１．．ｅｉｎの総数Ｎ’は、Ｎに等しい。
｛ｔｉｅｉ１．．ｅｉｎ｝はｔｉｅｉ１．．ｅｉｎをすべて含む集合であり、利用者Ｖの一時公開鍵ＴＫと呼ぶ。
【００５４】
利用者Ｖは｛ｔｉｅｉ１．．ｅｉｎ｝を利用者Ｕに送る。
【００５５】
利用者Ｖはシステムセンタの公開鍵管理簿から入手した利用者Ｕの公開鍵ＰＫと利用者Ｖの一時秘密鍵ＴＳＫから共通鍵Ｋｖを以下の手順で生成する。
【数４２】
［数３７］から
【数４３】
また、［数３８］から
【数４４】
が得られる。
ここで、ｅ０，．．，ｅｎは非負の整数でｅｉ１＋．．＋ｅｉｎ＝ｉ（ｉ＝１，．．，ｄ）を満足する。
【００５６】
一方、利用者Ｕは以下のように共通鍵Ｋｕを計算する。
【数４５】
［数４０］から
【数４６】
また、［数４１］から
【数４７】
が得られる。
ここで、ｅ０，．．，ｅｎは非負の整数でｅｉ１＋．．＋ｅｉｎ＝ｉ（ｉ＝１，．．，ｄ）を満足する。
【００５７】
［数４３］、［数４６］から
【数４８】
であることが分かる。利用者Ｕと利用者Ｖの共通鍵はＫｕ（Ｘ）またはＫｖ（Ｘ）である。
【００５８】
公開される利用者Ｕの公開鍵｛ｆｉｅｉ１．．ｅｉｎ｝の値から秘密鍵［ｈｉ，ｂｉ１∈Ｆｑ，（ｉ＝１，．．，ｍ；ｊ＝１，．．，ｎ）］を求めることは高次多変数連立代数方程式の解法に帰結される。この解法問題はＮＰ完全問題の一つである。
【００５９】
ところで、西岡方式の安全性は、乗法群や楕円曲線上の離散対数問題の困難さに依存する。
【００６０】
一方、本発明方式の安全性は、有限体Ｆｑ上の高次多変数連立代数方程式の解法の困難さに依存する。次数を大きくし、変数の数を多くすることにより、耐量子コンピュータ性をもつ鍵共有方式である。
【発明の効果】
【００６１】
西岡方式の安全性は、乗法群や楕円曲線上の離散対数問題の困難さに依存するので、量子コンピュータが出現すると、多項式時間で解読可能となる恐れがある。
【００６２】
一方、請求項１、請求項２、請求項３および請求項４の発明において、有限体Ｆｑ上の高次多変数連立代数方程式の解法の困難さに依存する鍵共有方式では、高次多変数連立代数方程式の解法がＮＰ完全問題の１つとなるので、量子コンピュータに耐えうる鍵共有方式を提供できる。
【００６３】
従ってこの発明によれば安全性を高く保持するものとなる。
【００６４】
なお、本発明は、上記において説明した実施形態に限定されるものではなく、その主旨を逸脱しない範囲において種々変更可能であり、それらも本発明の範囲内に包含されるものであることは言うまでもない。
【図面の簡単な説明】
【００６５】
【図１】本発明に係る鍵共有方法の実施形態例を示す概念図である。
【図２】図１中の利用者Ｕの通信装置の一例のブロック図である。
【図３】図１中の利用者Ｖの通信装置の一例のブロック図である。
【図４】図１中のシステムセンタの一例のブロック図である。
【符号の説明】
【００６６】
１００…システムセンタ
２００…利用者Ｕの通信装置
３００…利用者Ｖの通信装置
４００…安全でない通信路
１０１…システムセンタ公開鍵管理簿
２０１…乱数発生器
２０２…暗号化関数Ｆ（Ｘ）
２０３…共通鍵生成器
２０４…記憶装置
２０５…結合器
３０１…乱数発生器
３０２…一時暗号化関数Ｔ（Ｘ）
３０３…共通鍵生成器
３０４…記憶装置
【発明を実施するための形態】
【実施例】
【００６７】
請求項１の発明の一実施例について説明する。図１はこの発明の第１、第２、第３、第４の実施形態例を示す概念図である。利用者Ｕが事前にシステムセンタに登録しておいた利用者Ｕの公開鍵と利用者Ｖが発生する乱数をもとに生成する利用者Ｖの一時公開鍵を用いて、利用者Ｕと利用者Ｖがそれぞれ共通鍵を生成する場合を示している。
【００６８】
図２に利用者Ｕの通信装置の一例を示す。まず、システムに加入した利用者Ｕは、システムセンタ１００から入手したシステムパラメータと乱数発生器２０１から発生させた乱数である秘密鍵ＳＫから暗号化関数Ｆ（Ｘ）を作成し、Ｆ（Ｘ）を展開してその係数の集合である公開鍵ＰＫを生成し、公開鍵ＰＫを利用者Ｕの識別情報ＩＤと結合器にて対にして、システムセンタ１００の公開鍵管理簿１０１に登録する。
【００６９】
次に、利用者Ｕが共通鍵Ｋを生成する手順について説明する。利用者Ｕはシステムセンタ１００から入手したシステムパラメータと利用者Ｕの秘密鍵ＳＫと利用者Ｖから受信した利用者Ｖの一時公開鍵ＴＫから共通鍵生成器により共通鍵Ｋｕを生成する。
【００７０】
図３に利用者Ｖの通信装置を示す。利用者Ｖは乱数生成器３０１を用いて乱数である一時秘密鍵ＴＳＫを発生し、一時秘密鍵ＴＳＫとシステムセンタ１００から入手したシステムパラメータを用いて一時暗号関数Ｔ（Ｘ）を作成し、Ｔ（Ｘ）を展開して、その係数の集合である一時公開鍵ＴＫとを利用者Ｕに送信する。利用者Ｖはシステムセンタにアクセスして利用者Ｕの公開鍵ＰＫを入手して、利用者Ｖの一時秘密鍵ＴＳＫと利用者Ｕの公開鍵ＰＫから共通鍵Ｋｖを生成する。
【００７１】
図４にシステムセンタの一例を示す。
まず、システムセンタはシステムパラメータを公開する。次に利用者Ｕの公開鍵ＰＫとＩＤを受信して公開鍵管理簿に登録し公開する。
【００７２】
なお、本発明は、上記において説明した実施形態に限定されるものではなく、その主旨を逸脱しない範囲において種々変更可能であり、それらも本発明の範囲内に包含されるものであることは言うまでもない。
【産業上の利用可能性】
【００７３】
この発明は通信者同士がお互いに同一の秘密情報を持たずに共通鍵を確保できる鍵共有方式に関し、高次多変数連立代数方程式を利用して、特に安全性が高く、耐量子コンピュータ性をもつ鍵共有方式を提供するものである。
【特許請求の範囲】
【請求項１】
通信者同士がお互いに同一の秘密情報を持たずに共通鍵を確保できる鍵共有方式において、高次多変数連立代数方程式を利用して、特に安全性が高く、耐量子コンピュータ性をもつ鍵共有方式であって、システムセンタは奇素数ｑおよび３つの整数［ｄ，ｒ，ｍ］を選んで公開し、利用者Ｕはシステム加入時に、Ｆｑ上の四元数環Ｈ上の逆数をもつ任意のｍ個の要素である秘密鍵［Ａｉ（ｉ＝１，．．，ｍ）］を選び、利用者Ｕが公開されている３つのシステムパラメータ［ｄ，ｒ，ｍ］と秘密鍵［Ａｉ（ｉ＝１，．．，ｍ）］から、四元数環上の高次関数である暗号化関数Ｆ（Ｘ）＝Σｉ＝１ｍΠｊ＝０ｄＡｉｒ＾ｊＸｒ＾ｊを生成し、利用者Ｕが暗号化関数Ｆ（Ｘ）を展開して、展開式の各係数ｆｊｅ０ｅ１ｅ２ｅ３を求め、その集合｛ｆｊｅ０ｅ１ｅ２ｅ３｝をシステムセンタに利用者Ｕの公開鍵ＰＫとして利用者Ｕの識別情報ＩＤとともに送り、利用者Ｖは、四元数環Ｈの逆数をもつ任意のｍ個の要素Ｒｉ（ｉ＝１，．．，ｍ）を選び、Ｒｉ（ｉ＝１，．．，ｍ）を利用者Ｖの一時秘密鍵として、利用者Ｖは要素Ｒｉ（ｉ＝１，．．，ｍ）を用いて、Ｆｑ上の四元数環上の高次関数である一時暗号化関数Ｔ（Ｘ）＝Σｉ＝１ｍΠｊ＝０ｄＲｉｒ＾ｊＸｒ＾ｊを生成し、利用者ＶはＴ（Ｘ）を展開して、展開式の各係数ｔｊｅ０ｅ１ｅ２ｅ３を求め、その集合｛ｔｊｅ０ｅ１ｅ２ｅ３｝を利用者Ｖの一時公開鍵ＴＫとして、利用者ＶはＴＫを利用者Ｕに送り、利用者Ｖはシステムセンタの公開鍵管理簿から入手した利用者Ｕの公開鍵ＰＫと利用者Ｖの一時秘密鍵ＴＳＫから共通鍵Ｋｖ１，Ｋｖ２を生成し、利用者Ｕは利用者Ｖから送られてきた一時公開鍵ＴＫと自分の秘密鍵ＳＫから共通鍵Ｋｕ１，Ｋｕ２を生成することを特徴とする鍵共有方式。
【請求項２】
前記の暗号化関数Ｆ（Ｘ）をＦ（Ｘ）＝Σｉ＝１ｍΠｊ＝１ｄＸｊＡｉｊとして、一時暗号化関数Ｔ（Ｘ）をＴ（Ｘ）＝Σｉ＝１ｍΠｊ＝１ｄＸｊＢｉｊとすることを特徴とする請求項１記載の鍵共有方式。
【請求項３】
前記の暗号化関数Ｆ（Ｘ）をＦ（Ｘ）＝Σｉ＝１ｍ（ａｉ０ｘ０，ａｉ１ｘ１，ａｉ２，ｘ２，ａｉ３ｘ３）ｄとして、一時暗号化関数Ｔ（Ｘ）をＴ（Ｘ）＝Σｉ＝１ｍ（ｂｉ０ｘ０，ｂｉ１ｘ１，ｂｉ２ｘ２，ｂｉ３ｘ３）ｄとすることを特徴とする請求項１記載の鍵共有方式。
【請求項４】
システムセンタは素数ｑおよび３つの正整数［ｄ，ｍ，ｎ］を選んで公開し、利用者Ｕはシステム加入時に、Ｆｑ上のｋｉ，ａｉｊ（ｉ＝１，．．，ｍ；ｊ＝１，．．，ｎ）を選び、Ｘ＝（ｘ１，・・・，ｘｎ）Ｔ∈Ｆｑ［ｘ１，．．，ｘｎ］ｎを変数としてＡｉ（Ｘ）＝ａｉ１ｘ１＋・・・＋ａｉｎｘｎ（ｉ＝１，．．，ｍ）を用いて、ｎ変数多項式環Ｆｑ［ｘ１，．．，ｘｎ］上の暗号化関数Ｆ（Ｘ）＝Σｉ＝１ｍｋｉ［Ａｉ（Ｘ）ｄ＋Ａｉ（Ｘ）ｄ−１＋．．＋Ａｉ（Ｘ）］を生成し、利用者Ｕは暗号化関数Ｆ（Ｘ）を展開して、展開式の各係数ｆｊｅ１．．．ｅｎを求め、その集合｛ｆｊｅ１．．．ｅｎ｝をシステムセンタに利用者Ｕの公開鍵ＰＫとして利用者Ｕの識別情報ＩＤとともに送り、利用者Ｖは、Ｆｑ上のｈｉ，ｂｉｊ（ｉ＝１，．．，ｍ；ｊ＝１，．．，ｎ）を選び、Ｂｉ（Ｘ）＝ｂｉ１ｘ１＋・・・＋ｂｉｎｘｎ（ｉ＝１，．．，ｍ）を用いて、ｎ変数多項式環Ｆｑ［ｘ１，．．，ｘｎ］上の一時暗号化関数Ｔ（Ｘ）＝Σｉ＝１ｍｈｉ［Ｂｉ（Ｘ）ｄ＋Ｂｉ（Ｘ）ｄ−１＋．．＋Ｂｉ（Ｘ）］を生成し、利用者ＶはＴ（Ｘ）を展開して、展開式の各係数ｔｊｅ１．．．ｅｎを求め、その集合｛ｔｊｅ１．．．ｅｎ｝を利用者Ｖの一時公開鍵ＴＫとすることを特徴とする請求項１記載の鍵共有方式。
【請求項１】
通信者同士がお互いに同一の秘密情報を持たずに共通鍵を確保できる鍵共有方式において、高次多変数連立代数方程式を利用して、特に安全性が高く、耐量子コンピュータ性をもつ鍵共有方式であって、システムセンタは奇素数ｑおよび３つの整数［ｄ，ｒ，ｍ］を選んで公開し、利用者Ｕはシステム加入時に、Ｆｑ上の四元数環Ｈ上の逆数をもつ任意のｍ個の要素である秘密鍵［Ａｉ（ｉ＝１，．．，ｍ）］を選び、利用者Ｕが公開されている３つのシステムパラメータ［ｄ，ｒ，ｍ］と秘密鍵［Ａｉ（ｉ＝１，．．，ｍ）］から、四元数環上の高次関数である暗号化関数Ｆ（Ｘ）＝Σｉ＝１ｍΠｊ＝０ｄＡｉｒ＾ｊＸｒ＾ｊを生成し、利用者Ｕが暗号化関数Ｆ（Ｘ）を展開して、展開式の各係数ｆｊｅ０ｅ１ｅ２ｅ３を求め、その集合｛ｆｊｅ０ｅ１ｅ２ｅ３｝をシステムセンタに利用者Ｕの公開鍵ＰＫとして利用者Ｕの識別情報ＩＤとともに送り、利用者Ｖは、四元数環Ｈの逆数をもつ任意のｍ個の要素Ｒｉ（ｉ＝１，．．，ｍ）を選び、Ｒｉ（ｉ＝１，．．，ｍ）を利用者Ｖの一時秘密鍵として、利用者Ｖは要素Ｒｉ（ｉ＝１，．．，ｍ）を用いて、Ｆｑ上の四元数環上の高次関数である一時暗号化関数Ｔ（Ｘ）＝Σｉ＝１ｍΠｊ＝０ｄＲｉｒ＾ｊＸｒ＾ｊを生成し、利用者ＶはＴ（Ｘ）を展開して、展開式の各係数ｔｊｅ０ｅ１ｅ２ｅ３を求め、その集合｛ｔｊｅ０ｅ１ｅ２ｅ３｝を利用者Ｖの一時公開鍵ＴＫとして、利用者ＶはＴＫを利用者Ｕに送り、利用者Ｖはシステムセンタの公開鍵管理簿から入手した利用者Ｕの公開鍵ＰＫと利用者Ｖの一時秘密鍵ＴＳＫから共通鍵Ｋｖ１，Ｋｖ２を生成し、利用者Ｕは利用者Ｖから送られてきた一時公開鍵ＴＫと自分の秘密鍵ＳＫから共通鍵Ｋｕ１，Ｋｕ２を生成することを特徴とする鍵共有方式。
【請求項２】
前記の暗号化関数Ｆ（Ｘ）をＦ（Ｘ）＝Σｉ＝１ｍΠｊ＝１ｄＸｊＡｉｊとして、一時暗号化関数Ｔ（Ｘ）をＴ（Ｘ）＝Σｉ＝１ｍΠｊ＝１ｄＸｊＢｉｊとすることを特徴とする請求項１記載の鍵共有方式。
【請求項３】
前記の暗号化関数Ｆ（Ｘ）をＦ（Ｘ）＝Σｉ＝１ｍ（ａｉ０ｘ０，ａｉ１ｘ１，ａｉ２，ｘ２，ａｉ３ｘ３）ｄとして、一時暗号化関数Ｔ（Ｘ）をＴ（Ｘ）＝Σｉ＝１ｍ（ｂｉ０ｘ０，ｂｉ１ｘ１，ｂｉ２ｘ２，ｂｉ３ｘ３）ｄとすることを特徴とする請求項１記載の鍵共有方式。
【請求項４】
システムセンタは素数ｑおよび３つの正整数［ｄ，ｍ，ｎ］を選んで公開し、利用者Ｕはシステム加入時に、Ｆｑ上のｋｉ，ａｉｊ（ｉ＝１，．．，ｍ；ｊ＝１，．．，ｎ）を選び、Ｘ＝（ｘ１，・・・，ｘｎ）Ｔ∈Ｆｑ［ｘ１，．．，ｘｎ］ｎを変数としてＡｉ（Ｘ）＝ａｉ１ｘ１＋・・・＋ａｉｎｘｎ（ｉ＝１，．．，ｍ）を用いて、ｎ変数多項式環Ｆｑ［ｘ１，．．，ｘｎ］上の暗号化関数Ｆ（Ｘ）＝Σｉ＝１ｍｋｉ［Ａｉ（Ｘ）ｄ＋Ａｉ（Ｘ）ｄ−１＋．．＋Ａｉ（Ｘ）］を生成し、利用者Ｕは暗号化関数Ｆ（Ｘ）を展開して、展開式の各係数ｆｊｅ１．．．ｅｎを求め、その集合｛ｆｊｅ１．．．ｅｎ｝をシステムセンタに利用者Ｕの公開鍵ＰＫとして利用者Ｕの識別情報ＩＤとともに送り、利用者Ｖは、Ｆｑ上のｈｉ，ｂｉｊ（ｉ＝１，．．，ｍ；ｊ＝１，．．，ｎ）を選び、Ｂｉ（Ｘ）＝ｂｉ１ｘ１＋・・・＋ｂｉｎｘｎ（ｉ＝１，．．，ｍ）を用いて、ｎ変数多項式環Ｆｑ［ｘ１，．．，ｘｎ］上の一時暗号化関数Ｔ（Ｘ）＝Σｉ＝１ｍｈｉ［Ｂｉ（Ｘ）ｄ＋Ｂｉ（Ｘ）ｄ−１＋．．＋Ｂｉ（Ｘ）］を生成し、利用者ＶはＴ（Ｘ）を展開して、展開式の各係数ｔｊｅ１．．．ｅｎを求め、その集合｛ｔｊｅ１．．．ｅｎ｝を利用者Ｖの一時公開鍵ＴＫとすることを特徴とする請求項１記載の鍵共有方式。
【図１】
【図２】
【図３】
【図４】
【図２】
【図３】
【図４】
【公開番号】特開２０１２−１２９９６６（Ｐ２０１２−１２９９６６Ａ）
【公開日】平成２４年７月５日（２０１２．７．５）
【国際特許分類】
【出願番号】特願２０１０−２９４７３１（Ｐ２０１０−２９４７３１）
【出願日】平成２２年１２月１６日（２０１０．１２．１６）
【新規性喪失の例外の表示】特許法第３０条第１項適用申請有り 発明の掲載日 ２０１０年７月４日、８月２４日、１０月７日 発明を掲載したホームページアドレス（ＵＲＬ） ｈｔｔｐ：／／ｗｗｗ．ｉａｃｒ．ｏｒｇ／
【出願人】（５１０３１８０５５）
【Ｆターム（参考）】
【公開日】平成２４年７月５日（２０１２．７．５）
【国際特許分類】
【出願日】平成２２年１２月１６日（２０１０．１２．１６）
【新規性喪失の例外の表示】特許法第３０条第１項適用申請有り 発明の掲載日 ２０１０年７月４日、８月２４日、１０月７日 発明を掲載したホームページアドレス（ＵＲＬ） ｈｔｔｐ：／／ｗｗｗ．ｉａｃｒ．ｏｒｇ／
【出願人】（５１０３１８０５５）
【Ｆターム（参考）】
[ Back to top ]