(57)【要約】【課題】  多変数多項式公開鍵暗号に属する安全な暗号方式を用いた暗号装置等を提供する。【解決手段】  暗号装置は、核となる暗号方式として多変数多項式公開鍵暗号であるSquare方式を採用し、署名方式であるRainbow方式を独自に修正してSquareのサイズを拡大し、さらに、Plus方式を採用してRainbow方式の安全性を確保することにより、安全で、さらに、処理効率の良い暗号方式を用いた暗号装置等を構成することができる。また、復号装置は、Square方式により一部を復号化し、その復号結果を用いてRainbow方式により残りの部分の復号化を行うことにより、復号文を得る。これにより、公開鍵暗号基盤を、新たな安全性根拠を持つ耐量子暗号で構成することができるようになる。【選択図】  図１
2017037281.tif 000002
【特許請求の範囲】
【請求項１】
平文を暗号化して暗号文を得る暗号装置であって、
多変数多項式写像を用いて暗号化を行う核暗号処理と、前記核暗号処理のサイズを拡大する拡大処理と、前記拡大処理の安全性を確保する安全性確保処理とを用いて前記平文を暗号化して前記暗号文を得る暗号手段を備える暗号装置。
【請求項２】
前記核暗号処理は、Square処理であり、
前記拡大処理は、変数よりも多い方程式による写像であり、
前記安全性確保処理は、異なる数の方程式を用いたベクトル値写像であり、
前記暗号手段は、多変数多項式写像の変数に対して値を代入することにより、前記暗号化を実行する、請求項１記載の暗号装置。
【請求項３】
前記暗号手段は、公開鍵Ｆ＝Ａ2○Ｇ○Ａ1を用いて、前記平文Ｍに対する前記暗号文Ｃ＝Ｆ（Ｍ）を計算する、請求項１又は２に記載の暗号装置。
ここで、
Ｇは、中心写像であって、２次多変数多項式写像ＧSと、複数の層のそれぞれでベクトル値多変数２次多項式写像を構成して得られる写像ＧRと、複数の多変数２次多項式を並べて得られるベクトル値写像ＧPに対して、Ｇ＝ＧS||ＧR||ＧPにより得られるものであり、
Ａ1は、アファイン埋め込み写像であり、
Ａ2は、アファイン同型写像である。
【請求項４】
請求項１から３のいずれかに記載の暗号装置により得られた前記暗号文を復号して復号文を得る復号装置であって、
前記核暗号処理を用いた暗号化に対応する復号処理により一部を復号化し、その復号結果を用いて前記拡大処理に対応する復号処理により残りの部分の復号化を行うことにより、前記復号文を得る復号手段を備える復号装置。
【発明の詳細な説明】
【技術分野】
【０００１】
本願発明は、暗号装置及び復号装置に関し、特に、平文を暗号化して暗号文を得る暗号装置等に関する。
【背景技術】
【０００２】
現在社会で利用される暗号技術の１つに、公開鍵暗号がある。公開鍵暗号は、秘匿通信、電子署名、認証など様々な機会で利用され、特に不特定多数のユーザーが利用するネットワーク社会では必須の技術となっている。現在、公開鍵暗号の基盤となっている技術は、ＲＳＡ暗号と楕円曲線暗号である。しかしながら、この２つの暗号は量子コンピュータに耐性を持たない。そのため、量子コンピュータが普及する前に量子コンピュータに耐性を持つ公開鍵暗号（耐量子暗号）に公開鍵暗号基盤を移行する必要がある。
【０００３】
耐量子暗号の候補としては、格子ベース暗号（例えばNTRU暗号方式など）、コードベース暗号（例えばMcEliece暗号など）、多変数多項式公開鍵暗号、ハッシュベース暗号が知られている。これらは、安全性の数学的根拠の違いによる分類である。
【０００４】
ハッシュベース暗号は、署名方式しか開発されていない。多変数多項式公開鍵暗号では、現在も効率的解読法が知られていない暗号方式として、2014年に提案されたZHFE方式と2013年に提案されたABC方式の２つがある。
【０００５】
Square方式は、2009年に提案された暗号方式である。また、Squareの変形方式であるSquare-Vinegar（署名）方式、Double-Layer  Square方式、Square+方式も知られている（非特許文献１及び２参照）。
【先行技術文献】
【非特許文献】
【０００６】
【非特許文献１】Clough  C.、外４名著，Square, a New Multivariate Encryption Scheme，CT-RSA'09，Springer LNCS vol．5473，pp．252〜264，2009.
【非特許文献２】Clough  C.、他１名著，Secure Variants of Square Encryption Scheme", PQCrypto'10, Springer LNCS vol. 6061, pp. 154〜164, 2010.
【非特許文献３】Ding, J.、外１名著，Rainbow, a New Multivariable Polynomial Signature Scheme，ACNS'05, Springer LNCS vol. 3531, pp. 164〜175,2005.
【非特許文献４】Ding, J.、外１名著，Inoculating Multivariate Schemes Against Differential Attacks", PKC'06, Springer LNCS vol. 3958, pp. 290〜301, 2006.
【発明の概要】
【発明が解決しようとする課題】
【０００７】
現在、知られている耐量子暗号の暗号方式としては、NTRU暗号、McEliece暗号などが知られているが、処理効率、鍵長などの解決すべき課題がある。また、将来到来しうる量子コンピュータの普及に備え、異なる安全性の根拠を持つ耐量子暗号の暗号方式を複数用意する必要がある。そのため、格子ベース暗号やコードベース暗号とは安全性の根拠が異なる、多変数多項式公開鍵暗号の安全な暗号方式が求められている。
【０００８】
多変数多項式公開鍵暗号では、ZHFE方式とABC方式という２つの暗号方式が開発されている。しかしながら、ZHFE方式とABC方式は、共に処理効率に難がある。また、提案されて間もないこともあり、これらに対する安全性解析は不十分な状況である。
【０００９】
他方、Square方式、並びに、Squareの変形方式であるSquare-Vinegar（署名）方式、Double-Layer  Square方式、Square+方式は、処理効率が良いが、いずれも効率的解読法が知られている。
【００１０】
そこで、本願発明は、多変数多項式公開鍵暗号に属する安全な暗号方式を用いた暗号装置等を提供することを目的とする。
【課題を解決するための手段】
【００１１】
本願発明の第１の観点は、平文を暗号化して暗号文を得る暗号装置であって、前記平文を、多変数多項式写像を用いて暗号化を行う核暗号処理と、前記中心写像のサイズを拡大する拡大処理と、前記拡大処理の安全性を確保する安全性確保処理とを用いて暗号化して前記暗号文を得る暗号手段を備えるものである。
【００１２】
本願発明の第２の観点は、第１の観点の暗号装置であって、前記核暗号処理は、Square処理であり、前記拡大処理は、変数よりも多い方程式による写像であり、前記安全性確保処理は、異なる数の方程式を用いたベクトル値写像であり、前記暗号手段は、多変数多項式写像の変数に対して値を代入することにより、前記暗号化を実行するものである。
【００１３】
本願発明の第３の観点は、第１又は第２の観点の暗号装置であって、前記暗号手段は、公開鍵Ｆ＝Ａ2○Ｇ○Ａ1を用いて、前記平文Ｍに対する前記暗号文Ｃ＝Ｆ（Ｍ）を計算するものである。ここで、Ｇは、中心写像であって、２次多変数多項式写像ＧSと、複数の層のそれぞれでベクトル値多変数２次多項式写像を構成して得られる写像ＧRと、複数の多変数２次多項式を並べて得られるベクトル値写像ＧPに対して、Ｇ＝ＧS||ＧR||ＧPにより得られるものであり、Ａ1は、アファイン埋め込み写像であり、Ａ2は、アファイン同型写像である。
【００１４】
本願発明の第４の観点は、第１から第３のいずれかの観点の暗号装置により得られた前記暗号文を復号して復号文を得る復号装置であって、前記核暗号処理に対応する復号処理により一部を復号化し、その復号結果を用いて前記拡大処理に対応する復号処理により残りの部分の復号化を行うことにより、前記復号文を得る復号手段を備えるものである。
【００１５】
なお、本願発明を、第１から第３のいずれかの観点の暗号装置における暗号方法として捉えてもよく、第３の観点の復号装置における復号方法として捉えてもよく、また、コンピュータを、第１又は第２の観点の暗号装置や第３の観点の復号装置として機能させるためのプログラムやこのプログラムを記録するコンピュータ読み取り可能な記録媒体として捉えてもよい。
【発明の効果】
【００１６】
本願発明の各観点によれば、拡大処理により、多変数多項式写像による核暗号処理の安全性を強化し、さらに、安全性確保処理により追加する拡大処理の安全性を強化することにより、多変数多項式公開鍵暗号に属する安全な暗号処理を実現することができる。
【００１７】
特に、本願発明の第２の観点にあるように、核となる暗号方式としてSquare方式（非特許文献１及び２参照）を利用することにより、処理効率の良い多変数多項式公開鍵暗号の暗号方式を構成することができる。
【００１８】
Square方式は効率的解読法が知られているため、そのままでは利用できない。そのため、Rainbow（署名）方式（非特許文献３参照）と呼ばれる署名（変数）領域の拡大手法を利用することにより、安全性を強化する。ただし、Rainbow方式は、本来、署名方式で利用されるため、暗号方式では通常利用できない。より具体的には、暗号文を復号化したときに元の平文に戻らない可能性がある。そこで、Rainbow方式を用いた復号化でも元の平文に戻るような改良方法を取り入れる。
【００１９】
Square方式にRainbow方式を追加することで、Squareの安全性を補強することができる。ただし、追加したRainbow方式に対する安全性を考慮する必要がある。そのため、プラス手法（非特許文献４参照）と呼ばれる安全性の強化手法を取り入れる。
【００２０】
本願発明の第２の観点によれば、Square方式を核とすることにより処理効率の良い多変数多項式公開鍵暗号とすることができる。これをRainbow方式によりサイズを拡張することによりSquareの安全性を確保する。さらに、Plus手法を採用してRainbow方式に対する安全性を強化する。Square方式は処理効率が良く、また、Rainbow方式も処理効率が良い。プラス手法は復号処理に全く影響を与えないので、全体としても処理効率の良い方式が構成できる。よって、本願発明の第２の観点によれば、多変数多項式公開鍵暗号に属し、安全で、さらに、処理効率の良い暗号方式を用いた暗号装置等を構成することができる。
【００２１】
本願発明は、量子コンピュータが普及した将来や現在の公開鍵暗号基盤に問題が生じた場合に、公開鍵暗号基盤の一つとして利用されることを想定している。公開鍵暗号基盤として、秘匿通信、電子署名、認証などに用いられる。本願発明によれば、格子ベース暗号のNTRU暗号やコードベース暗号のMcEliece暗号に加えて、新たな公開鍵暗号基盤とすることができる。よって、本願発明によれば、公開鍵暗号基盤を、異なる安全性根拠を持つ複数の耐量子暗号で構成することができるようになる。
【図面の簡単な説明】
【００２２】
【図１】本願発明の実施の形態に係る（ａ）暗号装置及び（ｂ）復号装置の構成の一例を示すブロック図である。
【図２】図１の暗号装置１及び復号装置１１の動作の一例を示すフロー図である。
【発明を実施するための形態】
【００２３】
以下、本願発明の実施の形態について説明する。なお、本願発明の実施の形態は、下記の実施例に限定されるものではない。
【実施例】
【００２４】
本願発明の概要を説明する。本願発明において提案する暗号方式（以下、「ＳＲＰ方式」ともいう。）は、以下の３つの部分からなる。（１）Square部分（本願請求項の「核暗号処理」の一例）と、（２）Rainbow部分（本願請求項の「拡大処理」の一例）と、（３）Plus部分（本願請求項の「安全性確保処理」の一例）である。
【００２５】
（１）Square部分は、核となる暗号方式である。（２）Rainbow部分で、Squareのサイズを拡大する。（３）Plus部分で、安全性を強化する。暗号化は、多変数多項式写像の変数に対する値の代入で実行される。一方、復号化は、Square方式による復号化で一部を初めに復号化し、その復号結果を用いてRainbow方式で残りの部分の復号化を行うというのが基本アイデアとなる。
【００２６】
続いて、ＳＰＲ方式の一般的な構成について、数学的に説明をする。
【００２７】
ｑを素数の冪とするとき、位数ｑを持つ可換体が同型を除いてただ一つ存在する。それをＧＦ（ｑ）と表す。
【００２８】
ベクトル空間ＧＦ（ｑ）l_1からベクトル空間ＧＦ（ｑ）l_2への写像ψがアファイン写像であるとは、ＧＦ（ｑ）上のあるｌ2行ｌ1列の線形行列ＡとＧＦ（ｑ）l_2内のあるベクトルｖが存在し、写像ψが式(1)の形で表されるときをいう。
【００２９】
また、アファイン写像が単射写像であるときアファイン埋め込み写像という。アフィン写像が全単射写像であるときアファイン同型写像という。
【００３０】
【数１】
2017037281.tif 000003
【００３１】
まず、以下のパラメータを選択する。
Ｋ＝ＧＦ（ｑ）：奇標数の有限体（ｑ≡３mod４）
ｄ：Squareで用いる拡大体の次元（奇数）
ｈ：層数
ｏ1，…，ｏh：各層のオイル変数の個数
ｒ：復号成功確率を決める整数
ｓ：Plus部分の方程式数
ｌ：秘密鍵となるアフィン写像の（終域の次元）−（定義域の次元）
φ：ＧＦ（ｑd）→Ｋd：Ｋ上の線形同型写像
【００３２】
ｈ＝０とすると、ＳＰＲ方式は、Square+方式と一致する。これに加えて、ｓ＝０とするとオリジナルのSquare方式と一致する。したがって、ＳＰＲ方式では、常に、ｈ≧１、ｏ1≧１となるようにパラメータを選択する。
【００３３】
続いて、鍵生成について説明する。ｎ、ｍ及びｎ'を、それぞれ、式(2)、(3)及び(4)とする。ＳＰＲ方式の公開鍵となるベクトル値多変数多項式写像の変数の個数がｎ、方程式数がｍとなる。
【００３４】
【数２】
2017037281.tif 000004
【００３５】
Ｋn'上定義される３種類のベクトル値多変数２次多項式写像ＧS、ＧR、ＧPを次のように構成する。
【００３６】
ＧS：Ｋn'→Ｋdは、以下のように構成する。まず、Ｇ'S：Ｋd→Ｋdを、式(5)のように構成する。続いて、ＧSを、Ｇ'Sの自然な拡張として、式(6)により定義する。
【００３７】
【数３】
2017037281.tif 000005
【００３８】
ＧR：Ｋn'→Ｋo_1+…+o_h+hrは、以下のように構成する。各層ｋ＝１，…，ｈに対して、ｖk＝ｄ＋ｏ1＋…＋ｏk-1とし、Ｖk＝｛１，２，…，ｖk｝、Ｏk＝｛ｖk＋１，…，ｖk＋ｏk｝とする。まず、ベクトル値多変数２次多項式写像ＧR,k：Ｋd+o_1+…+o_h→Ｋo_k+rを構成する。ＧR,kは、ｏk＋ｒ個の多変数２次多項式成分を持つが、各成分は式(7)の形で選択する。ただし、αi,j、βi,j、γi、ηはＫの元であり、ＧR,kの成分ごとにランダムに選択される。ＧRを、式(8)により、ＧR,kを並べて一体とみなして定義する。
【００３９】
【数４】
2017037281.tif 000006
【００４０】
ＧP：Ｋn'→Ｋsは、以下のように構成する。ＧPは、ランダムな係数を持つ式(9)の形の多変数２次多項式をｓ個選択し、それらを並べてベクトル値写像にしたものである。ここで、αi,j、βi、γ∈Ｋである。
【００４１】
【数５】
2017037281.tif 000007
【００４２】
ベクトル値多変数２次多項式写像Ｇ：Ｋn'→Ｋmを、式(10)で定義する。
【００４３】
【数６】
2017037281.tif 000008
【００４４】
次に、以下の２つをランダムに構成する。
・アファイン埋め込み写像Ａ1：Ｋn→Ｋn'
・アファイン同型写像Ａ2：Ｋm→Ｋm
【００４５】
Ｆを式(11)とおく。ここで、演算○は、合成写像である。Ｆは、ＫnからＫmへの多変数２次多項式写像となる。このとき、Ｇ、Ａ1及びＡ2を秘密鍵とし、Ｆを公開鍵とする。
【００４６】
【数７】
2017037281.tif 000009
【００４７】
暗号化は、以下のように実現することができる。平文Ｍは、Ｋnの元と同一視する。Ｍに対する暗号文Ｃは、式(12)で得られる。
【００４８】
【数８】
2017037281.tif 000010
【００４９】
復号化は、以下のように実現することができる。Ｃ＝（ｃ1,…,ｃm）∈Ｋmを暗号文とする。
STEP 1  Ｂ＝（ｂ1,…,ｂm）＝Ａ2-1（Ｃ）を計算する。
STEP 2  Ｂの一部ＢS＝（ｂ1,…,ｂd）に対し、Ｂ0＝φ-1（ＢS）を計算する。
STEP 3  Ｒ＝±Ｂ0(q^d+1)/4、Ｄ0＝φ（Ｒ）を計算する。
STEP 4  ｋは１からｈまで順に動き、以下を実行する。
(4-1) Ｂk＝（ｂm_(k-1)+1,…,ｂm_k）（ただし、ｍt:＝ｄ＋ｏ1＋…＋ｏt＋ｔｒ（ｔ＝１，２，…））に対し、Ｘk＝（ｘv_(k-1)+1,…,ｘv_k）に関する線型方程式Ｇk（Ｄk-1,Ｘk）＝Ｂkを立てる。
(4-2) 線型方程式を解き、その解をＤkとおく。
STEP 5  Ｄ＝Ｄ0||Ｄ1||…||Ｄhとおく。
STEP 6  Ｍ'＝Ａ1-1（Ｄ）を計算する。Ｍ'が復号文である。
【００５０】
トイ・イクザンプルを説明する。以下のパラメータの場合を考える。
Ｋ＝ＧＦ（３１）：奇標数の有限体
ｄ＝３：Square方式で用いる拡大体の次元
ｈ＝２：層数
（ｏ1，ｏ2）＝（３，２）：各層のオイル変数の個数
ｒ＝１：復号成功確率を決める整数
ｓ＝１：Plus部分の方程式数
ｌ＝３：秘密鍵となるアフィン写像の（終域の次元）−（定義域の次元）
【００５１】
このとき、公開鍵ＦはＫ5からＫ11へのベクトル値多変数２次多項式写像となる。すなわち、Ｆの成分Ｆk（ｋ＝１，２，…，１１）は、式(13)と表される。
【００５２】
【数９】
2017037281.tif 000011
【００５３】
数１０は、公開鍵Ｆ（Ｆ1，…，Ｆ11）の一例である。
【００５４】
【数１０】
2017037281.tif 000012
【００５５】
数１１は、この公開鍵を用いた平文Ｍと暗号文Ｃの一例である。
【００５６】
【数１１】
2017037281.tif 000013
【００５７】
続いて、実用的なパラメータの実行時間の一例について説明する。以下のパラメータを考える。これは、80ビット安全相当である。
Ｋ＝ＧＦ（３１）：奇標数の有限体
ｄ＝３３：Square方式で用いる拡大体の次元
ｈ＝１：層数
ｏ1＝３２：各層のオイル変数の個数
ｒ＝１６：復号成功確率を決める整数
ｓ＝５：Plus部分の方程式数
ｌ＝１６：秘密鍵となるアフィン写像の（終域の次元）−（定義域の次元）
【００５８】
このとき、（ｎ，ｍ）＝（４９，８６）となる。異なる平文に対する暗号化と復号化を100 回行ったときの実行時間の平均は、暗号化平均時間が0.75ミリ秒であり、復号化平均時間が1.06ミリ秒であった。実行環境は以下のとおりである。
OS：Microsoft Windows（登録商標） 7 Professional 64bit
CPU：Intel(R) Xeon CPU E31270 @ 3.40GHz
メモリ：16.0GB
Compiler：Cygwin + gcc version 3.4.4
Language：C
【００５９】
ＳＰＲ方式では、Square部分にビッグフィールド手法を、Rainbow部分にシングルフィールド手法を用いており、両手法を混合する構成法を採用している。
【００６０】
また、Rainbow方式を署名方式としては利用せず、暗号方式として利用できるように独自の改良を施して使用している。
【００６１】
Rainbow署名方式は、多変数多項式方式の中では安全性が極めて高く、各層で線型方程式を解くだけでよいために署名生成が効率的であり、署名方式なので全射な一方向関数を用いているものである。
【００６２】
Rainbow署名方式を暗号方式で使うには、２つの問題がある。ランダム変数部分を既存の暗号方式に置き換えるため、どの暗号方式を用いるかという問題と、単射な一方向関数にしなければならないという問題である。
【００６３】
後者の問題について、Rainbowの各層ではｈ変数ｈ方程式の線型方程式を解く。この場合、１／ｑの確率で退化するため、下位は唯一に決まらない。他方、ＳＰＲ方式では、ｈ変数ｈ＋ｒ方程式の線型方程式にすることにより、１／ｑr+1の確率で退化するようにし、高い確率で唯一解を持つようにしている。
【００６４】
前者の問題について、ＳＰＲ方式では、Square方式を採用している。Square方式は、松本今井方式の特別な場合（Ｙ＝Ｘ1＋ｑθのθ＝０のとき）である。しかしながら、他の松本今井方式と異なるふるまいをする。特に、Squareは、グレブナー基底攻撃に強いことが理論的に証明されている。Squareは、復号の効率性を向上させている。
【００６５】
ＳＰＲ方式では、暗号化は、公開鍵の評価計算で行うことができる。復号化は、Ａ1とＡ2の逆写像は簡単に計算できる。Ｇの逆写像が計算できればよい。そのため、最初のｄ成分を用いてSquareの逆像計算を行い、Rainbowを用いて各層のoil変数の値を逐次的に計算することにより、復号成功確率１−ｈ／ｑr+1で解を一意的に定めることができる。
【００６６】
ＳＰＲ方式は、多変数多項式公開鍵暗号に属し、処理効率の良い暗号方式である。多変数多項式公開鍵暗号は、量子コンピュータに耐性を持つため、次世代の公開鍵基盤の有力候補である。ＳＰＲ方式は、秘匿通信などを効率よく実行する次世代暗号として期待される。
【００６７】
続いて、図１及び図２を参照して、本願発明の実施の形態に係る暗号装置及び復号装置の構成及び動作の一例を説明する。図１は、暗号装置及び復号装置の構成の一例を示すブロック図である。図２は、暗号装置及び復号装置の動作の一例を示すフロー図である。
【００６８】
図１（ａ）を参照して、暗号装置１の構成の一例を説明する。暗号装置１は、平文記憶部３と、暗号文記憶部５と、制御部７と、暗号処理部９（本願請求項の「暗号手段」の一例）を備える。平文記憶部３は、平文Ｍを記憶する。暗号文記憶部５は、暗号処理部９が平文Ｍを暗号化して得られた暗号文Ｃを記憶する。制御部７は、暗号装置１の動作を制御する。暗号処理部９は、平文Ｍを暗号化して暗号文Ｍを得るものである。
【００６９】
図２（ａ）を参照して、図１（ａ）の暗号装置１の動作の一例を説明する。制御部７は、平文記憶部３から平文Ｍを読みだす（ステップＳＴＥ１）。暗号処理部９は、式(11)を用いて、Ｃ＝Ｆ（Ｍ）により暗号文Ｃを計算する（ステップＳＴＥ２）。制御部７は、暗号文記憶部７に、暗号文Ｃを書き込む（ステップＳＴＥ３）。
【００７０】
図１（ｂ）を参照して、復号装置１１の構成の一例を説明する。復号装置１１は、暗号文記憶部１３と、復号文記憶部１５と、復号演算部１７（本願請求項の「復号手段」の一例）を備える。暗号文記憶部１３は、暗号文Ｃを記憶する。復号演算部１７は、暗号文Ｃを復号して復号文Ｍ'を得る。復号文記憶部１５は、復号文Ｍ'を記憶する。復号演算部１７は、制御部２１と、Ｂ演算部２３と、Ｂ0演算部２５と、Ｒ演算部２７と、方程式演算部２９と、Ｄ演算部３１と、復号文演算部３３を備える。
【００７１】
図２（ｂ）を参照して、図１（ｂ）の復号装置１１の動作の一例を説明する。制御部２１は、暗号文記憶部１３から、暗号文Ｃを読みだす（ステップＳＴＤ１）。Ｂ演算部２３は、Ｂ＝（ｂ1,…,ｂm）＝Ａ2-1（Ｃ）を計算する（ステップＳＴＤ２）。Ｂ0演算部２５は、Ｂの一部ＢS＝（ｂ1,…,ｂd）に対し、Ｂ0＝φ-1（ＢS）を計算する（ステップＳＴＤ３）。Ｒ計算部２７は、Ｒ＝±Ｂ0(q^d+1)/4、及び、Ｄ0＝φ（Ｒ）を計算する（ステップＳＴＤ４）。制御部２１は、ｋを１にする（ステップＳＴＤ５）。方程式演算部２９は、Ｂk＝（ｂm_(k-1)+1,…,ｂm_k）（ただし、ｍt:＝ｄ＋ｏ1＋…＋ｏt＋ｔｒ（ｔ＝１，２，…））に対し、Ｘk＝（ｘv_(k-1)+1,…,ｘv_k）に関する線型方程式Ｇk（Ｄk-1,Ｘk）＝Ｂｋを立てる（ステップＳＴＤ６）。方程式演算部２９は、線型方程式を解き、その解をＤkとおく（ステップＳＴＤ７）。制御部２１は、ｋがｈ以上であるか否かを判断する（ステップＳＴＤ８）。ｋがｈ未満であるならば、制御部２１は、ｋを１増加し、ステップＳＴＤ６に戻る（ステップＳＴＤ９）。ｋがｈ以上であるならば、Ｄ計算部３１は、Ｄ＝Ｄ0||Ｄ1||…||Ｄhとおく（ステップＳＴＤ１０）。そして、復号文演算部３３は、Ｍ'＝Ａ1-1（Ｄ）を計算する（ステップＳＴＤ１１）。制御部２１は、Ｍ'を復号文として復号文記憶部１５に記憶する（ステップＳＴＤ１２）。
【符号の説明】
【００７２】
１  暗号装置、３  平文記憶部、５  暗号文記憶部、７  制御部、９  暗号処理部、１１  復号装置、１３  暗号文記憶部、１５  復号文記憶部、１７  復号演算部、２１  制御部、２３  Ｂ演算部、２５  Ｂ0演算部、２７  Ｒ演算部、２９  方程式演算部、３１  Ｄ演算部、３３  復号文演算部
【図１】
2017037281.tif 000014
【図２】
2017037281.tif 000015