(57)【特許請求の範囲】
【請求項１】
平文と公開鍵とに基づき暗号文を作成する暗号化装置において、前記平文を公開されている変換関数に基づいて複数の変換平文に変換する手段と、前記平文と変換した前記変換平文と複数種の前記公開鍵とを用いて暗号文を作成する手段とを備えており、前記平文をｎビットのベクトルｍ（ｍ1 ，ｍ2 ，…，ｍn ）とし、２つの前記変換平文を夫々ｎビットのベクトルｍ′（ｍ1 ′，ｍ2 ′，…，ｍn ′）及びベクトルｍ″（ｍ1 ″，ｍ2 ″，…，ｍn ″）とし、２種類の前記公開鍵を夫々ｎビットのベクトルｃ(1) （ｃ1 (1) ，ｃ2 (1) ，…，ｃn (1) ）及びベクトルｃ(0) （ｃ1 (0) ，ｃ2 (0) ，…，ｃn (0) ）とした場合に、前記暗号文Ｃを下記（Ａ）のように作成するようにしたことを特徴とする暗号化装置。
【数１】
0003722744.tif 000022
【請求項２】
複数のエンティティ間で暗号文による情報通信を行う暗号通信システムにおいて、請求項１に記載の暗号化装置と、作成した暗号文を一方のエンティティから他方のエンティティへ送信する通信路と、送信された暗号文を平文に復号する復号装置とを備えることを特徴とする暗号通信システム。
【請求項３】
コンピュータに、暗号化すべき平文と公開鍵とに基づいて暗号文を作成させるコンピュータプログラムを記録してあるコンピュータでの読み取りが可能な記録媒体において、コンピュータに、ｎビットのベクトルｍ（ｍ1 ，ｍ2 ，…，ｍn ）で表される前記平文を、公開されている変換関数に基づいて、夫々ｎビットのベクトルｍ′（ｍ1 ′，ｍ2 ′，…，ｍn ′）及びベクトルｍ″（ｍ1 ″，ｍ2 ″，…，ｍn ″）で表される２つの変換平文に、変換する処理を変換器が行うように該変換器を制御させる手順と、コンピュータに、夫々ｎビットのベクトルｃ(1) （ｃ1 (1) ，ｃ2 (1) ，…，ｃn (1) ）及びベクトルｃ(0) （ｃ1 (0) ，ｃ2 (0) ，…，ｃn (0) ）で表される２種類の前記公開鍵と、前記平文と、前記２つの変換平文とを用いて、前記暗号文Ｃを下記（Ａ）のように作成する処理を暗号文作成器が行うように該暗号文作成器を制御させる手順とを含むコンピュータプログラムを記録してあることを特徴とする記録媒体。
【数２】
0003722744.tif 000023
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は、公開鍵を用いて平文を暗号文に変換する公開鍵暗号系の暗号化装置、その暗号化装置を備える暗号通信システム、及び、その暗号化装置を実施するためのコンピュータプログラムが記録されている記録媒体に関する。
【０００２】
【従来の技術】
高度情報化社会と呼ばれる現代社会では、コンピュータネットワークを基盤として、ビジネス上の重要な文書・画像情報が電子的な情報という形で伝送通信されて処理される。このような電子情報は、容易に複写が可能である、複写物とオリジナルとの区別が困難であるという性質があり、情報保全の問題が重要視されている。特に、「コンピュータリソースの共有」，「マルチアクセス」，「広域化」の各要素を満たすコンピュータネットワークの実現が高度情報化社会の確立に不可欠であるが、これは当事者間の情報保全の問題とは矛盾する要素を含んでいる。このような矛盾を解消するための有効な手法として、人類の過去の歴史上主として軍事，外交面で用いられてきた暗号技術が注目されている。
【０００３】
暗号とは、情報の意味が当事者以外には理解できないように情報を交換することである。暗号において、誰でも理解できる元の文（平文）を第三者には意味がわからない文（暗号文）に変換することが暗号化であり、また、暗号文を平文に戻すことが復号であり、この暗号化と復号との全過程をまとめて暗号系と呼ぶ。暗号化の過程及び復号の過程には、それぞれ暗号化鍵及び復号鍵と呼ばれる秘密の情報が用いられる。復号時には秘密の復号鍵が必要であるので、この復号鍵を知っている者のみが暗号文を復号でき、暗号化によって情報の秘密性が維持され得る。
【０００４】
暗号化方式は、大別すると共通鍵暗号系と公開鍵暗号系との二つに分類できる。共通鍵暗号系では、暗号化鍵と復号鍵とが等しく、送信者と受信者とが同じ共通鍵を持つことによって暗号通信を行う。送信者が平文を秘密の共通鍵に基づいて暗号化して受信者に送り、受信者はこの共通鍵を用いて暗号文を元に平文に復号する。
【０００５】
これに対して公開鍵暗号系では、暗号化鍵と復号鍵とが異なっており、公開されている受信者の公開鍵で送信者が平文を暗号化し、受信者が自身の秘密鍵でその暗号文を復号することによって暗号通信を行う。公開鍵は暗号化のための鍵、秘密鍵は公開鍵によって変換された暗号文を復号するための鍵であり、公開鍵によって変換された暗号文は秘密鍵でのみ復号することができる。
【０００６】
【発明が解決しようとする課題】
整数環上の演算を利用した公開鍵暗号系に関して、新規な方式及び攻撃法が次々に提案されているが、特に、多くの情報を短時間で処理できるように高速復号可能な暗号化・復号の手法の開発が望まれている。そこで、本発明者等は、暗号文が見かけ上２つの相異なる０，１−ナップザック暗号文の和となる構造の暗号化方式（以下、単に従来例という）を提案している（笠原正雄，村上恭通：”公開鍵暗号とその応用”，信学技報ＩＳＥＣ９９−５５，ｐｐ．２１−２８，１９９９）。
【０００７】
この従来例では、暗号化処理を加算のみ、復号処理をビットシフト演算及び偶奇判定のみで行うことができるため、極めて高速な処理が可能であるという特徴を有しているが、連接鍵攻撃または差分鍵攻撃に弱いという難点がある。本発明者等は、公開鍵暗号系に関して更なる研究を続けており、処理の高速化と安全性の向上とを実現できる暗号化方式の構築を目指している。
【０００８】
本発明は斯かる事情に鑑みてなされたものであり、高速な処理が可能であるという従来例の利点は維持しつつ、連接鍵攻撃及び差分鍵攻撃に強くて安全性を高めることができる公開鍵暗号系の暗号化装置、その暗号化装置を備える暗号通信システム、及び、その暗号化装置を実施するためのコンピュータプログラムを記録した記録媒体を提供することを目的とする。
【０００９】
ところで、暗号文の復号回路を入手し、その復号回路に適当な暗号文を入力して復号結果を取得し、その取得した復号結果に基づいて、所望の暗号文に対する平文を推定する攻撃、所謂選択暗号文攻撃なるものが存在する。そして、正当なエンティティによる暗号文の入力であるか、それとも攻撃者による適当な暗号文の入力であるかを復号時に判断できることが、この選択暗号文攻撃に対する安全性の根拠となる。この選択暗号文攻撃に強いか否かも安全性の重要な尺度となっており、その耐性向上が望まれている。
【００１０】
本発明の他の目的は、選択暗号文攻撃に対する安全性を向上できる公開鍵暗号系の暗号化装置、その暗号化装置を備える暗号通信システム、及び、その暗号化装置を実施するためのコンピュータプログラムを記録した記録媒体を提供することにある。
【００１１】
【課題を解決するための手段】
請求項１に係る暗号化装置は、平文と公開鍵とに基づき暗号文を作成する暗号化装置において、前記平文を公開されている変換関数に基づいて複数の変換平文に変換する手段と、前記平文と変換した前記変換平文と複数種の前記公開鍵とを用いて暗号文を作成する手段とを備えており、前記平文をｎビットのベクトルｍ（ｍ1 ，ｍ2 ，…，ｍn ）とし、２つの前記変換平文を夫々ｎビットのベクトルｍ′（ｍ1 ′，ｍ2 ′，…，ｍn ′）及びベクトルｍ″（ｍ1 ″，ｍ2 ″，…，ｍn ″）とし、２種類の前記公開鍵を夫々ｎビットのベクトルｃ(1) （ｃ1 (1) ，ｃ2 (1) ，…，ｃn (1) ）及びベクトルｃ(0) （ｃ1 (0) ，ｃ2 (0) ，…，ｃn (0) ）とした場合に、前記暗号文Ｃを下記（Ａ）のように作成するようにしたことを特徴とする。
【００１２】
【数３】
0003722744.tif 000002
【００２６】
請求項２に係る暗号通信システムは、複数のエンティティ間で暗号文による情報通信を行う暗号通信システムにおいて、請求項１に記載の暗号化装置と、作成した暗号文を一方のエンティティから他方のエンティティへ送信する通信路と、送信された暗号文を平文に復号する復号装置とを備えることを特徴とする。
【００３０】
請求項３に係る記録媒体は、コンピュータに、暗号化すべき平文と公開鍵とに基づいて暗号文を作成させるコンピュータプログラムを記録してあるコンピュータでの読み取りが可能な記録媒体において、コンピュータに、ｎビットのベクトルｍ（ｍ1 ，ｍ2 ，…，ｍn ）で表される前記平文を、公開されている変換関数に基づいて、夫々ｎビットのベクトルｍ′（ｍ1 ′，ｍ2 ′，…，ｍn ′）及びベクトルｍ″（ｍ1 ″，ｍ2 ″，…，ｍn ″）で表される２つの変換平文に、変換する処理を変換器が行うように該変換器を制御させる手順と、コンピュータに、夫々ｎビットのベクトルｃ(1) （ｃ1 (1) ，ｃ2 (1) ，…，ｃn (1) ）及びベクトルｃ(0) （ｃ1 (0) ，ｃ2 (0) ，…，ｃn (0) ）で表される２種類の前記公開鍵と、前記平文と、前記２つの変換平文とを用いて、前記暗号文Ｃを下記（Ａ）のように作成する処理を暗号文作成器が行うように該暗号文作成器を制御させる手順とを含むコンピュータプログラムを記録してあることを特徴とする。
【００３１】
【数４】
0003722744.tif 000003
【００３３】
本発明では、暗号化すべき平文を所定の変換関数に基づいて１または複数の変換平文に変換し（この変換処理のことをプリコーディングともいう）、その変換平文と元の平文と１種または複数種の公開鍵とを利用して暗号文を作成する。このようなプリコーディング手法を用いて変換した変換平文を組み込ませることにより、複雑な演算によって暗号文が構成されるため、連接鍵攻撃及び差分鍵攻撃は適用できず、本発明による暗号化方式の安全性は高い。
【００３４】
本発明では、入力された暗号文を復号した復号結果を暗号化し、その暗号化結果と入力された暗号文とが一致するか否かを判定して、一致しない場合にはその復号結果を出力しない、または、入力された暗号文を復号した復号結果が複数存在する場合に、それらの復号結果夫々に入力された暗号文の暗号化と同様の演算を秘密鍵を用いて施し、その演算結果に基づいて複数の復号結果から元の平文に一致する復号結果を得る。よって、不正な攻撃者による正規でない暗号文の入力であることを復号時に容易に確認できて、選択暗号文攻撃に対する安全性は高い。
【００３５】
【発明の実施の形態】
本発明の実施の形態について具体的に説明する。
まず、平文に施す変換処理（プリコーディング）について説明する。平文に変換を施す処理をプリコーディングと称し、具体的には平文ベクトルｍ＝（ｍ1 ，ｍ2 ，…，ｍn ）∈｛０，１｝n を変換平文ベクトルｍ′＝（ｍ1 ′，ｍ2 ′，…，ｍn ′）∈｛０，１｝n に変換する処理をプリコーディングという。
【００３６】
復号を保証するために、変換平文ベクトルｍ′の第ｉ成分ｍi ′（ｉ＝１，２，…，ｎ）を平文ベクトルｍの第１成分〜第ｉ成分によって決定する必要がある。即ち、適当な関数Ｆi （・）を用いてｍi ′が下記（１）のように表される必要がある。
ｍi ′＝Ｆi （ｍ1 ，ｍ2 ，…，ｍi ）  …（１）
このように本発明におけるプリコーディングは関数Ｆi （・）の集合であるが、以下では単にＦと記し、ベクトルｍ′＝Ｆ（ベクトルｍ）と表す。なお、各関数Ｆi （・）は夫々任意の関数で良く、逆関数が必ずしも存在する必要はない。
【００３７】
プリコーディングＦに関して、以下のことを定義する。
［定義１］
任意のベクトルｍ∈｛０，１｝n に対してベクトルｍ＝ＦL （ベクトルｍ）となるＬをＦの位数と定義し、Ｌ＝｜Ｆ｜と表す。
［定義２］
ベクトルｍ′＝Ｆ（ベクトルｍ）とし、ベクトルｍとベクトルｍ′との重みの和の最大値をＳmax （Ｆ）と定義する。
【００３８】
（第１実施の形態）
図１は、本発明の第１実施の形態による暗号化方式をエンティティａ，ｂ間の情報通信に利用した状態を示す模式図である。図１の例では、一方のエンティティａ側で、平文（暗号化単位としてのｎ次元ベクトルｍ（成分ｍi ））を暗号文Ｃに暗号化し、通信路１を介してその暗号文Ｃを他方のエンティティｂへ送信し、エンティティｂ側で、その暗号文Ｃを元の平文に復号する場合を示している。なお、エンティティとしては、人間、装置、機械、プログラム、または、それらを構成要素としたシステムなど多様なものがあり、これらの何れの間であっても、本発明は適用可能である。
【００３９】
送信側であるエンティティａの暗号化装置５０は、平文を入力する平文入力部２と、所定の変換関数Ｆ（・）に従って平文（ベクトルｍ）を変換平文（ｎ次元ベクトルｍ′（成分ｍi ′））に変換する変換平文生成部３と、平文用の公開鍵及び変換平文用の公開鍵を格納するデータベース１０と、平文（ｍi ），変換平文（ｍi ′），平文用の公開鍵（ｃi (1) ）及び変換平文用の公開鍵（ｃi (0) ）を用いて暗号文Ｃを作成する暗号文作成部４とを備えている。また、受信側であるエンティティｂの復号装置６０は、送られてきた暗号文Ｃを復号する復号部５と、得られた元の平文を出力する平文出力部６とを備えている。この例では、公開鍵の発行者は受信側のエンティティｂであり、その公開鍵の利用者は送信側のエンティティａである。
【００４０】
次に、具体的な手法について説明する。
〔鍵生成〕
第１実施の形態では、秘密鍵と公開鍵とを以下のように生成する。
・秘密鍵：Ｐ，｛ｖi (j) ｝，ｗ
・公開鍵：｛ｃi (j) ｝，Ｆ
（ｉ＝１，２，…，ｎ、ｊ＝０，１）
【００４１】
自然数であるｖi (j) を、下記（２）を満たすように生成する。但し、基数積Ｂi (j) を下記（３）のように定義し、全ての基数積が略同程度のビット長となるように設定する。即ち、ｖn (j) をｋビットとした場合、各基数積Ｂi (j) が（ｎ＋ｋ）ビット程度になるように設定する。ｖi (j) が全数探索によって露呈しないように、ｋ≧６４とすることが望ましい。
ｖi (j) ≡ｊ  （mod Ｐ）      …（２）
Ｂi (j) ＝２i-1 ｖi (j)       …（３）
【００４２】
全ての基数積を降順に並べ替えた数列をＢi ′（ｉ＝１，２，…，２ｎ）とし、素数Ｐを下記（４）を満たすように生成する。
【００４３】
【数５】
0003722744.tif 000004
【００４４】
また、秘密鍵ｗ∈ＺP をランダムに生成し、基数積Ｂi (j) を下記（５）に従ってモジュラ変換することによって公開鍵ｃi (j) を得る。
ｃi (j) ≡ｗＢi (j)   （mod Ｐ）      …（５）
【００４５】
更に、プリコーディング用の適当な関数Ｆを定めて、それを公開する。
【００４６】
〔暗号化〕
エンティティａ側にて、変換平文生成部３は、公開された関数Ｆを用いて、平文入力部２に入力された平文（ｍi ）から変換平文（ｍi ′）を生成する。そして、暗号文作成部４は、平文（ｍi ），変換平文（ｍi ′），平文用の公開鍵（ｃi (1) ）及び変換平文用の公開鍵（ｃi (0) ）を用いて、下記（６）に示す暗号化アルゴリズムに従って、エンティティｂへの暗号文Ｃを作成する。ｍi ，ｍi ′∈｛０，１｝であるため、暗号文Ｃは加算のみで求めることができる。
【００４７】
【数６】
0003722744.tif 000005
【００４８】
このようにして作成された暗号文Ｃは、通信路１を介してエンティティａからエンティティｂへ送信される。そしてエンティティｂ側で、その暗号文Ｃが元の平文（ｍi ）に復号される。
【００４９】
〔復号〕
中間平文Ｍ1 を下記（７）として求めた場合、Ｍ1 ＜Ｐであるため、下記（８）が成立する。
Ｍ1 ≡ｗ-1Ｃ  （mod Ｐ）      …（７）
Ｍ1 ＝Ｂ1 (0) ｍ1 ′＋Ｂ2 (0) ｍ2 ′＋…＋Ｂn (0) ｍn ′
＋Ｂ1 (1) ｍ1 ＋Ｂ2 (1) ｍ2 ＋…＋Ｂn (1) ｍn     …（８）
【００５０】
上記式（２）及び式（３）より、Ｂ1 (1) を除く全ての基数積Ｂi (j) は偶数であるため、下記（９）が成立する。
ｍ1 ≡Ｍ1   （mod ２）      …（９）
【００５１】
従って、エンティティｂにおける復号部５での復号処理は、下記（10）に示す復号アルゴリズムに従って行われる。
【００５２】
【数７】
0003722744.tif 000006
【００５３】
この復号アルゴリズムは、主に１ビットの右シフト演算，偶奇判定，減算だけによって行うことができ、極めて高速な処理が可能である。
【００５４】
復号アルゴリズムが終了した後に、下記（11）に示すような健全性チェックを行うことによって、選択暗号文攻撃に対する安全性を向上することができる。
【００５５】
【数８】
0003722744.tif 000007
【００５６】
この第１実施の形態では、ｃi (0) ，ｃi (1) の何れもが加算されていない場合、及び、逆に両方が加算されている場合が存在するので、暗号文Ｃを差分鍵｜ｃi (0) −ｃi (1) ｜の線形結合として表現できないため、差分鍵攻撃は適用できずに安全である。
【００５７】
（第２実施の形態）
図２は、本発明の第２実施の形態による暗号化方式をエンティティａ，ｂ間の情報通信に利用した状態を示す模式図である。第１実施の形態（図１）と同様に、エンティティａが送信側であり、エンティティｂが受信側である。
【００５８】
送信側のエンティティａの暗号化装置５０は、平文（暗号化単位としてのｎ次元ベクトルｍ（成分ｍi ））を入力する平文入力部１２と、所定の変換関数Ｈ（・）に従って平文（ベクトルｍ）を変換平文（ｎ次元ベクトルｍ″（成分ｍi ″））に変換する変換平文生成部１３と、公開鍵を格納するデータベース２０と、平文（ｍi ），変換平文（ｍi ″）及び公開鍵（ｃi (mi)）を用いて暗号文Ｃを作成する暗号文作成部１４とを備えている。また、受信側のエンティティｂの復号装置６０は、送られてきた暗号文Ｃを復号する復号部１５と、元の平文（ｍi ）を出力する平文出力部１６とを備えている。
【００５９】
次に、具体的な手法について説明する。
〔鍵生成〕
第２実施の形態では、秘密鍵と公開鍵とを以下のように生成する。
・秘密鍵：Ｐ，｛ｖi (j) ｝，ｗ
・公開鍵：｛ｃi (j) ｝，Ｈ
（ｉ＝１，２，…，ｎ、ｊ＝０，１）
【００６０】
自然数であるｖi (j) 及び基数積Ｂi (j) を、第１実施の形態と同様に設定する。また、素数Ｐを下記（12）を満たすように生成する。但し、ｍａｘ（ｘ，ｙ）はｘ，ｙの小さくない方を表す。
【００６１】
【数９】
0003722744.tif 000008
【００６２】
また、秘密鍵ｗ∈ＺP をランダムに生成し、ｃi (j) を上記（５）に従って求める。更に、プリコーディング用の適当な関数Ｈを定めて、それを公開する。
【００６３】
〔暗号化〕
エンティティａ側にて、変換平文生成部１３は、公開された関数Ｈを用いて、平文入力部１２に入力された平文（ｍi ）から変換平文（ｍi ″）を生成する。そして、暗号文作成部１４は、平文（ｍi ），変換平文（ｍi ″）及び公開鍵（ｃi (mi)）を用いて、下記（13）に示す暗号化アルゴリズムに従って、エンティティｂへの暗号文Ｃを作成する。ｍi ，ｍi ″∈｛０，１｝であるため、暗号文Ｃは加算及び減算のみで求めることができる。
【００６４】
【数１０】
0003722744.tif 000009
【００６５】
このようにして作成された暗号文Ｃは、通信路１を介してエンティティａからエンティティｂへ送信される。そしてエンティティｂ側で、その暗号文Ｃが元の平文（ｍi ）に復号される。
【００６６】
〔復号〕
中間平文Ｍ1 を下記（14）とする。
【００６７】
【数１１】
0003722744.tif 000010
【００６８】
２つの中間平文Ｍ1 + ，Ｍ1 - を下記（15），（16）として求めた場合、Ｍ1 ＝Ｍ1 + またはＭ1 ＝Ｍ1 - の何れか一方のみが成立する。
Ｍ1 + ≡ｗ-1Ｃ  （mod Ｐ）      …（15）
Ｍ1 - ＝Ｍ1 + −Ｐ      …（16）
エンティティｂ側では、何れが成立するかを特定できないため、夫々について復号を実行しなければならない。しかしながら、後述するような健全性チェックが可能であるので、平文が出力された方を採用することにより、正しい平文を得ることができる。
【００６９】
具体的に、エンティティｂにおける復号部１５での復号処理は、下記（17）に示す復号アルゴリズムに従って行われ、その後の健全性チェックは、下記（18）に示すようにして行われる。
【００７０】
【数１２】
0003722744.tif 000011
【００７１】
この第２実施の形態でも、第１実施の形態と同様に、高速な復号処理が可能である。
【００７２】
第２実施の形態では、暗号化において第１実施の形態のように公開鍵を加算するだけでなく、減算する場合もあるので、暗号文の大きさは更に小さくなり、暗号文密度が高くなる。また、この第２実施の形態の解読問題はナップザック問題よりも更に複雑度が高い問題と考えられ、安全性が向上している。なお、第２実施の形態では、Ｍ1 + 及びＭ1 - の両方が健全性チェックを満足する可能性があるが、プリコーディングされた変換平文ベクトルは乱数性が高く、そのような可能性は無視できる程度に小さいと考えられる。
【００７３】
（第３実施の形態）
図３は、本発明の第３実施の形態による暗号化方式をエンティティａ，ｂ間の情報通信に利用した状態を示す模式図である。第１実施の形態（図１）と同様に、エンティティａが送信側であり、エンティティｂが受信側である。この第３実施の形態は、前述した第１及び第２実施の形態を組み合わせたものである。
【００７４】
送信側のエンティティａの暗号化装置５０は、平文（暗号化単位としてのｎ次元ベクトルｍ（成分ｍi ））を入力する平文入力部２２と、所定の変換関数Ｆ（・）に従って平文（ベクトルｍ）を変換平文（ｎ次元ベクトルｍ′（成分ｍi ′））に変換すると共に、所定の変換関数Ｈ（・）に従って平文（ベクトルｍ）を変換平文（ｎ次元ベクトルｍ″（成分ｍi ″））に変換する変換平文生成部２３と、公開鍵を格納するデータベース３０と、平文（ｍi ），変換平文（ｍi ′とｍi ″），平文用の公開鍵（ｃi (1) ）及び変換平文用の公開鍵（ｃi (0) ）を用いて暗号文Ｃを作成する暗号文作成部２４とを備えている。また、受信側のエンティティｂの復号装置６０は、送られてきた暗号文Ｃを復号する復号部２５と、元の平文（ｍi ）を出力する平文出力部２６とを備えている。
【００７５】
次に、具体的な手法について説明する。
〔鍵生成〕
第３実施の形態では、秘密鍵と公開鍵とを以下のように生成する。
・秘密鍵：Ｐ，｛ｖi (j) ｝，ｗ
・公開鍵：｛ｃi (j) ｝，Ｆ，Ｈ
（ｉ＝１，２，…，ｎ、ｊ＝０，１）
【００７６】
自然数であるｖi (j) 及び基数積Ｂi (j) を、第１実施の形態と同様に設定する。また、素数Ｐを上記（12）を満たすように生成する。また、秘密鍵ｗ∈ＺP をランダムに生成し、ｃi (j) を上記（５）に従って求める。更に、プリコーディング用の適当な関数Ｆ，Ｈを夫々定めて、それらを公開する。
【００７７】
〔暗号化〕
エンティティａ側にて、変換平文生成部２３は、公開された関数Ｆを用いて、平文入力部２２に入力された平文（ｍi ）から変換平文（ｍi ′）を生成すると共に、公開された関数Ｈを用いて、平文（ｍi ）から変換平文（ｍi ″）を生成する。そして、暗号文作成部２４は、平文（ｍi ），変換平文（ｍi ′とｍi ″），平文用の公開鍵（ｃi (1) ）及び変換平文用の公開鍵（ｃi (0) ）を用いて、下記（19）に示す暗号化アルゴリズムに従って、エンティティｂへの暗号文Ｃを作成する。ｍi ，ｍi ′，ｍi ″∈｛０，１｝であるため、暗号文Ｃは加算及び減算のみで求めることができる。
【００７８】
【数１３】
0003722744.tif 000012
【００７９】
このようにして作成された暗号文Ｃは、通信路１を介してエンティティａからエンティティｂへ送信される。そしてエンティティｂ側で、その暗号文Ｃが元の平文（ｍi ）に復号される。
【００８０】
〔復号〕
エンティティｂ側では、第２実施の形態と同様、Ｍ1 + ≡ｗ-1Ｃ（mod Ｐ）及びＭ1 - ＝Ｍ1 + −Ｐの夫々について復号を実行する。具体的に、エンティティｂにおける復号部２５での復号処理は、下記（20）に示す復号アルゴリズムに従って行われ、その後の健全性チェックは、下記（21）に示すようにして行われる。
【００８１】
【数１４】
0003722744.tif 000013
【００８２】
この第３実施の形態でも、第１，第２実施の形態と同様に、復号処理は高速化されている。第３実施の形態では、前述した第１，第２実施の形態における利点を併せて持っているので、極めて安全性が高い暗号化方式と言える。
【００８３】
ところで、上記説明において、平文を変換平文に変換するプリコーディングのための変換関数は一例であり、他の変換関数を用いても良い。また、複数の変換関数を合成して構成される新しい関数を、プリコーディング用の変換関数に採用することも可能である。なお、以下では、簡単に構成できるプリコーディング用の変換関数として、喜安−Ｇｒａｙ逆変換に基づく変換関数について詳述する。
【００８４】
喜安−Ｇｒａｙ逆変換に基づく２通りの変換関数Ｇ0 及びＧ1 を考え、夫々を下記（22）及び（23）のように定義する。
【００８５】
【数１５】
0003722744.tif 000014
【００８６】
このような変換関数Ｇ0 ，Ｇ1 に関して、以下の定理が成立する。
［定理１］
変換関数Ｇ0 ，Ｇ1 の位数ＬGo，ＬG1は夫々下記（24），（25）のように    なる。
【００８７】
【数１６】
0003722744.tif 000015
【００８８】
下記（26）に示されるベクトルｍ′を上記（22）を繰り返し用いて展開すると、任意のｎに対してｍi ′＝ｍi （ｉ＝１，２，…，ｎ）となる。Ｇ1 h についても同様である。
【００８９】
【数１７】
0003722744.tif 000016
【００９０】
［定理２］
ベクトルｍ＝（ｍ1 ，ｍ2 ，…，ｍn ）とし、ｎを２のべき数とした場合には、Ｇ1 h （ベクトルｍ）の重みとＧ1 n+h （ベクトルｍ）の重みとの差は１である。
【００９１】
ベクトルｍ″＝Ｇ1 h （ベクトルｍ），ベクトルｍ′＝Ｇ1 n+h （ベクトルｍ）とおくと、Ｇ1 n+h （ベクトルｍ）＝Ｇ1 n （ベクトルｍ″）である。このとき、Ｇ1 n （ベクトルｍ″）を上記（23）を用いて展開した場合、下記（27）が成立する。従って、任意のｈに対してベクトルｍ″の重みとベクトルｍ′の重みとの差は１となる。
【００９２】
【数１８】
0003722744.tif 000017
【００９３】
［定理３］
ベクトルｍ＝（ｍ1 ，ｍ2 ，…，ｍn ）とした場合、ベクトルｍ′＝Ｇ0 （ベクトルｍ），ベクトルｍ′＝Ｇ1 （ベクトルｍ）夫々におけるＳmax （Ｇ0 ），Ｓmax （Ｇ1 ）は下記（28），（29）で与えられる。
【００９４】
【数１９】
0003722744.tif 000018
【００９５】
第ｉビット目までのベクトルｍとベクトルｍ′との重みの和をＳi とする。即ち、下記（30）のように定義する。Ｓi ＝Ｓi-1 ＋ｍi ＋ｍi ′であるので、下記（31）が成立する。
【００９６】
【数２０】
0003722744.tif 000019
【００９７】
従って、（ｂ）→（ｄ）→（ｂ）→（ｄ）→・・・と選ぶことによってＳn は最大となり、変換関数Ｇ0 を施す場合は最初に（ｄ）が選ばれるのでＳn 即ちＳmax （Ｇ0 ）は上記（28）で与えられ、同様に、変換関数Ｇ1 を施す場合は最初に（ｂ）が選ばれるのでＳn 即ちＳmax （Ｇ1 ）は上記（29）で与えられる。
【００９８】
［定理４］
可逆なプリコーディング用の変換関数Ｆの位数をＬとした場合、Ｓmax （ＦL/2-h ）とＳmax （ＦL/2+h ）とは一致する。
【００９９】
ベクトルｍ′＝ＦL/2-h （ベクトルｍ）のときに、Ｓmax （ＦL/2-h ）を与えるとする。Ｆの位数がＬであることにより、ベクトルｍ＝ＦL/2+h （ベクトルｍ′）である。このとき、Ｓmax （ＦL/2+h ）が与えられて、両者は等しい。
【０１００】
プリコーディング用の変換関数Ｇ0 h ，Ｇ1 h を前述した第１〜第３実施の形態に適用した場合について考察する。Ｇ0 h は全成分が０となるような平文ベクトルｍに対して恒等変換となるので、暗号文から直ちに平文を求められてしまうため、Ｇ0 h を利用すべきではない。一方、Ｇ1 h は下記（32）において任意の平文に対して恒等変換とはなり得ないので、Ｇ1 h を用いることが望ましい。
【０１０１】
【数２１】
0003722744.tif 000020
【０１０２】
平文ベクトルｍの次元ｎ＝８，１２，…，３２としてＧ1 h を適用する場合について、繰り返し回数ｈとＳmax （Ｇ1 h ）との関係を図４に示す。図４より、下記（33）が成立する。
【０１０３】
【数２２】
0003722744.tif 000021
【０１０４】
変換関数Ｇ1 h を前述した第１〜第３実施の形態に適用する際には、以下の点に留意すべきである。
・定理２及び定理３より、１≦ｈ≦Ｌ／２とすることが望ましい。
・第１実施の形態に適用する場合、Ｓmax （Ｇ1 h ）が小さくなるようなｈ（図４の谷の部分）を選ぶことが望ましい。
【０１０５】
喜安−Ｇｒａｙ逆変換は可逆演算であり、定理２及び定理４から明らかなように、周期性及び対称性を有するため、それらの性質を利用した攻撃法が存在する可能性がある。従って、Ｇ0 とＧ1 とを適当に混合した変換関数、論理積，論理和などの非可逆な演算を一部に組み込ませてそれらの性質を除去した変換関数を利用することが好ましい。
【０１０６】
ここで、前述した暗号化装置５０，復号装置６０のハードウェアの構成例について図５を参照して説明する。
【０１０７】
暗号化装置５０は、ＣＰＵ５１，通信部５２，操作部５３，表示部５４，ＲＯＭ５５，ＲＡＭ５６，鍵格納部５７等を備えている。ＣＰＵ５１は、バス５８を介して暗号化装置５０の上記ハードウェア各部と接続されていて、それらを制御すると共に、ＲＯＭ５５に格納された暗号化処理のコンピュータプログラムに従って、種々のソフトウェア的機能を実行する。通信部５２は、通信路１を介した送信・受信処理を実行する。操作部５３は、ユーザによる暗号化すべき平文の入力等の外部からの操作を受け付ける。表示部５４は、入力された暗号化すべき平文等を表示する。ＲＯＭ５５は、暗号化装置５０の上述した暗号化処理の動作に必要な種々のソフトウェアのコンピュータプログラムを予め格納している。ＲＡＭ５６は、ＳＲＡＭまたはフラッシュメモリ等で構成され、暗号化処理の動作時に発生する一時的なデータ（変換平文等）を記憶する。鍵格納部２７は、上述した変換関数を含む公開鍵を格納している。
【０１０８】
一方、復号装置６０は、ＣＰＵ６１，通信部６２，操作部６３，表示部６４，ＲＯＭ６５，ＲＡＭ６６，鍵格納部６７，出力部６８等を備えている。ＣＰＵ６１は、バス６９を介して復号装置６０の上記ハードウェア各部と接続されていて、それらを制御すると共に、ＲＯＭ６５に格納された復号処理のコンピュータプログラムに従って、種々のソフトウェア的機能を実行する。通信部６２は、通信路１を介した送信・受信処理を実行する。操作部６３は、ユーザによる外部からの操作を受け付ける。表示部６４は、復号結果等を表示する。ＲＯＭ６５は、復号装置６０の上述した復号処理の動作に必要な種々のソフトウェアのコンピュータプログラムを予め格納している。ＲＡＭ６６は、ＳＲＡＭまたはフラッシュメモリ等で構成され、復号処理の動作時に発生する一時的なデータ（中間平文，複数の復号結果等）を記憶する。鍵格納部６７は、上述した秘密鍵及び公開鍵を格納している。出力部６８は、復号した元の平文を出力する。
【０１０９】
図６は、本発明の記録媒体の実施の形態の構成を示す図である。ここに例示するプログラムは、上述した第１，第２，第３実施の形態にあって、平文から変換平文を作成する処理と、暗号文を作成する処理とを含むか、または、このように作成された暗号文を復号する処理を含んでおり、以下に説明する記録媒体に記録されている。なお、コンピュータ４０は、各エンティティ側に設けられている。
【０１１０】
図５において、コンピュータ４０とオンライン接続する記録媒体３１は、コンピュータ４０の設置場所から隔たって設置される例えばＷＷＷ(World Wide Web)のサーバコンピュータを用いてなり、記録媒体３１には前述の如きプログラム３１ａが記録されている。記録媒体３１から通信線等の伝送媒体３４を介して読み出されたプログラム３１ａがコンピュータ４０を制御することにより、コンピュータ３０が暗号文を作成するか、または、暗号文を平文に復号する。
【０１１１】
コンピュータ４０の内部に設けられた記録媒体３２は、内蔵設置される例えばハードディスクドライブまたはＲＯＭ（図５のＲＯＭ５５またはＲＯＭ６５に相当）等を用いてなり、記録媒体３２には前述の如きプログラム３２ａが記録されている。記録媒体３２から読み出されたプログラム３２ａがコンピュータ４０を制御することにより、コンピュータ４０が暗号文を作成するか、または、暗号文を平文に復号する。
【０１１２】
コンピュータ４０に設けられたディスクドライブ４０ａに装填して使用される記録媒体３３は、運搬可能な例えば光磁気ディスク，ＣＤ−ＲＯＭまたはフレキシブルディスク等を用いてなり、記録媒体３３には前述の如きプログラム３３ａが記録されている。記録媒体３３から読み出されたプログラム３３ａがコンピュータ４０を制御することにより、コンピュータ４０が暗号文を作成するか、または、暗号文を平文に復号する。
【０１１３】
【発明の効果】
以上詳述したように、本発明では、暗号化すべき平文を所定の変換関数に基づいて１または複数の変換平文に変換（プリコーディング）し、その変換平文と元の平文と１種または複数種の公開鍵とを利用して暗号文を作成するようにしたので、プリコーディング手法を用いて変換した変換平文を組み込ませているため、高速な暗号化・復号処理が可能であるという従来例の利点は維持しつつ、特に連接鍵攻撃及び差分鍵攻撃に対する安全性の向上を実現することができる。
【０１１４】
本発明では、入力された暗号文を復号した復号結果を暗号化し、その暗号化結果と入力された暗号文とが一致するか否かを判定して、一致しない場合にはその復号結果を出力しないか、または、入力された暗号文を復号した復号結果が複数存在する場合に、それらの復号結果夫々に入力された暗号文の暗号化と同様の演算を秘密鍵を用いて施し、その演算結果に基づいて複数の復号結果から元の平文に一致する復号結果を得るようにしたので、不正な攻撃者による正規でない暗号文の入力であることを復号時に容易に確認できて、選択暗号文攻撃にする安全性の向上を実現することができる。
【０１１５】
以上のことから、公開鍵暗号系の発展及び実用化を図る上で、本発明は大いに寄与できる。
【図面の簡単な説明】
【図１】第１実施の形態での両エンティティ間における情報の暗号通信状態を示す模式図である。
【図２】第２実施の形態での両エンティティ間における情報の暗号通信状態を示す模式図である。
【図３】第３実施の形態での両エンティティ間における情報の暗号通信状態を示す模式図である。
【図４】変換の繰り返し回数ｈと最大重みＳmax （Ｇ1 h ）との関係を示すグラフである。
【図５】暗号化装置及び復号装置のハードウェア構成例を示す図である。
【図６】記録媒体の実施の形態の構成を示す図である。
【符号の説明】
１  通信路
２，１２，２２  平文入力部
３，１３，２３  変換平文生成部
４，１４，２４  暗号文作成部
５，１５，２５  復号部
６，１６，２６  平文出力部
１０，２０，３０  データベース
３１，３２，３３  記録媒体
４０  コンピュータ
５０  暗号化装置
６０  復号装置
【図１】
0003722744.tif 000024
【図２】
0003722744.tif 000025
【図３】
0003722744.tif 000026
【図４】
0003722744.tif 000027
【図５】
0003722744.tif 000028
【図６】
0003722744.tif 000029