(57)【要約】【課題】伸長処理と復号化処理を行う情報処理装置の記憶容量を最小限にするとともに、効率的な伸長処理および復号化処理を実現すること。【解決手段】復号化処理装置２００において、圧縮データと最終出力データまたは補助出力データとを入力して暗号文データと補助出力データを出力する伸長写像を、圧縮暗号文データに含まれる複数の圧縮データに施して、複数の圧縮データのそれぞれを伸長した複数の暗号文データを求める伸長処理部２０４と、複数の暗号文データのそれぞれに対して、公開鍵に対応する秘密鍵を用いて復号化処理を施して平文データを取得する復号化処理部２０３と、復号化手順に基づいて、伸長処理と復号化処理の並列実行を制御するとともに、伸長処理部で出力された暗号文データに対する復号化処理部による復号化処理を制御する並列処理制御部２０２とを備えた。【選択図】        図１
2009193024.tif 000002
【特許請求の範囲】
【請求項１】
平文データに対して公開鍵を用いて暗号化処理を施して複数の暗号文データを出力する暗号化処理と、前記暗号文データのそれぞれと付加的な入力である付加入力データとから前記暗号文データを圧縮した圧縮データと中間的な出力である補助出力データとを出力する圧縮写像を、前記暗号文データのそれぞれについて施して、複数の前記圧縮データと前記補助出力データとして最終的に出力された最終出力データとを含む圧縮暗号文データを出力する圧縮処理とを行う暗号化処理装置からネットワークを介して前記圧縮暗号文データを受信する受信部と、
前記複数の暗号文データの前記暗号化処理における出力順序、前記複数の暗号文データおよび前記付加入力データの前記圧縮写像への入力順序に基づいて前記複数の圧縮データの伸長処理の順序および前記複数の暗号文データの復号化処理の順序を予め定めた復号化手順を記憶する記憶部と、
前記圧縮データと前記最終出力データまたは前記補助出力データとを入力して前記暗号文データと前記補助出力データを出力する伸長写像を、前記圧縮暗号文データに含まれる前記複数の圧縮データに施して、前記複数の圧縮データのそれぞれを伸長した前記複数の暗号文データを求める伸長処理部と、
前記複数の暗号文データのそれぞれに対して、前記公開鍵に対応する秘密鍵を用いて復号化処理を施して前記平文データを取得する復号化処理部と、
前記復号化手順に基づいて、前記伸長処理と前記復号化処理の並列実行を制御するとともに、前記伸長処理部で出力された前記暗号文データに対する前記復号化処理部による前記復号化処理を制御する制御部と、
を備えたことを特徴とする復号化処理装置。
【請求項２】
前記圧縮処理は、前記暗号文データに対して２回目以降に前記圧縮写像を施す場合に、前回の前記圧縮写像で出力された前記補助出力データを前記付加入力データとして入力し、
前記伸長処理部は、最初に前記圧縮データを前記伸長写像に施す場合に、一の前記圧縮データと前記最終出力データを入力し、２回目以降に前記圧縮データを前記伸長写像に施す場合に、前記一の圧縮データと異なる圧縮データと前回の前記伸長写像で出力された補助出力データとを前記伸長写像に入力し、
前記復号化手順は、さらに、前記補助出力データの前記圧縮写像への入力順序に基づいて前記複数の圧縮データの伸長処理の順序および前記複数の暗号文データの復号化処理の順序を予め定めたことを特徴とする請求項１に記載の復号化処理装置。
【請求項３】
前記暗号化処理は、複数回のべき乗または乗算により前記平文データに暗号化処理を施し、
前記復号化処理部は、複数回のべき乗または乗算により前記複数の圧縮データのそれぞれに復号化処理を施すことを特徴とする請求項１または２に記載の復号化処理装置。
【請求項４】
前記暗号化処理は、ハッシュ関数を用いて前記平文データに暗号化処理を施し、
前記復号化処理部は、前記ハッシュ関数を用いて前記複数の圧縮データのそれぞれに復号化処理を施すことを特徴とする請求項１〜３のいずれか一つに記載の復号化処理装置。
【請求項５】
前記暗号化処理は、前記複数の暗号文データのうち一部の暗号文データを入力する前記ハッシュ関数を用いることにより前記平文データに暗号化処理を施し、
前記復号化処理部は、前記複数の暗号文データのうち復号化された一部の暗号文データを入力する前記ハッシュ関数を用いて前記複数の圧縮データのそれぞれに復号化処理を施すことを特徴とする請求項４に記載の復号化処理装置。
【請求項６】
前記暗号化処理は、前記圧縮写像により出力された圧縮データを入力する前記ハッシュ関数を用いることにより前記平文データに暗号化処理を施し、
前記復号化処理部は、前記圧縮データを入力する前記ハッシュ関数を用いて前記複数の圧縮データのそれぞれに復号化処理を施すことを特徴とする請求項４に記載の復号化処理装置。
【請求項７】
前記圧縮処理は、前記複数の暗号文データのうち一部の前記暗号文データに対して、前記付加入力データの入力を行わず、かつ前記補助出力データを出力しない第２の圧縮写像を施して前記圧縮データを求め、
前記伸長処理部は、前記複数の圧縮データのうち一部の前記圧縮データに対して、前記最終出力データまたは前記補助出力データを入力せずに前記暗号文データのみを出力する第２の伸長写像を施して前記暗号文データを求めることを特徴とする請求項４に記載の復号化処理装置。
【請求項８】
前記圧縮処理は、代数的トーラスに基づく前記圧縮写像を用いて前記複数の暗号文データを圧縮し、
前記伸長処理部は、代数的トーラスに基づく前記圧縮写像を用いて前記複数の圧縮データを伸長することを特徴とする請求項１〜７のいずれか一つに記載の復号化処理装置。
【請求項９】
前記暗号化処理は、前記平文データに対して、有限体上の離散対数問題に基づいた暗号化処理を施し、
前記復号化処理部は、伸長処理が施された前記複数の暗号文データに対して、有限体上の離散対数問題に基づいた復号化処理を施すことを特徴とする請求項１〜８のいずれか一つに記載の復号化処理装置。
【請求項１０】
暗号化処理装置と、前記暗号化処理装置とネットワークで接続された復号化処理装置とを備えた暗号処理システムであって、
前記暗号化処理装置は、
平文データに対して公開鍵を用いて暗号化処理を施して複数の暗号文データを出力する暗号化処理部と
前記暗号文データのそれぞれと付加的な入力である付加入力データとから前記暗号文データを圧縮した圧縮データと中間的な出力である補助出力データとを出力する圧縮写像を、前記暗号文データのそれぞれについて施して、複数の前記圧縮データと前記補助出力データとして最終的に出力された最終出力データとを含む圧縮暗号文データを出力する圧縮処理部と、
前記圧縮暗号文データを前記復号化処理装置に送信する送信部と、
前記複数の暗号文データの前記暗号化処理における出力順序、前記複数の暗号文データおよび前記付加入力データの前記圧縮写像への入力順序に基づいて前記平文データの暗号化処理の順序および前記複数の暗号文データの圧縮処理の順序を予め定めた暗号化手順を記憶する第１記憶部と、
前記暗号化手順に基づいて、前記暗号化処理と前記圧縮処理との並列実行を制御するとともに、前記暗号化処理部で出力された前記複数の暗号文データに対する前記圧縮処理部による前記圧縮処理を制御する第１制御部と、を備え、
前記暗号化処理部は、前記圧縮写像により出力された圧縮データを入力する前記ハッシュ関数を用いることにより前記平文データに暗号化処理を施し、
前記復号化処理装置は、
前記暗号化処理装置から前記圧縮暗号文データを受信する受信部と、
前記複数の暗号文データの前記暗号化処理における出力順序、前記複数の暗号文データおよび前記付加入力データの前記圧縮写像への入力順序に基づいて前記複数の圧縮データの伸長処理の順序および前記複数の暗号文データの復号化処理の順序を予め定めた復号化手順を記憶する記憶部と、
前記圧縮データと前記最終出力データまたは前記補助出力データとを入力して前記暗号文データと前記補助出力データを出力する伸長写像を、前記圧縮暗号文データに含まれる前記複数の圧縮データに施して、前記複数の圧縮データのそれぞれを伸長した前記複数の暗号文データを求める伸長処理部と、
前記複数の暗号文データのそれぞれに対して、前記公開鍵に対応する秘密鍵を用いて復号化処理を施して前記平文データを取得する復号化処理部と、
前記復号化手順に基づいて、前記伸長処理と前記復号化処理の並列実行を制御するとともに、前記伸長処理部で出力された前記暗号文データに対する前記復号化処理部による前記復号化処理を制御する第２制御部と、を備え、
前記復号化処理部は、前記圧縮データを入力する前記ハッシュ関数を用いて前記複数の圧縮データのそれぞれに復号化処理を施すことを特徴とする暗号処理システム。
【請求項１１】
前記圧縮処理部は、前記複数の暗号文データのうち一部の前記暗号文データに対して、前記付加入力データの入力を行わず、かつ前記補助出力データを出力しない第２の圧縮写像を施して前記圧縮データを求め、
前記伸長処理部は、前記複数の圧縮データのうち一部の前記圧縮データに対して、前記最終出力データまたは前記補助出力データを入力せずに前記暗号文データのみを出力する第２の伸長写像を施して前記暗号文データを求めることを特徴とする請求項１０に記載の暗号処理システム。
【請求項１２】
復号化処理装置で実行される復号化処理方法であって、
平文データに対して公開鍵を用いて暗号化処理を施して複数の暗号文データを出力する暗号化処理と、前記暗号文データのそれぞれと付加的な入力である付加入力データとから前記暗号文データを圧縮した圧縮データと中間的な出力である補助出力データとを出力する圧縮写像を、前記暗号文データのそれぞれについて施して、複数の前記圧縮データと前記補助出力データとして最終的に出力された最終出力データとを含む圧縮暗号文データを出力する圧縮処理とを行う暗号化処理装置からネットワークを介して前記圧縮暗号文データを受信する受信ステップと、
前記圧縮データと前記最終出力データまたは前記補助出力データとを入力して前記暗号文データと前記補助出力データを出力する伸長写像を、前記圧縮暗号文データに含まれる前記複数の圧縮データに施して、前記複数の圧縮データのそれぞれを伸長した前記複数の暗号文データを求める伸長処理ステップと、
前記複数の暗号文データのそれぞれに対して、前記公開鍵に対応する秘密鍵を用いて復号化処理を施して前記平文データを取得する復号化処理ステップと、
前記複数の暗号文データの前記暗号化処理における出力順序、前記複数の暗号文データおよび前記付加入力データの前記圧縮写像への入力順序に基づいて前記複数の圧縮データの伸長処理の順序および前記複数の暗号文データの復号化処理の順序を予め定めた復号化手順を記憶する記憶部の前記復号化手順に基づいて、前記伸長処理と前記復号化処理の並列実行を制御するとともに、前記伸長処理部で出力された前記暗号文データに対する前記復号化処理部による前記復号化処理を制御する制御ステップと、
を含むことを特徴とする復号化処理方法。
【請求項１３】
コンピュータを、
平文データに対して公開鍵を用いて暗号化処理を施して複数の暗号文データを出力する暗号化処理と、前記暗号文データのそれぞれと付加的な入力である付加入力データとから前記暗号文データを圧縮した圧縮データと中間的な出力である補助出力データとを出力する圧縮写像を、前記暗号文データのそれぞれについて施して、複数の前記圧縮データと前記補助出力データとして最終的に出力された最終出力データとを含む圧縮暗号文データを出力する圧縮処理とを行う暗号化処理装置からネットワークを介して前記圧縮暗号文データを受信する受信部と、
前記複数の暗号文データの前記暗号化処理における出力順序、前記複数の暗号文データおよび前記付加入力データの前記圧縮写像への入力順序に基づいて前記複数の圧縮データの伸長処理の順序および前記複数の暗号文データの復号化処理の順序を予め定めた復号化手順を記憶する記憶部と、
前記圧縮データと前記最終出力データまたは前記補助出力データとを入力して前記暗号文データと前記補助出力データを出力する伸長写像を、前記圧縮暗号文データに含まれる前記複数の圧縮データに施して、前記複数の圧縮データのそれぞれを伸長した前記複数の暗号文データを求める伸長処理部と、
前記複数の暗号文データのそれぞれに対して、前記公開鍵に対応する秘密鍵を用いて復号化処理を施して前記平文データを取得する復号化処理部と、
前記復号化手順に基づいて、前記伸長処理と前記復号化処理の並列実行を制御するとともに、前記伸長処理部で出力された前記暗号文データに対する前記復号化処理部による前記復号化処理を制御する制御部と、
として機能させることを特徴とする復号化処理プログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、平文データを暗号化処理して圧縮した圧縮暗号文データを伸長して復号化処理を施す復号化処理装置、暗号処理システム、復号化処理方法およびプログラムに関する。
【背景技術】
【０００２】
事前の鍵共有なしに安全な通信を実現する公開鍵暗号、デジタル文書の正当性を保障する電子署名など公開鍵を用いた各種スキームやプロトコルはネットワーク・セキュリティの基盤技術として幅広く利用されている。また、情報端末の多様化が進み、小型機器においても方式や実装を工夫して公開鍵を用いた各種スキームやプロトコルが使用されるようになってきている。
【０００３】
公開鍵暗号の典型的な鍵サイズは１０２４ビットであるが、計算機の進歩とともに攻撃者の能力も向上していることから、解読が困難とされる鍵サイズは年々増大してきている。公開鍵暗号では暗号文サイズは、暗号化の方式によって異なるが、一般的には鍵サイズの数倍となるので、メモリ容量や通信帯域が十分でない計算機にとっては鍵サイズの増大が問題になる。
【０００４】
このため、ＥｌＧａｍａｌ暗号において公開鍵暗号における暗号文サイズを圧縮する暗号圧縮技術が考えられている（例えば、非特許文献１参照）。この暗号圧縮技術は、公開鍵暗号で用いる数の集合のうち代数的トーラスと呼ばれる部分集合を用いると、集合の要素を少ないビット数で表現できるという事実に基づいている。圧縮率、すなわち圧縮前のビット数の圧縮後のビット数に対する割合を増大するための改良技術として、集合の要素を少ないビット数の表現に変換する際に、補助入力と呼ばれる付加的入力を用いる技術が知られている（例えば、非特許文献２参照）。
【０００５】
ここで、少ないビット数の表現へ変換を行う写像をθと書き、θを圧縮写像とする。圧縮写像θでは、暗号文ｃが入力として与えられたときに、（１）式に示すように、適当な付加的入力ａ１を用いて計算を行い、圧縮暗号文であるγと補助出力ａ2を得る。
【０００６】
θ（ｃ，ａ1）＝（γ，ａ2）  ・・・（１）
圧縮写像θによる変換前の元のビット数の表現は、変換後のビット数の表現に対してθの逆写像である伸長写像θ-1を計算することにより求めることができる。伸長写像θ-1を用いて（２）式に示すように、圧縮暗号文としてγと補助出力（中間出力）ａ2の組を入力して計算を行い、元のビット数の表現である暗号文ｃと補助入力ａ1が算出される。
【０００７】
θ-1（γ，ａ2）＝  （ｃ，ａ1）  ・・・（２）
代数的トーラスを用いた圧縮伸長は、公開鍵暗号における暗号文だけでなく、電子署名における署名や鍵交換スキームにおける交換メッセージにも適用することができる。
【０００８】
【非特許文献１】Ｋ．Ｒｕｂｉｎ  ａｎｄ  Ａ．Ｓｉｌｖｅｒｂｅｒｇ．“Ｔｏｒｕｓ−Ｂａｓｅｄ  Ｃｒｙｐｔｏｇｒａｐｈｙ”，ＣＲＹＰＴＯ  ２００３，Ｓｐｒｉｎｇｅｒ  ＬＮＣＳ  ２７２９，３４９−３６５，２００３．
【非特許文献２】Ｍ．ｖａｎ  Ｄｉｊｋ  ａｎｄ  Ｄ．Ｗｏｏｄｒｕｆｆ．“Ａｓｙｍｐｔｏｔｉｃａｌｌｙ  Ｏｐｔｉｍａｌ  Ｃｏｍｍｕｎｉｃａｔｉｏｎ  ｆｏｒ  Ｔｏｒｕｓ−Ｂａｓｅｄ  Ｃｒｙｐｔｏｇｒａｐｈｙ”  ＣＲＹＰＴＯ  ２００４，Ｓｐｒｉｎｇｅｒ  ＬＮＣＳ  ３１５２，１５７−１７８，２００４．
【発明の開示】
【発明が解決しようとする課題】
【０００９】
上記非特許文献１で開示されているＥｌＧａｍａｌ暗号の暗号文は、２つの要素（ｃ１，ｃ２）からなっている。そこで、圧縮率を向上させるために、（３−１）、（３−２）式に示すように、第１番目の要素の補助出力ａ２を第２番目の要素の補助入力に用いる。
【００１０】
θ（ｃ1，ａ1）＝（γ1，ａ2）  ・・・（３−１）
θ（ｃ2，ａ2）＝（γ2，ａ3）  ・・・（３−２）
圧縮暗号文は（γ1，γ2，ａ3）となり、補助出力ａ2の分だけ短縮することができる。圧縮暗号文を復号化する際には、まず圧縮暗号文の伸長を行って圧縮前の元の暗号文（ｃ1，ｃ2）に変換してから、暗号文（ｃ1，ｃ2）を復号化して平文を取得する。
【００１１】
圧縮率の向上のため、上記のように第ｉ番目の圧縮の補助出力を第ｉ＋１番目の圧縮の補助入力として入力すると、圧縮暗号文には最後の補助出力しか含まれないことから、伸長処理は圧縮処理の順序と逆の順序で実行する必要がある。
【００１２】
例えば、暗号化処理等の送信者側の処理において計算されたメッセージ（暗号文など送受信されるデータ）から順に圧縮すると、暗号化処理と圧縮処理は並列実行することが容易である。
【００１３】
一方で、復号化処理の際には必要な順に伸長されたメッセージが得られるとは限らず、伸長処理と復号化処理の並列実行を行うことができず、両処理は直列で、すなわち伸長処理を実行してから復号化処理を行うしかなかった。このため通信路上ではメッセージが少ないビット数で圧縮できていても、受信者側の計算機は、元のメッセージが扱えるだけの記憶容量を有するメモリ等の記憶媒体を搭載している必要がある。
【００１４】
本発明は、上記に鑑みてなされたものであって、圧縮暗号文の伸長処理と復号化処理との並列実行を可能として、伸長処理と復号化処理を行う情報処理装置の記憶容量を最小限にするとともに、効率的な伸長処理および復号化処理を実現することができる復号化処理装置、暗号処理システム、復号化処理方法およびプログラムを提供することを目的とする。
【課題を解決するための手段】
【００１５】
上述した課題を解決し、目的を達成するために、本発明にかかる復号化処理装置は、平文データに対して公開鍵を用いて暗号化処理を施して複数の暗号文データを出力する暗号化処理と、前記暗号文データのそれぞれと付加的な入力である付加入力データとから前記暗号文データを圧縮した圧縮データと中間的な出力である補助出力データとを出力する圧縮写像を、前記暗号文データのそれぞれについて施して、複数の前記圧縮データと前記補助出力データとして最終的に出力された最終出力データとを含む圧縮暗号文データを出力する圧縮処理とを行う暗号化処理装置からネットワークを介して前記圧縮暗号文データを受信する受信部と、前記複数の暗号文データの前記暗号化処理における出力順序、前記複数の暗号文データおよび前記付加入力データの前記圧縮写像への入力順序に基づいて前記複数の圧縮データの伸長処理の順序および前記複数の暗号文データの復号化処理の順序を予め定めた復号化手順を記憶する記憶部と、前記圧縮データと前記最終出力データまたは前記補助出力データとを入力して前記暗号文データと前記補助出力データを出力する伸長写像を、前記圧縮暗号文データに含まれる前記複数の圧縮データに施して、前記複数の圧縮データのそれぞれを伸長した前記複数の暗号文データを求める伸長処理部と、前記複数の暗号文データのそれぞれに対して、前記公開鍵に対応する秘密鍵を用いて復号化処理を施して前記平文データを取得する復号化処理部と、前記復号化手順に基づいて、前記伸長処理と前記復号化処理の並列実行を制御するとともに、前記伸長処理部で出力された前記暗号文データに対する前記復号化処理部による前記復号化処理を制御する制御部と、を備えたことを特徴とする。
【００１６】
また、本発明にかかる暗号処理システムは、暗号化処理装置と、前記暗号化処理装置とネットワークで接続された復号化処理装置とを備えた暗号処理システムであって、前記暗号化処理装置は、平文データに対して公開鍵を用いて暗号化処理を施して複数の暗号文データを出力する暗号化処理部と、前記暗号文データのそれぞれと付加的な入力である付加入力データとから前記暗号文データを圧縮した圧縮データと中間的な出力である補助出力データとを出力する圧縮写像を、前記暗号文データのそれぞれについて施して、複数の前記圧縮データと前記補助出力データとして最終的に出力された最終出力データとを含む圧縮暗号文データを出力する圧縮処理部と、前記圧縮暗号文データを前記復号化処理装置に送信する送信部と、前記複数の暗号文データの前記暗号化処理における出力順序、前記複数の暗号文データおよび前記付加入力データの前記圧縮写像への入力順序に基づいて前記平文データの暗号化処理の順序および前記複数の暗号文データの圧縮処理の順序を予め定めた暗号化手順を記憶する第１記憶部と、前記暗号化手順に基づいて、前記暗号化処理と前記圧縮処理との並列実行を制御するとともに、前記暗号化処理部で出力された前記複数の暗号文データに対する前記圧縮処理部による前記圧縮処理を制御する第１制御部と、を備え、前記暗号化処理部は、前記圧縮写像により出力された圧縮データを入力する前記ハッシュ関数を用いることにより前記平文データに暗号化処理を施し、前記復号化処理装置は、前記暗号化処理装置から前記圧縮暗号文データを受信する受信部と、前記複数の暗号文データの前記暗号化処理における出力順序、前記複数の暗号文データおよび前記付加入力データの前記圧縮写像への入力順序に基づいて前記複数の圧縮データの伸長処理の順序および前記複数の暗号文データの復号化処理の順序を予め定めた復号化手順を記憶する記憶部と、前記圧縮データと前記最終出力データまたは前記補助出力データとを入力して前記暗号文データと前記補助出力データを出力する伸長写像を、前記圧縮暗号文データに含まれる前記複数の圧縮データに施して、前記複数の圧縮データのそれぞれを伸長した前記複数の暗号文データを求める伸長処理部と、前記複数の暗号文データのそれぞれに対して、前記公開鍵に対応する秘密鍵を用いて復号化処理を施して前記平文データを取得する復号化処理部と、前記復号化手順に基づいて、前記伸長処理と前記復号化処理の並列実行を制御するとともに、前記伸長処理部で出力された前記暗号文データに対する前記復号化処理部による前記復号化処理を制御する第２制御部と、を備え、前記復号化処理部は、前記圧縮データを入力する前記ハッシュ関数を用いて前記複数の圧縮データのそれぞれに復号化処理を施すことを特徴とする。
【００１７】
また、本発明は、上記復号化処理装置で実行される方法および上記復号化処理装置としてコンピュータを機能させるプログラムである。
【発明の効果】
【００１８】
本発明によれば、伸長処理と復号化処理を行う復号化処理装置の記憶容量を最小限にするとともに、効率的な伸長処理および復号化処理を実現することができるという効果を奏する。
【発明を実施するための最良の形態】
【００１９】
以下に添付図面を参照して、この発明にかかる復号化処理装置、暗号処理システム、復号化処理方法およびプログラムの最良な実施の形態を詳細に説明する。
【００２０】
（実施の形態１）
図１は、実施の形態１にかかる暗号処理システムのネットワーク構成および機能的構成を示すブロック図である。本実施の形態にかかる暗号処理システムは、図１に示すように、暗号化処理装置１００と復号化処理装置２００とが、インターネット等のネットワーク２１０に接続された構成となっている。
【００２１】
暗号化処理装置１００は、平文データに公開鍵を用いた暗号化処理を施し、これにより得られた暗号文データを圧縮して圧縮暗号文データを生成し、生成された圧縮暗号文データを公開鍵に対応した秘密鍵を有する復号化処理装置２００にネットワーク２１０を介して送信するＰＣ（Ｐｅｒｓｏｎａｌ  Ｃｏｍｐｕｔｅｒ）等の情報処理装置である。
【００２２】
復号化処理装置２００は、暗号化処理装置１００から圧縮暗号文データを受信し、受信した圧縮暗号文データを伸長して、復号化処理を施して平文データを得るＰＣ等の情報処理装置である。
【００２３】
まず、暗号化処理装置１００について説明する。暗号化処理装置１００は、図１に示すように、暗号化処理部１０１と、圧縮処理部１０２と、平文データ記憶部１０３と、公開鍵記憶部１０４と、送信部１０５とを主に備えている。
【００２４】
平文データ記憶部１０３は、暗号化の対象となる平文データｍを記憶するメモリ、ハードディスクドライブ装置（ＨＤＤ）等の記憶媒体である。公開鍵記憶部１０４は、暗号化処理部１０１による暗号化処理で用いる公開鍵を記憶するメモリ、ＨＤＤ等の記憶媒体である。
【００２５】
暗号化処理部１０１は、平文データｍに対して公開鍵を用いて、有限体上の離散対数問題に基づいた暗号化処理を施して複数の暗号文データｃを出力する。具体的には、暗号化処理部１０１は、有限体上の離散対数問題に基づく暗号化方式として、ＥｌＧａｍａｌ暗号方式やＣｒａｍｅｒ−Ｓｈｏｕｐ暗号方式により、複数回のべき乗または乗算、あるいは暗号文データを入力値として用いるハッシュ関数Ｈを用いて平文データｍに暗号化処理を施して複数の暗号文データｃを出力する。
【００２６】
圧縮処理部１０２は、トーラス圧縮方式を採用し、暗号化処理部１０１により出力された複数の暗号文データｃを圧縮して複数の圧縮データを含む圧縮暗号文データを出力するものである。すなわち、圧縮処理部１０２は、複数の暗号文データのそれぞれと付加的な入力である付加入力データａとから暗号文データｃを圧縮した圧縮データγと中間的な出力である補助出力データａとを出力する代数的トーラスに基づく圧縮写像θを、暗号文データのそれぞれについて施して、複数の圧縮データと補助出力データとして最終的に出力された最終出力データとを含む圧縮暗号文データを出力する。この圧縮処理部１０２は、圧縮処理は、暗号文データｃに対してｎ回目（ｎ＝２以上の整数）に圧縮写像θを施す場合に、（ｎ−１）回目の圧縮写像θで出力された補助出力データを付加入力データとして入力して、補助出力データと圧縮データを出力する。
【００２７】
送信部１０５は、暗号化処理部１０１および圧縮処理部１０２により出力された圧縮暗号文データをネットワーク２１０を介して復号化処理装置２００に送信するものである。
【００２８】
次に、復号化処理装置２００について説明する。復号化処理装置２００は、図１に示すように、受信部２０１と、復号化処理部２０３と、伸長処理部２０４と、並列処理制御部２０２と、出力部２０５と、秘密鍵記憶部２０７と、手順記憶部２０６とを主に備えている。
【００２９】
受信部２０１は、暗号化処理装置１００からネットワークを介して圧縮暗号文データを受信するものである。
【００３０】
伸長処理部２０４は、受信した圧縮暗号文データに含まれる圧縮データを、トーラス圧縮方式の圧縮暗号文データに含まれる最終出力データを用いて伸長して、複数の暗号文データを出力するものである。すなわち、伸長処理部２０４は、圧縮縮データと最終出力データまたは補助出力データとを入力して暗号文データと補助出力データを出力する伸長写像θ-1（代数的トーラスに基づく圧縮写像の逆写像）を、圧縮暗号文データに含まれる複数の圧縮データに施して、複数の圧縮データのそれぞれを伸長した複数の暗号文データを求める。具体的には、伸長処理部２０４は、最初に圧縮データを伸長写像θ-1に入力する場合に、圧縮暗号文データに含まれる一の圧縮データと最終出力データを入力し、ｎ回目（ｎ＝２以上の整数）に圧縮データを伸長写像θ-1に入力する場合に、一の圧縮データと異なる圧縮データと（ｎ−１）回目の入力で伸長写像θ-1が出力した補助出力データとを伸長写像θ-1に入力する。
【００３１】
秘密鍵記憶部２０７は、暗号文データに復号化処理を施す際に使用する秘密鍵を記憶するメモリ、ＨＤＤ等の記憶媒体である。ここで、秘密鍵は、暗号化処理装置１００で平文データｍを暗号化する際に使用した公開鍵に対応したものである。
【００３２】
復号化処理部２０３は、伸長処理部２０４で伸長された複数の暗号文データのそれぞれに対して、秘密鍵記憶部２０７に記憶された秘密鍵を用いて、有限体上の離散対数問題に基づいた復号化処理を施して平文データｍを出力するものである。具体的には、復号化処理部２０３は、ＥｌＧａｍａｌ暗号方式やＣｒａｍｅｒ−Ｓｈｏｕｐ暗号方式により、複数回のべき乗または乗算または暗号文データｃを入力値として用いるハッシュ関数Ｈを用いて、複数の暗号文データｃに復号化処理を施して平文データｍを得る。
【００３３】
手順記憶部２０６は、復号化手順を記憶するハードディスクドライブ装置やメモリ等の記憶媒体である。復号化手順は、暗号圧縮プロトコル、すなわち複数の暗号文データの暗号化処理における出力順序、複数の暗号文データおよび付加入力データの圧縮写像θへの入力順序に基づいて複数の圧縮データの伸長処理の順序および複数の暗号文データの復号化処理の順序を予め定めている。復号化手順の詳細については後述する。
【００３４】
並列処理制御部２０２は、手順記憶部２０６に記憶された復号化手順で定められた複数の圧縮データの伸長処理の順序および複数の暗号文データの復号化処理の順序に従って、伸長処理部２０４による複数の圧縮データの伸長処理と、伸長された複数の暗号文データの復号化処理部２０３による復号化処理の並列実行を制御する。また、並列処理制御部２０２は、伸長処理部２０４で出力された暗号文データに対する復号化処理部２０３による復号化処理を実行させる。すなわち、並列処理制御部２０２は、復号化手順を参照して、上記順序から伸長処理と復号化処理の中で並列に実行する処理と直列に実行する処理とを判断し、判断した結果により伸長処理部２０４と復号化処理部２０３に実行指示を送出する。
【００３５】
復号化手順、伸長処理部２０４による伸長処理と復号化処理部２０３による復号化処理の並列実行の詳細については後述する。
【００３６】
出力部２０５は、復号化された平文データｍをモニタ等の表示装置（図示せず）等にしたり、プリンタ装置等に出力するものである。
【００３７】
次に、復号化手順の詳細について説明する。本実施の形態では、トーラス圧縮公開鍵暗号方式として、トーラス圧縮ＥｌＧａｍａｌ暗号方式による平文の暗号化および圧縮、伸長および復号化を行っている。
【００３８】
まず、ＥｌＧａｍａｌ暗号方式について説明する。図２は、ＥｌＧａｍａｌ暗号方式の暗号化および復号化の処理手順を示す説明図である。図２において、ｐは素巾、ｇは暗号が定義される巡回群Ｇ（位数はｐ−１）の生成元、ｙはｙ＝ｇxをみたすＧの元、ｘは秘密鍵である。平文ｍもＧの元である必要がある。
【００３９】
暗号化処理では、平文ｍに対応する暗号文ｃ1，ｃ2を計算する。具体的には、（４−１）式で示すように、ランダムに生成した乱数ｒを用いて、生成元ｇのｒ乗を計算して暗号文ｃ1を求める。そして、（４−２）式に示すように、元ｙのｒ乗に平文ｍを乗算して暗号文ｃ2を求める。
【００４０】
復号化処理では、秘密鍵ｘ（１からｐ−１までの整数）と暗号文ｃ1，ｃ2から平文ｍを計算する。具体的には、（５）式に示すように、暗号文ｃ1の（ｐ−１−ｘ）乗と暗号文ｃ2を乗算して平文ｍを求める。
【００４１】
このようなＥｌＧａｍａｌ暗号方式において暗号文を圧縮する方式であるトーラス圧縮ＥｌＧａｍａｌ暗号方式（非特許文献１参照）による従来の暗号化および圧縮処理と伸長および復号化処理について説明する。図３は、トーラス圧縮ＥｌＧａｍａｌ暗号方式による従来の暗号化および圧縮処理と伸長および復号化処理の手順を示す説明図である。
【００４２】
図３において、θは圧縮写像であり、γ1，γ2はそれぞれ暗号文データｃ1，ｃ2を圧縮写像θで圧縮した圧縮データである。また、ａ1，ａ2は、それぞれ圧縮写像θへの入力の際に暗号文ｃ1，ｃ2とともに入力される付加入力データである。ここで、付加入力データａ1は任意に定めたデータを用い、付加入力データａ2は、暗号文データｃ1の圧縮の際に圧縮写像θから圧縮データγ1とともに出力される補助出力データとして得られる。また、ａ3は圧縮写像θから圧縮データγ1とともに出力される補助出力データであり、最終出力データとなる。
【００４３】
図３に示すように、暗号化処理３０１は、（４−１）式による暗号文データｃ1の算出、（４−２）式による暗号文データｃ2の算出の順で行われる。圧縮処理３０２は、（６−１）式による暗号文データｃ1の圧縮、（６−２）式による暗号文データｃ2の圧縮の順で行われる。圧縮の順序は、暗号化処理３０１で生成される暗号文データと同じ順序となっている。
【００４４】
すなわち、圧縮処理３０２では、まず、（６−１）式により、暗号文データｃ1と付加入力データａ1を圧縮写像θに入力して、圧縮データγ1と補助出力データａ2を求める。次に、（６−２）式により、求めた補助入力データａ2と暗号文データｃ2とを圧縮写像θに入力して、圧縮データγ2と最終出力データとしての補助出力データａ3を求める。そして、圧縮データγ1，γ2と最終出力データａ3とから構成される圧縮暗号文データ（γ1，γ2,ａ3）が復号化処理装置２００に送信される。
【００４５】
一方、伸長処理３０３は、（７−１）式による圧縮データγ2の伸長処理、（７−２）式による圧縮データγ1の伸長処理の順、すなわち、圧縮処理の順序とは逆順に、暗号文データｃ2の算出、暗号文データｃ1の算出の順に行われる。すなわち、伸長処理３０３は、（７−１）式により圧縮暗号文データ（γ1，γ2,ａ3）の圧縮データγ2と最終出力データ（補助出力データ）ａ3を伸長写像θ-1に入力して、まず暗号文データｃ2と補助出力データａ2を求める。次に、（７−２）式により、求めた補助出力データａ2と圧縮データγ1を伸長写像θ-1に入力して、暗号文データｃ1と付加入力データａ1を求めている。そして、復号化処理３０４では、（７−１）式で求めた暗号文データｃ1を使って（５−１）式によりｃ1’を求め、次に、（５−２）式で求めたｃ1’と（７−１）式で求めた暗号文データｃ2とを用いて（５−２）式により平文ｍを求めている。
【００４６】
このように、従来のトーラス圧縮ＥｌＧａｍａｌ暗号方式の手順では、伸長処理３０３は、先に（７−１）式により暗号文データｃ2を求める一方、復号化処理３０４では、先に暗号文データｃ1を使って（５−１）式を実行しているので、伸長処理３０３と復号化処理３０４は直列にしか実行できず、両処理を並列に実行することが不可能である。
【００４７】
このため、本実施の形態では、トーラス圧縮ＥｌＧａｍａｌ暗号方式における暗号化処理と圧縮処理の手順を、伸長処理と復号化処理を並列実行可能な順序で定め、さらに、伸長処理と復号化処理の手順を並列処理を行うように予め定めて、手順記憶部２０６に記憶している。
【００４８】
図４は、実施の形態１のトーラス圧縮ＥｌＧａｍａｌ暗号方式における暗号化処理および圧縮処理と伸長処理と復号化処理の手順（以下、「トーラス圧縮ＥｌＧａｍａｌ暗号手順」という。）を示す説明図である。
【００４９】
実施の形態１の暗号化処理装置１００では、暗号化処理部１０１による暗号化処理の手順を、図３で示した（４−２）式による暗号文データｃ2の算出を先に行い、次に、（４−１）式による暗号文データｃ1の算出を行うように定めており、従来の手順と逆になっている。そして、圧縮処理部１０２による圧縮処理の手順を、まず、（８−１）式によって暗号文データｃ2の圧縮を先に行い、次に、暗号文データｃ1の圧縮を行うように定めており、従来の手順と逆になっている。すなわち、（８−１）式により暗号文データｃ2と付加入力データａ1を圧縮写像θに入力して、圧縮データγ2と補助出力データａ’2を求める。次に、（８−２）式により、求めた補助入力データａ’2と暗号文データｃ1とを圧縮写像θに入力して、圧縮データγ1と最終出力データとしての補助出力データａ’3を求める。そして、圧縮データγ2，γ1と最終出力データａ’3とから構成される圧縮暗号文データ（γ2，γ1,ａ’3）が復号化処理装置２００に送信される。
【００５０】
このため、復号化処理装置２００の伸長処理部２０４で行われる伸長処理の手順は、（９−１）式による圧縮データγ1の伸長処理、（９−２）式による圧縮データγ2の伸長処理の順、すなわち、圧縮処理の順序とは逆順に、暗号文データｃ2の算出、暗号文データｃ1の算出の順に行われる。すなわち、伸長処理部２０４は、この手順に従い、圧縮暗号文データ（γ2，γ1,ａ’3）の圧縮データγ1と最終出力データ（補助出力データ）ａ’3を伸長写像θ-1に入力して、まず暗号文データｃ1と補助出力データａ’2を求め、次に、求めた補助出力データａ’2と圧縮データγ2を伸長写像θ-1に入力して、暗号文データｃ2と付加入力データａ1を求めている。そして、復号化処理部２０３による復号化処理の手順を、図３に示す従来と同様に、暗号文データｃ1を使って（５−１）式によりｃ1’を求め、次に、求めたｃ1’を用いて（５−２）式により平文ｍを求める手順としている。
【００５１】
すなわち、本実施の形態の暗号化処理の手順および圧縮処理の手順では、暗号文データｃ2に関する処理が暗号文データｃ1により処理より先に行われるため、伸長処理の手順および復号化処理の手順では、暗号文データｃ1に関する処理を暗号文データｃ2により処理より先に行うことが可能となり、これによって、先に（９−１）式により暗号文データｃ1が求められるので、暗号文データｃ1を用いる（５−１）式の復号化処理と、暗号文データｃ2を求める伸長処理とを並列処理可能となる。
【００５２】
このような（４−２）式→（４−１）式→（８−１）式→（８−２）式→（９−１）式→（９−２）式＆（５−１）式→（５−２）式の順に行う旨がトーラス圧縮ＥｌＧａｍａｌ暗号手順として記述され、手順記憶部２０６に保存されている。ここで、「＆」は並列実行可能を示している。
【００５３】
このため、本実施の形態の並列処理制御部２０２は、手順記憶部２０６に記憶されたこのトーラス圧縮ＥｌＧａｍａｌ暗号手順を読み出し、上述の（９−２）式＆（５−１）式の手順から、暗号文データｃ2を用いる（５−１）式の復号化処理部２０３による復号化処理と、暗号文データｃ2を求める伸長処理部２０４による伸長処理とを並列実行するように制御する。
【００５４】
次に、このように構成された本実施の形態にかかる復号化処理装置２００による伸長処理および復号化処理について説明する。図５は、実施の形態１のトーラス圧縮ＥｌＧａｍａｌ暗号方式における伸長処理および復号化処理の手順を示すフローチャートである。
【００５５】
まず。受信部２０１は、暗号化処理装置１００から圧縮暗号文データ（γ2，γ1,ａ’3）を受信する（ステップＳ１１）。そして、復号化処理部２０３は、秘密鍵記憶部２０７から秘密鍵ｘを読み込み、並列処理制御部２０２は、手順記憶部２０６からトーラス圧縮ＥｌＧａｍａｌ暗号手順を読み込む（ステップＳ１２）。
次に、並列処理制御部２０２は、読み込んだトーラス圧縮ＥｌＧａｍａｌ暗号手順から直列に実行する処理、並列に実行する処理を判断し（ステップＳ１３）、伸長処理部２０４と復号化処理部２０３に実行の指示を行う。具体的には、トーラス圧縮ＥｌＧａｍａｌ暗号手順において、（９−２）式＆（５−１）式等のように「＆」で記述された手順の処理は並列実行するものとし、それ以外の処理は記述されている順番で直列に実行すると判断し、以下のような処理を伸長処理部２０４と復号化処理部２０３に実行するように指示する。
【００５６】
まず、伸長処理部２０４は、受信した圧縮暗号文データ（γ2，γ1,ａ’3）と最終出力データ（補助出力データ）ａ’3を用いて（９−１）式により圧縮データγ1を伸長して暗号文データｃ1と補助出力データａ’2を求める（ステップＳ１４）。
【００５７】
次に、伸長処理部２０４が求めた補助出力データａ’2を用いて（９−２）式により圧縮データγ2を伸長する処理（ステップＳ１６）と、復号化処理部２０３が、ステップＳ１４で求めた暗号文データｃ1を使って（５−１）式によりｃ1’を求める復号化処理（ステップＳ１５）を並列処理で実行する。
【００５８】
次に、ステップＳ１４で求めたｃ1’を用いて（５−２）式により平文ｍを求める復号化処理を行う（ステップＳ１７）。求めた平文ｍは出力部２０５により出力される（ステップＳ１８）。
【００５９】
このように実施の形態１のトーラス圧縮ＥｌＧａｍａｌ暗号方式における伸長処理および復号化処理の手順では、予め（５−１）式と（９−２）式が並列実行できるような手順で定められており、伸長処理部２０４と復号化処理部２０３は、これらの処理をそれぞれ並列処理で実行する。
【００６０】
また、本実施の形態では、トーラス圧縮Ｃｒａｍｅｒ−Ｓｈｏｕｐ暗号方式における暗号化処理と圧縮処理の手順を、伸長処理と復号化処理を並列実行可能な順序で定め、さらに、伸長処理と復号化処理の手順を並列処理を行うように予め定めて、手順記憶部２０６に記憶している。
【００６１】
まず、Ｃｒａｍｅｒ−Ｓｈｏｕｐ暗号方式について説明する。図６は、Ｃｒａｍｅｒ−Ｓｈｏｕｐ暗号方式の暗号化および復号化の処理手順を示す説明図である。図６において、ｑは素数、ｇは暗号が定義される群Ｇ（位数はｑ）の生成元、ｇ^，ｅ，ｆ，ｈは群Ｇの元である。平文ｍもＧの元である。ｒはランダムに生成される乱数である。
【００６２】
暗号化処理６０１では、（１０−１）〜（１０−４）式により平文ｍに対応する暗号文データ（ｃ1，ｃ2，ｃ3，ｃ4）を計算する。ここで、（１０−３）式におけるＨはハッシュ関数を示しており、ハッシュ関数Ｈに暗号文データを入力してハッシュ値νを求めている。秘密鍵は１からｑまでの整数とする。
【００６３】
復号化処理６０２では、（１１−１）〜（１１−６）式により秘密鍵（ｘ1，ｘ2，ｙ1，ｙ2，ｚ1，ｚ2）と暗号文データ（ｃ1，ｃ2，ｃ3，ｃ4）から正当な平文であるか否かのチェックを行い、平文ｍを計算する。ここで、秘密鍵（ｘ1，ｘ2，ｙ1，ｙ2，ｚ1，ｚ2）は１からｑまでの整数とする。また、ｃ∈?Ｇ（またはＧ＾）は、ｃが群Ｇ（または群Ｇ＾）に属するか否かを判断することを示している。
【００６４】
ここで、復号化処理６０２の手順をみてみると、復号化処理６０２は、ｃ1→ｃ2→ｃ3→ｃ4の順またはｃ2→ｃ1→ｃ3→ｃ4の順で暗号文データを用いている。このため、伸長処理と復号処理を並列化するためには、伸長処理において、暗号文データを、ｃ1→ｃ2→ｃ3→ｃ4の順で用いればよいことがわかる。
【００６５】
そこで、本実施の形態では、トーラス圧縮Ｃｒａｍｅｒ−Ｓｈｏｕｐ暗号方式において、暗号文データをｃ1→ｃ2→ｃ3→ｃ4の順に用いるように伸長処理の手順を定め、暗号文データをｃ1→ｃ2→ｃ3→ｃ4の順で用いるように復号化処理の手順を定めて、伸長処理と復号化処理とを並列実行可能にした手順を手順記憶部２０６に記憶している。
【００６６】
図７は、実施の形態１のトーラス圧縮Ｃｒａｍｅｒ−Ｓｈｏｕｐ暗号方式における暗号化処理および圧縮処理、伸長処理および復号化処理の手順（以下、「トーラス圧縮Ｃｒａｍｅｒ−Ｓｈｏｕｐ暗号手順」という。）を示す説明図である。
【００６７】
実施の形態１の暗号化処理装置１００では、暗号化処理部１０１による暗号化処理の手順として図６で示した暗号化処理と同様に、（１０−１）、（１０−２）式の順で行って暗号文データｃ1，ｃ2，ｃ3の順で求め、（１０−３）式により暗号文データｃ1，ｃ2，ｃ3をハッシュ関数Ｈに入力してハッシュ値νを求め、このνを使って（１０−４）式により、暗号文データｃ4を求めている。そして、圧縮処理部１０２によって、（１２−１）、（１２−２）、（１２−３）、（１２−４）式の順、すなわち、暗号文データｃ4，ｃ3，ｃ2，ｃ1の順でそれぞれから圧縮データγ4，γ3，γ2，γ1を求める。ここで、ａ1は付加入力データであり、ａ2，ａ3，ａ4，ａ5は補助出力データである。補助出力データａ2は（１２−２）式の圧縮写像に付加入力データとして入力され、補助出力データａ3は（１２−３）式の圧縮写像に付加入力データとして入力され、補助出力データａ4は（１２−４）式の圧縮写像に付加入力データとして入力される。また、そして、圧縮データγ4，γ3，γ2，γ1と最終出力データである補助出力データａ5から構成される圧縮暗号文データ（γ4，γ3，γ2，γ1,ａ5）が復号化処理装置２００に送信される。
【００６８】
復号化処理装置２００の伸長処理部２０４で行われる伸長処理の手順は、（１３−１）式による圧縮データγ1の伸長処理、（１３−２）式による圧縮データγ2の伸長処理、（１３−３）式による圧縮データγ3の伸長処理、（１３−４）式による圧縮データγ2の伸長処理の順に行われる。より具体的には、伸長処理部２０４は、この手順に従い、（１３−１）式により圧縮暗号文データ（γ4，γ3，γ2，γ1,ａ5）の圧縮データγ1と最終出力データ（補助出力データ）ａ5を伸長写像θ-1に入力して、まず暗号文データｃ1と補助出力データａ4を求め、次に、（１３−２）式により、求めた補助出力データａ4と圧縮データγ2を伸長写像θ-1に入力して、暗号文データｃ2と付加入力データａ3を求めている。さらに、伸長処理部２０４は、（１３−３）式により、求めた補助出力データａ3と圧縮データγ3を伸長写像θ-1に入力して、暗号文データｃ3と付加入力データａ2を求め、次に、（１３−４）式により、求めた補助出力データａ2と圧縮データγ4を伸長写像θ-1に入力して、暗号文データｃ4と付加入力データａ1を求めている。すなわち、伸長処理は、暗号文データｃ1の算出、暗号文データｃ2の算出、暗号文データｃ3の算出、暗号文データｃ4の算出の順に行われる。
【００６９】
そして、復号化処理部２０３による復号化処理の手順は、伸長処理により算出された暗号文データを、算出された順に用いる順序、すなわち、暗号文データｃ1を用いる（１４−１）、暗号文データｃ2を用いる（１４−２）式、暗号文データｃ3を用いる（１４−３）、暗号文データｃ4を用いる（１４−４）式の順に復号化処理を行っている。
【００７０】
このため、伸長処理の（１３−１）式により暗号文データｃ1が求められた後であれば、伸長処理の（１３−２）式と復号化処理の（１４−１）式を並列処理で実行することができる。また、（１３−２）式により暗号文データｃ2が求められた後であれば、同様に伸長処理の（１３−３）式と復号化処理の（１４−２）式を並列処理で実行することができる。さらに、（１３−３）式により暗号文データｃ3が求められた後であれば、同様に伸長処理の（１３−４）式と復号化処理の（１４−３）式を並列処理で実行することができる。
【００７１】
このため、本実施の形態の伸長処理および復号化処理の手順としては、（１３−１）式→（１３−２）式＆（１４−１）式→（１３−３）式＆（１４−２）式→（１３−４）式＆（１４−３）式→（１４−４）式の順に行う旨がトーラス圧縮Ｃｒａｍｅｒ−Ｓｈｏｕｐ暗号手順として記述され、手順記憶部２０６に保存されている。
【００７２】
従って、本実施の形態の並列処理制御部２０２は、手順記憶部２０６に記憶されたこのトーラス圧縮Ｃｒａｍｅｒ−Ｓｈｏｕｐ暗号手順を読み出し、上述の（１３−２）式＆（１４−１）式→（１３−３）式＆（１４−２）式→（１３−４）式＆（１４−３）式の手順から、（１３−２）式と（１４−１）式の並列実行、（１３−３）式と（１４−２）式の並列実行、（１３−４）式と（１４−３）式の並列実行を行うように伸長処理部２０４と復号化処理部２０３とを制御している。
【００７３】
なお、暗号化処理では、暗号文データｃ1，ｃ2，ｃ3（いずれが先でもよい）→暗号文データｃ4の順で生成される。一方、圧縮処理では暗号文データｃ4→ｃ3→ｃ2→ｃ1の順で圧縮が行われるため、暗号文データｃ4が求められた後に圧縮処理を開始する。このため、暗号化処理と圧縮処理は並列実行せずに直列に実行されている。
【００７４】
次に、このような本実施の形態のトーラス圧縮Ｃｒａｍｅｒ−Ｓｈｏｕｐ暗号手順に基づく伸長処理および復号化処理について説明する。図８は、実施の形態１のトーラス圧縮Ｃｒａｍｅｒ−Ｓｈｏｕｐ暗号方式における伸長処理および復号化処理の手順を示すフローチャートである。
【００７５】
まず、受信部２０１は、暗号化処理装置１００から圧縮暗号文データ（γ4，γ3，γ2，γ1,ａ5）を受信する（ステップＳ２１）。そして、復号化処理部２０３は、秘密鍵記憶部２０７から秘密鍵（ｘ1，ｘ2，ｙ1，ｙ2，ｚ1，ｚ2）を読み込み、並列処理制御部２０２は、手順記憶部２０６からトーラス圧縮Ｃｒａｍｅｒ−Ｓｈｏｕｐ暗号手順を読み込む（ステップＳ２２）。
次に、並列処理制御部２０２は、読み込んだトーラス圧縮Ｃｒａｍｅｒ−Ｓｈｏｕｐ暗号手順から直列に実行する処理、並列処理に実行する処理を判断し（ステップＳ２３）、伸長処理部２０４と復号化処理部２０３に実行の指示を行う。具体的には、トーラス圧縮Ｃｒａｍｅｒ−Ｓｈｏｕｐ暗号手順において、（１３−２）式＆（１４−１）式、（１３−３）式＆（１４−２）式、（１３−４）式＆（１４−３）式等のように「＆」で記述された手順の処理は並列実行するものとし、それ以外の処理は記述されている順番で直列に実行すると判断し、以下のような処理を伸長処理部２０４と復号化処理部２０３に実行するように指示する。
【００７６】
まず、伸長処理部２０４は、受信した圧縮暗号文データ（γ4，γ3，γ2，γ1,ａ5）と最終出力データ（補助出力データ）ａ5を用いて（１３−１）式により圧縮データγ1を伸長して暗号文データｃ1と補助出力データａ4を求める（ステップＳ２４）。
【００７７】
次に、伸長処理部２０４が、求めた補助出力データａ4を用いて（１３−２）式により圧縮データγ2を伸長して暗号文データｃ2および補助出力データａ3を求める処理（ステップＳ２６）と、復号化処理部２０３が、ステップＳ２４で求めた暗号文データｃ1を使って（１４−１）式によりｃ1が群Ｇ、Ｇ＾に属するか否かを判断する復号化処理（ステップＳ２５）を並列処理で実行する。
【００７８】
次に、伸長処理部２０４が、求めた補助出力データａ3を用いて（１３−３）式により圧縮データγ3を伸長して暗号文データｃ3および補助出力データａ2を求める処理（ステップＳ２８）と、復号化処理部２０３が、ステップＳ２４で求めた暗号文データｃ1とステップＳ２６で求めた暗号文データｃ2を使って（１４−２）式によりｃ2が群Ｇ、Ｇ＾に属するか否かを判断し、ｂを求める復号化処理（ステップＳ２７）を並列処理で実行する。
【００７９】
次に、伸長処理部２０４が、求めた補助出力データａ2を用いて（１３−４）式により圧縮データγ4を伸長して暗号文データｃ4および補助出力データａ1を求める処理（ステップＳ３０）と、復号化処理部２０３が、ステップＳ２４で求めた暗号文データｃ1とステップＳ２６で求めた暗号文データｃ2とステップＳ２８で求めた暗号文データｃ3とを使って（１４−３）式によりｃ3が群Ｇ、Ｇ＾に属するか否かを判断し、平文ｍと、ハッシュ値νを求める復号化処理（ステップＳ２９）を並列処理で実行する。
【００８０】
次に、復号化処理部２０３は、今まで求めた暗号文データｃ1〜ｃ4やハッシュ値νを使って、（１４−４）式による暗号文データｃ4の判断処理を単独で実行する（ステップＳ３１）。求めた平文ｍは出力部２０５により出力される（ステップＳ３２）。
【００８１】
このように実施の形態１のトーラス圧縮Ｃｒａｍｅｒ−Ｓｈｏｕｐ暗号方式における伸長処理および復号化処理の手順では、予め（１３−２）式と（１４−１）式、（１３−３）式と（１４−２）式、（１３−４）式と（１４−３）式がそれぞれ並列実行できるような手順で定められており、伸長処理部２０４と復号化処理部２０３は、これらの処理をそれぞれ並列処理で実行する。
【００８２】
従って、実施の形態１の復号化処理装置２００によれば、記憶容量を最小限にするとともに、効率的な伸長処理および復号化処理を実現することができる。
【００８３】
（実施の形態２）
実施の形態１の暗号化処理システムでは、復号化処理装置２００において、伸長処理と復号化処理とを並列処理として実行するものであったが、この実施の形態２の暗号化処理システムでは、さらに、暗号化処理装置において暗号化処理と圧縮処理とを並列に実行する。
【００８４】
図９は、実施の形態２にかかる暗号処理システムのネットワーク構成および機能的構成を示すブロック図である。本実施の形態にかかる暗号処理システムは、図９に示すように、暗号化処理装置９００と復号化処理装置９５０とが、インターネット等のネットワーク２１０に接続された構成となっている。
【００８５】
暗号化処理装置９００は、平文データに公開鍵を用いた暗号化処理を施し、これにより得られた暗号文データを圧縮して圧縮暗号文データを生成し、生成された圧縮暗号文データを公開鍵に対応した秘密鍵を有する復号化処理装置２００にネットワーク２１０を介して送信するＰＣ等の情報処理装置である。
【００８６】
復号化処理装置９５０は、暗号化処理装置９００から圧縮暗号文データを受信し、受信した圧縮暗号文データを伸長して、復号化処理を施して平文データを得るＰＣ等の情報処理装置である。
【００８７】
まず、暗号化処理装置９００について説明する。暗号化処理装置９００は、図９に示すように、暗号化処理部９０１と、圧縮処理部１０２と、平文データ記憶部１０３と、公開鍵記憶部１０４と、送信部１０５と、手順記憶部９０３と、並列処理制御部９０２とを主に備えている。圧縮処理部１０２、平文データ記憶部１０３、公開鍵記憶部１０４、送信部１０５の機能および構成については実施の形態１と同様である。
【００８８】
手順記憶部９０３は、暗号化処理から圧縮処理、伸長処理、復号化処理までの一連の暗号化復号化手順を記憶するハードディスクドライブ装置やメモリ等の記憶媒体である。暗号化復号化手順は、暗号圧縮プロトコル、すなわち複数の暗号文データの暗号化処理における出力順序、複数の暗号文データおよび付加入力データの圧縮写像への入力順序に基づいて、平文データｍの暗号化処理における暗号文データの出力順序および複数の暗号文データの圧縮処理の順序、複数の圧縮データの伸長処理の順序および複数の暗号文データの復号化処理の順序を予め定めている。暗号化復号化手順の詳細については後述する。
【００８９】
暗号化処理部９０１は、実施の形態１と同様に、平文データｍに対して公開鍵を用いて、有限体上の離散対数問題に基づいた暗号化処理を施して複数の暗号文データｃを出力する。本実施の形態では、暗号化処理部９０１は、有限体上の離散対数問題に基づく暗号化方式として、Ｃｒａｍｅｒ−Ｓｈｏｕｐ暗号方式により、実施の形態１と同様に、複数回のべき乗または乗算、あるいは暗号文データを入力値として用いるハッシュ関数Ｈを用いる他、暗号文データｃを圧縮した圧縮データγを入力値として用いるハッシュ関数Ｈを用いて、平文データｍに暗号化処理を施して複数の暗号文データｃを出力する。
【００９０】
並列処理制御部９０２は、手順記憶部９０３に記憶された暗号化手順で定められた複数の暗号文データの生成処理の順序および複数の暗号文データの圧縮処理の順序から、暗号化処理部１０１による暗号化処理と圧縮処理部１０２による圧縮処理の並列実行を制御する。また、並列処理制御部９０２は、暗号化処理と圧縮処理の直列の実行を制御して、暗号化処理部９０１で出力された複数の暗号文データに対する圧縮処理部１０２による圧縮処理を実行させる。すなわち、並列処理制御部９０２は、暗号化手順を参照して、暗号化処理と圧縮処理の中で並列に実行する処理と直列に実行する処理とを判断し、判断した結果により暗号化処理部９０１と圧縮処理部１０２に実行指示を送出する。
【００９１】
暗号化手順、暗号化処理部９０１による暗号化処理と圧縮処理部１０２による圧縮処理の並列実行の詳細については後述する。
【００９２】
次に、復号化処理装置９５０について説明する。復号化処理装置９５０は、図９に示すように、受信部２０１と、復号化処理部９５３と、伸長処理部２０４と、並列処理制御部２０２と、出力部２０５と、秘密鍵記憶部２０７と、手順記憶部９５６とを主に備えている。ここで、受信部２０１、伸長処理部２０４、出力部２０５、並列処理制御部２０２、秘密鍵記憶部２０７については実施の形態１と同様の機能および構成を有している。
【００９３】
復号化処理部９５３は、実施の形態１と同様に、伸長処理部２０４で伸長された複数の暗号文データのそれぞれに対して、秘密鍵記憶部２０７に記憶された秘密鍵を用いて、有限体上の離散対数問題に基づいたＣｒａｍｅｒ−Ｓｈｏｕｐ暗号化方式による復号化処理を施して平文データｍを出力する。本実施の形態では、復号化処理部９５３は、実施の形態１と同様に複数回のべき乗または乗算または暗号文データｃを入力値として用いるハッシュ関数Ｈを用いる他、圧縮データγを入力値として用いるハッシュ関数Ｈを用いて、複数の暗号文データｃに復号化処理を施して平文データｍを得る。
【００９４】
手順記憶部９５６は、暗号化復号化手順を記憶するハードディスクドライブ装置やメモリ等の記憶媒体である。暗号化復号化手順は、暗号化処理装置９００の手順記憶部９０３に記憶されている暗号化復号化手順と同一のものである。ただし、これに限定されるものではなく、暗号化処理装置９００の手順記憶部９０３に暗号化処理と圧縮処理のみの暗号化手順を記憶させ、復号化処理装置９５０の手順記憶部９５６に伸長処理と復号化処理のみの復号化手順を記憶させる構成としてもよい。
【００９５】
次に、本実施の形態で手順記憶部９０３，９５６に記憶されている暗号化復号化手順について説明する。本実施の形態では、実施の形態１と同様に、暗号化方式としてはＣｒａｍｅｒ−Ｓｈｏｕｐ暗号化方式を採用し、圧縮暗号方式として、トーラス圧縮Ｃｒａｍｅｒ−Ｓｈｏｕｐ暗号化方式を採用している。
【００９６】
本実施の形態の暗号化復号化手順では、暗号化処理装置９００において暗号化処理と圧縮処理も並列処理で実行可能な手順としている。図１０は、実施の形態２のトーラス圧縮Ｃｒａｍｅｒ−Ｓｈｏｕｐ暗号方式における暗号化処理および圧縮処理と伸長処理と復号化処理の手順（トーラス圧縮Ｃｒａｍｅｒ−Ｓｈｏｕｐ暗号手順）を示す説明図である。
【００９７】
実施の形態２の暗号化処理装置９００では、暗号化処理部９０１による暗号化処理の手順として、（１５−１）、（１５−２）、（１５−３）、（１５−４）式の順で行って暗号文データｃ3，ｃ1，ｃ2の順で求める。そして、この暗号文データｃ3，ｃ1，ｃ2のそれぞれを圧縮処理部１０２の圧縮処理の（１６−１）、（１６−２）、（１６−３）式で順次用いて、圧縮データγ3，γ1，γ2を求めている。そして、その後、暗号化処理部９０１では、（１５−５）式でハッシュ関数Ｈに求めた圧縮データγ3，γ1，γ2を入力してν’を求め、（１５−６）式により暗号文データｃ4を求める。圧縮処理部１０２では、（１６−４）式により、（１５−６）式で求めた暗号文データｃ4を用いて圧縮データγ4を求める。すなわち、本実施の形態では、暗号文データをｃ3→ｃ1→ｃ2の順で求め、その上で、暗号文データをｃ3→ｃ1→ｃ2の順で圧縮して圧縮データγ3，γ1，γ2を算出し、暗号文データｃ4を算出するために必要なハッシュ値は、（１５−５）式のハッシュ関数Ｈによって、暗号文データｃ1，ｃ2，ｃ3のハッシュ値ではなく、圧縮データγ3，γ1，γ2のハッシュ値を求めている。
【００９８】
このため、（１５−３）式と（１６−１）式、（１５−４）式と（１６−２）式はそれぞれ並列処理で実行可能となる。
【００９９】
このため、暗号化復号化手順における暗号化と圧縮処理の手順は、（１５−１）式→（１５−２）式→（１５−３）式＆（１６−１）式→（１５−４）式＆（１６−２）式→（１６−３）式→（１５−５）式→（１５−６）式→（１６−４）式の順に行う旨がトーラス圧縮Ｃｒａｍｅｒ−Ｓｈｏｕｐ暗号手順として記述されている。
【０１００】
従って、本実施の形態の暗号化処理装置９００の並列処理制御部９０２は、手順記憶部９０３に記憶されたこのトーラス圧縮Ｃｒａｍｅｒ−Ｓｈｏｕｐ暗号手順を読み出し、上述の手順の記述から、（１５−３）式と（１６−１）式の並列実行、（１５−４）式と（１６−２）式の並列実行を行うように暗号化処理部９０１と圧縮処理部１０２とを制御している。
【０１０１】
なお、本実施の形態では、暗号文データの算出順序はｃ3→ｃ1→ｃ2→ｃ4の順となっているが、ｃ1,ｃ2,ｃ3の算出後にｃ4を算出し、圧縮データも求めた暗号文データを順に使用して算出するのであれば、ｃ1,ｃ2,ｃ3の算出順序はこれに限定されるものではない。
【０１０２】
また、付加入力データａ1、補助出力データａ2，ａ3，ａ4，ａ5の用い方も実施の形態１と同様である。
【０１０３】
そして、圧縮データγ3，γ1，γ2，γ4と最終出力データである補助出力データａ5から構成される圧縮暗号文データ（γ3，γ1，γ2，γ4,ａ5）が復号化処理装置９５０に送信される。
【０１０４】
復号化処理装置９５０の伸長処理部２０４で行われる伸長処理の手順は、（１７−１）式による圧縮データγ4の伸長処理、（１７−２）式による圧縮データγ2の伸長処理、（１７−３）式による圧縮データγ1の伸長処理、（１７−４）式による圧縮データγ3の伸長処理の順に行われる。より具体的には、伸長処理部２０４は、（１７−１）式により圧縮暗号文データ（γ3，γ1，γ2，γ4，ａ5）の圧縮データγ3と最終出力データ（補助出力データ）ａ5を伸長写像θ-1に入力して、まず暗号文データｃ4と補助出力データａ4を求め、次に、（１７−２）式により、求めた補助出力データａ4と圧縮データγ2を伸長写像θ-1に入力して、暗号文データｃ2と付加入力データａ3を求めている。さらに、伸長処理部２０４は、（１７−３）式により、求めた補助出力データａ3と圧縮データγ1を伸長写像θ-1に入力して、暗号文データｃ1と付加入力データａ2を求め、伸長処理部２０４は、（１７−４）式により、求めた補助出力データａ2と圧縮データγ3を伸長写像θ-1に入力して、暗号文データｃ3と付加入力データａ1を求めている。すなわち、伸長処理は、暗号文データｃ4の算出、暗号文データｃ2の算出、暗号文データｃ1の算出、暗号文データｃ3の算出の順に行われる。
【０１０５】
そして、復号化処理部９５３による復号化処理の手順は、ハッシュ関数Ｈに圧縮データγ1，γ2，γ3を入力してν’を求める（１８−１）式の処理をまず実行し、その後に伸長処理により算出された暗号文データを、算出された順に用いる順序、すなわち、暗号文データｃ4を用いる（１８−２）式、暗号文データｃ2を用いる（１８−３）式、暗号文データｃ1およびｃ2を用いる（１８−４）式、暗号文データｃ3を用いる（１８−５）式の順に復号化処理を行っている。
【０１０６】
ハッシュ関数Ｈへの入力は、暗号文データではなく、伸長前の圧縮データγ1，γ2，γ3であり、これらは圧縮暗号文データ（γ3，γ1，γ2，γ4，ａ5）から取得することができるため、復号化処理における（１８−１）式と伸長処理における（１７−１）式とを並列で実行することができる。また、伸長処理の（１７−１）式により暗号文データｃ4が求められた後であれば、伸長処理の（１７−２）式と復号化処理の（１８−２）式を並列処理で実行することができる。また、（１７−２）式により暗号文データｃ2が求められた後であれば、同様に伸長処理の（１７−３）式と復号化処理の（１８−３）式を並列処理で実行することができる。さらに、（１７−３）式により暗号文データｃ1が求められた後であれば、同様に伸長処理の（１７−４）式と復号化処理の（１８−４）式を並列処理で実行することができる。
【０１０７】
このため、本実施の形態の伸長処理および復号化処理の手順としては、（１７−１）式＆（１８−１）式→（１７−２）式＆（１８−２）式→（１７−３）式＆（１８−３）式→（１７−４）式＆（１８−４）式→（１８−５）式の順に行う旨がトーラス圧縮Ｃｒａｍｅｒ−Ｓｈｏｕｐ暗号手順として記述されている。
【０１０８】
従って、本実施の形態の復号化処理装置９５０の並列処理制御部２０２は、手順記憶部９５６に記憶されたこのトーラス圧縮Ｃｒａｍｅｒ−Ｓｈｏｕｐ暗号手順を読み出し、上述の記述の手順から、（１７−１）式と（１８−１）式の並列実行、（１７−２）式と（１８−２）式の並列実行、（１７−３）式と（１８−３）式の並列実行、（１７−４）式と（１８−４）式の並列実行を行うように伸長処理部２０４と復号化処理部９５３とを制御している。
【０１０９】
次に、このような本実施の形態のトーラス圧縮Ｃｒａｍｅｒ−Ｓｈｏｕｐ暗号手順に基づく暗号化処理および圧縮処理について説明する。図１１は、実施の形態２のトーラス圧縮Ｃｒａｍｅｒ−Ｓｈｏｕｐ暗号方式における暗号化処理および圧縮処理の手順を示すフローチャートである。
【０１１０】
まず、暗号化処理部９０１は、平文データ記憶部１０３から平文データｍと読み込み、公開鍵記憶部１０４から公開鍵を読み込む（ステップＳ４１）。そして、並列処理制御部９０２は、手順記憶部９０３からトーラス圧縮Ｃｒａｍｅｒ−Ｓｈｏｕｐ暗号手順を読み込む（ステップＳ４２）。
【０１１１】
次に、並列処理制御部９０２は、読み込んだトーラス圧縮Ｃｒａｍｅｒ−Ｓｈｏｕｐ暗号手順から直列に実行する処理、並列処理に実行する処理を判断し（ステップＳ４３）、暗号化処理９０１と圧縮処理部１０２に実行の指示を行う。具体的には、トーラス圧縮Ｃｒａｍｅｒ−Ｓｈｏｕｐ暗号手順において、（１５−３）式＆（１６−１）式、（１５−４）式＆（１６−２）式、（１５−６）式＆（１６−３）式等のように「＆」で記述された手順の処理は並列実行するものとし、それ以外の処理は記述されている順番で直列に実行すると判断し（ステップＳ４３）、以下のような処理を暗号化処理部９０１と圧縮処理部１０２に実行するように指示する。
【０１１２】
まず、暗号化処理部９０１は、（１５−１）式による暗号化処理を行い（ステップＳ４４）、次に（１５−２）式による暗号化処理により暗号文データｃ3を求める（ステップＳ４５）。
【０１１３】
次に、暗号化処理部９０１による（１５−３）式による暗号文データｃ1の算出（ステップＳ４６）と圧縮処理部１０２による（１６−１）式による暗号文データｃ3の圧縮データγ2および補助出力データａ2の算出（ステップＳ４７）とを並列処理で実行する。
【０１１４】
次に、暗号化処理部９０１による（１５−４）式による暗号文データｃ2の算出（ステップＳ４８）と圧縮処理部１０２による（１６−２）式による暗号文データｃ1の圧縮データγ1および補助出力データａ3の算出（ステップＳ４９）とを並列処理で実行する。
【０１１５】
次に、圧縮処理部１０２により、（１６−３）式により、算出された暗号文データｃ2から圧縮データγ2および補助出力データａ4の算出を行う（ステップＳ５０）。次に、暗号化処理部９０１により、（１５−５）式により、これまで算出された圧縮データγ1，γ2，γ3のハッシュ値ν’を算出し（ステップＳ５１）、その後、（１５−６）式により、このハッシュ値ν’を用いて暗号文データｃ4を算出する（ステップＳ５２）。
【０１１６】
圧縮処理部１０２は、（１６−４）式により、算出された暗号文データｃ4の圧縮データγ4および補助出力データａ5の算出を行う（ステップＳ５３）。
【０１１７】
そして、送信部１０５は、これまで算出された圧縮データγ3，γ1，γ2，γ4と最終出力データである補助出力データａ5から圧縮暗号文データ（γ3，γ1，γ2，γ4,ａ5）を生成して、生成された圧縮暗号文データ（γ3，γ1，γ2，γ4,ａ5）を復号化処理装置９５０に送信する（ステップＳ５４）。
【０１１８】
次に、本実施の形態のトーラス圧縮Ｃｒａｍｅｒ−Ｓｈｏｕｐ暗号手順に基づく伸長処理および復号化処理について説明する。図１２は、実施の形態２のトーラス圧縮Ｃｒａｍｅｒ−Ｓｈｏｕｐ暗号方式における伸長処理および復号化処理の手順を示すフローチャートである。
【０１１９】
まず、受信部２０１は、暗号化処理装置１００から圧縮暗号文データ（γ3，γ1，γ2，γ4,ａ5）を受信する（ステップＳ６１）。そして、復号化処理部９５３は、秘密鍵記憶部２０７から秘密鍵（ｘ1，ｘ2，ｙ1，ｙ2，ｚ1，ｚ2）を読み込み、並列処理制御部２０２は、手順記憶部９５６からトーラス圧縮Ｃｒａｍｅｒ−Ｓｈｏｕｐ暗号手順を読み込む（ステップＳ６２）。
次に、並列処理制御部２０２は、読み込んだトーラス圧縮Ｃｒａｍｅｒ−Ｓｈｏｕｐ暗号手順から直列に実行する処理、並列処理に実行する処理を判断し（ステップＳ６３）、伸長処理部２０４と復号化処理部９５３に実行の指示を行う。具体的には、トーラス圧縮Ｃｒａｍｅｒ−Ｓｈｏｕｐ暗号手順において、（１７−１）式＆（１８−１）式、（１７−２）式＆（１８−２）式、（１７−３）式＆（１８−３）式、（１７−４）式＆（１８−４）式等のように「＆」で記述された手順の処理は並列実行するものとし、それ以外の処理は記述されている順番で直列に実行すると判断し、以下のような処理を伸長処理部２０４と復号化処理部９５３に実行するように指示する。
【０１２０】
まず、伸長処理部２０４が（１７−１）式により圧縮暗号文データ（γ3，γ1，γ2，γ4,ａ5）の圧縮データγ4を最終出力データ（補助出力データ）ａ5を用いて伸長して暗号文データｃ4と補助出力データａ4を求める処理（ステップＳ６５）と、復号化処理部９５３が（１８−１）式により圧縮データγ1，γ2，γ3のハッシュ値ν’を求める処理（ステップＳ６４）を並列処理として実行する。
【０１２１】
次に、伸長処理部２０４が（１７−２）式により圧縮データγ2を補助出力データａ4を用いて伸長して暗号文データｃ2と補助出力データａ3を求める処理（ステップＳ６７）と、復号化処理部９５３が（１８−２）式によりステップＳ６５で求めた暗号文データｃ4が群Ｇ＾に属するか否かを判断する処理（ステップＳ６６）を並列処理として実行する。
【０１２２】
次に、伸長処理部２０４が（１７−３）式により圧縮データγ1を補助出力データａ3を用いて伸長して暗号文データｃ1と補助出力データａ2を求める処理（ステップＳ６９）と、復号化処理部９５３が（１８−３）式によりステップＳ６７で求めた暗号文データｃ2が群Ｇ，Ｇ＾に属するか否かを判断する処理（ステップＳ６８）を並列処理として実行する。
【０１２３】
次に、伸長処理部２０４が（１７−４）式により圧縮データγ3を補助出力データａ2を用いて伸長して暗号文データｃ3と補助出力データａ1を求める処理（ステップＳ７１）と、復号化処理部９５３が（１８−４）式により今まで求めた暗号文データｃ1，ｃ2，ｃ3，ｃ4を用いる処理（ステップＳ７０）を並列処理として実行する。
【０１２４】
そして、復号化処理部９５３は、（１８−５）式により、ステップＳ７１で求めた暗号文データｃ3が群Ｇ，Ｇ＾に属するか否かを判断し、暗号文データｃ3を用いて平文データｍを求める（ステップＳ７２）。求めた平文ｍは出力部２０５により出力される（ステップＳ３２）。
【０１２５】
このように実施の形態２のトーラス圧縮Ｃｒａｍｅｒ−Ｓｈｏｕｐ暗号方式における暗号化復号化手順では、ハッシュ関数Ｈにより暗号文データのハッシュ値を用いるのではなく、圧縮データγ1，γ2，γ3をのハッシュ値を求めて暗号化処理と復号化処理を行っているので、暗号化処理と圧縮処理の並列実行と、伸長処理と復号化処理の並列実行を共に実現することができる。このため、実施の形態２の暗号処理システムによれば、記憶容量を最小限にするとともに、効率的な暗号化処理および圧縮処理と、伸長処理および復号化処理を実現することができる。
【０１２６】
（変形例）
さらに、変形例として、暗号化復号化手順を以下のように定めて、暗号化処理と圧縮処理の並列実行、伸長処理と復号化処理の並列実行を実現することもできる。
【０１２７】
この変形例では、実施の形態２と同様に、暗号化方式としてはＣｒａｍｅｒ−Ｓｈｏｕｐ暗号化方式を採用し、圧縮暗号方式として、トーラス圧縮Ｃｒａｍｅｒ−Ｓｈｏｕｐ暗号化方式を採用している。ただし、本変形例では、圧縮処理の一部として、付加入力データを用いず、かつ補助出力データを出力しない圧縮写像ρを用いて暗号文データを圧縮し、伸長処理の一部として、補助出力データを用いず、かつ出力しない伸長写像ρ-1により圧縮データを伸長している。
【０１２８】
図１３は、実施の形態２の変形例のトーラス圧縮Ｃｒａｍｅｒ−Ｓｈｏｕｐ暗号方式における暗号化処理および圧縮処理と伸長処理と復号化処理の手順（トーラス圧縮Ｃｒａｍｅｒ−Ｓｈｏｕｐ暗号手順）を示す説明図である。
【０１２９】
本変形例の暗号化処理装置９００では、暗号化処理部９０１による暗号化処理の手順として、（１９−１）、（１９−２）、（１９−３）、（１９−４）式の順で行って暗号文データｃ3，ｃ1，ｃ2の順で求める。そして、この暗号文データｃ1，ｃ2，ｃ3のそれぞれを圧縮処理部１０２による圧縮処理の（２０−１）、（２０−２）、（２０−３）式で順次用いて、圧縮データγ3，γ1，γ2を求めている。そして、その後、暗号化処理部９０１では、（１９−５）式によりハッシュ関数Ｈに求めた暗号文データｃ1，ｃ2，ｃ3を入力してハッシュ値ν’を求め、（１９−６）式により暗号文データｃ4を求める。圧縮処理部１０２では、（１６−４）式により、（１５−６）式で求めた暗号文データｃ4を用いて圧縮データγ4を求める。また、圧縮処理部１０２では、（２０−４）式により、付加入力データを用いず、かつ補助出力データを出力しない圧縮写像ρを用いて暗号文データｃ4の圧縮データγ4’を求めている。
【０１３０】
すなわち、本実施の形態では、暗号文データをｃ3→ｃ1→ｃ2の順で求め、その上で、暗号文データをｃ3→ｃ1→ｃ2の順で使用して圧縮データγ3，γ1，γ2を算出し、暗号文データｃ4を算出するために必要なハッシュ値ν’を、（１９−５）式のハッシュ関数Ｈに暗号文データｃ1，ｃ2，ｃ3を入力して求め、この暗号文データｃ4の圧縮処理では、付加入力データを用いていない。
【０１３１】
このため、（１９−３）式と（２０−１）式、（１９−４）式と（２０−２）式、（１９−５）式と（２０−３）式はそれぞれ並列処理で実行可能となる。
【０１３２】
このため、暗号化復号化手順における暗号化と圧縮処理の手順は、（１９−１）式→（１９−２）式→（１９−３）式＆（２０−１）式→（１９−４）式＆（２０−２）式→（１９−５）式＆（２０−３）式→（１９−６）式→（２０−４）式の順に行う旨がトーラス圧縮Ｃｒａｍｅｒ−Ｓｈｏｕｐ暗号手順として記述されている。
【０１３３】
従って、本実施の形態の暗号化処理装置９００の並列処理制御部９０２は、手順記憶部９０３に記憶されたこのトーラス圧縮Ｃｒａｍｅｒ−Ｓｈｏｕｐ暗号手順を読み出し、上述の手順の記述から、（１９−３）式と（２０−１）式、（１９−４）式と（２０−２）式、（１９−５）式と（２０−３）式の並列実行を行うように暗号化処理部９０１と圧縮処理部１０２とを制御している。
【０１３４】
なお、本実施の形態では、暗号文データの算出順序はｃ3→ｃ1→ｃ2→ｃ4の順となっているが、ｃ1,ｃ2,ｃ3の算出後にｃ4を算出し、圧縮データも求めた暗号文データを順に使用して算出するのであれば、ｃ1,ｃ2,ｃ3の算出順序はこれに限定されるものではない。
【０１３５】
また、付加入力データａ1、補助出力データａ2，ａ3の用い方も実施の形態２と同様である。
【０１３６】
そして、圧縮データγ3，γ1，γ2，γ4’と補助出力データａ4から構成される圧縮暗号文データ（γ3，γ1，γ2，ａ4，γ4’）が復号化処理装置９５０に送信される。
【０１３７】
復号化処理装置９５０の伸長処理部２０４で行われる伸長処理の手順は、（２１−１）式による圧縮データγ2の伸長処理、（２１−２）式による圧縮データγ1の伸長処理、（２１−３）式による圧縮データγ3の伸長処理、（２１−４）式による圧縮データγ4’の伸長処理の順に行われる。
【０１３８】
より具体的には、伸長処理部２０４は、（２１−１）式により圧縮暗号文データ（γ3，γ1，γ2，ａ4，γ4’）の圧縮データγ2と最終出力データ（補助出力データ）ａ4を伸長写像θ-1に入力して、まず暗号文データｃ2と補助出力データａ3を求め、次に、（２１−２）式により、求めた補助出力データａ3と圧縮データγ1を伸長写像θ-1に入力して、暗号文データｃ1と補助出力データａ2を求めている。さらに、伸長処理部２０４は、（２１−３）式により、求めた補助出力データａ2と圧縮データγ3を伸長写像θ-1に入力して、暗号文データｃ3と付加入力データａ1を求める。そして、伸長処理部２０４は、（２１−４）式により、γ4’を伸長写像ρ-1に入力して、暗号文データｃ4を求めている。すなわち、伸長処理は、暗号文データｃ2の算出、暗号文データｃ1の算出、暗号文データｃ3の算出、暗号文データｃ4の算出の順に行われる。
【０１３９】
そして、復号化処理部９５３による復号化処理の手順は、暗号文データｃ2を用いる（２２−１）式、暗号文データｃ1，ｃ2を用いる（２２−２）式、暗号文データｃ1，ｃ2，ｃ3のハッシュ値νを求める（２２−３）式、ハッシュ値ν、暗号文データｃ1，ｃ2を用いる（２２−４）式の順に復号化処理を行っている。
【０１４０】
伸長処理の（２１−１）式により暗号文データｃ2が求められた後であれば、伸長処理の（２１−２）式と復号化処理の（２２−１）式を並列処理で実行することができる。また、（２１−２）式により暗号文データｃ1が求められた後であれば、同様に伸長処理の（２１−３）式と復号化処理の（２２−２）式を並列処理で実行することができる。さらに、（２１−３）式により暗号文データｃ3が求められた後であれば、同様に伸長処理の（２１−４）式と復号化処理の（２２−３）式を並列処理で実行することができる。
【０１４１】
このため、本実施の形態の伸長処理および復号化処理の手順としては、（２１−１）式→（２１−２）式＆（２２−１）式→（２１−３）式＆（２２−２）式→（２１−４）式＆（２２−３）式→（２３−４）式の順に行う旨がトーラス圧縮Ｃｒａｍｅｒ−Ｓｈｏｕｐ暗号手順として記述されている。
【０１４２】
従って、本実施の形態の復号化処理装置９５０の並列処理制御部２０２は、手順記憶部９５６に記憶されたこのトーラス圧縮Ｃｒａｍｅｒ−Ｓｈｏｕｐ暗号手順を読み出し、上述の記述の手順から、（２１−２）式と（２２−１）式の並列実行、（２１−３）式と（２２−２）式の並列実行、（２１−４）式と（２２−３）式の並列実行を行うように伸長処理部２０４と復号化処理部９５３とを制御している。
【０１４３】
次に、このような本変形例のトーラス圧縮Ｃｒａｍｅｒ−Ｓｈｏｕｐ暗号手順に基づく暗号化処理および圧縮処理について説明する。図１４は、実施の形態２の変形例のトーラス圧縮Ｃｒａｍｅｒ−Ｓｈｏｕｐ暗号方式における暗号化処理および圧縮処理の手順を示すフローチャートである。
【０１４４】
まず、暗号化処理部９０１は、平文データ記憶部１０３から平文データｍと読み込み、公開鍵記憶部１０４から公開鍵を読み込む（ステップＳ８１）。そして、並列処理制御部９０２は、手順記憶部９０３からトーラス圧縮Ｃｒａｍｅｒ−Ｓｈｏｕｐ暗号手順を読み込む（ステップＳ８２）。
【０１４５】
次に、並列処理制御部９０２は、読み込んだトーラス圧縮Ｃｒａｍｅｒ−Ｓｈｏｕｐ暗号手順から直列に実行する処理、並列処理に実行する処理を判断し（ステップＳ８３）、暗号化処理部９５１と圧縮処理部１０２に実行の指示を行う。具体的には、トーラス圧縮Ｃｒａｍｅｒ−Ｓｈｏｕｐ暗号手順において、（１９−３）式＆（２０−１）式→（１９−４）式＆（２０−２）式→（１９−５）式＆（２０−３）式等のように「＆」で記述された手順の処理は並列実行するものとし、それ以外の処理は記述されている順番で直列に実行すると判断し（ステップＳ８３）、以下のような処理を暗号化処理部９０１と圧縮処理部１０２に実行するように指示する。
【０１４６】
まず、暗号化処理部９０１は、（１９−１）式による暗号化処理を行い（ステップＳ８４）、次に（１９−２）式による暗号化処理により暗号文データｃ3を求める（ステップＳ８５）。
【０１４７】
次に、暗号化処理部９０１が（１９−３）式により暗号文データｃ1を算出する処理（ステップＳ８６）と、圧縮処理部１０２が（２０−１）式により暗号文データｃ3の圧縮データγ2および補助出力データａ2を算出する処理（ステップＳ８７）とを並列処理で実行する。
【０１４８】
次に、暗号化処理部９０１が（１９−４）式により暗号文データｃ2を算出する処理（ステップＳ８８）と、圧縮処理部１０２が（２０−２）式により暗号文データｃ1の圧縮データγ1および補助出力データａ3を算出する処理（ステップＳ８９）とを並列処理で実行する。
【０１４９】
次に、暗号化処理部９０１が（１９−５）式により暗号文データｃ1，ｃ2，ｃ3のハッシュ値νを算出する処理（ステップＳ９０）と、圧縮処理部１０２が（２０−３）式により暗号文データｃ2の圧縮データγ2および補助出力データａ4を算出する処理（ステップＳ９１）とを並列処理で実行する。
【０１５０】
そして、暗号化処理部９０１によって、（１９−６）式によりハッシュ値νから暗号文データｃ4を算出する（ステップS９２）。次に、圧縮処理部１０２によって、算出された暗号文データｃ4を圧縮写像ρにより圧縮して、圧縮データγ4’を算出する（ステップＳ９３）。
【０１５１】
そして、送信部１０５は、これまで算出された圧縮データγ3，γ1，γ2，γ4’と補助出力データａ4から圧縮暗号文データ（γ3，γ1，γ2，ａ4，γ4’）を生成して、生成された圧縮暗号文データ（γ3，γ1，γ2，ａ4，γ4’）を復号化処理装置９５０に送信する（ステップＳ９４）。
【０１５２】
次に、本実施の形態のトーラス圧縮Ｃｒａｍｅｒ−Ｓｈｏｕｐ暗号手順に基づく伸長処理および復号化処理について説明する。図１５は、実施の形態２の変形例のトーラス圧縮Ｃｒａｍｅｒ−Ｓｈｏｕｐ暗号方式における伸長処理および復号化処理の手順を示すフローチャートである。
【０１５３】
まず、受信部２０１は、暗号化処理装置１００から圧縮暗号文データ（γ3，γ1，γ2，ａ4，γ4’）を受信する（ステップＳ１０１）。そして、復号化処理部９５３は、秘密鍵記憶部２０７から秘密鍵（ｘ1，ｘ2，ｙ1，ｙ2，ｚ1，ｚ2）を読み込み、並列処理制御部２０２は、手順記憶部９５６からトーラス圧縮Ｃｒａｍｅｒ−Ｓｈｏｕｐ暗号手順を読み込む（ステップＳ１０２）。
【０１５４】
次に、並列処理制御部２０２は、読み込んだトーラス圧縮Ｃｒａｍｅｒ−Ｓｈｏｕｐ暗号手順から直列に実行する処理、並列処理に実行する処理を判断し（ステップＳ１０３）、伸長処理部２０４と復号化処理部９５３に実行の指示を行う。具体的には、トーラス圧縮Ｃｒａｍｅｒ−Ｓｈｏｕｐ暗号手順において、（２１−２）式＆（２２−１）式→（２１−３）式＆（２２−２）式→（２１−４）式＆（２２−３）式等のように「＆」で記述された手順の処理は並列実行するものとし、それ以外の処理は記述されている順番で直列に実行すると判断し、以下のような処理を伸長処理部２０４と復号化処理部９５３に実行するように指示する。
【０１５５】
まず、伸長処理部２０４が（２１−１）式により圧縮暗号文データ（γ3，γ1，γ2，ａ4，γ4’）の圧縮データγ2を補助出力データａ4を用いて伸長して暗号文データｃ2と補助出力データａ3を求める（ステップＳ１０４）。
【０１５６】
次に、伸長処理部２０４が（２１−２）式により圧縮データγ1を補助出力データａ3を用いて伸長して暗号文データｃ1と補助出力データａ2を求める処理（ステップＳ１０６）と、復号化処理部９５３が（２２−２）式によりステップＳ１０４で求めた暗号文データｃ2が群Ｇ，Ｇ＾に属するか否かを判断する処理（ステップＳ１０５）を並列処理として実行する。
【０１５７】
次に、伸長処理部２０４が（２１−３）式により圧縮データγ3を補助出力データａ2を用いて伸長して暗号文データｃ3と補助出力データａ1を求める処理（ステップＳ１０８）と、復号化処理部９５３が（２３−３）式により、ステップＳ１０８で求めた暗号文データｃ3が群Ｇ，Ｇ＾に属するか否かを判断し、平文ｍを求め、今まで求めた暗号文データｃ1，ｃ2，ｃ3のハッシュ値νを求める処理（ステップＳ１０９）を並列処理として実行する。
【０１５８】
そして、復号化処理部９５３は、（２３−４）式により、ハッシュ値ν、暗号文データｃ1，ｃ2を用いて暗号文データｃ4の判断処理を行う（ステップＳ１１１）。そして、平文ｍは出力部２０５により出力される（ステップＳ１１２）。
【０１５９】
このように実施の形態２の変形例のトーラス圧縮Ｃｒａｍｅｒ−Ｓｈｏｕｐ暗号方式における暗号化復号化手順では、付加入力データや補助出力データを用いない圧縮写像ρ及び伸長写像ρ-1を用い、暗号文データｃを用いる順序に基づいて、暗号化処理と圧縮処理の並列実行と、伸長処理と復号化処理の並列実行を共に実現することができる。このため、実施の形態２の変形例の暗号処理システムによれば、記憶容量を最小限にするとともに、効率的な暗号化処理および圧縮処理と、伸長処理および復号化処理を実現することができる。
【０１６０】
実施の形態１および２の暗号化処理装置１００，９００および復号化処理装置２００，９５０は、ＣＰＵなどの制御装置と、ＲＯＭ（Read Only Memory）やＲＡＭなどの記憶装置と、ＨＤＤ、ＣＤドライブ装置などの外部記憶装置と、ディスプレイ装置などの表示装置と、キーボードやマウスなどの入力装置を備えており、通常のコンピュータを利用したハードウェア構成となっている。
【０１６１】
実施の形態１および２の暗号化処理装置１００，９００で実行される暗号圧縮プログラム、実施の形態１および２の復号化処理装置２００，９５０で実行される伸長復号化プログラムは、インストール可能な形式又は実行可能な形式のファイルでＣＤ−ＲＯＭ、フレキシブルディスク（ＦＤ）、ＣＤ−Ｒ、ＤＶＤ（Ｄｉｇｉｔａｌ  Ｖｅｒｓａｔｉｌｅ  Ｄｉｓｋ）等のコンピュータで読み取り可能な記録媒体に記録されて提供される。
【０１６２】
また、実施の形態１および２の暗号化処理装置１００，９００で実行される暗号圧縮プログラム、実施の形態１および２の復号化処理装置２００，９５０で実行される伸長復号化プログラムを、インターネット等のネットワークに接続されたコンピュータ上に格納し、ネットワーク経由でダウンロードさせることにより提供するように構成しても良い。また、実施の形態１および２の暗号化処理装置１００，９００で実行される暗号圧縮プログラム、実施の形態１および２の復号化処理装置２００，９５０で実行される伸長復号化プログラムをインターネット等のネットワーク経由で提供または配布するように構成しても良い。
【０１６３】
また、実施の形態１および２の暗号化処理装置１００，９００で実行される暗号圧縮プログラム、実施の形態１および２の復号化処理装置２００，９５０で実行される伸長復号化プログラムを、ＲＯＭ等に予め組み込んで提供するように構成してもよい。
【０１６４】
実施の形態１および２の暗号化処理装置１００，９００で実行される暗号圧縮プログラム、実施の形態１および２の復号化処理装置２００，９５０で実行される伸長復号化プログラムは、上述した各部（並列処理制御部、暗号化処理部、圧縮処理部、送信部、受信部、並列処理制御部、伸長処理部、復号化処理部）を含むモジュール構成となっており、実際のハードウェアとしてはＣＰＵ（プロセッサ）が上記記憶媒体から暗号圧縮プログラム、伸長復号化プログラムを読み出して実行することにより上記各部が主記憶装置上にロードされ、並列処理制御部、暗号化処理部、圧縮処理部、送信部、受信部、並列処理制御部、伸長処理部、復号化処理部が主記憶装置上に生成されるようになっている。
【０１６５】
なお、本発明は、上記実施の形態そのままに限定されるものではなく、実施段階ではその要旨を逸脱しない範囲で構成要素を変形して具体化することができる。また、上記実施の形態に開示されている複数の構成要素の適宜な組み合わせにより、種々の発明を形成することができる。例えば、実施の形態に示される全構成要素からいくつかの構成要素を削除してもよい。さらに、異なる実施の形態にわたる構成要素を適宜組み合わせても良い。
【図面の簡単な説明】
【０１６６】
【図１】実施の形態１にかかる暗号処理システムのネットワーク構成および機能的構成を示すブロック図である。
【図２】ＥｌＧａｍａｌ暗号方式の暗号化および復号化の処理手順を示す説明図である。
【図３】トーラス圧縮ＥｌＧａｍａｌ暗号方式による従来の暗号化および圧縮処理と伸長および復号化処理の手順を示す説明図である。
【図４】実施の形態１のトーラス圧縮ＥｌＧａｍａｌ暗号手順を示す説明図である。
【図５】実施の形態１のトーラス圧縮ＥｌＧａｍａｌ暗号方式における伸長処理および復号化処理の手順を示すフローチャートである。
【図６】Ｃｒａｍｅｒ−Ｓｈｏｕｐ暗号方式の暗号化および復号化の処理手順を示す説明図である。
【図７】実施の形態１のトーラス圧縮Ｃｒａｍｅｒ−Ｓｈｏｕｐ暗号手順を示す説明図である。
【図８】実施の形態１のトーラス圧縮Ｃｒａｍｅｒ−Ｓｈｏｕｐ暗号方式における伸長処理および復号化処理の手順を示すフローチャートである。
【図９】実施の形態２にかかる暗号処理システムのネットワーク構成および機能的構成を示すブロック図である。
【図１０】実施の形態２のトーラス圧縮Ｃｒａｍｅｒ−Ｓｈｏｕｐ暗号手順を示す説明図である。
【図１１】実施の形態２のトーラス圧縮Ｃｒａｍｅｒ−Ｓｈｏｕｐ暗号方式における暗号化処理および圧縮処理の手順を示すフローチャートである。
【図１２】実施の形態２のトーラス圧縮Ｃｒａｍｅｒ−Ｓｈｏｕｐ暗号方式における伸長処理および復号化処理の手順を示すフローチャートである。
【図１３】実施の形態２の変形例のトーラス圧縮Ｃｒａｍｅｒ−Ｓｈｏｕｐ暗号手順を示す説明図である。
【図１４】実施の形態２の変形例のトーラス圧縮Ｃｒａｍｅｒ−Ｓｈｏｕｐ暗号方式における暗号化処理および圧縮処理の手順を示すフローチャートである。
【図１５】実施の形態２の変形例のトーラス圧縮Ｃｒａｍｅｒ−Ｓｈｏｕｐ暗号方式における伸長処理および復号化処理の手順を示すフローチャートである。
【符号の説明】
【０１６７】
１０１，９０１  暗号化処理部
１０２  圧縮処理部
１０３  平文データ記憶部
１０４  公開鍵記憶部
１０５  送信部
２００，９５０  復号化処理装置
２０１  受信部
２０２，９０２  並列処理制御部
２０３，９５３  復号化処理部
２０６，９０３，９５３  手順記憶部
２０４  伸長処理部
２０６  手順記憶部
２０７  秘密鍵記憶部
３０１  暗号化処理
３０２  圧縮処理
３０３  伸長処理
３０４  復号化処理
【図１】
2009193024.tif 000003
【図２】
2009193024.tif 000004
【図３】
2009193024.tif 000005
【図４】
2009193024.tif 000006
【図５】
2009193024.tif 000007
【図６】
2009193024.tif 000008
【図７】
2009193024.tif 000009
【図８】
2009193024.tif 000010
【図９】
2009193024.tif 000011
【図１０】
2009193024.tif 000012
【図１１】
2009193024.tif 000013
【図１２】
2009193024.tif 000014
【図１３】
2009193024.tif 000015
【図１４】
2009193024.tif 000016
【図１５】
2009193024.tif 000017