(57)【要約】【課題】複数のユーザがユーザごとに独立に生成した鍵を用いてデータの暗号化を行う場合に、暗号化されたデータが格納されるストレージ側でユーザが生成した鍵を知らなくても、データの重複排除を行うことができる暗号化装置を提供する。【解決手段】第一ハッシュ値算出手段８２は、左ブロックについてハッシュ値を算出する。暗号化用疑似乱数生成手段８３は、ハッシュ値と右端ブロックとの排他的論理和を入力ブロックとして、左ブロックと等しい長さの疑似乱数を生成する。共通鍵ブロック暗号化手段８４は、入力ブロックについて、秘密鍵を用いてブロック暗号文を生成する。暗号文生成手段８５は、疑似乱数と左ブロックとの排他的論理和と、ブロック暗号文とを連結して暗号文を生成する。重複排除手段８６は、２つの暗号文における左ブロックのハッシュ値または実際の値を比較し、一致する場合に、２つの暗号文のうち一方の暗号文の左ブロックを削除する。【選択図】図８
2015022318.tif 000002
【特許請求の範囲】
【請求項１】
暗号化の対象となるn-bit 以上の平文を、当該平文の右端のn-bit の固定長ブロックである右端ブロックと、前記平文から当該右端ブロックを除いたブロックである左ブロックとに分割する平文分割手段と、
暗号学的ハッシュ関数を用いて、前記左ブロックについてn-bit ハッシュ値を算出する第一ハッシュ値算出手段と、
前記第一ハッシュ値算出手段が算出したハッシュ値と前記右端ブロックとの排他的論理和を入力ブロックとして、前記左ブロックと等しい長さの疑似乱数を生成する暗号化用疑似乱数生成手段と、
前記入力ブロックについて、秘密鍵を用いたn-bit 共通鍵ブロック暗号化を行うことで、暗号化されたn-bit のブロック暗号文を生成する共通鍵ブロック暗号化手段と、
前記疑似乱数と前記左ブロックとの排他的論理和と、前記ブロック暗号文とを連結して暗号文を生成する暗号文生成手段と、
前記暗号文生成手段により生成された２つの暗号文における左ブロックのハッシュ値または実際の値を比較し、一致すると判断した場合に、前記２つの暗号文のうち一方の暗号文の左ブロックを削除する重複排除手段とを備えた
ことを特徴とする暗号化装置。
【請求項２】
暗号化用疑似乱数生成手段は、入力ブロックを鍵として生成されるストリーム暗号、または、入力ブロックを入力として固定長入力および可変長出力のハッシュ関数から出力される結果を疑似乱数とする
請求項１記載の暗号化装置。
【請求項３】
復号の対象となるn-bit 以上の暗号文を、当該暗号文の右端のn-bit の固定長ブロックである暗号文右端ブロックと、前記暗号文から当該暗号文右端ブロックを除いたブロックである暗号文左ブロックとに分割する暗号文分割手段と、
前記暗号文右端ブロックについて、秘密鍵を用いたn-bit 共通鍵ブロック暗号により復号を行うことで、復号された復号ブロックを生成する共通鍵ブロック復号手段と、
前記共通鍵ブロック復号手段が生成した復号ブロックを用いて、前記暗号文左ブロックと等しい長さの疑似乱数を生成する復号用疑似乱数生成手段と、
暗号学的ハッシュ関数を用いて、前記疑似乱数と前記暗号文左ブロックとの排他的論理和についてのハッシュ値を算出する第二ハッシュ値算出手段と、
前記疑似乱数と前記暗号文左ブロックとの排他的論理和と、前記ハッシュ値と前記復号ブロックとの排他的論理和とを連結した結果を復号結果の平文として生成する平文生成手段とを備えた
ことを特徴とする復号装置。
【請求項４】
復号用疑似乱数生成手段は、復号ブロックを鍵として生成されるストリーム暗号、または、復号ブロックを入力として固定長入力および可変長出力のハッシュ関数から出力される結果を疑似乱数とする
請求項３記載の復号装置。
【請求項５】
暗号化の対象となるn-bit 以上の平文を、当該平文の右端のn-bit の固定長ブロックである右端ブロックと、前記平文から当該右端ブロックを除いたブロックである左ブロックとに分割し、
暗号学的ハッシュ関数を用いて、前記左ブロックについてn-bit ハッシュ値を算出し、
算出されたハッシュ値と前記右端ブロックとの排他的論理和を入力ブロックとして、前記左ブロックと等しい長さの疑似乱数を生成し、
前記入力ブロックについて、秘密鍵を用いたn-bit 共通鍵ブロック暗号化を行うことで、暗号化されたn-bit のブロック暗号文を生成し、
前記疑似乱数と前記左ブロックとの排他的論理和と、前記ブロック暗号文とを連結して暗号文を生成し、
生成された２つの暗号文における左ブロックのハッシュ値または実際の値を比較し、一致すると判断した場合に、前記２つの暗号文のうち一方の暗号文の左ブロックを削除する
ことを特徴とする暗号化方法。
【請求項６】
入力ブロックを鍵として生成されるストリーム暗号、または、入力ブロックを入力として固定長入力および可変長出力のハッシュ関数から出力される結果を疑似乱数とする
請求項５記載の暗号化方法。
【請求項７】
復号の対象となるn-bit 以上の暗号文を、当該暗号文の右端のn-bit の固定長ブロックである暗号文右端ブロックと、前記暗号文から当該暗号文右端ブロックを除いたブロックである暗号文左ブロックとに分割し、
前記暗号文右端ブロックについて、秘密鍵を用いたn-bit 共通鍵ブロック暗号により復号を行うことで、復号された復号ブロックを生成し、
生成された復号ブロックを用いて、前記暗号文左ブロックと等しい長さの疑似乱数を生成し、
暗号学的ハッシュ関数を用いて、前記疑似乱数と前記暗号文左ブロックとの排他的論理和についてのハッシュ値を算出し、
前記疑似乱数と前記暗号文左ブロックとの排他的論理和と、前記ハッシュ値と前記復号ブロックとの排他的論理和とを連結した結果を復号結果の平文として生成する
ことを特徴とする復号方法。
【請求項８】
復号ブロックを鍵として生成されるストリーム暗号、または、復号ブロックを入力として固定長入力および可変長出力のハッシュ関数から出力される結果を疑似乱数とする
請求項７記載の復号方法。
【請求項９】
コンピュータに、
暗号化の対象となるn-bit 以上の平文を、当該平文の右端のn-bit の固定長ブロックである右端ブロックと、前記平文から当該右端ブロックを除いたブロックである左ブロックとに分割する平文分割処理、
暗号学的ハッシュ関数を用いて、前記左ブロックについてn-bit ハッシュ値を算出する第一ハッシュ値算出処理、
前記第一ハッシュ値算出処理で算出されたハッシュ値と前記右端ブロックとの排他的論理和を入力ブロックとして、前記左ブロックと等しい長さの疑似乱数を生成する暗号化用疑似乱数生成処理、
前記入力ブロックについて、秘密鍵を用いたn-bit 共通鍵ブロック暗号化を行うことで、暗号化されたn-bit のブロック暗号文を生成する共通鍵ブロック暗号化処理、
前記疑似乱数と前記左ブロックとの排他的論理和と、前記ブロック暗号文とを連結して暗号文を生成する暗号文生成処理、および、
前記暗号文生成処理で生成された２つの暗号文における左ブロックのハッシュ値または実際の値を比較し、一致すると判断した場合に、前記２つの暗号文のうち一方の暗号文の左ブロックを削除する重複排除処理
を実行させるための暗号化プログラム。
【請求項１０】
コンピュータに、
復号の対象となるn-bit 以上の暗号文を、当該暗号文の右端のn-bit の固定長ブロックである暗号文右端ブロックと、前記暗号文から当該暗号文右端ブロックを除いたブロックである暗号文左ブロックとに分割する暗号文分割処理、
前記暗号文右端ブロックについて、秘密鍵を用いたn-bit 共通鍵ブロック暗号により復号を行うことで、復号された復号ブロックを生成する共通鍵ブロック復号処理、
前記共通鍵ブロック復号処理で生成された復号ブロックを用いて、前記暗号文左ブロックと等しい長さの疑似乱数を生成する復号用疑似乱数生成処理、
暗号学的ハッシュ関数を用いて、前記疑似乱数と前記暗号文左ブロックとの排他的論理和についてのハッシュ値を算出する第二ハッシュ値算出処理、および、
前記疑似乱数と前記暗号文左ブロックとの排他的論理和と、前記ハッシュ値と前記復号ブロックとの排他的論理和とを連結した結果を復号結果の平文として生成する平文生成処理
を実行させるための復号プログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、共通鍵を用いて暗号化された暗号文の重複排除を行う暗号化装置、暗号化方法および暗号化プログラム並びに暗号文の復号を行う復号装置、復号方法および復号プログラムに関する。
【背景技術】
【０００２】
ストレージ装置や、Ｗｅｂ上で提供されるストレージサービスの容量の圧迫を避けるために、重複排除という技術が広く使われている。これは、複数の同じファイルをストレージに格納する際、どちらか一つのみを実際に格納するものである。
【０００３】
典型的な重複排除の方法では、ファイルごとにハッシュ値が保存され、新たに追加されるファイルについて、計算したハッシュ値が過去に保存したハッシュ値と一致する場合に、既に同じファイルがあるものとして、新たなファイルは保存しないという判断が行われる。なお、保存されたファイルはハッシュ値ベースでアクセスされる。
【０００４】
用いられるハッシュ関数が暗号学的に安全であれば、上記のような処理を行った場合に、同じハッシュ値を持つ二つの異なるファイルを作り出すことは困難と考えられる。そのため、保存すべき新しいファイルを誤って保存しないという危険性は、十分低いと考えられる。
【０００５】
実際には、ファイルがより細かいチャンク単位に分割されたうえでハッシュ値が求められ、チャンク単位で重複排除が行われることが多い。チャンク単位で重複排除を行う具体的な方式は、例えば、特許文献１に記載されている。
【０００６】
なお、関連する技術として、非特許文献１や非特許文献２には、初期ベクトルを持たない暗号化方式（確定的暗号化、Deterministic Encryption）が記載されている。また、特許文献２には、収束暗号化（CE：Convergent Encryption ）と呼ばれる方式が記載されている。また、非特許文献３には、Scramble All, Encrypt Smallとよばれる暗号化方式が記載されている。
【０００７】
また、非特許文献４には、スポンジ構造のハッシュ関数について記載されており、非特許文献５には、ブロック暗号のブロックサイズを変更する方法について記載されている。
【先行技術文献】
【特許文献】
【０００８】
【特許文献１】国際公開第２０１０／０８６９２２号
【特許文献２】欧州特許第１２９９９７１号明細書
【非特許文献】
【０００９】
【非特許文献１】NIST Special Publication 800-38E, "Recommendation for Block Cipher Modes of Operation: The XTS-AES Mode for Confidentiality on Storage Devices", Jan. 2010.
【非特許文献２】Debrup Chakraborty, Palash Sarkar, "HCH: A New Tweakable Enciphering Scheme Using the Hash-Encrypt-Hash Approach", pp. 287-302, Progress in Cryptology - INDOCRYPT 2006, Proceedings. Lecture Notes in Computer Science 4329 Springer 2006.
【非特許文献３】M. Jakobsson, J. P. Stern, and M. Yung., "Scramble All, Encrypt Small", L. Knudsen (Ed.): FSE’99, LNCS 1636, pp. 95-111, 1999.
【非特許文献４】G. Bertoni, J. Daemen, M. Peeters and G. Van Assche, "Sponge functions, Ecrypt Hash Workshop", May 2007.
【非特許文献５】Mihir Bellare, Thomas Ristenpart, Phillip Rogaway, Till Stegers, "Format-Preserving Encryption", SAC 2009, pp. 295-312.
【発明の概要】
【発明が解決しようとする課題】
【００１０】
ストレージ装置や、ストレージサービスを利用する場合に、データを秘匿することを目的として、共通鍵暗号による暗号化が用いられることがある。重複排除技術と暗号化を組み合わせることを考えた場合、ストレージ側で鍵を持てば、重複排除技術した後に暗号化すればよいため容易である。しかし、この場合、装置の管理者の内部犯行などによる、ストレージからの情報漏洩のリスクは残る。このようなリスクをなくすため、ストレージを使うユーザのみが鍵を持ち、ユーザ側で暗号化と、ストレージ装置へ暗号文を送信することが考えられる。
【００１１】
ここで、カウンターモードなど、一般的な暗号化方式を用いると、たとえ同じ平文と同じ鍵であっても、初期ベクトルの違いにより異なる暗号文へ変換されてしまうため、ストレージ側での重複排除は不可能になる。
【００１２】
ユーザが単一かつ用いる鍵も一つである場合、非特許文献１や非特許文献２に記載された暗号化方式を用いることで、同じ平文、同じ鍵であれば同じ暗号文が生成されるようになり、重複排除が可能になる。
【００１３】
しかし、ユーザが複数存在する（マルチユーザ）場合には、ユーザごとに鍵が異なるため、初期ベクトルを持たない暗号化方法でも重複排除は不可能になる。特許文献２に記載された収束暗号化方式CEを用いることで、この問題を解決することは可能である。
【００１４】
図１０は、収束暗号化方式の例を示す説明図である。収束暗号化方式は、平文Ｍに対して、暗号学的ハッシュ関数h(*)と、共通鍵暗号による確定的暗号化Enc(*,*)を組み合わせて、暗号文Ｃ= Enc(h(Ｍ), Ｍ) を生成する方式である。
【００１５】
ここで、Enc(K,X)は、鍵K を用いたX の暗号化結果である。したがって、収束暗号化方式CEは、平文のハッシュ値を鍵とした確定的暗号化ということができる。この方法では、異なるユーザが同じ平文Ｍを持っている場合に、生成される暗号文は、どのユーザでも同一である。よって、ストレージ側で暗号文が一致するか否かを判断できるため、重複排除が可能になる。
【００１６】
収束暗号化方式CEでは、平文ごとに異なる鍵が生成されるため、この鍵をどのように管理するかが問題になる。一つの方法として、ユーザがすべての鍵を記憶し、その鍵と対応する暗号文とを関連づけて、データベースなどで管理する方法がある。また、他の方法として、ユーザがマスター鍵MKを一つ用意しておく。このマスター鍵MKを用いて、平文Ｍの暗号化に用いた鍵h(Ｍ) を暗号化し、Ｍの暗号文Ｃと、鍵h(Ｍ) の暗号文L = Enc(MK, h(M)) とをストレージに保存する、という方法を用いることも可能である。この場合、ストレージ側で、鍵の暗号文L と平文の暗号文Ｃとの対応付けを記憶しておく必要がある。
【００１７】
いずれにせよ、収束暗号化方式CEでは、鍵は平文ごとに生成される。そのため、平文ごとにユーザまたはストレージ側で保持するデータが鍵の分増加してしまう。さらに、収束暗号化方式CEでは、鍵の暗号文を保持するエンティティにおいて、鍵の暗号文と平文の暗号文とを対応付けて管理する手間が増えてしまうという問題がある。
【００１８】
そこで、本発明は、複数のユーザがユーザごとに独立に生成した鍵を用いてデータの暗号化を行う場合に、暗号化されたデータが格納されるストレージ側でユーザが生成した鍵を知らなくても、データの重複排除を行うことができる暗号化装置、暗号化方法および暗号化プログラム並びに暗号文の復号を行う復号装置、復号方法および復号プログラムを提供することを目的とする。
【課題を解決するための手段】
【００１９】
本発明による暗号化装置は、暗号化の対象となるn-bit 以上の平文を、その平文の右端のn-bit の固定長ブロックである右端ブロックと、平文からその右端ブロックを除いたブロックである左ブロックとに分割する平文分割手段と、暗号学的ハッシュ関数を用いて、左ブロックについてn-bit ハッシュ値を算出する第一ハッシュ値算出手段と、第一ハッシュ値算出手段が算出したハッシュ値と右端ブロックとの排他的論理和を入力ブロックとして、左ブロックと等しい長さの疑似乱数を生成する暗号化用疑似乱数生成手段と、入力ブロックについて、秘密鍵を用いたn-bit 共通鍵ブロック暗号化を行うことで、暗号化されたn-bit のブロック暗号文を生成する共通鍵ブロック暗号化手段と、疑似乱数と左ブロックとの排他的論理和と、ブロック暗号文とを連結して暗号文を生成する暗号文生成手段と、暗号文生成手段により生成された２つの暗号文における左ブロックのハッシュ値または実際の値を比較し、一致すると判断した場合に、２つの暗号文のうち一方の暗号文の左ブロックを削除する重複排除手段とを備えたことを特徴とする。
【００２０】
本発明による復号装置は、復号の対象となるn-bit 以上の暗号文を、その暗号文の右端のn-bit の固定長ブロックである暗号文右端ブロックと、暗号文からその暗号文右端ブロックを除いたブロックである暗号文左ブロックとに分割する暗号文分割手段と、暗号文右端ブロックについて、秘密鍵を用いたn-bit 共通鍵ブロック暗号により復号を行うことで、復号された復号ブロックを生成する共通鍵ブロック復号手段と、共通鍵ブロック復号手段が生成した復号ブロックを用いて、暗号文左ブロックと等しい長さの疑似乱数を生成する復号用疑似乱数生成手段と、暗号学的ハッシュ関数を用いて、疑似乱数と暗号文左ブロックとの排他的論理和についてのハッシュ値を算出する第二ハッシュ値算出手段と、疑似乱数と暗号文左ブロックとの排他的論理和と、ハッシュ値と復号ブロックとの排他的論理和とを連結した結果を復号結果の平文として生成する平文生成手段とを備えたことを特徴とする。
【００２１】
本発明による暗号化方法は、暗号化の対象となるn-bit 以上の平文を、その平文の右端のn-bit の固定長ブロックである右端ブロックと、平文からその右端ブロックを除いたブロックである左ブロックとに分割し、暗号学的ハッシュ関数を用いて、左ブロックについてn-bit ハッシュ値を算出し、算出されたハッシュ値と右端ブロックとの排他的論理和を入力ブロックとして、左ブロックと等しい長さの疑似乱数を生成し、入力ブロックについて、秘密鍵を用いたn-bit 共通鍵ブロック暗号化を行うことで、暗号化されたn-bit のブロック暗号文を生成し、疑似乱数と左ブロックとの排他的論理和と、ブロック暗号文とを連結して暗号文を生成し、生成された２つの暗号文における左ブロックのハッシュ値または実際の値を比較し、一致すると判断した場合に、２つの暗号文のうち一方の暗号文の左ブロックを削除することを特徴とする。
【００２２】
本発明による復号方法は、復号の対象となるn-bit 以上の暗号文を、その暗号文の右端のn-bit の固定長ブロックである暗号文右端ブロックと、暗号文からその暗号文右端ブロックを除いたブロックである暗号文左ブロックとに分割し、暗号文右端ブロックについて、秘密鍵を用いたn-bit 共通鍵ブロック暗号により復号を行うことで、復号された復号ブロックを生成し、生成された復号ブロックを用いて、暗号文左ブロックと等しい長さの疑似乱数を生成し、暗号学的ハッシュ関数を用いて、疑似乱数と暗号文左ブロックとの排他的論理和についてのハッシュ値を算出し、疑似乱数と暗号文左ブロックとの排他的論理和と、ハッシュ値と復号ブロックとの排他的論理和とを連結した結果を復号結果の平文として生成することを特徴とする。
【００２３】
本発明による暗号化プログラムは、コンピュータに、暗号化の対象となるn-bit 以上の平文を、その平文の右端のn-bit の固定長ブロックである右端ブロックと、平文からその右端ブロックを除いたブロックである左ブロックとに分割する平文分割処理、暗号学的ハッシュ関数を用いて、左ブロックについてn-bit ハッシュ値を算出する第一ハッシュ値算出処理、第一ハッシュ値算出処理で算出されたハッシュ値と右端ブロックとの排他的論理和を入力ブロックとして、左ブロックと等しい長さの疑似乱数を生成する暗号化用疑似乱数生成処理、入力ブロックについて、秘密鍵を用いたn-bit 共通鍵ブロック暗号化を行うことで、暗号化されたn-bit のブロック暗号文を生成する共通鍵ブロック暗号化処理、疑似乱数と左ブロックとの排他的論理和と、ブロック暗号文とを連結して暗号文を生成する暗号文生成処理、および、暗号文生成処理で生成された２つの暗号文における左ブロックのハッシュ値または実際の値を比較し、一致すると判断した場合に、２つの暗号文のうち一方の暗号文の左ブロックを削除する重複排除処理を実行させることを特徴とする。
【００２４】
本発明による復号プログラムは、コンピュータに、復号の対象となるn-bit 以上の暗号文を、その暗号文の右端のn-bit の固定長ブロックである暗号文右端ブロックと、暗号文からその暗号文右端ブロックを除いたブロックである暗号文左ブロックとに分割する暗号文分割処理、暗号文右端ブロックについて、秘密鍵を用いたn-bit 共通鍵ブロック暗号により復号を行うことで、復号された復号ブロックを生成する共通鍵ブロック復号処理、共通鍵ブロック復号処理で生成された復号ブロックを用いて、暗号文左ブロックと等しい長さの疑似乱数を生成する復号用疑似乱数生成処理、暗号学的ハッシュ関数を用いて、疑似乱数と暗号文左ブロックとの排他的論理和についてのハッシュ値を算出する第二ハッシュ値算出処理、および、疑似乱数と暗号文左ブロックとの排他的論理和と、ハッシュ値と復号ブロックとの排他的論理和とを連結した結果を復号結果の平文として生成する平文生成処理を実行させることを特徴とする。
【発明の効果】
【００２５】
本発明によれば、複数のユーザがユーザごとに独立に生成した鍵を用いてデータの暗号化を行う場合に、暗号化されたデータが格納されるストレージ側でユーザが生成した鍵を知らなくても、データの重複排除を行うことができる。
【図面の簡単な説明】
【００２６】
【図１】本発明による重複排除付きの暗号化装置の一実施形態を示すブロック図である。
【図２】暗号化部１１の構成例を示すブロック図である。
【図３】重複排除手段１０５が行う重複排除の例を示す説明図である。
【図４】本発明による復号装置の一実施形態を示すブロック図である。
【図５】暗号化部１１の動作例を示すフローチャートである。
【図６】重複排除手段１０５の動作例を示すフローチャートである。
【図７】復号装置２０の動作例を示すフローチャートである。
【図８】本発明による暗号化装置の概要を示すブロック図である。
【図９】本発明による復号装置の概要を示すブロック図である。
【図１０】収束暗号化方式の例を示す説明図である。
【発明を実施するための形態】
【００２７】
以下、本発明の実施形態を図面を参照して説明する。以下の説明では、特に断りのない限り、１ブロックの長さをn ビットとする。
【００２８】
図１は、本発明による重複排除付きの暗号化装置の一実施形態を示すブロック図である。本発明の重複排除付き暗号化装置１０は、暗号化部１１と、重複排除手段１０５とを備えている。また、暗号化部１１は、平文入力手段１００と、ハッシュ手段１０１と、鍵なし疑似乱数生成手段１０２と、共通鍵ブロック暗号化手段１０３と、暗号文出力手段１０４とを含む。
【００２９】
重複排除付き暗号化装置１０は、ＣＰＵ（Central Processing Unit ）、メモリおよび磁気ディスク装置により実現可能である。重複排除付き暗号化装置１０の各手段は、プログラム（暗号化プログラム）を磁気ディスク装置に格納しておき、このプログラムをＣＰＵ上で動作させることにより実現できる。
【００３０】
図２は、本実施形態の暗号化部１１の構成例を示すブロック図である。平文入力手段１００は、暗号化対象となるm ブロックの平文Ｍを入力する手段である。ただし、m は２以上である。平文入力手段１００は、例えば、キーボードなどの文字入力装置により実現されてもよく、ネットワーク装置等を介して他の装置から送信されるデータを受信するインタフェースにより実現されていてもよい。
【００３１】
ハッシュ手段１０１は、平文Ｍの左m-1 ブロックをＭＬとし、右端の1 ブロックをＭＲとしたときに、SHA-1 などの暗号学的ハッシュ関数H を用いて、ハッシュ値S=H(ＭＬ) を出力する手段である。
【００３２】
例えば、共通鍵ブロック暗号が用いられる場合、標準的なブロック長は１６バイトであり、ＭＲは、１２８ビットになる。以下、この右端のブロックの長さを、n-bit と記すこともある。また、平文Ｍは、この右端のブロックを少なくとも含むことから、平文の長さは、少なくともn-bit 以上の長さを有する。
【００３３】
以下の説明では、平文Ｍの右端のn-bit 固定長ブロックを右端ブロックまたはＭＲと記し、平文Ｍで右端ブロックを除いたそれ以外のブロック（すなわち、平文の左側のブロック）のことを左ブロックまたはＭＬと記すこともある。すなわち、ハッシュ手段１０１は、平文Ｍを右端ブロックと左ブロックに分割する処理を行っていると言える。
【００３４】
鍵なし疑似乱数生成手段１０２は、ハッシュ手段１０１が出力する、ハッシュ値S と平文右端の1 ブロックＭＲとの排他的論理和の結果をブロックV としたとき、このブロックV を入力として疑似乱数R を出力する手段である。ここで、疑似乱数R は、ＭＬと同じ長さである。
【００３５】
また、鍵なし疑似乱数生成手段１０２は、内部で秘密鍵やその他の乱数を用いない関数を使用する。鍵なし疑似乱数生成手段１０２は、例えば、ブロックV を鍵としたストリーム暗号の出力を疑似乱数R とすればよい。
【００３６】
なお、一般的な暗号学的ハッシュ関数は、可変長の入力で、かつ比較的短い固定長の結果を出力する。そのため、一般的な暗号学的ハッシュ関数を単に用いるだけでは、鍵なし疑似乱数生成手段１０２の機能を実現できない。しかし、暗号学的ハッシュ関数が内部で用いる固定長入出力の圧縮関数と呼ばれる関数を部品化し、固定長入力および可変長出力のハッシュ関数を構成すれば、上述する鍵なし疑似乱数生成手段１０２の機能を実現可能である。
【００３７】
また、鍵なし疑似乱数生成手段１０２は、ブロックV を基に、固定長入力および可変長出力のハッシュ関数から出力される結果を疑似乱数R としてもよい。また、鍵なし疑似乱数生成手段１０２は、例えば、非特許文献４に記載されたスポンジ構造のハッシュ関数を用いてもよい。この関数は、可変長入力、可変長出力を実現する関数であるため、この関数を直接的に用いることで、上述する鍵なし疑似乱数生成手段１０２の機能を実現可能である。
【００３８】
共通鍵ブロック暗号化手段１０３は、ブロックV を、秘密鍵を備えたAES （Advanced Encryption Standard）などの共通鍵ブロック暗号で暗号化し、暗号文の右端ブロックであるＣＲを生成する手段である。なお、ブロックV は、長さが標準的な共通鍵ブロック暗号に用いられるブロックサイズでない場合、共通鍵ブロック暗号化手段１０３は、例えば、非特許文献５に記載された方法を用いて、既存のブロック暗号から任意のブロックサイズのブロック暗号を生成すればよい。
【００３９】
暗号文出力手段１０４は、共通鍵ブロック暗号化手段１０３が出力する暗号文の右端ブロックＣＲと、鍵なし疑似乱数生成手段１０２が出力する疑似乱数R とＭＬとの排他的論理和（この排他的論理和をＣＬとする）をもとに、ＣＬとＣＲとを連結した暗号文Ｃを出力する。
【００４０】
重複排除手段１０５は、上記の平文入力手段１００、ハッシュ手段１０１、鍵なし疑似乱数生成手段１０２、共通鍵ブロック暗号化手段１０３および暗号文出力手段１０４を含む暗号化部１１によって出力された二つの暗号文ＣおよびＣ’を入力として、重複排除を行う手段である。
【００４１】
なお、二つの暗号文ＣとＣ’の鍵は同じである必要はない。また、重複排除手段１０５は、鍵を持たずに重複排除処理を行う。
【００４２】
具体的には、暗号文Ｃの右端ブロックをＣＲ、それ以外のブロックをＣＬ、暗号文Ｃ’の右端ブロックをＣＲ’、それ以外のブロックをＣＬ’とする。このとき、重複排除手段１０５は、ＣＬとＣＬ’が長さも含めて等しい場合に重複排除を行い、（ＣＬ, ＣＲ, ＣＲ’）を出力する。一方、ＣＬとＣＬ’が異なる場合、重複排除手段１０５は、重複排除を行わずに、（ＣＬ, ＣＲ, ＣＬ’, ＣＲ’）を出力する。
【００４３】
ＣＬとＣＬ’の同一性をチェックする際、重複排除手段１０５は、一部のブロックが一致するか否かで判断してもよいし、ハッシュ関数H を用いて判断してもよい。すなわち、重複排除手段１０５は、H(ＣＬ)とH(ＣＬ’) が等しい場合に、ＣＬとＣＬ’が等しいと見なしてもよい。また、重複排除手段１０５は、ハッシュ値だけでなく、実際の値を比較して、ＣＬとＣＬ’の同一性をチェックしてもよい。
【００４４】
また、二つ以上の任意の暗号文が存在した場合、重複排除手段１０５は、上述する２つの暗号文に対する同一性チェックを全ての組み合わせについて実行し、各暗号文の右端ブロック以外について、重複排除を行うことも可能である。
【００４５】
図３は、重複排除手段１０５が行う重複排除の例を示す説明図である。図３に示す例では、暗号化部１１に入力された平文Ｍ、Ｍ’が暗号化されて、それぞれＣ、Ｃ’として出力される。このとき、重複排除手段１０５は、ＣＬとＣＬ’が等しい場合に、ＣＬ’を除いたＣおよびＣＲ’を出力し、それ以外の場合に、ＣおよびＣ’を出力する。
【００４６】
なお、図３では、暗号化部１１を２つ示しているが、暗号化部１１の数は２つに限定されない。１つの暗号化部１１が、複数の暗号化処理を行ってもよく、３つ以上の暗号化部１１がそれぞれ独立に暗号化処理を行ってもよい。
【００４７】
本発明における重複排除付きの暗号化装置は、コンピュータと、そのコンピュータ上で実行されるプログラムにより実現することができる。具体的には、平文入力手段１００と、ハッシュ手段１０１と、鍵なし疑似乱数生成手段１０２と、共通鍵ブロック暗号化手段１０３と、暗号文出力手段１０４と、重複排除手段１０５とは、プログラム（暗号化プログラム）に従って動作するコンピュータのＣＰＵによって実現される。
【００４８】
例えば、プログラムは、重複排除付き暗号化装置１０の記憶部（図示せず）に記憶され、ＣＰＵは、そのプログラムを読み込み、プログラムに従って、平文入力手段１００、ハッシュ手段１０１、鍵なし疑似乱数生成手段１０２、共通鍵ブロック暗号化手段１０３、暗号文出力手段１０４および重複排除手段１０５として動作してもよい。
【００４９】
また、平文入力手段１００と、ハッシュ手段１０１と、鍵なし疑似乱数生成手段１０２と、共通鍵ブロック暗号化手段１０３と、暗号文出力手段１０４と、重複排除手段１０５とは、それぞれが専用のハードウェアで実現されていてもよい。
【００５０】
図４は、本発明による復号装置の一実施形態を示すブロック図である。本発明の復号装置２０は、暗号文入力手段２００と、共通鍵ブロック復号手段２０１と、鍵なし疑似乱数生成手段２０２と、ハッシュ手段２０３と、平文出力手段２０４とを備えている。
【００５１】
暗号文入力手段２００は、復号対象となるm ブロックの暗号文Ｃを入力する手段である。ただし、m は２以上である。暗号文入力手段２００は、例えば、キーボードなどの文字入力装置により実現されてもよく、ネットワーク装置等を介して他の装置から送信されるデータを受信するインタフェースにより実現されていてもよい。
【００５２】
共通鍵ブロック復号手段２０１は、暗号文Ｃの左m-1 ブロックをＣＬとし、右端の1 ブロックをＣＲとしたときに、ＣＲを、秘密鍵を備えたAESなどの共通鍵ブロック暗号で復号し、ブロックV を生成する手段である。
【００５３】
なお、暗号化の場合と同様、暗号文Ｃの右端のブロックの長さを、n-bit と記すこともある。また、暗号文Ｃは、この右端のブロックを少なくとも含むことから、暗号文の長さは、少なくともn-bit 以上の長さを有する。
【００５４】
ここでは、暗号文Ｃの右端のn-bit 固定長ブロックを暗号文右端ブロックまたはＣＲと記し、暗号文Ｃで暗号文右端ブロックを除いたそれ以外のブロック（すなわち、暗号文の左側のブロック）のことを暗号文左ブロックまたはＣＬと記す。すなわち、共通鍵ブロック復号手段２０１は、暗号文Ｃを暗号文右端ブロックと暗号文左ブロックに分割する処理を行っていると言える。
【００５５】
鍵なし疑似乱数生成手段２０２は、共通鍵ブロック復号手段２０１が出力するブロックV を入力として疑似乱数R を出力する手段である。ここで、疑似乱数R は、ＣＬと同じ長さである。また、ブロックV から疑似乱数R を生成するために用いられる関数は、重複排除付き暗号化装置１０の鍵なし疑似乱数生成手段１０２が用いる関数と同様である。
【００５６】
すなわち、鍵なし疑似乱数生成手段２０２は、復号されたブロックを鍵としたストリーム暗号の出力を疑似乱数R としてもよく、復号されたブロックを基に、固定長入力および可変長出力のハッシュ関数から出力される結果を疑似乱数R としてもよい。このとき、鍵なし疑似乱数生成手段２０２は、鍵を用いずに疑似乱数R を生成する。
【００５７】
ハッシュ手段２０３は、SHA-1 などの暗号学的ハッシュ関数H を用いて、疑似乱数R とＣＬとの排他的論理和を入力とし、ハッシュ値S を出力する手段である。
【００５８】
平文出力手段２０４は、ハッシュ手段２０３に入力される、疑似乱数R とＣＬとの排他的論理和を、平文の右端以外のブロックＭＬとし、ハッシュ手段２０３が出力する、疑似乱数R とブロックV との排他的論理和を、平文の右端ブロックＭＲとして、ＭＬとＭＲとを連結した平文Ｍを出力する。
【００５９】
暗号文入力手段２００と、共通鍵ブロック復号手段２０１と、鍵なし疑似乱数生成手段２０２と、ハッシュ手段２０３と、平文出力手段２０４とは、プログラム（復号プログラム）に従って動作するコンピュータのＣＰＵによって実現される。
【００６０】
例えば、プログラムは、復号装置２０の記憶部（図示せず）に記憶され、ＣＰＵは、そのプログラムを読み込み、プログラムに従って、暗号文入力手段２００、共通鍵ブロック復号手段２０１、鍵なし疑似乱数生成手段２０２、ハッシュ手段２０３および平文出力手段２０４として動作してもよい。
【００６１】
また、暗号文入力手段２００と、共通鍵ブロック復号手段２０１と、鍵なし疑似乱数生成手段２０２と、ハッシュ手段２０３と、平文出力手段２０４とは、それぞれが専用のハードウェアで実現されていてもよい。
【００６２】
次に、本実施形態の重複排除付き暗号化装置１０および復号装置２０の動作を説明する。初めに、重複排除付き暗号化装置１０における暗号化部１１の暗号化処理を説明する。図５は、本実施形態の暗号化部１１の動作例を示すフローチャートである。
【００６３】
まず、平文入力手段１００が、暗号化対象となるm ブロックの平文Ｍを入力する（ステップＳ１１）。ただし、m は2 以上である。また、平文Ｍは、ＭＬとＭＲが結合した文であると言うこともできる。
【００６４】
次に、ハッシュ手段１０１が、平文M の左m-1 ブロックをＭＬとし、右端の1 ブロックをＭＲとしたときに、SHA-1 などの暗号学的ハッシュ関数H を用いて、ハッシュ値S=H(ＭＬ) を計算する（ステップＳ１２）。
【００６５】
ハッシュ値S と平文右端の1 ブロックＭＲとの排他的論理和を算出した結果をブロックV としたとき、鍵なし疑似乱数生成手段１０２が、このブロックV を入力として、疑似乱数R を計算する（ステップＳ１３）。
【００６６】
次に、共通鍵ブロック暗号化手段１０３は、ブロックV を秘密鍵を備えたAES などの共通鍵ブロック暗号で暗号化し、ブロックＣＲを求める（ステップＳ１４）。
【００６７】
ＣＲを暗号文の右端ブロックとし、鍵なし疑似乱数生成手段１０２が出力する疑似乱数R とＭＬとの排他的論理和の算出結果をＣＬとしたとき、暗号文出力手段１０４は、ＣＬとＣＲを連結して暗号文Ｃを求め（ステップＳ１５）、求めた暗号文Ｃを出力する（ステップＳ１６）。
【００６８】
次に、重複排除付き暗号化装置１０における重複排除手段１０５の重複排除処理を説明する。図６は、本実施形態の重複排除手段１０５の動作例を示すフローチャートである。
【００６９】
また、重複排除手段１０５は、暗号化部１１が出力する２つの暗号文ＣとＣ’を入力する（ステップＳ２１）。ここでは、２つの暗号文ＣとＣ’のそれぞれの右端ブロックをＣＲ、ＣＲ’とし、残りのブロックをＣＬ、ＣＬ’とする。
【００７０】
重複排除手段１０５は、ＣＬとＣＬ’が長さも含めて等しいか否かを判断する（ステップＳ２２）。ＣＬとＣＬ’が長さも含めて等しい場合（ステップＳ２２におけるｙｅｓ）、重複排除手段１０５は、重複排除を行って、（ＣＬ, ＣＲ, ＣＲ’）を出力する（ステップＳ２３）。一方、ＣＬとＣＬ’が異なる場合（ステップＳ２２におけるｎｏ）、重複排除手段１０５は、重複排除を行わずに、（ＣＬ, ＣＲ, ＣＬ’, ＣＲ’）を出力する（ステップＳ２４）。
【００７１】
次に、復号装置２０の復号処理を説明する。図７は、本実施形態の復号装置２０の動作例を示すフローチャートである。
【００７２】
まず、暗号文入力手段２００は、復号対象となるm ブロックの暗号文Ｃを入力する（ステップＳ３１）。ただし m は、2 以上である。また、暗号文Ｃは、ＣＬとＣＲが結合した文であると言うこともできる。
【００７３】
次に、共通鍵ブロック復号手段２０１は、暗号文Ｃの左m-1 ブロックをＣＬとし、右端の1 ブロックをＣＲとしたときに、ＣＬを、秘密鍵を備えたAES などの共通鍵ブロック暗号で復号し、ブロックV を生成する（ステップＳ３２）。
【００７４】
次に、ブロックV を入力として、鍵なし疑似乱数生成手段２０２は、疑似乱数R を出力する（ステップＳ３３）。
【００７５】
疑似乱数R とＣＬとの排他的論理和をＭＬとしたとき、ハッシュ手段２０３は、SHA-1 などの暗号学的ハッシュ関数H を用いて、ハッシュ値S=H(ＭＬ) を出力する（ステップＳ３４）。
【００７６】
平文出力手段２０４は、ハッシュ値S とブロックV との排他的論理和の結果を、平文右端の1 ブロックＭＲとし、ＭＬとＭＲを連結して平文Ｍを復号する（ステップＳ３５）。そして、平文出力手段２０４は、平文Ｍ（すなわち、ＭＬとＭＲの連結結果）を出力する（ステップＳ３６）。
【００７７】
以上のように、本実施形態によれば、ハッシュ手段１０１が、入力された平文ＭをＭＲとＭＬとに分割し、暗号学的ハッシュ関数を用いて、ＭＬについてハッシュ値S を算出する。次に、鍵なし疑似乱数生成手段１０２が、ハッシュ値S とＭＲとの排他的論理和を入力ブロックV として、ＭＬと等しい長さの疑似乱数R を生成する。次に、共通鍵ブロック暗号化手段１０３が、入力ブロックV について、秘密鍵を用いた共通鍵ブロック暗号化を行うことで、暗号化されたＣＲを生成し、暗号文出力手段１０４が、疑似乱数R とＭＬとの排他的論理和ＣＬと、ＣＲとを連結して暗号文Ｃを生成する。最後に、重複排除手段１０５が、生成された２つの暗号文における左ブロックＣＬおよびＣＬ’のハッシュ値または実際の値を比較し、一致すると判断した場合に、２つの暗号文のうち一方の暗号文のＣＬ（ＣＬ’）を削除する。
【００７８】
したがって、複数のユーザがユーザごとに独立に生成した鍵を用いてデータの暗号化を行う場合に、暗号化されたデータが格納されるストレージ側でユーザが生成した鍵を知らなくても、データの重複排除を行うことができる。
【００７９】
具体的には、暗号文の特定箇所の1 ブロックを除いた部分が、平文全体に対する鍵無しの計算から決定されるように、平文が暗号化される。そして、残る1 ブロックについてのみ、ユーザが任意に設定した秘密鍵とブロック暗号で暗号化が行われる。これにより、平文が一致すれば、用いた鍵によらず、暗号文の特定箇所の1 ブロックを除いた部分が一致するという特徴を有することになる。したがって、ストレージ側では鍵を知らなくとも、1 ブロックを除いた部分について重複排除が可能になる。
【００８０】
また、鍵無しの計算を行う処理では、ハッシュ関数を用いた2 ラウンドの処理が用いられるため、鍵を知らない者が暗号文から平文を復号するという攻撃を防ぐことが可能になる。
【００８１】
例えば、本発明を用いることで、Convergent Encryption における本質的な制約である、平文ごとに鍵が生成されるという問題が解決される。平文ごとに鍵が生成されると、平文ごとにユーザ側やサーバ（ストレージ）側で保持するデータが鍵の分増加し、さらに鍵の暗号文を保持するエンティティにおいて、鍵の暗号文と平文の暗号文とを対応付けて管理する手間が増えるというデメリットが生じるからである。
【００８２】
一方、本実施形態によれば、暗号化部１１が、単一の鍵を生成するため、暗号化により保持すべきデータが増加することはない。本実施形態で用いられる暗号化方式では、暗号文は、その右端ブロックを除き、鍵無しの計算により決定されるため、平文が一致すれば、用いた鍵によらず、暗号文のほとんどが一致するという特徴を持つ。これにより、サーバ（ストレージ）側では、鍵を知らなくとも、暗号文の右端ブロックを除いた部分について重複排除が可能になる。
【００８３】
また、本実施形態によれば、共通鍵ブロック復号手段２０１が、入力された暗号文Ｃを、ＣＲとＣＬとに分割し、ＣＲについて、秘密鍵を用いた共通鍵ブロック暗号により復号を行うことで、復号された復号ブロックV を生成する。次に、鍵なし疑似乱数生成手段２０２が、生成された復号ブロックV を用いて、ＣＬと等しい長さの疑似乱数R を生成し、ハッシュ手段２０３が、暗号学的ハッシュ関数を用いて、疑似乱数R とＣＬとの排他的論理和についてのハッシュ値を算出する。そして、平文出力手段２０４が、疑似乱数とＣＬとの排他的論理和ＭＬと、ハッシュ値と復号ブロックV との排他的論理和ＭＲとを連結した結果を復号結果の平文Ｍとして生成する。
【００８４】
そのため、重複排除付き暗号化装置１０により重複排除されて格納されたデータも正しく復号することが可能になる。
【００８５】
以下、具体例を用いて説明する。ユーザＡとユーザＢが独立に、同じm ブロックの平文Ｍについて暗号化を行ったとする。このとき、ユーザＡは、暗号文Ｃ＝（ＣＬ, ＣＲ）を得たとする。ただし、ＣＲは、1 ブロック、ＣＬは、m-1 ブロックである。また、ユーザＢは、暗号文Ｃ’＝（ＣＬ’, ＣＲ’）を得たとする。ただし、ＣＲ’は、1 ブロック、ＣＬ’は、m-1 ブロックである。この場合、ＣＬ＝ＣＬ’が満たされるため、サーバはm+1 ブロックのデータ（ＣＬ, ＣＲ, ＣＲ’）を保持すればよい。
【００８６】
そして、ユーザＡがサーバにアクセスしてきた場合、サーバは、（ＣＬ, ＣＲ）を返し、ユーザＢがサーバにアクセスしてきた場合、サーバは（ＣＬ, ＣＲ’）を返すことで、どちらのユーザも正しく平文Ｍを復号できる。
【００８７】
なお、本実施形態で用いられる暗号化方式は、例えば、非特許文献３に記載されたScramble All, Encrypt Small とよばれる暗号化方式と似ているとも言える。しかし、非特許文献３に記載された暗号化方式では、暗号化において、平文と独立な、nonce と呼ばれる乱数が用いられる。そのため、この方法では、平文がたとえ同じであっても暗号文が毎回変わるため、暗号文の重複排除は不可能である。
【００８８】
また、重複排除手段１０５が重複排除できる範囲は、暗号文全体より常に1 ブロック少なくなる。そのため、Convergent Encryption と比べた重複排除の効果はわずかに劣る。しかし、現実には平文のブロック長m は、ある程度大きいと考えられるため、効果の劣化は、無視できるレベルと言える。
【００８９】
例えば、平文の長さがHDD （Hard disk drive ）の標準的なセクタ長である4K(4096)byte、ブロック長が、共通鍵ブロック暗号の標準的なブロック長である16byteである場合、本実施形態における重複排除の効率は、16/4096=約0.4%しか低下しない。同様に、Convergent Encryption の場合では、4Kbyte単位の暗号化で約0.4%データが増えることになる。
【００９０】
両者は、割合としては同じだが、一般に重複排除は、大量の暗号化データのある一部分に対してのみ機能する。そのため、全体のデータ量の削減量を考えると、一般に本実施形態で用いられる重複削除の方が有利と言える。
【００９１】
したがって、本実施形態によれば、Convergent Encryption の課題である暗号化によるデータの増加と、データごとに鍵が生成されることを解消できる。
【００９２】
次に、本発明の概要を説明する。図８は、本発明による暗号化装置の概要を示すブロック図である。本発明の暗号化装置（例えば、重複排除付き暗号化装置１０）は、暗号化の対象となるn-bit 以上の平文（例えば、平文Ｍ）を、平文の右端のn-bit の固定長ブロックである右端ブロック（例えば、ＭＲ）と、平文から右端ブロックを除いたブロックである左ブロック（例えば、ＭＬ）とに分割する平文分割手段８１（例えば、ハッシュ手段１０１）と、暗号学的ハッシュ関数を用いて、左ブロックについてn-bit ハッシュ値（例えば、ハッシュ値S ）を算出する第一ハッシュ値算出手段８２（例えば、ハッシュ手段１０１）と、第一ハッシュ値算出手段８２が算出したハッシュ値と右端ブロックとの排他的論理和を入力ブロック（例えば、ブロックV ）として、左ブロックと等しい長さの疑似乱数（例えば、疑似乱数R ）を生成する暗号化用疑似乱数生成手段８３（例えば、鍵なし疑似乱数生成手段１０２）と、入力ブロックについて、秘密鍵を用いたn-bit 共通鍵ブロック暗号化を行うことで、暗号化されたn-bit のブロック暗号文（例えば、ＣＲ）を生成する共通鍵ブロック暗号化手段８４（例えば、共通鍵ブロック暗号化手段１０３）と、疑似乱数と左ブロックとの排他的論理和（例えば、ＣＬ）と、ブロック暗号文（例えば、ＣＲ）とを連結して暗号文（例えば、Ｃ）を生成する暗号文生成手段８５（例えば、暗号文出力手段１０４）と、（例えば、独立した秘密鍵を用いて）暗号文生成手段８５により生成された２つの暗号文（例えば、（ＣＬ, ＣＲ）, （ＣＬ’, ＣＲ’）。ただし、ＣＲとＣＲ’は右端のn-bit 固定長ブロック）における左ブロック（ＣＬとＣＬ’）のハッシュ値または実際の値を比較し、一致すると判断した場合に、２つの暗号文のうち一方の暗号文の左ブロックを削除する（すなわち、（ＣＬ, ＣＲ, ＣＲ’）を出力する）重複排除手段８６（例えば、重複排除手段１０５）とを備えている。
【００９３】
そのような構成により、複数のユーザがユーザごとに独立に生成した鍵を用いてデータの暗号化を行う場合に、暗号化されたデータが格納されるストレージ側でユーザが生成した鍵を知らなくても、データの重複排除を行うことができる。また、そのような構成により、鍵の暗号文と平文の暗号文とを対応付けて管理する手間も削減できる。
【００９４】
このとき、暗号化用疑似乱数生成手段８３は、入力ブロックを鍵として生成されるストリーム暗号、または、入力ブロックを入力として固定長入力および可変長出力のハッシュ関数から出力される結果を疑似乱数としてもよい。
【００９５】
また、図９は、本発明による復号装置の概要を示すブロック図である。本発明による復号装置（例えば、復号装置２０）は、復号の対象となるn-bit 以上の暗号文（例えば、暗号文Ｃ）を、その暗号文の右端のn-bit の固定長ブロックである暗号文右端ブロック（例えば、ＣＲ）と、暗号文から暗号文右端ブロックを除いたブロックである暗号文左ブロック（例えば、ＣＬ）とに分割する暗号文分割手段９１（例えば、共通鍵ブロック復号手段２０１）と、暗号文右端ブロックについて、秘密鍵を用いたn-bit 共通鍵ブロック暗号により復号を行うことで、復号された復号ブロック（例えば、ブロックV ）を生成する共通鍵ブロック復号手段９２（例えば、共通鍵ブロック復号手段２０１）と、共通鍵ブロック復号手段９２が生成した復号ブロックを用いて、暗号文左ブロックと等しい長さの疑似乱数を生成する復号用疑似乱数生成手段９３（例えば、鍵なし疑似乱数生成手段２０２）と、暗号学的ハッシュ関数を用いて、疑似乱数と暗号文左ブロックとの排他的論理和（例えば、ＭＬ）についてのハッシュ値を算出する第二ハッシュ値算出手段９４（例えば、ハッシュ手段２０３）と、疑似乱数と暗号文左ブロックとの排他的論理和（例えば、ＭＬ）と、ハッシュ値と復号ブロックとの排他的論理和（例えば、ＭＲ）とを連結した結果を復号結果の平文として生成する平文生成手段９５（例えば、平文出力手段２０４）とを備えている。
【００９６】
そのような構成により、例えば、図８に例示する暗号化装置により重複排除されて格納されたデータも正しく復号することが可能になる。
【００９７】
このとき、復号用疑似乱数生成手段９３は、復号ブロックを鍵として生成されるストリーム暗号、または、復号ブロックを入力として固定長入力および可変長出力のハッシュ関数から出力される結果を疑似乱数としてもよい。
【００９８】
また、上記の実施形態の一部又は全部は、以下の付記のようにも記載されうるが、以下には限られない。
【００９９】
（付記１）コンピュータに、暗号化の対象となるn-bit 以上の平文を、当該平文の右端のn-bit の固定長ブロックである右端ブロックと、前記平文から当該右端ブロックを除いたブロックである左ブロックとに分割する平文分割処理、暗号学的ハッシュ関数を用いて、前記左ブロックについてn-bit ハッシュ値を算出する第一ハッシュ値算出処理、前記第一ハッシュ値算出処理で算出されたハッシュ値と前記右端ブロックとの排他的論理和を入力ブロックとして、前記左ブロックと等しい長さの疑似乱数を生成する暗号化用疑似乱数生成処理、前記入力ブロックについて、秘密鍵を用いたn-bit 共通鍵ブロック暗号化を行うことで、暗号化されたn-bit のブロック暗号文を生成する共通鍵ブロック暗号化処理、前記疑似乱数と前記左ブロックとの排他的論理和と、前記ブロック暗号文とを連結して暗号文を生成する暗号文生成処理、および、前記暗号文生成処理で生成された２つの暗号文における左ブロックのハッシュ値または実際の値を比較し、一致すると判断した場合に、前記２つの暗号文のうち一方の暗号文の左ブロックを削除する重複排除処理を実行させるための暗号化プログラム。
【０１００】
（付記２）暗号化用疑似乱数生成処理で、入力ブロックを鍵として生成されるストリーム暗号、または、入力ブロックを入力として固定長入力および可変長出力のハッシュ関数から出力される結果を疑似乱数とさせる付記１記載の暗号化プログラム。
【０１０１】
（付記３）コンピュータに、復号の対象となるn-bit 以上の暗号文を、当該暗号文の右端のn-bit の固定長ブロックである暗号文右端ブロックと、前記暗号文から当該暗号文右端ブロックを除いたブロックである暗号文左ブロックとに分割する暗号文分割処理、前記暗号文右端ブロックについて、秘密鍵を用いたn-bit 共通鍵ブロック暗号により復号を行うことで、復号された復号ブロックを生成する共通鍵ブロック復号処理、前記共通鍵ブロック復号処理で生成された復号ブロックを用いて、前記暗号文左ブロックと等しい長さの疑似乱数を生成する復号用疑似乱数生成処理、暗号学的ハッシュ関数を用いて、前記疑似乱数と前記暗号文左ブロックとの排他的論理和についてのハッシュ値を算出する第二ハッシュ値算出処理、および、前記疑似乱数と前記暗号文左ブロックとの排他的論理和と、前記ハッシュ値と前記復号ブロックとの排他的論理和とを連結した結果を復号結果の平文として生成する平文生成処理を実行させるための復号プログラム。
【０１０２】
（付記４）復号用疑似乱数生成処理で、復号ブロックを鍵として生成されるストリーム暗号、または、復号ブロックを入力として固定長入力および可変長出力のハッシュ関数から出力される結果を疑似乱数とさせる付記３記載の復号プログラム。
【産業上の利用可能性】
【０１０３】
本発明は、共通鍵を用いて暗号化された暗号文の重複排除を行う暗号化装置に好適に適用される。例えば、無線もしくは有線のデータ通信における暗号化、データベースなどのストレージを保護するといった用途に本発明を適用できる。
【符号の説明】
【０１０４】
１０  重複排除付き暗号化装置
１１  暗号化部
１００  平文入力手段
１０１  ハッシュ手段
１０２  鍵なし疑似乱数生成手段
１０３  共通鍵ブロック暗号化手段
１０４  暗号文出力手段
１０５  重複排除手段
２０  復号装置
２００  暗号文入力手段
２０１  共通鍵ブロック復号手段
２０２  鍵なし疑似乱数生成手段
２０３  ハッシュ手段
２０４  平文出力手段
【図１】
2015022318.tif 000003
【図２】
2015022318.tif 000004
【図３】
2015022318.tif 000005
【図４】
2015022318.tif 000006
【図５】
2015022318.tif 000007
【図６】
2015022318.tif 000008
【図７】
2015022318.tif 000009
【図８】
2015022318.tif 000010
【図９】
2015022318.tif 000011
【図１０】
2015022318.tif 000012