(57)【要約】      （修正有）【課題】  素因数分解の困難性や離散対数問題の求解困難性に依拠しない公開鍵暗号化方法を提供する。【解決手段】  素数Ｐを定め、有限体ＦＰ上で、平文をＸ＝（ｘ１，ｘ２，・・・，ｘｍ）Ｔとし、正則行列Ａ、Ｂ、行列Ｑを用い、Ｑの第ｉ列を下から見ていき、初めて０でない要素が含まれる行をｒｉ行とした場合、Ｘの左からＡを乗じてＶ’＝ＡＸとする。Ｖ’の左からＱを乗じてＶ＝ＱＶ’とする。定数行列Ｃ，Ｕと、多項式、対角行列Ｔ（Ｖ）を用い、Ｔ（Ｖ）の左からＵを乗じてＳ（Ｖ）＝ＵＴ（Ｖ）とする。１列以上の各列に２個以上のｖの多項式ｇｋ（Ｖ）を含み、それ以外の要素がすべて０である行列Ｎ（Ｖ）をＳ（Ｖ）に加えたものをＦ（Ｖ）とする。Ｆ（Ｖ）の左からＣを乗じてＤ（Ｖ）＝ＣＦ（Ｖ）とし、このときＤ（Ｖ）はｇｋ（Ｖ）を含まず、ｒｉ行目だけに注目した際に上三角行列になるようにする。次に、Ｇ（Ｘ）＝ＢＦ（Ｖ）ＶmodＰとし、Ｙ＝Ｇ（Ｘ）modＰにより暗号文Ｙ＝（ｙ１，ｙ２，・・・，ｙｎ）Ｔを得る。【選択図】  なし【特許請求の範囲】
【請求項１】
素数Ｐを定め、有限体ＦＰ上において、平文をＸ＝（ｘ１，ｘ２，・・・，ｘｍ）Ｔ（Ｔはベクトルの転置を表す）とし、（ｍ×ｍ）型正則行列Ａ、（ｎ×ｎ）型正則行列Ｂ（ｍ＜ｎ）、（ｎ×ｍ）型行列Ｑ（ただし、（ｍ×ｎ）型で（１，１）成分および（ｍ，ｎ）成分が０でない階段行列をＱ’＝［（ｑ’ｉ，ｊ）］（ｉ＝１，２，・・・，ｍ、ｊ＝１，２，・・・，ｎ）としたとき、行列Ｑ＝［（ｑｊ，ｉ）］は、（ｑｊ，ｉ）＝（ｑ’ｍ−ｉ＋１，ｎ−ｊ＋１）で表される。）を用い、
前記行列Ｑの第ｉ列を下から見ていき、初めて０でない要素が含まれる行をｒｉ行とした仮定した場合、前記Ｘの左からＡを乗じてＶ’＝ＡＸとする第１の計算工程と、
前記Ｖ’の左からＱを乗じてＶ＝ＱＶ’とする第２の計算工程と、
（ｎ×ｎ）型定数行列Ｃ，Ｕと、（ｋ，ｋ）成分（１≦ｋ≦ｎ）がｖｋ＋１，ｖｋ＋２，・・・，ｖｎの多項式、（ｎ，ｎ）成分が定数である（ｎ×ｎ）型対角行列Ｔ（Ｖ）を用い、Ｔ（Ｖ）の左からＵを乗じてＳ（Ｖ）＝ＵＴ（Ｖ）とする第３の計算工程と、
１列以上の各列に２個以上のｖの多項式ｇｋ（Ｖ）（ｋ以下の添字をもつｖｊ（ｊ≦ｋ）を含見、当該ｋは列を表す添字である。）を含み、それ以外の要素がすべて０である（ｎ×ｎ）型行列Ｎ（Ｖ）をＳ（Ｖ）に加えたものをＦ（Ｖ）とする第４の計算工程と、
前記Ｆ（Ｖ）の左からＣを乗じてＤ（Ｖ）＝ＣＦ（Ｖ）とし、このとき前記Ｄ（Ｖ）は前記ｇｋ（Ｖ）を含まず、ｒｉ行目だけに注目した際に上三角行列になるようにする第５の計算工程と、
Ｇ（Ｘ）＝ＢＦ（Ｖ）ＶmodＰとし、Ｙ＝Ｇ（Ｘ）modＰにより暗号文Ｙ＝（ｙ１，ｙ２，・・・，ｙｎ）Ｔを得る暗号化工程と、
を有することを特徴とする暗号化方法。
【請求項２】
素数Ｐを定め、有限体ＦＰ上において、平文をＸ＝（ｘ１，ｘ２，・・・，ｘｍ）Ｔ（Ｔはベクトルの転置を表す）とし、（ｍ×ｍ）型正則行列Ａ、（ｎ×ｎ）型正則行列Ｂ（ｍ＜ｎ）、（ｎ×ｍ）型行列Ｑ（ただし、（ｍ×ｎ）型で（１，１）成分および（ｍ，ｎ）成分が０でない階段行列をＱ’＝［（ｑ’ｉ，ｊ）］（ｉ＝１，２，・・・，ｍ、ｊ＝１，２，・・・，ｎ）としたとき、行列Ｑ＝［（ｑｊ，ｉ）］は、（ｑｊ，ｉ）＝（ｑ’ｍ−ｉ＋１，ｎ−ｊ＋１）で表される。）を用い、前記行列Ｑの第ｉ列を下から見ていき、初めて０でない要素が含まれる行をｒｉ行とした仮定した場合、前記Ｘの左からＡを乗じてＶ’＝ＡＸとする第１の計算工程と、
前記Ｖ’の左からＱを乗じてＶ＝ＱＶ’とする第２の計算工程と、
（ｎ×ｎ）型定数行列Ｃ，Ｕと、（ｋ，ｋ）成分（１≦ｋ≦ｎ）がｖｋ＋１，ｖｋ＋２，・・・，ｖｎの多項式、（ｎ，ｎ）成分が定数である（ｎ×ｎ）型対角行列Ｔ（Ｖ）を用い、Ｔ（Ｖ）の左からＵを乗じてＳ（Ｖ）＝ＵＴ（Ｖ）とする第３の計算工程と、
１列以上の各列に２個以上のｖの多項式ｇｋ（Ｖ）（ｋ以下の添字をもつｖｊ（ｊ≦ｋ）を含見、当該ｋは列を表す添字である。）を含み、それ以外の要素がすべて０である（ｎ×ｎ）型行列Ｎ（Ｖ）をＳ（Ｖ）に加えたものをＦ（Ｖ）とする第４の計算工程と、
前記Ｆ（Ｖ）の左から前記（ｎ×ｎ）型定数行列Ｃを乗じてＤ（Ｖ）＝ＣＦ（Ｖ）とし、このとき前記Ｄ（Ｖ）は前記ｇｋ（Ｖ）を含まず、ｒｉ行目だけに注目した際に上三角行列になるようにする第５の計算工程と、
Ｇ（Ｘ）＝ＢＦ（Ｖ）ＶmodＰとし、前記Ｇ（Ｘ）、前記素数Ｐ、サイズｍを公開鍵として、当該Ｙ＝Ｇ（Ｘ）modＰにより暗号文Ｙ＝（ｙ１，ｙ２，・・・，ｙｎ）Ｔを得る暗号化工程と、
を有することを特徴とする公開鍵暗号化方法。
【請求項３】
請求項２記載の公開鍵暗号化方法によって暗号化された暗号文Ｙ＝（ｙ１，ｙ２，・・・，ｙｎ）Ｔを復号する復号化方法において、
前記（ｍ×ｍ）型正則行列Ａ、前記（ｎ×ｎ）型正則行列Ｂ（ｍ＜ｎ）、前記（ｎ×ｎ）型定数行列Ｃ、前記Ｄ（Ｖ）、前記（ｎ×ｍ）型行列Ｑ、前記ｒｉを秘密鍵として取得する工程と
前記秘密鍵を前記（ｎ×ｎ）型正則行列Ｂとして、当該秘密鍵Ｂの逆行列を前記暗号文Ｙ＝Ｇ（Ｘ）の両辺の左から乗じて、
Ｂ−１Ｙ＝Ｆ（Ｖ）Ｖとする第６の計算工程と、
Ｄ（Ｖ）＝ＣＦ（Ｖ）を用いて、ＣＢ−１Ｙ＝ＣＦ（Ｖ）Ｖ＝Ｄ（Ｖ）Ｖとし、ＣＢ−１Ｙ＝Ｄ（Ｖ）Ｖの式ｎ個のうち、第ｒｉ番目の式ｍ個とＶ＝ＱＶ’より得られる連立方程式を解いてＶ，Ｖ’を求める第７の計算工程と、
Ｘ＝Ａ−１Ｖ’より復号文Ｘを得る復号化工程と、
を有することを特徴とする復号化方法。
【請求項４】
コンピュータに、
素数Ｐを定め、有限体ＦＰ上において、平文をＸ＝（ｘ１，ｘ２，・・・，ｘｍ）Ｔ（Ｔはベクトルの転置を表す）とし、（ｍ×ｍ）型正則行列Ａ、（ｎ×ｎ）型正則行列Ｂ（ｍ＜ｎ）、（ｎ×ｍ）型行列Ｑ（ただし、（ｍ×ｎ）型で（１，１）成分および（ｍ，ｎ）成分が０でない階段行列をＱ’＝［（ｑ’ｉ，ｊ）］（ｉ＝１，２，・・・，ｍ、ｊ＝１，２，・・・，ｎ）としたとき、行列Ｑ＝［（ｑｊ，ｉ）］は、（ｑｊ，ｉ）＝（ｑ’ｍ−ｉ＋１，ｎ−ｊ＋１）で表される。）を用い、
前記行列Ｑの第ｉ列を下から見ていき、初めて０でない要素が含まれる行をｒｉ行とした仮定した場合、前記Ｘの左からＡを乗じてＶ’＝ＡＸとする第１の計算工程と、
前記Ｖ’の左からＱを乗じてＶ＝ＱＶ’とする第２の計算工程と、
（ｎ×ｎ）型定数行列Ｃ，Ｕと、（ｋ，ｋ）成分（１≦ｋ≦ｎ）がｖｋ＋１，ｖｋ＋２，・・・，ｖｎの多項式、（ｎ，ｎ）成分が定数である（ｎ×ｎ）型対角行列Ｔ（Ｖ）を用い、Ｔ（Ｖ）の左からＵを乗じてＳ（Ｖ）＝ＵＴ（Ｖ）とする第３の計算工程と、
１列以上の各列に２個以上のｖの多項式ｇｋ（Ｖ）（ｋ以下の添字をもつｖｊ（ｊ≦ｋ）を含見、当該ｋは列を表す添字である。）を含み、それ以外の要素がすべて０である（ｎ×ｎ）型行列Ｎ（Ｖ）をＳ（Ｖ）に加えたものをＦ（Ｖ）とする第４の計算工程と、
前記Ｆ（Ｖ）の左からＣを乗じてＤ（Ｖ）＝ＣＦ（Ｖ）とし、このとき前記Ｄ（Ｖ）は前記ｇｋ（Ｖ）を含まず、ｒｉ行目だけに注目した際に上三角行列になるようにする第５の計算工程と、
Ｇ（Ｘ）＝ＢＦ（Ｖ）ＶmodＰとし、Ｙ＝Ｇ（Ｘ）modＰにより暗号文Ｙ＝（ｙ１，ｙ２，・・・，ｙｎ）Ｔを得る暗号化工程と
を実行させることを特徴とするプログラム。
【請求項５】
コンピュータに、
素数Ｐを定め、有限体ＦＰ上において、平文をＸ＝（ｘ１，ｘ２，・・・，ｘｍ）Ｔ（Ｔはベクトルの転置を表す）とし、（ｍ×ｍ）型正則行列Ａ、（ｎ×ｎ）型正則行列Ｂ（ｍ＜ｎ）、（ｎ×ｍ）型行列Ｑ（ただし、（ｍ×ｎ）型で（１，１）成分および（ｍ，ｎ）成分が０でない階段行列をＱ’＝［（ｑ’ｉ，ｊ）］（ｉ＝１，２，・・・，ｍ、ｊ＝１，２，・・・，ｎ）としたとき、行列Ｑ＝［（ｑｊ，ｉ）］は、（ｑｊ，ｉ）＝（ｑ’ｍ−ｉ＋１，ｎ−ｊ＋１）で表される。）を用い、前記行列Ｑの第ｉ列を下から見ていき、初めて０でない要素が含まれる行をｒｉ行とした仮定した場合、前記Ｘの左からＡを乗じてＶ’＝ＡＸとする第１の計算工程と、
前記Ｖ’の左からＱを乗じてＶ＝ＱＶ’とする第２の計算工程と、
（ｎ×ｎ）型定数行列Ｃ，Ｕと、（ｋ，ｋ）成分（１≦ｋ≦ｎ）がｖｋ＋１，ｖｋ＋２，・・・，ｖｎの多項式、（ｎ，ｎ）成分が定数である（ｎ×ｎ）型対角行列Ｔ（Ｖ）を用い、Ｔ（Ｖ）の左からＵを乗じてＳ（Ｖ）＝ＵＴ（Ｖ）とする第３の計算工程と、
１列以上の各列に２個以上のｖの多項式ｇｋ（Ｖ）（ｋ以下の添字をもつｖｊ（ｊ≦ｋ）を含見、当該ｋは列を表す添字である。）を含み、それ以外の要素がすべて０である（ｎ×ｎ）型行列Ｎ（Ｖ）をＳ（Ｖ）に加えたものをＦ（Ｖ）とする第４の計算工程と、
前記Ｆ（Ｖ）の左から前記（ｎ×ｎ）型定数行列Ｃを乗じてＤ（Ｖ）＝ＣＦ（Ｖ）とし、このとき前記Ｄ（Ｖ）は前記ｇｋ（Ｖ）を含まず、ｒｉ行目だけに注目した際に上三角行列になるようにする第５の計算工程と、
Ｇ（Ｘ）＝ＢＦ（Ｖ）ＶmodＰとし、前記Ｇ（Ｘ）、前記素数Ｐ、サイズｍを公開鍵として、当該Ｙ＝Ｇ（Ｘ）modＰにより暗号文Ｙ＝（ｙ１，ｙ２，・・・，ｙｎ）Ｔを得る暗号化工程と、
を実行させることを特徴とするプログラム。
【請求項６】
コンピュータに、
請求項５記載の公開鍵暗号化方法によって暗号化された暗号文Ｙ＝（ｙ１，ｙ２，・・・，ｙｎ）Ｔを復号する復号化方法において、
前記（ｍ×ｍ）型正則行列Ａ、前記（ｎ×ｎ）型正則行列Ｂ（ｍ＜ｎ）、前記（ｎ×ｎ）型定数行列Ｃ、前記Ｄ（Ｖ）、前記（ｎ×ｍ）型行列Ｑ、前記ｒｉを秘密鍵として取得する工程と
前記秘密鍵Ｂの逆行列を前記暗号文Ｙ＝Ｇ（Ｘ）の両辺の左から乗じて、
Ｂ−１Ｙ＝Ｆ（Ｖ）Ｖとする第６の計算工程と、
Ｄ（Ｖ）＝ＣＦ（Ｖ）を用いて、ＣＢ−１Ｙ＝ＣＦ（Ｖ）Ｖ＝Ｄ（Ｖ）Ｖとし、ＣＢ−１Ｙ＝Ｄ（Ｖ）Ｖの式ｎ個のうち、第ｒｉ番目の式ｍ個とＶ＝ＱＶ’より得られる連立方程式を解いてＶ，Ｖ’を求める第７の計算工程と、
Ｘ＝Ａ−１Ｖ’より復号文Ｘを得る復号化工程と、
を実行させることを特徴とするプログラム。
【請求項７】
請求項４〜６のいずれかに記載のプログラムを記録したことを特徴とするコンピュータ読取可能な情報記録媒体（コンパクトディスク、フレキシブルディスク、ハードディスク、光磁気ディスク、ディジタルビデオディスク、磁気テープ、または、半導体メモリを含む。）。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、暗号化方法、公開鍵暗号化方法、コンピュータに当該方法を実行させるプログラム、及び当該プログラムを記録したコンピュータ読取可能な情報記録媒体に関する。
【背景技術】
【０００２】
従来から、公開鍵と秘密鍵を用いる鍵暗号システムが利用されている。このような公開鍵暗号システムは、通信セキュリティの必要性が高まっている今日、ますます注目を浴びる分野となっている。
【０００３】
このほか、公開鍵による暗号化や秘密鍵による復号化自体の計算量が大きいために、メッセージを共有鍵で暗号化し、この共有鍵を公開鍵で暗号化して、両者を伝送し、受け取った側では暗号化された共有鍵を秘密鍵で復号し、復号された共有鍵を用いてメッセージを復号する手法も広く使われている。尚、当該背景技術に関連した先行技術文献情報として以下の非特許文献１がある。必要があれば参照されたい。
【０００４】
ところで、今日のセキュリティ意識の高まりにともない、公開鍵暗号システムにおいては、セキュリティが高いシステムがますます求められるようになっている。公開鍵暗号システムは、共通鍵暗号で問題となる鍵配送の問題や鍵の管理の問題などを解決する手段として普及した暗号システムであり、公開鍵暗号システムの代表的なものとして、ＲＳＡ（Ｒｉｖｅｓｔ，Ｓｈａｍｉｒ，Ａｄｌｅｍａｎ）暗号、ＥｒＧａｍａｒ暗号、楕円曲線暗号（楕円ＥｒＧａｍａｒ暗号）などが挙げられる。
【０００５】
これらの暗号は、いずれも素因数分解の困難性もしくは離散対数問題の求解の困難性に基づいている。ＲＳＡ暗号、Ｒａｂｉｎ暗号は素因数分解の難しさに、ＥｒＧａｍａｒ暗号、楕円曲線暗号は、有限体の乗法群、有限体上の楕円曲線上の離散対数問題の難しさに基づいている。
【０００６】
したがって、ＲＳＡ暗号やＲａｂｉｎ暗号は、公開鍵を素因数分解することができれば、完全に解読することができ、ＥｒＧａｍａｒ暗号、楕円曲線暗号は、それぞれの暗号の安全性の基になる離散対数問題が解ければ完全に解読することができる。現在のコンピュータでは、上記の暗号システムの解読は計算量的に不可能とされているが、量子コンピュータの出現が現実のものとなると、これらの安全性は崩壊する。
【非特許文献１】辻井重男，笠原正雄編著，「暗号と情報セキュリティ」，株式会社昭晃堂，１９９０年３月２９日初版１刷発行
【発明の開示】
【発明が解決しようとする課題】
【０００７】
従来の暗号システムは素因数分解および離散対数問題の求解の計算量的な難しさに安全性を委ねているが、その問題が解けてしまえば、これらの暗号は完全に解読されてしまう。また、今後、量子コンピュータが実用の域に達した場合、素因数分解の困難性および離散対数問題の求解困難性に基づいているこれらの暗号システムの安全性は保障されない。そのため、耐量子コンピュータ公開鍵暗号の構築のための一歩として、素因数分解や離散対数問題の求解困難性に依拠しないタイプの公開鍵暗号の構成を考えるべきである。
【０００８】
本発明は、素因数分解の困難性や離散対数問題の求解困難性に依拠しない公開鍵暗号化方法、コンピュータに当該方法を実行させるプログラム、及び当該プログラムを記録したコンピュータ読取可能な情報記録媒体を提供することを目的としている。
【課題を解決するための手段】
【０００９】
本暗号化方法は、個々の行列を秘密鍵とし、それらを合成して生成された関数を公開鍵とするものである。これは、個々の関数の逆行列が比較的容易に求めることができるとしても、それらを掛け合わせるなどして合成された関数の逆行列を求めることが極めて困難であるという特徴を利用したものである。
【００１０】
さらに、本方法では、公開鍵には組み込まない秘密鍵を用意し、それを本暗号系の落とし戸とする。
【００１１】
素数Ｐを定め、有限体ＦＰ上において、平文をＸ＝（ｘ１，ｘ２，・・・，ｘｍ）Ｔ（Ｔはベクトルの転置を表す）とし、（ｍ×ｍ）型正則行列Ａ、（ｎ×ｎ）型正則行列Ｂ（ｍ＜ｎ）、（ｎ×ｍ）型行列Ｑを用意する。ただし、（ｍ×ｎ）型で（１，１）成分および（ｍ，ｎ）成分が０でない階段行列をＱ’＝［（ｑ’ｉ，ｊ）］（ｉ＝１，２，・・・，ｍ、ｊ＝１，２，・・・，ｎ）としたとき、行列Ｑ＝［（ｑｊ，ｉ）］は、（ｑｊ，ｉ）＝（ｑ’ｍ−ｉ＋１，ｎ−ｊ＋１）で表される。ここで、行列Ｑの第ｉ列を下から見ていき、初めて０でない要素が含まれる行をｒｉ行と呼ぶ。平文Ｘの左から（ｍ×ｍ）型正則行列Ａを乗じてＶ’＝ＡＸとし、さらに左からＱを乗じてＶ＝ＱＶ’とする。（ｎ×ｎ）型定数行列Ｃ，Ｕと、（ｋ，ｋ）成分（１≦ｋ≦ｎ）がｖｋ＋１，ｖｋ＋２，・・・，ｖｎの多項式、（ｎ，ｎ）成分が定数である（ｎ×ｎ）型対角行列Ｔ（Ｖ）を用意する。（ｎ×ｎ）型対角行列Ｔ（Ｖ）の左からＵを乗じてＳ（Ｖ）＝ＵＴ（Ｖ）とする。さらに、１列以上の各列に２個以上のｖの多項式ｇｋ（Ｖ）（ｋは列を表す添字）を含み、それ以外の要素がすべて０である（ｎ×ｎ）型行列Ｎ（Ｖ）をＳ（Ｖ）に加えたもの（Ｓ（Ｖ）＋Ｎ（Ｖ））をＦ（Ｖ）とする。ただし、ｇｋ（Ｖ）はｋ以下の添字をもつｖｊ（ｊ≦ｋ）を含む。Ｆ（Ｖ）の左からＣを乗じてＤ（Ｖ）＝ＣＦ（Ｖ）とし、このときＤ（Ｖ）はｇｋ（Ｖ）を含まず、ｒｉ行目だけに注目した際に上、三角行列になるようにする。Ａ，Ｂ，Ｃ，Ｄ（Ｖ），Ｑ，ｒｉを秘密鍵とし、秘密鍵Ｃ（これを持駒秘密行列と呼ぶ）以外の秘密鍵を掛け合わせて、Ｇ（Ｘ）＝ＢＦ（Ｖ）ＶmodＰを構成し、このＧ（Ｘ）と素数Ｐ、サイズｍを公開鍵とする。暗号文Ｙ＝（ｙ１，ｙ２，・・・，ｙｎ）ＴはＹ＝Ｇ（Ｘ）modＰにより得られる。
【００１２】
上式を用いて暗号化された暗号文Ｙは、Ｙ＝Ｇ（Ｘ）modＰの両辺に左から秘密鍵Ｂの逆行列を乗じ、Ｂ−１Ｙ＝Ｆ（Ｖ）Ｖとし、さらに両辺の左から持駒秘密行列Ｃを乗じると、Ｄ（Ｖ）＝ＣＦ（Ｖ）を利用することで、ＣＢ−１Ｙ＝Ｄ（Ｖ）Ｖ’となり、ＣＢ−１Ｙ＝Ｄ（Ｖ）Ｖ’の式ｎ個のうち、第ｒｉ番目の式ｍ個とＶ＝ＱＶ’より得られる連立方程式を解いてＶ，Ｖ’を求めれば、Ｘ＝Ａ−１Ｖ’から復号することができる。
【発明の効果】
【００１３】
本発明に係る暗号化方法によれば素因数分解や離散対数問題の困難性に依拠しないタイプの新しい公開鍵暗号システムが構築できる。
【発明を実施するための最良の形態】
【００１４】
以下の本発明の一実施の形態を説明する。なお、以下に説明する実施形態は説明のためのものであり、本発明の範囲を制限するものではない。したがって、当業者であればこれらの各要素もしくは全要素をこれと均等なものに置換した実施形態を採用することが可能であるが、これらの実施形態も本発明の範囲に含まれる。
【００１５】
本発明の実施形態を簡単な値を用いて説明する。素数P＝７と定め、有限体ＦＰ上とする。サイズｍ＝３，ｎ＝５とし、平文をＸ＝（ｘ１，ｘ２，ｘ３）Ｔとする。秘密鍵として、数１、
2005173294.tif 000002
数２、
2005173294.tif 000003
数３、
2005173294.tif 000004
数４、
2005173294.tif 000005
また行列Ｃ，Ｆ（Ｖ）より数５、
2005173294.tif 000006
を用意する。
【００１６】
また、計算を簡単にするため（ｎ×ｎ）型行列Ｂを単位行列とする。さらに、数６、
2005173294.tif 000007
数７
2005173294.tif 000008
の計算処理を実行すれば、ｖ１＝ｖ１’＋３ｖ２’＋５ｖ３’，ｖ２＝４ｖ２’＋２ｖ３’，ｖ３＝ｖ２’＋ｖ３’，ｖ４＝６ｖ３’，ｖ５＝ｖ３’が得られる。
【００１７】
一方、Ｂ，Ｖ，Ｆ（Ｖ）より公開鍵Ｇ（Ｘ）＝ＢＦ（Ｖ）ＶmodＰが生成される。暗号文Ｙ＝（ｙ１，ｙ２，ｙ３，ｙ４，ｙ５）Ｔは公開鍵、素数Ｐ、サイズｍ、Ｙ＝Ｇ（Ｘ）より生成され、平文をＸ＝（２，１，３）Ｔとすれば、暗号文ＹはＹ＝（２，１，１，３，６）Ｔとなる。
【００１８】
上記の方法により生成された暗号文の復号は以下の手順で行う。ＣＢ−１Ｙ＝ＣＦ（Ｖ）Ｖ＝Ｄ（Ｖ）Ｖを用いれば、左辺は数８、
2005173294.tif 000009
右辺は数９
2005173294.tif 000010
となり、
ＣＢ−１Ｙ＝Ｄ（Ｖ）Ｖのｎ個の式のうち、第ｒｉ番目の式とＶ＝ＱＶ’より得られるＤ（Ｖ）Ｖに基づいて連立方程式を解くと、数１０
2005173294.tif 000011
が得られる。
【００１９】
数式（３）よりｖ５＝４、数式（８）よりｖ３’＝４、数式（７）よりｖ４＝３、数式（２）よりｖ３＝５、数式（６）よりｖ２’＝１、数式（５）よりｖ２＝５、数式（１）よりｖ１＝０、数式（４）よりｖ１’＝５となるので、最後にＸ＝Ａ−１Ｖ’とすれば復号ができる。