(57)【要約】【構成】  秘密の数Ｐ,ｗと２つの秘密鍵ベクトルｖ０,ｖ１を用いたナップザック暗号の公開鍵として、秘密のベクトルｔを用い、 ａｉ＝ｗｖｔｉｉ   modＰ ｂｉ＝ｗｖ１−ｔｉｉ  modＰにより公開鍵ベクトルａ,ｂを得る。なおｖ０は正整数の乱数ベクトル、ｖ１は超増加ベクトルとする。【効果】  ナップザック暗号の密度を増して低密度攻撃への耐性を向上させ、秘密鍵ベクトルの超増加性等を利用した攻撃も困難にできる。【選択図】  図２
2006235291.tif 000002
【特許請求の範囲】
【請求項１】
秘密の数Ｐ及びｗと少なくとも２つの秘密鍵ベクトルｖ０,ｖ１(ｖ０,ｖ１は各々ｎ次元のベクトル)とを用いた、ナップザック暗号用の公開鍵の作成装置において、
秘密のｎ次元のデータｔ＝(ｔ１,ｔ２,…,ｔｎ)を用いて、ｔｉに応じて、ｖ０ｉ,ｖ１ｉ  の一方をｘｉとし、他方をｘ＊ｉとして、
少なくとも２つのｎ次元の公開鍵ベクトルａ,ｂを  ｉ＝１〜ｎ  に対し、
ａ＝(ａ１,ａ２,…,ａｎ),ｂ＝(ｂ１,ｂ２,…,ｂｎ))
ａｉ＝ｗｆｉ(ｘｉ)  modＰ
ｂｉ＝ｗｇｉ(ｘ＊ｉ) modＰ
として作成するための手段を設けたことを特徴とする、公開鍵の作成装置。
【請求項２】
前記公開鍵ベクトルａ,ｂと、下式を充たす変換として定義される可逆プリコーディングＨとを、 Ｃ＝ｍａ＋ｍ＊ｂ により、平文ベクトルｍを暗号文Ｃに暗号化するための公開鍵とする、ことを特徴とする、請求項１の公開鍵の作成装置。
プリコーディング間の順序をｉ＝１〜ｎとして、
Ｈ＝(Ｈ１,Ｈ２,…,Ｈｎ)  
ｍｉ＊＝Ｈｉ(ｍ１,ｍ２,…,ｍｉ)
ｍｉ  ＝Ｈｉ(ｍ１,ｍ２,…,ｍｉ＊)
【請求項３】
前記秘密鍵ベクトルｖ０,ｖ１の一方を乱数ベクトル、他方を以下の条件により定義される準超増加ベクトルとしたことを特徴とする、請求項１または２の公開鍵の作成装置。
ｖ１を準超増加ベクトルとした際に、  ｉ＋ｊ＝ｎ＋１  かつ  ｊ＝１〜ｎの３ｎ／４個以上のｊについて、
ｖ０,ｖ１の双方の成分の１〜ｊ−１までの和をＳｊ−１として、  ｖ１ｊ＞Ｓｊ−１＋ｖ０ｊ    
(ただしｖ１を準超増加ベクトルとする場合、  ｖ０ｊ＞Ｓｊ−１＋ｖ１ｊ)
【請求項４】
前記秘密鍵ベクトルｖ０,ｖ１の一方の各成分を偶数、他方の各成分を奇数とし、かつ
ｆｉ＝２ｉ−１ｘｉ
ｇｉ＝２ｉ−１ｘ＊ｉ
としたことを特徴とする、請求項１または２の公開鍵の作成装置。
【請求項５】
秘密の数Ｐ及びｗと少なくとも２つの秘密鍵ベクトルｖ０,ｖ１(ｖ０,ｖ１は各々ｎ次元のベクトル)とを用いた、ナップザック暗号用の公開鍵の作成プログラムにおいて、
秘密のｎ次元のデータｔ＝(ｔ１,ｔ２,…,ｔｎ)を用いて、ｔｉに応じて、ｖ０ｉ,ｖ１ｉ  の一方をｘｉとし、他方をｘ＊ｉとして、
少なくとも２つのｎ次元の公開鍵ベクトルａ,ｂを  ｉ＝１〜ｎ  に対し、
ａ＝(ａ１,ａ２,…,ａｎ),ｂ＝(ｂ１,ｂ２,…,ｂｎ))
ａｉ＝ｗｆｉ(ｘｉ)  modＰ
ｂｉ＝ｗｇｉ(ｘ＊ｉ) modＰ
として作成するための命令を設けたことを特徴とする、公開鍵の作成プログラム。
【請求項６】
前記公開鍵ベクトルａ,ｂと、下式を充たす変換として定義される可逆プリコーディングＨとを、 Ｃ＝ｍａ＋ｍ＊ｂ により、平文ベクトルｍを暗号文Ｃに暗号化するための公開鍵とする、ことを特徴とする、請求項５の公開鍵の作成プログラム。
プリコーディング間の順序をｉ＝１〜ｎとして、
Ｈ＝(Ｈ１,Ｈ２,…,Ｈｎ)  
ｍｉ＊＝Ｈｉ(ｍ１,ｍ２,…,ｍｉ)
ｍｉ  ＝Ｈｉ(ｍ１,ｍ２,…,ｍｉ＊)
【請求項７】
前記秘密鍵ベクトルｖ０,ｖ１の一方を乱数ベクトル、他方を以下の条件により定義される準超増加ベクトルとしたことを特徴とする、請求項５または６の公開鍵の作成プログラム。
ｖ１を準超増加ベクトルとした際に、ｉ＋ｊ＝ｎ＋１  かつ  ｊ＝１〜ｎの３ｎ／４個以上のｊについて、
ｖ０,ｖ１の双方の成分の１〜ｊ−１までの和をＳｊ−１として、  ｖ１ｊ＞Ｓｊ−１＋ｖ０ｊ    
(ただしｖ１を準超増加ベクトルとする場合、  ｖ０ｊ＞Ｓｊ−１＋ｖ１ｊ)
【請求項８】
前記秘密鍵ベクトルｖ０,ｖ１の一方の各成分を偶数、他方の各成分を奇数とし、かつ
ｆｉ＝２ｉ−１ｘｉ
ｇｉ＝２ｉ−１ｘ＊ｉ
としたことを特徴とする、請求項５または６の公開鍵の作成プログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
この発明は新規なナップザック暗号に関し、特にそれに用いる公開鍵の作成装置とそのプログラムとに関する。
【背景技術】
【０００２】
MerkleとHellmanは、積和演算のみで暗号化でき、かつ大小判断と減算のみで復号できる公開鍵暗号として、ナップザック暗号(MH暗号)を提案した(非特許文献１)。ナップザック暗号では、公開鍵ベクトルａを  ａ＝(ａ１,ａ２,ａ３,…,ａｎ),平文ベクトルｍを  ｍ＝(ｍ１,ｍ２,ｍ３,…,ｍｎ)  とした際に、暗号文Ｃを
ａ１ｍ１＋ａ２ｍ２＋ａ３ｍ３＋…＋ａｎｍｎ＝Ｃ   (1)
により求める。しかしMH暗号はShamirの攻撃(非特許文献２)や、低密度攻撃(非特許文献３〜５)により容易に解読できることが知られている。
【０００３】
Shamirの攻撃では、ナップザック暗号での公開鍵ベクトルａが、超増加ベクトルｖから   ａ＝ｗｖ  modP      (2)
により、導かれたものであることを利用する。ここにｖは超増加ベクトルで、その１項からｉ項までの和をＳｉとした際に、
ｖｉ＋１＞Ｓｉ      (3)
を満たし、Pは大きな素数で、
Ｐ＞Ｓｎ       (4)
を満たす。またｗは秘密の数で、  
ｗ∈Ｚ＊Ｐ      (5)
を満たし、Ｚ＊Ｐは１以上Ｐ未満の正整数からなる乗法群である。
【０００４】
Shamirの攻撃では、公開鍵ベクトル  ａ＝(ａ１,ａ２,ａ３,…,ａｎ)  に対して、正整数の組(ｗ',Ｐ')で、Ａ'＝{ａｉｗ'  modＰ'}が超増加数列をなし、かつａｉｗ'の総和がＰ'以下となるものを発見する。得られたＡ',ｗ',Ｐ'は本来の秘密鍵と一致する必要はなく、超増加数列Ａ'を用いると暗号文Ｃを復号できることが知られている。  
【０００５】
低密度攻撃では、低密度なナップザック暗号への攻撃に有効である。ナップザック暗号の密度は種々の定義があるが、ここでは比較的密度を低く評価するように、密度ρを
ρ＝ｎ／(Log２Ｃｍａｘ)     (6)
で定義する。ここにｎは平文のブロック長で、超増加ベクトルや公開鍵ベクトルなどの次元であり、Ｃmaxはブロック長ｎの平文に対する暗号文の最大値である。低密度攻撃では、密度ρが０.９４０８未満の時に、暗号文を解読可能なことが知られている(非特許文献５)。
【０００６】
発明者らは、ナップザック暗号の、高速で暗号化や復号ができ、かつ素因数問題や離散対数問題、楕円離散対数問題等に基礎を置かないので、量子コンピュータが実現されても信頼性があるとの利点に着目して、改良を進めてきた(非特許文献６,７)。例えば非特許文献６では、逐次プリコーディングと、２つの秘密鍵ベクトルｖ０,ｖ１および２つの公開鍵ベクトルａ０,ａ１を用いて、ナップザック暗号を高密度化する。
【０００７】
また非特許文献７では、Ｓｎよりも小さな法Ｐを用いることにより、ナップザック暗号の密度を１以上にする。そしてこの場合、法Ｐと秘密の数ｗは必ずしも互いに素である必要はなく、また秘密鍵ベクトルｖは部分的には超増加性を有しなくても、復号できることを見出した。なおこの明細書で、ベクトルの成分の大部分が超増加性を有するが、一部の成分、例えばｎ／４個未満の成分、好ましくはｎ／８個未満の成分に付いて超増加性を有しないことがあるものを、準超増加ベクトルと呼ぶ。
【０００８】
しかしながらナップザック暗号は多くの攻撃法知られていることから明らかなように、さらに安全性を高める必要がある。
【非特許文献１】R.C. Merkle,M.E. Hellman: “Hiding information and Signatures in trapdoor knapsacks,” IEEE,Trans. Inf. Theory,IT-24(5),pp.525.530,1978.
【非特許文献２】A. Shamir: “A polynomial time algorithm for breaking the basic Merkle-Hellman cryptosystems,” Proc. Crypto'82,LNCS,pp.279.288,Springer-Verlag,Berlin,1982.
【非特許文献３】E.F. Brickell: “Solving loｗ density knapsacks,” Proc. Crypto'83,LNCS,pp.25.37,Springer-Verlag,Berlin,1984.
【非特許文献４】J.C. Lagarias,A.M. Odlyzko: “Solving loｗ density Subset Sum problems,” J. Assoc. Comp. Math.,Vol.32,pp.229.246,Preliminary Version in Proc. 24th IEEE,1985.
【非特許文献５】M.J. Coster,B.A. LaMacchia,A.M. Odlyzko,C.P. Schnorr:”An improved loｗ-density subset sum algorithm,” Proc. Eurocrypto'91,LNCS,pp.54.67. Springer-Verlag,Berlin,1991.
【非特許文献６】服部保,村上恭通,笠原正雄,”プリコーディングを用いる二,三の加算暗号の提案”,2001年  情報理論とその応用シンポジウム予稿集,pp.351-354,Dec.2001
【非特許文献７】名迫健,横山晃子,村上恭通,”ナップザック暗号の法縮小による高密度化手法および探索復号法の提案”2004年  情報理論とその応用シンポジウム予稿集,pp.123-126,Dec.2004
【発明の開示】
【発明が解決しようとする課題】
【０００９】
この発明の課題は、Shamirの攻撃や低密度攻撃への耐性が高く、かつ高速で復号可能な暗号システムを実現するために、それに用いる公開鍵を提供することにある。
【課題を解決するための手段】
【００１０】
この発明は、秘密の数Ｐ及びｗと少なくとも２つの秘密鍵ベクトルｖ０,ｖ１(ｖ０,ｖ１は各々ｎ次元のベクトル)とを用いた、ナップザック暗号用の公開鍵の作成装置において、秘密のｎ次元のデータｔ＝(ｔ１,ｔ２,…,ｔｎ)を用いて、ｔｉに応じて、ｖ０ｉ,ｖ１ｉ  の一方をｘｉとし、他方をｘ＊ｉとして、少なくとも２つのｎ次元の公開鍵ベクトルａ,ｂを  ｉ＝１〜ｎ  に対し、  ａ＝(ａ１,ａ２,…,ａｎ),ｂ＝(ｂ１,ｂ２,…,ｂｎ))
ａｉ＝ｗｆｉ(ｘｉ)  modＰ    (7)
ｂｉ＝ｗｇｉ(ｘ＊ｉ) modＰ    (8)
として作成するための手段を設けたことを特徴とする。
【００１１】
好ましくは、前記公開鍵ベクトルａ,ｂと、下式を充たす変換として定義される可逆プリコーディングＨとを、 Ｃ＝ｍａ＋ｍ＊ｂ により、平文ベクトルｍを暗号文Ｃに暗号化するための公開鍵とする。
プリコーディング間の順序をｉ＝１〜ｎとして、
Ｈ＝(Ｈ１,Ｈ２,…,Ｈｎ)       (9)
ｍｉ＊＝Ｈｉ(ｍ１,ｍ２,…,ｍｉ)    (10)
ｍｉ  ＝Ｈｉ(ｍ１,ｍ２,…,ｍｉ＊)    (11)
ｉはプリコーデング間の順序、従って復号時の順序を定めるパラメータで、平文ベクトルｍでの順序を定めるものではない。
【００１２】
なお可逆プリコーディング以外のコーディング、例えば非特許文献６で用いられるシーケンシャルコーディング(逐次コーディング)で、一部のｉについて  ｍｉ  ＝Ｈｉ(ｍ１,ｍ２,…,ｍｉ＊)  が成立しないものを用いると、復号が困難になる。この場合、ｍｉ  ＝Ｈｉ(ｍ１,ｍ２,…,ｍｉ＊)が成立しない部分について、ｍｉを推定して復号する必要が生じる。
【００１３】
秘密鍵ベクトルｖ０,ｖ１は例えば一方を乱数ベクトル、他方を以下の条件により定義される準超増加ベクトルとする。これは超増加性を利用したタイプの秘密鍵で、非特許文献１の秘密鍵を発展させたものである。
ｖ１を準超増加ベクトルとした際に、ｉ＋ｊ＝ｎ＋１  かつ  ｊ＝１〜ｎの３ｎ／４個以上、より好ましくは７ｎ／８個以上のｊについて、
ｖ０,ｖ１の双方の成分の１〜ｊ−１までの和をＳｊ−１として、  
ｖ１ｊ＞Ｓｊ−１＋ｖ０ｊ         (12)
(ただしｖ１を準超増加ベクトルとする場合、  ｖ０ｊ＞Ｓｊ−１＋ｖ１ｊ) (12')
【００１４】
秘密鍵ベクトルｖ０,ｖ１は例えば一方の各成分を偶数、他方の各成分を奇数とし、かつ
ｆｉ＝２ｉ−１ｘｉ      (13)
ｇｉ＝２ｉ−１ｘ＊ｉ      (14)
が成立するものでも良い。ただしｘｉ,ｘ＊ｉの一方がｖ０で他方がｖ１である。これは奇数と偶数とに基礎を置いた秘密鍵である(非特許文献６)。
【００１５】
この発明はまた、秘密の数Ｐ及びｗと少なくとも２つの秘密鍵ベクトルｖ０,ｖ１(ｖ０,ｖ１は各々ｎ次元のベクトル)とを用いた、ナップザック暗号用の公開鍵の作成プログラムにおいて、秘密のｎ次元のデータｔ＝(ｔ１,ｔ２,…,ｔｎ)を用いて、ｔｉに応じて、ｖ０ｉ,ｖ１ｉ  の一方をｘｉとし、他方をｘ＊ｉとして、少なくとも２つのｎ次元の公開鍵ベクトルａ,ｂを  ｉ＝１〜ｎ  に対し、
ａ＝(ａ１,ａ２,…,ａｎ),ｂ＝(ｂ１,ｂ２,…,ｂｎ))
ａｉ＝ｗｆｉ(ｘｉ)  modＰ
ｂｉ＝ｗｇｉ(ｘ＊ｉ) modＰ
として作成するための命令を設けたことを特徴とする。
【００１６】
なおこの明細書において、公開鍵の作成装置に関する記載はそのまま公開鍵の作成プログラムにも当てはまり、その逆に公開鍵の作成プログラムに関する記載は公開鍵の作成装置にも当てはまる。
【００１７】
実施例ではｍ,ｍ＊を推定せずに復号できるように公開鍵を定めるが、非特許文献７で記載のように、ナップザック暗号では平文の一部を推定しながら、中間平文Ｍが最終的に０になるものを選択することにより復号できる。このため公開鍵に関する条件は、実施例に記載のものよりも緩やかである。例えば低密度攻撃に対する耐性を増すため、法Ｐを実施例よりも小さくできる。またＰをＳｎよりも縮小する場合、Ｐとｗは互いに素であることが好ましいが、これに限るものではない。この発明では少なくとも２つの秘密のベクトルを用い、公開鍵ベクトルａ,ｂの各成分がｖ０,ｖ１のいずれに由来するかをデータｔにより秘密にし、暗号強度を増す。公開鍵ベクトルや秘密鍵ベクトルが各２つのベクトルの場合、データｔは例えば  ｔ∈{０,１}ｎ  となるが、公開鍵ベクトルや秘密鍵ベクトルが例えば各４つのベクトルの場合、ｔの各成分は例えばＳ４(４次対称群)の元となる。
【発明の効果】
【００１８】
この発明では、２つの公開鍵ベクトルａ,ｂと秘密鍵ベクトルｖ０,ｖ１との間で、ｔによるシャッフルを行う。このため超増加数列を利用したShamirの攻撃は、公開鍵ベクトルａ,ｂから超増加数列に対応する元を抽出できない限り困難である。また非特許文献６と比較した場合、公開鍵ベクトルａは偶数成分のベクトルに由来し,ｂは奇数成分のベクトルに由来するなどの規則性がない。従って、秘密鍵ベクトルの超増加性や偶奇性などを利用した攻撃も成立しにくい。
【００１９】
またこの発明では暗号の密度を１以上にできるので、低密度攻撃も成立し難い。しかもこの発明では、平文を推定しながら復号するなどの手法は原則として不要である。このため安全で、暗号化も復号も高速で行える暗号通信システムのための公開鍵を提供できる。
【００２０】
請求項２の発明では、復号時にｔiに依存してｍｉ,ｍｉ＊のいずれかが得られ、しかも復号側ではｍｉ,ｍｉ＊のどちらが得られるかは既知である。ここで可逆プリコーディングを用いると、ｍｉ,ｍｉ＊のいずれが得られても他方を得ることができ、復号時にｍｉ等の値等を推定する必要が無く、復号が容易になる。他の作用効果は、実施例より明らかになる。
【発明を実施するための最良の形態】
【００２１】
以下に本発明を実施するための最適実施例を示す。
【実施例】
【００２２】
図１〜図３に実施例の概要を、図４〜図７に実施例の詳細を示す。図８、図９は実施例での暗号強度を説明し、図１０〜図１３は変形例を示す。図１４,図１５は秘密鍵ベクトルと公開鍵ベクトルとを各４個設けた変形例を示す。図１〜図３の実施例の概要に関する記載は、各変形例にもそのまま当てはまる。
【００２３】
図１〜図３において、２は暗号通信装置システムで、複数の暗号通信装置４,６がインターネットなどの必ずしも安全でない通信路で結ばれ、暗号通信装置４,６はここでは同一のものとし、以下では説明の便宜上、暗号通信装置４として説明する。暗号通信装置４,６はコンピュータ資源を用い、ハードウェアとソフトウェアとで実現され、扱うデータは電子データである。
【００２４】
１０は通信インターフェースで、インターネットなどとのインターフェースとなり、秘密鍵記憶部１２は秘密鍵を記憶する。公開鍵作成部１４は、秘密鍵から公開鍵を作成して記憶し、インターネットを介して通信相手の暗号通信装置６へ公開する。復号部１６は受信した暗号文Ｃを復号し、暗号化部１８は平文ｍを暗号化する。
【００２５】
暗号通信装置４は、例えば鍵作成プログラム２０や復号プログラム２２,暗号化プログラム２４を記憶し、鍵作成プログラム２０は秘密鍵作成命令３０と公開鍵作成命令３２とを備えている。これらのプログラム２０〜２４や命令３０,３２の作用は、秘密鍵記憶部１２〜暗号化部１８と同様である。
【００２６】
図４に秘密鍵と公開鍵の詳細を示す。秘密鍵ベクトルｖ０,ｖ１は各ｎ次元のベクトルで、ｖ０は各成分が正整数の乱数ベクトル、ｖ１は(12)で定義する意味での超増加ベクトルである。また図１〜図９では、復号はｉについて降順に行うものとし、特許請求の範囲での変数ｊに相当するものをｉとする。ｉは増加ベクトルや可逆プリコーディングでの復号の順序を意味し、平文ベクトル内での順序を意味しない。必要であれば、実施例での復号後に平文ベクトルでの要素間の置換を行って最終的な平文とする。ｖ０,ｖ１の双方の成分の１〜ｉ−１までの和をＳｉ−１として、  
ｖ１ｉ＞Ｓｉ−１＋ｖ０ｉ         (12)
なおｖ０,ｖ１のいずれを超増加ベクトル、いずれを乱数ベクトルと呼ぶかは、単に用語だけの問題である。ここでｖ０の各成分のビット長をｒビット以下とし、ｒは例えば６４とする。Ｐは素数でＳｎよりも大きな数が好ましいが、非特許文献７に示すように、Ｓｎ未満の数でも良く、また素数には限らない。ｗは秘密の数で、好ましくは１以上Ｐ未満であるが、  Ｐ＜Ｓｎ  の場合、Ｐとｗとが公約数を有しても良い。また非特許文献７のように、平文ｍの成分の一部を推定しながら復号する場合、ｖ１は準超増加ベクトルであれば良く、その成分の３ｎ／４個以上、好ましくは７ｎ／８個以上が超増加性を満たせばよい。ｔは秘密のベクトルで、その成分は例えば０または１で、各成分は０または１にランダムに選ばれている。
【００２７】
公開鍵は２つのベクトルａ,ｂ(いずれもｎ次元)と可逆プリコーディングＨとからなり、ａ,ｂの各元は(15),(16)で定義される。ここにｖｔｉｉやｖ１−ｔｉｉはｖｉのti乗や(1-ti)乗を意味するのではなく、tiの値に従ってｖ０ｉ,ｖ１ｉのいずれかの元となることを意味する。
ａｉ＝ｗｖｔｉｉ modＰ     (15)
ｂｉ＝ｗｖ１−ｔｉｉ modＰ     (16)
(15),(16)はａ,ｂの各元がｖ０,ｖ１のいずれかの元で定まり、かつｖ０,ｖ１のいずれの元で定められているかがランダムで推定不能なことを意味する。従ってａ,ｂの各元の定義を(7),(8)のように一般化できる。ここにｆｉ,ｇｉはｉの値毎に定まる関数で、ｖ０ｉ,ｖ１ｉ  の一方をｘｉし、他方をｘ＊ｉとする。
ａｉ＝ｗｆｉ(ｘｉ)  modＰ    (7)
ｂｉ＝ｗｇｉ(ｘ＊ｉ) modＰ    (8)
【００２８】
Ｈは(9)〜(11)により定義される可逆プリコーディングの集合で、ここでは単純に可逆プリコーディングＨなどと呼ぶ。なおここで ｉ＝１〜ｎ  である。
Ｈ＝(Ｈ１,Ｈ２,…,Ｈｎ)       (9)
ｍｉ＊＝Ｈｉ(ｍ１,ｍ２,…,ｍｉ)    (10)
ｍｉ  ＝Ｈｉ(ｍ１,ｍ２,…,ｍｉ＊)    (11)
ただし非特許文献７のように、平文ｍの値を推定しながら復号する場合、Ｈの一部の元、例えばｎ／４個未満の元、好ましくはｎ／８未満の元が、(11)を満たさなくても良い。(9),(10)を満たすコーディング（(11)を満たす必要はない)を逐次プリコーディングと呼ぶ。
【００２９】
可逆プリコーディングの例として、図５に示すように(17)を満たすものなどがある。
Ｈｉ  ＝Ｈｉ−１(ｍ１,ｍ２,…,ｍｉ−１)(+)ｍｉ   (17)
また図５に示す喜安-Gray逆変換に基づく２つのプリコーディングＧ０ｉ,Ｇ１ｉはそれぞれ可逆プリコーディングである。可逆プリコーディングを用いることの意味を説明する。例えば  ｉ＝１  から始めてシーケンシャルにｉ−１まで復号すると、次のtiの値に依存してｍｉ＊,またはｍｉが得られる。ここでｍｉ＊とｍｉのいずれが得られても、ｍｉを得ることができるように保証するのが、可逆プリコーディングの役割である。なおｍｉ＊やｍｉの意味は図６に示してある。
【００３０】
暗号化の手続を図６に示すと、
ｍ＊＝Ｈ(ｍ)      (18)
として、
Ｃ＝ｍａ＋ｍ＊ｂ      (19)
により、暗号文Ｃを求める。なお平文ｍはｎ次元のベクトルで、暗号文Ｃは、２つの公開鍵ベクトルａ,ｂとｍやｍ＊との積和演算の結果を、加算することにより得られる。ｎ次元の平文ベクトルｍに対する、暗号文Ｃの最大値をＣmaxとし、(6)により暗号の密度ρを定義する。
ρ＝ｎ／(Log２Ｃｍａｘ)     (6)
【００３１】
図７に復号アルゴリズムを示す。ナップザック暗号での定法に従い、(20)により中間平文Ｍを求める。なお  (Ｐ,ｗ)＝ｐ＞１  の場合、Ｐ／ｐを法とする乗法環での(ｗ／ｐ)の逆元をｗ−１とするように、Ｐの代わりにＰ／ｐを用いると良い。
Ｍ＝ｗ−１Ｃ  modＰ     (20)
【００３２】
次いでｖ１の超過増加性を用い、  Ｍ≧ｖ１ｉ  でｍｉｔｉを１とする。tiの値は既知なのでこれからｍ１ｉまたはｍ０ｉが定まり、Ｈが可逆プリコーディングであることから、ｍ１ｉとｍ０ｉの双方が求まる。この手続を  ｉ＝ｎ  から始めて  ｉ＝１  まで実行し、復号の正否は最終的に  Ｍ＝０  が成立するかどうかでチェックできる。
【００３３】
図８に、実施例での暗号密度ρを模式的に示す。非特許文献１のナップザック暗号では、秘密鍵ベクトルｖの超増加性と  Ｐ＞Ｓｎ  とのために、Log２Ｃmaxはｎよりも大きく、低密度攻撃が成立する。低密度攻撃に関する密度の評価において、実施例では密度ρの分子はｎではなく２ｎとなり、 ρ≧１ が成立する。例えばｖ０の各元を６４ビット程度とし、ｎを１２８とすると、ｖ１の各元を６４ビット以上１９１ビット程度に設定可能である。そこでＰは１９２ビット程度に設定可能であり、密度ρは例えば１.３程度にできる。このため低密度攻撃は一般に成立しない。
【００３４】
Shamirの攻撃への耐性を図９に示す。実施例では、ｔによるシャッフルのため、{ａｉ},{ｂｉ}は超増加数列に由来しない。そこでShamirの攻撃は基本的に成立しない。ｔ∈{０,１}ｎを知ればShamirの攻撃は可能であるが、０と１をランダムに並べたベクトルｔを推定することは極めて困難である。従って、Shamirの攻撃も極めて困難である。
【００３５】
図１０〜図１３に、偶数成分のベクトルｖ０と奇数成分のベクトルｖ１とを秘密鍵ベクトルとする変形例を示す。(13),(14)の具体例として、(21),(22)により、中間的な秘密鍵ｂ０,ｂ１を定める。また図１０に従って、好ましくは素数となる秘密の数Ｐと秘密の数ｗとを定める。次いで図１１に従い公開鍵ベクトルａ０(実施例でのｂに相当)と、公開鍵ベクトルａ１(実施例でのａに相当)とを定める。また実施例と同様に可逆プリコーディングＨを定めて公開鍵とする。
ｂ０ｉ＝２ｉ−１ｖ０ｉ      (21)
ｂ１ｉ＝２ｉ−１ｖ１ｉ      (22)
【００３６】
図１２のように暗号化すると、中間平文Ｍを経て、平文ｍの１ビット目から始めて、ｎビット目への順で、図１３のように復号できる。例えば  ｉ＝１  において、Ｍが奇数であるとする。  t1＝１  の時、ｂ１１はａ１１を定めるので、ｍ１１(平文ベクトルｍの第１成分)が１となる。ここで  t1＝０  の時、ｂ１１がａ０１を定めるので、ｍ０１(ｍ＊＝Ｈ(ｍ)の第１成分)が１となる。１つのｉでの処理が終わる毎に、残余を１／２倍してから次のｉを処理し、  ｉ＝ｎ  での処理が終了すると、  Ｍ＝０  となるはずである。なおｍ＝(ｍ１１,ｍ１２,…,ｍ１ｎ)で、ｍ＊＝(ｍ０１,ｍ０２,…,ｍ０ｎ)である。
【００３７】
この変形例でも、暗号の密度を１以上にできる。また偶数成分のベクトルｖ０と奇数成分のベクトルｖ１とを用いたことが、解読の手掛かりにならないように、秘密のベクトルｔによるシャッフルを行っている。  
【００３８】
図１４,図１５に、４つの秘密鍵ベクトルｖ０〜ｖ３と４つの公開鍵ベクトルａ０〜ａ３とを用いる例を示す。各成分が(０,１,２,３)の互換tiとなる、秘密のｎ次元ベクトルｔを定める。ｔのｉ番目の成分tiにより、ｖ０ｉ〜ｖ３ｉの順序を入れ換えてａ０ｉ〜ａ３ｉに対応させて、公開鍵ベクトルａ０〜ａ３を定める。また例えばｖ３,ｖ１を図１４の意味での超増加ベクトルとする。平文ベクトルｍを可逆な変換Ｆにより、２つの平文ベクトルｍ１,ｍ３に変換し、２つの可逆プリコーディングＨ１,Ｈ２により平文ベクトルｍ０,ｍ２を定める。そして図１４の下部のようにして、暗号化する。    
【００３９】
復号では、図１５のように中間平文Ｍを求め、最上位の  ｉ＝ｎ  から  ｉ＝１  への順に復号する。例えば  ｉ＝ｎ  で、Ｍ≧ｖ３ｎ  であれば、互換ｔｎが既知なので、ｍ０ｎ〜ｍ３ｎの１つで、ｖ３ｎに対応する項が定まる。可逆プリコーディングＨ１またはＨ２によりｍ０ｎ〜ｍ３ｎの他の１つが定める。次にｍ０ｎ〜ｍ３ｎ中の既知の２つの成分に対応する項を図７と同様に減算してＭを小さくする。減算後のＭが  Ｍ≧ｖ１ｎ  かどうかから、残る２つの成分の１つのｖ１ｎに対応する項を求め、最後の項を可逆プリコーディングの性質を利用して求める。なお４つの秘密鍵ベクトルと公開鍵ベクトルとを用いる際の、暗号化や復号の手順は、図１４,図１５以外にも種々のものが可能である。
【００４０】
実施例では、高速で暗号化と復号とができ、量子コンピュータが将来実用化されても安全性を維持できる、とのナップザック暗号の長所を維持し、かつShamirの攻撃や低密度攻撃などへの耐性を高めた公開鍵暗号システムを提供すると共に、その公開鍵の作成装置や作成プログラム、作成方法などを提供できる。
【図面の簡単な説明】
【００４１】
【図１】実施例の暗号通信システムのブロック図
【図２】実施例の暗号通信装置のブロック図
【図３】実施例での鍵作成プログラムのブロック図
【図４】実施例での秘密鍵と公開鍵とを示す図
【図５】実施例で用いた可逆プリコーディングを示す図
【図６】実施例での暗号化アルゴリズムを示す図
【図７】実施例での復号アルゴリズムを示す図
【図８】実施例(左側)とＭＨ方式の従来例(右側)とでの、暗号文の密度を示す図
【図９】実施例でのShamirの攻撃に対する耐性を示す図
【図１０】変形例で用いた秘密鍵の作成アルゴリズムを示す図
【図１１】変形例での公開鍵の作成アルゴリズムを示す図
【図１２】変形例での暗号化アルゴリズムを示す図
【図１３】変形例での復号アルゴリズムを示す図
【図１４】４つの秘密鍵ベクトルｖ０,ｖ１,ｖ２,ｖ３を用いた変形例の概要を示す図
【図１５】図１４の変形例での復号アルゴリズムを示す図
【符号の説明】
【００４２】
２ 暗号通信システム
４,６ 暗号通信装置
１０ 通信インターフェース
１２ 秘密鍵記憶部
１４ 公開鍵作成部
１６ 復号部
１８ 暗号化部
２０ 鍵作成プログラム
２２ 復号プログラム
２４ 暗号化プログラム
３０ 秘密鍵作成命令
３２ 公開鍵作成命令  
【図１】
2006235291.tif 000003
【図２】
2006235291.tif 000004
【図３】
2006235291.tif 000005
【図４】
2006235291.tif 000006
【図５】
2006235291.tif 000007
【図６】
2006235291.tif 000008
【図７】
2006235291.tif 000009
【図８】
2006235291.tif 000010
【図９】
2006235291.tif 000011
【図１０】
2006235291.tif 000012
【図１１】
2006235291.tif 000013
【図１２】
2006235291.tif 000014
【図１３】
2006235291.tif 000015
【図１４】
2006235291.tif 000016
【図１５】
2006235291.tif 000017