(57)【要約】      （修正有）【課題】ナップザック暗号には低密度攻撃が知られており、密度によって解読が可能なことが知られている。したがって、ナップザック暗号の安全性をさらに高めることが課題である。また、公開鍵からの秘密鍵の露呈を防止することにある。【解決手段】入力された暗号文をモジュラ変換し、互いに素な法Ｌ１，Ｌ２での剰余を求め、各剰余をナップザック暗号の中間平文と見なして部分鍵を用いて部分的に復号し、復号結果を連接し、逆プリコーディングする。中間平文を部分鍵で各々部分的に復号するので、部分鍵やそれに同等な鍵が露呈する可能性をさらに小さくできる。【選択図】図３
2008009051.tif 000002
【特許請求の範囲】
【請求項１】
入力された暗号文に対し、少なくとも、第１の法に対する第１の剰余と第２の法に対する第２の剰余とを、電子的に剰余演算する剰余演算部と、
少なくとも、前記第１の剰余を第１の部分鍵により電子的にかつ部分的に復号すると共に、前記第２の剰余を第２の部分鍵により電子的にかつ部分的に復号する部分復号部を設け、ここで前記第１の部分鍵及び第２の部分鍵は各々、ナップザック暗号の復号用の所定の性質を備えた数列からなる鍵部分と、乱数列からなる乱数部分とを含むベクトルであり、
少なくとも、前記第１の部分鍵による部分的な復号結果と、前記第２の部分鍵による部分的な復号結果とを接続して平文に復号する接続部、をさらに設けた、暗号通信装置。
【請求項２】
入力された暗号文を中間平文へ電子的にモジュラ変換するモジュラ変換部をさらに設けて、モジュラ変換後の中間平文を前記剰余演算部へ入力するようにしたことを特徴とする、請求項１の暗号通信装置。
【請求項３】
入力された暗号文に対し、少なくとも、第１の法に対する第１の剰余と第２の法に対する第２の剰余とを、電子的に剰余演算し、
少なくとも、前記第１の剰余を第１の部分鍵により電子的にかつ部分的に復号すると共に、前記第２の剰余を第２の部分鍵により電子的にかつ部分的に復号し、ここで前記第１の部分鍵及び第２の部分鍵は各々、ナップザック暗号の復号用の所定の性質を備えた数列からなる鍵部分と、乱数列からなる乱数部分とを含むベクトルであり、
少なくとも、前記第１の部分鍵による部分的な復号結果と、前記第２の部分鍵による部分的な復号結果とを接続して平文に復号する、電子的な情報処理装置を用いた暗号通信方法。
【請求項４】
入力された暗号文に対し、少なくとも、第１の法に対する第１の剰余と第２の法に対する第２の剰余とを、電子的に剰余演算するための剰余演算命令と、
少なくとも、前記第１の剰余を第１の部分鍵により電子的にかつ部分的に復号すると共に、前記第２の剰余を第２の部分鍵により電子的にかつ部分的に復号するための部分復号命令を備え、ここで前記第１の部分鍵及び第２の部分鍵は各々、ナップザック暗号の復号用の所定の性質を備えた数列からなる鍵部分と、乱数列からなる乱数部分とを含むベクトルであり、
少なくとも、前記第１の部分鍵による部分的な復号結果と、前記第２の部分鍵による部分的な復号結果とを接続して、平文に復号するための接続命令、をさらに設けた、電子的な情報処理装置のための復号プログラム。
【請求項５】
少なくとも、各々ナップザック暗号の復号用の所定の性質を備えた数列からなる、第１の鍵部分と第２の鍵部分とを電子的に生成する鍵部分生成部と、
乱数列を電子的に生成する乱数生成部と、
少なくとも、前記第１の鍵部分と前記乱数生成部で生成した第１の乱数列とを組み合わせて第１の部分鍵とし、前記第２の鍵部分と前記乱数発生部で生成した第２の乱数列とを組み合わせて第２の部分鍵として、各々記憶する部分鍵記憶部と、
少なくとも、前記第１の部分鍵のｉ番目の成分に対し第１の法に関して合同で、前記第２の部分鍵のｉ番目の成分に対し、第２の法に関して合同な成分をｉ番目の成分とする、秘密鍵を電子的に算出するための連立合同方程式処理部（ここで第１の部分鍵と第２の部分鍵及び秘密鍵はｎ個の成分の数列で、ｉ＝１〜ｎ）、とを設けた、電子的な情報処理装置を用いた鍵生成装置。
【請求項６】
前記秘密鍵の各成分をモジュラ変換して公開鍵とするためのモジュラ変換部をさらに設けた（ここで公開鍵はｎ個の成分の数列である）、ことを特徴とする、請求項５の鍵生成装置。
【発明の詳細な説明】
【技術分野】
【０００１】
この発明はナップザック型の公開鍵暗号に関し、特に暗号通信装置や暗号通信方法、復号プログラム及び秘密鍵と公開鍵の生成に関する。
【背景技術】
【０００２】
超増加数列を用いたナップザック型の暗号(非特許文献１)が知られている。しかしながらナップザック暗号には低密度攻撃が知られており、平文長をｎビット、暗号化に用いる暗号化ベクトル｛ａ｝での最大の元をmax｛ａ｝として、密度ｄを
ｄ＝ｎ／log2 max｛ａ｝                                        (1)
で定義すると、ｄが０．９４０８以下で解読が可能であることが知られている（非特許文献２）。また発明者らは、超増加数列ではなく偶奇性をトラップドアに用いたナップザック暗号を提案した（非特許文献３）。発明者は、さらに複数の種類のトラップドアを混合して用いることを提案した（非特許文献４）。
【非特許文献１】R.C.Merkle and M.E.Hellman: "Hiding Information and signatures in trapdoor knapsacks" IEEE Trans.Inf.Theory,IT-24(5),p.p.525-530,September,1978
【非特許文献２】M.J.Coster,B.A.LaMacchia,A.M.Odlyzko,and C.P.Schnorr:"An Improved low-density subset sum algorithm" In Advances in Cryptology Proceedings Eurocrypt'91,LNCS,pp.54-67.Springet-Verlag,Berlin,1991
【非特許文献３】M.Kasahara and Y.Murakami: "New public key cryptosystems and the application" Technical Report of IEICE,ISEC99-55(1999-11),pp.21-28,1999.
【非特許文献４】名迫  健，村上  恭通：「トラップドア複合型高密度ナップザック暗号の提案」，２００６年  暗号と情報セキュリティシンポジウム(SCIS2006)予稿集CD-ROM  2A4-3，2006
【発明の開示】
【発明が解決しようとする課題】
【０００３】
この発明の基本的課題は、ナップザック暗号の安全性をさらに高めることにある。
またこの発明の他の課題は、公開鍵からの秘密鍵の露呈を防止することにある。
【課題を解決するための手段】
【０００４】
この発明の暗号通信装置は、入力された暗号文に対し、少なくとも、第１の法に対する第１の剰余と第２の法に対する第２の剰余とを、電子的に剰余演算する剰余演算部と、
少なくとも、前記第１の剰余を第１の部分鍵により電子的にかつ部分的に復号すると共に、前記第２の剰余を第２の部分鍵により電子的にかつ部分的に復号する部分復号部を設け、ここで前記第１の部分鍵及び第２の部分鍵は各々、ナップザック暗号の復号用の所定の性質を備えた数列からなる鍵部分と、乱数列からなる乱数部分とを含むベクトルであり、少なくとも、前記第１の部分鍵による部分的な復号結果と、前記第２の部分鍵による部分的な復号結果とを接続して平文に復号する接続部、をさらに設けたものである。
【０００５】
好ましくは、入力された暗号文を中間平文へ電子的にモジュラ変換するモジュラ変換部をさらに設けて、モジュラ変換後の中間平文を前記剰余演算部へ入力する。
【０００６】
この発明の暗号通信方法は電子的な情報処理装置を用いたもので、入力された暗号文に対し、少なくとも、第１の法に対する第１の剰余と第２の法に対する第２の剰余とを、電子的に剰余演算し、少なくとも、前記第１の剰余を第１の部分鍵により電子的にかつ部分的に復号すると共に、前記第２の剰余を第２の部分鍵により電子的にかつ部分的に復号し、ここで前記第１の部分鍵及び第２の部分鍵は各々、ナップザック暗号の復号用の所定の性質を備えた数列からなる鍵部分と、乱数列からなる乱数部分とを含むベクトルであり、少なくとも、前記第１の部分鍵による部分的な復号結果と、前記第２の部分鍵による部分的な復号結果とを接続して平文に復号する。
【０００７】
この発明の復号プログラムは電子的な情報処理装置のためのもので、入力された暗号文に対し、少なくとも、第１の法に対する第１の剰余と第２の法に対する第２の剰余とを、電子的に剰余演算するための剰余演算命令と、少なくとも、前記第１の剰余を第１の部分鍵により電子的にかつ部分的に復号すると共に、前記第２の剰余を第２の部分鍵により電子的にかつ部分的に復号するための部分復号命令を備え、ここで前記第１の部分鍵及び第２の部分鍵は各々、ナップザック暗号の復号用の所定の性質を備えた数列からなる鍵部分と、乱数列からなる乱数部分とを含むベクトルであり、少なくとも、前記第１の部分鍵による部分的な復号結果と、前記第２の部分鍵による部分的な復号結果とを接続して、平文に復号するための接続命令、をさらに設ける。
【０００８】
この発明の鍵生成装置は電子的な情報処理装置を用いたもので、少なくとも、各々ナップザック暗号の復号用の所定の性質を備えた数列からなる、第１の鍵部分と第２の鍵部分とを電子的に生成する鍵部分生成部と、乱数列を電子的に生成する乱数生成部と、少なくとも、前記第１の鍵部分と前記乱数生成部で生成した第１の乱数列とを組み合わせて第１の部分鍵とし、前記第２の鍵部分と前記乱数発生部で生成した第２の乱数列とを組み合わせて第２の部分鍵として、各々記憶する部分鍵記憶部と、少なくとも、前記第１の部分鍵のｉ番目の成分に対し第１の法に関して合同で、前記第２の部分鍵のｉ番目の成分に対し、第２の法に関して合同な成分をｉ番目の成分とする、秘密鍵を電子的に算出するための連立合同方程式処理部（ここで第１の部分鍵と第２の部分鍵及び秘密鍵はｎ個の成分の数列で、ｉ＝１〜ｎ）、とを設ける。
【０００９】
好ましくは、前記秘密鍵の各成分をモジュラ変換して公開鍵とするためのモジュラ変換部をさらに設ける（ここで公開鍵はｎ個の成分の数列である）。
【００１０】
この明細書で、暗号通信装置やその復号部に関する記載は、暗号通信方法や復号方法、暗号通信プログラムや復号プログラムにもそのまま当てはまり、暗号通信方法や復号方法に関する記載は、暗号通信装置や復号部、復号通信プログラムや復号プログラムにもそのまま当てはまる。また鍵生成は鍵生成装置について説明するが、この発明には鍵の生成方法の発明が内在しており、鍵生成の記載は鍵の生成方法にもそのまま当てはまる。
【発明の効果】
【００１１】
部分鍵や鍵部分等は２個以上用いればよいが、２個用いるものとしてこの発明を説明する。この発明の暗号通信装置や暗号通信方法、復号プログラムでは、秘密鍵中でトラップドアとして実際に使用されるのは、第１と第２の鍵部分である。そして第１と第２の鍵部分を公開鍵等から推定するには、第１の法と第２の法とを解読する必要があり、これは極めて困難である。このため、この発明の暗号通信装置や暗号通信方法、復号プログラムでは、復号に必要な部分鍵もしくはこれと同等な鍵が露呈する可能性を極めて低くできる。なおナップザックタイプの暗号を低密度攻撃から安全にするには、平文を拡大平文へ引き伸ばせば良く、平文から拡大平文への変換と組み合わせると、極めて安全な暗号通信ができる。
【００１２】
次に入力された暗号文をモジュラ変換して中間平文とし、中間平文を第１及び第２の部分鍵で各々部分的に復号すると、部分鍵やそれに同等な鍵が露呈する可能性をさらに小さくできる。
【００１３】
この発明の鍵生成装置では、公開鍵は２つの部分鍵から得られる秘密鍵に基づいて生成するが、実際に復号に用いられるのは、上記の秘密鍵自体ではなく、第１及び第２の部分鍵中の第１及び第２の鍵部分である。そして第１及び第２の部分鍵は連立合同方程式により秘密鍵に結びつけられている。この結果、公開鍵から上記の秘密鍵が露呈しても、連立合同方程式で用いた２つの法を解読しないと部分鍵を解読することが困難である。このため安全性の高いナップザック暗号が得られる。なお上記の秘密鍵をモジュラ変換して公開鍵とすると、公開鍵から上記の秘密鍵が露呈するのを困難にできる。
【発明を実施するための最良の形態】
【００１４】
以下に本発明を実施するための最適実施例を示す。
【実施例】
【００１５】
図１〜図１０に実施例とその変形とを示す。図１〜図８において、２，２'は暗号通信装置で、インターネット３などの安全でない通信路を経由して通信し、それぞれパーソナルコンピュータや携帯電話などの電子的な情報処理装置により構成される。４は暗号化部で、平文ｍ*を暗号文Ｃへ変換し、６は復号部で、暗号文Ｃを平文ｍ*に変換する。また８は通信インターフェースである。暗号化部４を図２に示すと、平文ｍ*はｕビットのベクトルで、これをプリコーディング部１０により適宜の線形符号化を施し、ｎビットの拡大平文（ｎ＞ｕ）に拡張する。積和演算部１１は公開鍵ベクトルａと拡大平文ｍとの内積を行い、これを暗号文Ｃとする。
【００１６】
図３に復号部６を示すと、２段のモジュラ変換部１５，１６を設けて、暗号文Ｃを第１の法Ｎ1と第１の数Ｗ1-1とによりモジュラ変換し、最初の中間平文Ｍ0へ変換する。モジュラ変換部１６は第２の法Ｎ2と第２の数Ｗ2-1とを用いて、さらにモジュラ変換し、中間平文Ｍを得る。なおモジュラ変換の段数は実施例では２段であるが、段数は任意で、またモジュラ変換を行わなくても良い。
【００１７】
中間平文Ｍを剰余演算部１８と部分復号部２０で部分的に復号し、同様に剰余演算部１９と部分復号部２１とで部分的に復号する。剰余演算部１８では第１の法Ｌ1に関する剰余を求め、剰余演算部１９では第２の法Ｌ2に関する剰余を求める。部分復号部２０では第１の剰余  Ｍ modＬ1  に対し、部分鍵Ｓ1を用いて暗号文の一部を復号する。剰余演算部１９での第２の復号結果  Ｍ modＬ2  に対し、部分復号部２１は部分鍵Ｓ2を用いて部分的に復号する。部分的に復号したデータを連接部２２で連接する。なお連接後にデータの置換を行ってもよい。そして連接部２２の出力を逆プリコーディング部２４で逆プリコーディングする。逆プリコーディングは、図２のプリコーディング部１０での線形符号化に対応するデコード処理であり、連接部２２の出力を逆プリコーディング部２４によりデコードする。この結果平文ｍ*が復号される。以下に実施例での記号の意味を示す。
【００１８】
実施例での記号の意味                                
ｍ*         平文：        ｕビットデータ
ｍ          拡大平文：    平文ｍ*を、線形符号化などのプリコーディングにより、ｎビットデータに引き伸ばしたもの（ｎ＞ｕ）  
Ｃ          暗号文        Ｃ≡ｍ*・ａ
Ｎ１，Ｎ２  法：          Ｎ1，Ｎ2は例えば素数；  法の数は例えば２段であるが、１段でもよい、暗号文Ｃから中間平文Ｍへの変換用
Ｗ１        Ｎ１に対して逆元Ｗ1-1を持つ数
Ｗ２        Ｎ２に対して逆元Ｗ2-1を持つ数
Ｍ          中間平文
Ｍ0≡Ｗ1-1 mod Ｎ1
Ｍ ≡Ｗ2-1 mod Ｎ2
｛ａ｝      暗号化鍵:    ｎ次元のベクトルで各成分をａｉとする
｛Ｓ｝      秘密鍵：    ｎ次元のベクトルで暗号化鍵｛ａ｝の生成に用い、これ自体は復号に使用しない、各成分をｓ0ｉとする、秘密鍵｛Ｓ｝から暗号化鍵｛ａ｝への変換は、図６に記載
Ｌ１，Ｌ２  法：        部分鍵｛Ｓ1｝，｛Ｓ2｝から秘密鍵｛Ｓ｝の生成に用いた法、法の数は２以上で、例えば２
｛Ｓ1｝，｛Ｓ2｝    部分鍵：  ｎ次元のベクトルで図４の構造を持ち、各成分をｓ1ｉ，ｓ2ｉとする      ｉ＝１〜ｎに対し
ｓ0ｉ modＬ1≡ｓ1ｉ                    (2)
ｓ0ｉ modＬ2≡ｓ2ｉ                    (3)
法が３個以上ある場合も同様で、例えば３番目の法Ｌ3と３番目の部分鍵｛Ｓ3｝の成分ｓ3ｉに対し、下式が成立
ｓ0ｉ modＬ3≡ｓ3ｉ                    (4)
｛ｒ1｝〜｛ｒ4｝    乱数ベクトル
｛ｔ1｝，｛ｔ2｝    鍵部分
【００１９】
図４に部分鍵Ｓ1，Ｓ2と秘密鍵Ｓとの関係を示す。鍵Ｓ，Ｓ1，Ｓ2はいずれも成分が整数で、次元数はｎであり、逆プリコーディング時に元の平文へ復号するためにｕ'個の成分が必要であるとする。部分鍵Ｓ1は鍵部分ｔ1と乱数列ｒ3，ｒ1を含み、部分鍵Ｓ2は鍵部分ｔ2と乱数列ｒ2，ｒ4を含む。鍵部分ｔ2と鍵部分ｔ2は異なる位置に配置され、鍵部分ｔ1には乱数列ｒ4が対応し、鍵部分ｔ2には乱数列ｒ3が対応し、乱数列ｒ1と乱数列ｒ2が対応する。部分鍵Ｓ1に対する法を例えば素数のＬ1，部分鍵Ｓ2に対する法を例えば素数のＬ2とすると、  Ｌ＝Ｌ1・Ｌ2  である。鍵Ｓ，Ｓ1，Ｓ2での成分の番号をｉで表すと、部分鍵Ｓ1の各成分をｓ1ｉ，部分鍵Ｓ2の各成分をｓ2ｉ，秘密鍵Ｓの成分をｓ0ｉとして、
ｓ0ｉ modＬ1≡ｓ1ｉ                          (2)
ｓ0ｉ modＬ2≡ｓ2ｉ                          (3)
がｉ＝１〜ｎに対して成立し、Ｌを法としてこの関係を満たすｓ0ｉが、各ｉに対して、一意に存在する。以上のようにして秘密鍵Ｓを決定する。乱数列ｒ1〜ｒ4には、鍵部分ｔ1，ｔ2をナップザック暗号のトラップドアとして用い得るように制限がある。例えば鍵部分ｔ1が超増加数列で有れば、乱数列ｒ1，ｒ3の成分の総和は、超増加数列の初項未満の値となる。また鍵部分ｔ2が偶奇性を用いた数列で、その成分の数がｕ'／２であれば、乱数列ｒ２，ｒ4の各成分は下位ｕ'／２ビットが全て、０または１に固定される。
【００２０】
秘密鍵Ｓから公開鍵ａへの変換を図５に示す。なお秘密鍵Ｓ，部分鍵Ｓ1，Ｓ2はベクトルであるので、これらを秘密鍵ベクトル、もしくは部分鍵ベクトルということがあり、公開鍵ａもｎ次元のベクトルなので、これを公開鍵ベクトルということがある。さらに秘密鍵Ｓをそのままあるいは置換して、図５のように変換し公開鍵ａとする。秘密鍵Ｓの各成分に対し、法をＮ1，秘密の数をＷ1としてモジュラ変換部３１によりモジュラ変換をし、中間鍵Ａを得る。中間鍵Ａに対し、第２のモジュラ変換部３２で法をＮ2，秘密の数をＷ2としモジュラ変換し、公開鍵ａを得る。なおベクトルに対してモジュラ変換を行うとは、ベクトルの各成分毎にモジュラ変換を行うことである。またベクトルに対して連立合同方程式を解くとは、ベクトルの各成分毎に連立合同方程式を解くことである。
【００２１】
図６に鍵生成装置３０の構造を示す。鍵生成装置３０は公開鍵ベクトルａと部分鍵Ｓ1，Ｓ2もしくは鍵部分ｔ1，ｔ2，並びに法Ｌ1，Ｌ2，Ｎ1，Ｎ2、秘密の数Ｗ1，Ｗ2及びこれらの逆数Ｗ1-1，Ｗ2-1を生成し、これらを安全な通信路により、もしくは記憶媒体に記憶させて暗号通信装置２に供給する。鍵部分生成部３４，３５は鍵部分ｔ1，ｔ2を生成し、乱数生成部３６は乱数列ｒ1〜ｒ4を生成し、これらを図４のように合成して、部分鍵記憶部３７，３８に記憶する。図４の下側に記載した、連立合同方程式を中国人の剰余定理処理部４４で解いて、秘密鍵Ｓを生成し、図５のモジュラ変換部３１，３２により公開鍵ａを生成する。また連立合同方程式の法Ｌ１，Ｌ２は法生成部４０で生成し、乗算部４２で乗算してＬとし、例えばパラメータ生成部４５へ供給する。パラメータ生成部４５は法Ｎ1，Ｎ2と秘密の数Ｗ1，Ｗ2を生成する。また乗算部４２で求めたＬの値を、パラメータ生成部４５へ入力しなくてもよい。
【００２２】
図７に復号プログラム７０を示すと、７１はモジュラ変換命令で、図３でのモジュラ変換部１５，１６の処理を、パーソナルコンピュータや携帯電話などに、実行させるための命令である。剰余演算命令７２は、図３の剰余演算部１８，１９での剰余演算を実行するための命令である。部分復号命令７３は、図３の部分復号部２０，２１での復号を実行させるための命令である。連接命令７４は部分復号結果を連接し、必要であれば復号結果をさらに置換し、逆プリコーディング命令７５は逆プリコーディング部２４と同様に平文ｍ*へ復号する。
【００２３】
図８に、実施例での復号過程を示す。暗号文Ｃが入力されると、ステップ１でモジュラ変換し、ステップ２で所定段数モジュラ変換を繰り返す。これは図３のモジュラ変換部１５，１６の処理である。ステップ３で図３の剰余演算部１８，１９の剰余演算を実行し、ステップ４で図３の部分復号部２０，２１での処理を実行する。
ａ・ｍ  ≡  Ｃ                              (4)
Ｗ1・Ｓ  modＮ1≡  Ａ                       (5)
Ｗ2・Ａ  modＮ2≡  ａ                        (6)
より、
Ｃ・Ｗ２−１  modＮ2≡  Ａ・ｍ                 (7)  
Ｃ・Ｗ1−１  modＮ1  ≡  Ｍ  ≡  Ｓ・ｍ       (8)
が成立する。(5)〜(8)式で”・”は内積を意味する。次に、  
ｓ0ｉ modＬ1≡ｓ1ｉ                          (2)
ｓ0ｉ modＬ2≡ｓ2ｉ                          (3)
が成立するので、  
Ｓ・ｍ modＬ1≡Ｓ1・ｍ                      (9)
Ｓ・ｍ modＬ2≡Ｓ2・ｍ                      (10)
が成立する。(9),(10)式は、トラップドアを備えた部分鍵Ｓ1，Ｓ2を用いたナップザック暗号の復号に、問題が還元されたことを意味する。そして部分鍵Ｓ1，Ｓ2は鍵部分ｔ1，ｔ2分の復号能力を備えている。ステップ５で、設けた法や鍵部分の乱数分の処理を終了するまで、剰余演算と部分復号を繰り返させる。ステップ６で部分復号した結果を連接し、ステップ７で逆プリコーディングして平文ｍ*を出力する。
【００２４】
図９，図１０に変形例の暗号化部９０と復号部９６とを示す。特に指摘する点以外は、図１〜図８の実施例と同様である。暗号化部９０では平文ｍ*を連接部９１に入力し、乱数発生部９２で発生させた乱数列ｘと連接して、拡大平文ｍに変換し、積和演算部１１で暗号文Ｃへ変換する。拡大平文ｍでは、乱数列ｘを除く、平文ｍ*の部分を復号できれば良い。
【００２５】
図１０の復号部９６で、連接部２２の出力をそのまま平文ｍ*とし、逆プリコーディングを行わない。この変形例では例えば  ｕ＝ｕ'  とし、鍵部分ｔ1により乱数部分ｒ4の存在にかかわらず、鍵部分ｔ1の成分の数（例えばu／２ビット）だけのビット長を部分的に復号する。同様に鍵部分ｔ2によりその成分の数（例えばu／２ビット）だけ、部分的に復号する。図４の乱数部分ｒには図９の乱数列ｘが対応し、この部分は復号不能である。
【００２６】
実施例では以下の効果が得られる。
(1)  法Ｌ1，Ｌ2を知らない限り、公開鍵ａから鍵部分ｔ1，ｔ2を推定することが極めて困難である。従って公開鍵ａからの攻撃が事実上封じ込められる。
(2)  平文ｍ*を拡大平文ｍに変換することにより、暗号文の密度ｄを増し、低密度攻撃を不可能にできる。
(3)  部分鍵Ｓ1，Ｓ2は例えば一方が超増加数列を鍵部分ｔ1に用い、他方が偶奇性を鍵部分ｔ2に用いるように、種類の異なるトラップドアを組み合わせることができる。
【００２７】
実施例ではプリコーディングとして線形符号化を行ったが、線形符号以外の誤り訂正能力を備えた符号化でも良く、より広義には、元の平文へデコードするための逆プリコーディングが可能な変換であればよい。さらにプリコーディングによる拡大平文への変換は省略しても良い。
【図面の簡単な説明】
【００２８】
【図１】実施例の暗号通信装置間の接続を示すブロック図
【図２】実施例での暗号化部のブロック図
【図３】実施例での復号部のブロック図
【図４】実施例での部分鍵から秘密鍵への変換を示す図
【図５】実施例での公開鍵の生成方法を示すフローチャート
【図６】実施例での鍵生成装置のブロック図
【図７】実施例での復号プログラムのブロック図
【図８】実施例での復号方法を示すフローチャート
【図９】変形例での暗号化部のブロック図
【図１０】変形例での復号部のブロック図
【符号の説明】
【００２９】
２          暗号通信装置
３          インターネット
４          暗号化部
６          復号部
８          通信インターフェース
１０        プリコーディング部
１１        積和演算部
１５，１６  モジュラ変換部
１８，１９  剰余演算部
２０，２１  部分復号部
２２        連接部
２４        逆プリコーディング部
３０        鍵生成装置
３１，３２  モジュラ変換部
３４，３５  部分鍵生成部
３６        乱数生成部
３７，３８  部分鍵記憶部
４０        法生成部
４２        乗算部
４４        中国人の剰余定理処理部
４５        パラメータ生成部
７０        復号プログラム
７１        モジュラ変換命令
７２        剰余演算命令
７３        部分復号命令
７４        連接命令
７５        逆プリコーディング命令
９０        暗号化部
９２        乱数発生部
９６        復号部
【図１】
2008009051.tif 000003
【図２】
2008009051.tif 000004
【図３】
2008009051.tif 000005
【図４】
2008009051.tif 000006
【図５】
2008009051.tif 000007
【図６】
2008009051.tif 000008
【図７】
2008009051.tif 000009
【図８】
2008009051.tif 000010
【図９】
2008009051.tif 000011
【図１０】
2008009051.tif 000012