(57)【要約】  乱数長を増加したり状態変数を導入することなく、乱数の衝突が起きたときの平文に関する情報漏洩の防止性能を向上することができる暗号化装置を提供すること。暗号化装置は、乱数を生成する乱数生成部と、入力された平文に対し、等長暗号化または加法的暗号化のいずれか一方を行って中間暗号文を生成する第１の暗号化部と、前記中間暗号文に対し、等長暗号化または加法的暗号化のうち、前記第１の暗号化部で行わなかった方の処理を行うことにより、暗号文を生成する第２の暗号化部と、前記暗号文および前記加法的暗号化に用いた乱数を出力する暗号文出力部と、を備える。（図３）
2012011455.tif 000002
【特許請求の範囲】
【請求項１】
乱数を生成する乱数生成部と、
入力された平文に対し、等長暗号化または加法的暗号化のいずれか一方を行って中間暗号文を生成する第１の暗号化部と、
前記中間暗号文に対し、等長暗号化または加法的暗号化のうち、前記第１の暗号化部で行わなかった方の処理を行うことにより、暗号文を生成する第２の暗号化部と、
前記暗号文および前記加法的暗号化に用いた乱数を出力する暗号文出力部と、
を備える暗号化装置。
【請求項２】
さらに、前記平文に対して前記乱数を用いてオフセット処理を行うことにより、中間平文を生成するオフセット処理部を備え、
前記第１の暗号化部にて、前記中間平文に対する等長暗号化を行い、前記第２の暗号化部にて、加法的暗号化を行う請求項１の暗号化装置。
【請求項３】
前記第１の暗号化部にて、加法的暗号化を行い、前記第２の暗号化部にて、等長暗号化を行う請求項１の暗号化装置。
【請求項４】
前記加法的暗号化として、ブロック暗号によるＸＯＲモードで加法的暗号化を実行する請求項１から３のいずれか一の暗号化装置。
【請求項５】
暗号文および乱数が入力される入力部と、
入力された暗号文に対し、等長復号または加法的復号のいずれか一方を行って中間暗号文を生成する第１の復号部と、
前記中間暗号文に対し、等長復号または加法的復号のうち、前記第１の復号部で行わなかった方の処理を行うことにより、平文を生成する第２の復号部と、
前記平文を出力する平文出力部と、
を備える復号装置。
【請求項６】
前記第１の復号部にて、加法的復号を行い、前記第２の復号部にて、前記中間暗号文に対して等長復号を行って中間平文を生成し、
さらに、前記中間平文に対して前記乱数を用いてオフセット処理を行うことにより、平文を生成するオフセット処理部を備える請求項５の復号装置。
【請求項７】
前記第１の復号部にて、等長復号を行い、前記第２の復号部にて、加法的復号を行う請求項５の復号装置。
【請求項８】
前記加法的復号として、ブロック暗号によるＸＯＲモードで加法的復号を実行する請求項５から７のいずれか一の復号装置。
【請求項９】
入力された平文に対し、等長暗号化または加法的暗号化のいずれか一方を行って中間暗号文を生成する第１の暗号化ステップと、
前記中間暗号文に対し、等長暗号化または加法的暗号化のうち、前記第１の暗号化部で行わなかった方の処理を行うことにより、暗号文を生成する第２の暗号化ステップと、
前記暗号文および前記加法的暗号化に用いた乱数を出力する暗号文出力ステップと、を含む暗号化方法。
【請求項１０】
入力された暗号文に対し、等長復号または加法的復号のいずれか一方を行って中間暗号文を生成する第１の復号ステップと、
前記中間暗号文に対し、等長復号または加法的復号のうち、前記第１の復号部で行わなかった方の処理を行うことにより、平文を生成する第２の復号ステップと、
前記平文を出力する平文出力ステップと、含む復号方法。
【発明の詳細な説明】
【技術分野】
【０００１】
（関連出願についての記載）
本発明は、日本国特許出願：特願２０１０−１６２７３５号（２０１０年７月２０日出願）の優先権主張に基づくものであり、同出願の全記載内容は引用をもって本書に組み込み記載されているものとする。
本発明は、共通鍵を用いた暗号化技術に関し、特に、共通鍵に加えて乱数を用いて暗号化を行う乱数付き暗号化による暗号化装置、復号装置、暗号化方法、復号方法、および、コンピュータ・プログラムに関する。
【背景技術】
【０００２】
共通鍵暗号の技術としては、乱数付き暗号化（Randomized Encryption, REnc）、状態変数付き暗号化（Stateful Encryption, SEnc）、および、決定的暗号化（Deterministic Encryption, DEnc）等が知られている。【０００３】
乱数付き暗号化とは、秘密に共通鍵を共有する暗号化装置および復号装置において、暗号化装置が、暗号化対象の平文ごとに乱数を生成し、生成した乱数および共通鍵を用いて平文を暗号化し、暗号文および乱数を復号装置に対して送信する技術である。これにより、乱数付き暗号化は、共通鍵を知らない第三者による盗聴を防ぐことができる。なお、以下では、共通鍵のことを単に鍵とも記載する。【０００４】
乱数付き暗号化では、暗号文Cは次式で表される。
C=Enc(K,M,U)
ここで、Mは平文、Kは鍵、Uは乱数、Encは暗号化関数を表す。また、暗号化装置は、暗号文Cおよび乱数Uを、通信路を通じて復号装置に送信する。【０００５】
状態変数付き暗号化とは、暗号化装置が、カウンター等の状態変数および共通鍵を用いて平文を暗号化し、暗号文および状態変数を復号装置に対して送信する技術である。【０００６】
決定的暗号化とは、暗号化装置が、平文と鍵以外の付加的情報を用いずに平文の暗号化を行う技術である。決定的暗号化では、メッセージ認証の機能を求めない場合には、平文と暗号文との長さを等しくすることが、冗長性排除の観点から望ましいとされる。この条件を満たす決定的暗号化は、等長暗号化（Length-Preserving Encryption, LPE）とも呼ばれる。【０００７】
等長暗号化として提案されている技術としては、例えば非特許文献１に記載のHCTRモードのように、ブロック暗号を利用したモードとして実現されるものがある。また、等長暗号化として提案されている他の技術としては、非特許文献２に記載されたMercyのように、単体のブロック暗号として一から構成されるものもある。【０００８】
このような等長暗号化の技術は、主としてストレージの暗号化に用いられる。ストレージの暗号化では、ハードディスクのセクタ等といったストレージの単位ごとに独立な暗号化が必要となることがある。このような場合に対応する等長暗号化の技術として、暗号化および復号の際に、平文および暗号文に加えて、tweakと呼ばれる付加的パラメータを用いるものがある。tweakとしては、例えば、ストレージの単位ごとに振られたアドレスが用いられる。【０００９】
このようなtweakを用いた等長暗号化は、Tweakable Enciphering Scheme（TES）と呼ばれる。非特許文献１に記載されたHCTRモードは、TESの一例である。TESは、等長暗号化を拡張した技術であり、TESにおいてtweakを固定することにより、等長暗号化が実現される。【００１０】
このようなTESの他の一例として、非特許文献３に記載されたHEHモードがある。HCTRモードやHEHモードでは、暗号化装置は、tweakをパラメータとする２つのユニバーサルハッシュ関数を用いて平文を暗号化する。ここで、ユニバーサルハッシュ関数は、任意の２入力に対応した２出力系列の衝突確率や差分確率のみを小さく保証する鍵付き関数である。【００１１】
また、非特許文献４には、並列処理可能なTESのモードとしてEMEモードが記載されている。【００１２】
また、非特許文献５には、tweakを持たないnビットブロック暗号からnビットのtweakableなブロック暗号を構成する技術が記載されている。【００１３】
なお、状態変数付き暗号化や乱数付き暗号化で用いられるカウンターや乱数は、初期ベクトル（Initial Vector, IV）とも呼ばれる。このため、状態変数付き暗号化および乱数付き暗号化は、総称してIVベース暗号化とも呼ばれる。【００１４】
また、状態変数を用いない乱数付き暗号化および決定的暗号化は、総称して状態変数無し暗号化（Stateless Encryption）とも呼ばれる。【００１５】
このような状態変数無し暗号化は、状態変数付き暗号化に対して、複数の暗号化装置が同じ鍵を非同期的に利用する場合や暗号化装置が状態を管理するための不揮発性メモリを有していない場合等でも使用可能である、というメリットを有する。【００１６】
このようなメリットを持つ乱数付き暗号化は、典型的には、加法的暗号化で実現される。加法的暗号化では、まず、nビット入力可変長出力の暗号化関数Fにnビット乱数Uを与えて平文Mと同じ長さの出力を得る。そして、暗号化関数Fの出力と、平文Mとの和をとることにより、暗号文を得る。ここで、和とは、排他的論理和（exclusive or, XOR）を意味する。【００１７】
このような加法的暗号化について、図１を参照して説明する。図１は、ブロック暗号によるXORモードで加法的暗号化を実現する例である。図１において、乱数Uはnビット長である。また、平文Mは、nビット長のL個のブロックM[1]〜M[L]によって構成される。nビット入力可変長出力の暗号化関数Fは、与えられた乱数Uを更新（１を算術加算）し、更新した乱数Uをnビットブロック暗号Ekに入力することにより実現される。そして、L個のnビットブロック暗号Ekの出力と、平文M[1]〜M[L]とが排他的論理和されることにより、暗号文C[1]〜C[L]が得られる。このような加法的暗号化については、例えば、特許文献１に記載されている。【００１８】
加法的暗号化による乱数付き暗号化は、簡素で効率がよい反面、もし、異なる２平文の暗号化において乱数が一致（以下、衝突ともいう）した場合、平文情報が漏洩する可能性があるという問題がある。【００１９】
これは、２つの暗号文C=Enc(M,U,K)=F(K,U)+Mと、C'=Enc(M',U',K)=F(K,U')+M'とにおいて、U=U'であれば、常にC+C'=M+M'が成立するためである。なお、“+”は、ビットごとの排他的論理和を指す。このことは、乱数衝突を観測した攻撃者は、対応する２平文の差分を知ることを意味する。一般的に、このような平文情報の漏洩は重大である。【００２０】
一方、加法的暗号化による状態変数付き暗号化では、状態変数を重複無く更新することにより常に暗号化関数Fへの入力がユニークとなり、上記の問題は回避される。【００２１】
加法的暗号化による乱数付き暗号化において、乱数衝突が起きる確率は、q個の平文について約q2/2nである。このため、2n/2個の平文について暗号化を行えば、約１回の乱数衝突が期待される。したがって、加法的暗号化による乱数付き暗号化では、q2/2nが無視できるほど小さくなるようにnを大きくとるか、qを小さくとる必要がある。すなわち、一つの鍵で処理する平文の数ｑを、2n/2より十分小さくする必要がある。なお、q2/2nは、nに関するバースデーバウンドと呼ばれる。【００２２】
ブロック暗号によるXORモードでは、nを大きくとる場合、使用するブロック暗号のブロックサイズを大きくする必要があり、一般的にはブロック暗号自体の変更を必要とする。これを不要とする技術が、非特許文献６に記載されているENCRXである。ENCRXは、nビット長の平文を暗号化する際に、2nビット長の乱数を必要としている。
【先行技術文献】
【特許文献】
【００２３】
【特許文献１】特開２００３−３２４４２４号公報
【非特許文献】
【００２４】
【非特許文献１】P. Wang, D. Feng, and W. Wu. HCTR: A Variable-Input-Length Enciphering Mode. Information Security and Cryptology, First SKLOIS Conference, CISC 2005, LNCS 3822, pp. 175-188, 2005.
【非特許文献２】P. Crowley. Mercy: A Fast Large Block Cipher for Disk Sector Encryption. Fast Software Encryption- FSE'00, LNCS 1978, pp. 49-63, 2000.
【非特許文献３】P. Sarkar. Improving Upon the TET Mode of Operation, K.-H. Nam and G. Rhee (Eds.): ICISC 2007, LNCS 4817, pp. 180-192, 2007.
【非特許文献４】S. Halevi and P. Rogaway. A Parallelizable Enciphering Mode, Proceeding of RSA Conference 2004, Cryptographer's Track, pp. 292-304.
【非特許文献５】M. Liskov, R. Rivest, D. Wagner, Tweakable Block Ciphers, Advances in Cryptology - CRYPTO 2002, 22nd Annual International Cryptology Conference, Santa Barbara, California, USA, August 18-22, 2002, Proceedings. Lecture Notes in Computer Science 2442 Springer 2002, pp. 31-46.
【非特許文献６】M. Bellare, O. Goldreich, and H. Krawczyk, Stateless evaluation of pseudorandom functions: Security beyond the birthday barrier, Advances in Cryptology - CRYPTO '99, 19th Annual International Cryptology Conference, Santa Barbara, California, USA, August 15-19, 1999, Proceedings. Lecture Notes in Computer Science 1666 Springer 1999, pp. 270-287.
【発明の概要】
【発明が解決しようとする課題】
【００２５】
なお、上記特許文献および非特許文献の各開示を、本書に引用をもって繰り込むものとする。
以下の分析は、本発明者によってなされたものである。
しかしながら、一般的な加法的暗号化による乱数付き暗号化では、上述のように、乱数衝突により平文の差分が漏洩する可能性が高いという課題があった。乱数長を伸ばすことや状態変数を導入することにより、この問題を解決することは可能である。しかしながら、そのような解決策は、通信メッセージのフォーマット変更、通信のオーバーヘッドの増加、あるいは暗号化デバイスの状態変数管理等、システム上の大きな変更を必要とする。このような変更は、システムの制約上不可能な場合もある。したがって、乱数長を伸ばすことや状態変数を導入することは、回避されることが望ましい。【００２６】
また、非特許文献６に記載されたものは、上述のように、乱数衝突による平文情報の漏洩の問題を解決するために、平文の長さの２倍の長さの乱数を必要とする。また、非特許文献６には、さらに長い平文を暗号化する技術については述べられていない。したがって、非特許文献６に記載されたENCRXを、長い平文に対して単純に適用すると、通信におけるオーバーヘッドが大きく増加するというデメリットがある。【００２７】
また、非特許文献１、３、４、５に記載されたものでは、TESをnビットブロック暗号で実現し、乱数をtweakとして用いることにより乱数付き暗号化を実現可能である。このようなTESによる乱数付き暗号化は、一見、乱数衝突による平文情報の漏洩の課題を回避しているように見える。【００２８】
しかしながら、一般に、TESをnビットブロック暗号で実現した場合、2n/2回程度の暗号化処理を行うと内部変数の衝突等により鍵の一部が漏洩することが知られている。このため、TESによる乱数付き暗号化においても、乱数衝突が期待されるほどの大量の暗号化を行った場合には、平文情報が漏洩する可能性が高い。したがって、乱数付き暗号化をTESを用いて実現することは、上述の課題の解決策とならない。【００２９】
本発明は、上述の課題を解決するためになされたもので、乱数付き暗号化において、乱数長を増加したり状態変数を導入することなく、乱数の衝突が起きたときの平文に関する情報漏洩の防止性能を向上することを目的とする。
【課題を解決するための手段】
【００３０】
本発明の第１の視点によれば、乱数を生成する乱数生成部と、入力された平文に対し、等長暗号化または加法的暗号化のいずれか一方を行って中間暗号文を生成する第１の暗号化部と、前記中間暗号文に対し、等長暗号化または加法的暗号化のうち、前記第１の暗号化部で行わなかった方の処理を行うことにより、暗号文を生成する第２の暗号化部と、前記暗号文および前記加法的暗号化に用いた乱数を出力する暗号文出力部と、を備える暗号化装置が提供される。【００３１】
本発明の第２の視点によれば、暗号文および乱数が入力される入力部と、入力された暗号文に対し、等長復号または加法的復号のいずれか一方を行って中間暗号文を生成する第１の復号部と、前記中間暗号文に対し、等長復号または加法的復号のうち、前記第１の復号部で行わなかった方の処理を行うことにより、平文を生成する第２の復号部と、前記平文を出力する平文出力部と、を備える復号装置が提供される。【００３２】
本発明の第３の視点によれば、入力された平文に対し、等長暗号化または加法的暗号化のいずれか一方を行って中間暗号文を生成する第１の暗号化ステップと、前記中間暗号文に対し、等長暗号化または加法的暗号化のうち、前記第１の暗号化部で行わなかった方の処理を行うことにより、暗号文を生成する第２の暗号化ステップと、前記暗号文および前記加法的暗号化に用いた乱数を出力する暗号文出力ステップと、を含む暗号化方法が提供される。本方法は、上述した各ステップを実施可能なコンピュータという、特定の機械に結びつけられている。【００３３】
本発明の第４の視点によれば、入力された暗号文に対し、等長復号または加法的復号のいずれか一方を行って中間暗号文を生成する第１の復号ステップと、前記中間暗号文に対し、等長復号または加法的復号のうち、前記第１の復号部で行わなかった方の処理を行うことにより、平文を生成する第２の復号ステップと、前記平文を出力する平文出力ステップと、含む復号方法が提供される。本方法は、上述した各ステップを実施可能なコンピュータという、特定の機械に結びつけられている。【００３４】
本発明の第５の視点によれば、入力された平文に対し、等長暗号化または加法的暗号化のいずれか一方を行って中間暗号文を生成する第１の暗号化処理と、前記中間暗号文に対し、等長暗号化または加法的暗号化のうち、前記第１の暗号化部で行わなかった方の処理を行うことにより、暗号文を生成する第２の暗号化処理と、前記暗号文および前記加法的暗号化に用いた乱数を出力する暗号文出力処理と、をコンピュータに実行させるプログラムが提供される。なお、このプログラムは、コンピュータが読み取り可能な記憶媒体に記録することができる。即ち、本発明は、コンピュータプログラム製品として具現することも可能である。【００３５】
本発明の第６の視点によれば、入力された暗号文に対し、等長復号または加法的復号のいずれか一方を行って中間暗号文を生成する第１の復号処理と、前記中間暗号文に対し、等長復号または加法的復号のうち、前記第１の復号部で行わなかった方の処理を行うことにより、平文を生成する第２の復号処理と、前記平文を出力する平文出力処理と、をコンピュータに実行させるプログラムが提供される。なお、このプログラムは、コンピュータが読み取り可能な記憶媒体に記録することができる。即ち、本発明は、コンピュータプログラム製品として具現することも可能である。
【発明の効果】
【００３６】
本発明は、乱数付き暗号化において、乱数長を増加したり状態変数を導入することなく、乱数の衝突が起きたときの平文に関する情報漏洩の防止性能を向上することができる暗号化装置および復号装置を提供することができる。
【図面の簡単な説明】
【００３７】
【図１】一般的な加法的暗号化を説明する図である。
【図２】本発明の第１の実施の形態としての暗号化装置のハードウェア構成を示すブロック図である。
【図３】本発明の第１の実施の形態としての暗号化装置の機能ブロック図である。
【図４】本発明の第１の実施の形態における等長暗号化部が用いるTESの構成を説明する図である。
【図５】本発明の第１の実施の形態としての暗号化装置の動作を説明するフローチャートである。
【図６】本発明の第２の実施の形態としての復号装置の機能ブロック図である。
【図７】本発明の第２の実施の形態としての復号装置の動作を説明するフローチャートである。
【図８】本発明の第３の実施の形態としての暗号化装置の機能ブロック図である。
【図９】本発明の第３の実施の形態としての暗号化装置の動作を説明するフローチャートである。
【図１０】本発明の第４の実施の形態としての復号装置の機能ブロック図である。
【図１１】本発明の第４の実施の形態としての復号装置の動作を説明するフローチャートである。
【発明を実施するための形態】
【００３８】
以下、本発明の実施の形態について、図面を参照して説明する。なお、以下では、とくに断りのない限り、“＋”は、ビットごとの排他的論理和を表すものとする。
【００３９】
（第１の実施の形態）
本発明の第１の実施の形態としての暗号化装置１０のハードウェア構成を図２に示す。図２において、暗号化装置１０は、ＣＰＵ（Central Processing Unit）１００１と、ＲＡＭ（Random Access Memory）１００２と、ＲＯＭ（Read Only Memory）１００３と、ハードディスク等の記憶装置１００４と、キーボード等の入力装置１００５と、ディスプレイ等の出力装置１００６と、ネットワークインタフェース１００７とを備えた汎用的なコンピュータ装置によって構成されている。
【００４０】
ＲＯＭ１００３および記憶装置１００４には、コンピュータ装置を暗号化装置１０として機能させるためのコンピュータ・プログラムが記憶されている。すなわち、ＣＰＵ１００１がＲＡＭ１００２を作業領域としてＲＯＭ１００３および記憶装置１００４に記憶されたコンピュータ・プログラムを実行することにより、コンピュータ装置は、暗号化装置１０として機能する。
【００４１】
次に、暗号化装置１０の機能ブロック構成について、図３を参照して説明する。
【００４２】
暗号化装置１０は、平文取得部（入力部）１００と、乱数生成部１０１と、オフセット処理部１０２と、等長暗号化部１０３と、加法的暗号化部１０４と、暗号文出力部１０５と、を備えている。なお、本実施形態では、等長暗号化部１０３が、第１の暗号化部に相当し、その後段にある加法的暗号化部１０４が、第２の暗号化部に相当する。
【００４３】
ここで、平文取得部１００は、入力装置１００５、および、コンピュータプログラムを実行するＣＰＵ１００１によって構成される。また、乱数生成部１０１、オフセット処理部１０２、等長暗号化部１０３および加法的暗号化部１０４は、コンピュータプログラムを実行するＣＰＵ１００１によって構成される。暗号文出力部１０５は、出力装置１００６、および、コンピュータプログラムを実行するＣＰＵ１００１によって構成される。
【００４４】
平文取得部１００は、暗号化の対象となる平文Mを取得する。平文取得部１００は、例えば、キーボード等の入力装置１００５を介して平文Mを取得してもよい。また、平文取得部１００は、平文Mを、記憶装置１００４から読み込むことにより取得してもよい。また、平文取得部１００は、平文Mを、ネットワークインタフェース１００７を介して受信することにより取得してもよい。
【００４５】
なお、図１は、平文Mの最小長がnビットの例を示しており、平文MがL個のnビットブロックM[1]〜M[L]に分割されて各部によって処理されることを示している。
【００４６】
乱数生成部１０１は、平文Mとは独立にnビットの乱数Uを生成する。乱数生成部１０１は、熱雑音等の物理現象を表す値に基づいて乱数Uを生成してもよい。また、乱数生成部１０１は、汎用的なコンピュータ装置に搭載されるＯＳ（Operating System）に付属するコンピュータ・プログラムを利用することにより、キーボード等の入力装置１００５を介して入力される情報を乱数発生用のソースとして乱数Uを生成してもよい。いずれにせよ、乱数生成部１０１は、十分高いエントロピーを持つ乱数Uを生成することが好ましい。
【００４７】
オフセット処理部１０２は、平文取得部１００によって取得された平文Mに対して、乱数生成部１０１によって生成された乱数Uを用いてオフセット処理を行うことにより、中間平文MMを生成する。
【００４８】
具体的には、オフセット処理部１０２は、平文Mおよび乱数Uのうち長さが短い方に対してゼロパディングを行うことにより平文Mおよび乱数Uの長さを等しくする。そののち、オフセット処理部１０２は、平文Mおよび乱数Uの排他的論理和を計算することにより中間平文MMを生成する。
【００４９】
すなわち、オフセット処理部１０２は、平文Mの最小長がnビットである場合には、平文Mの先頭nビットへ乱数Uを排他的論理和する。
【００５０】
なお、オフセット処理部１０２は、平文Mおよび乱数Uの長さを等しくした後、排他的論理和に限らず、算術加算等の群演算を行うことより中間平文MMを生成してもよい。
【００５１】
等長暗号化部１０３は、オフセット処理部１０２によって生成された中間平文MMに対して、長さを変えずに暗号化する等長暗号化を行うことにより、中間暗号文CCを生成する。等長暗号化部１０３は、等長暗号化においてカウンターや乱数等の初期ベクトルを用いない。
【００５２】
ここで、等長暗号化部１０３が用いる等長暗号化関数をLPE、鍵の空間をSetK、平文の空間をSetMとすると、等長暗号化関数LPEは定義域がSetK×SetM、値域がSetMの関数である。また、等長暗号化関数LPEは、LPE(K,M)の長さが常にMのそれと等しく、任意の固定された鍵KについてLPE(K,＊)がSetM上の置換となるものである（“×”は直積を表し、“＊”は任意の平文Mを表す）。
【００５３】
また、等長暗号化関数LPEは、選択平文攻撃に対して真のランダム置換と計算量的に識別困難な安全性を有することが好ましい。例えば、平文Mの長さが常にnビットの場合、等長暗号化関数LPEは、既存のnビットブロック暗号によって構成可能である。もし、平文Mの長さがnビット以上の可変値の場合、等長暗号化関数LPEは、ブロック暗号によるTESによって構成可能である。なお、この場合、TESにおけるtweakは任意の値に固定される。
【００５４】
等長暗号化関数LPEを実現するブロック暗号によるTESとしては、例えば、非特許文献１に記載のHCTRモード、非特許文献３に記載のHEHモード、あるいは非特許文献４に記載のEMEモード等を用いることができる。
【００５５】
また、等長暗号化部１０３は、選択平文攻撃に対する安全性を保証すればよい。このため、等長暗号化部１０３は、等長暗号化関数LPEをブロック暗号によるTESを用いて構成する場合、TESにおいて選択暗号文攻撃に対する安全性を保証する処理を省略することにより、処理を簡略化してもよい。
【００５６】
ここで、HCTRモードおよびHEHモード等の、ブロック暗号によるTESの大域的構成を図４に示す。ブロック暗号によるTESは、平文を第１のユニバーサルハッシュ関数によって処理した結果に対して、ブロック暗号ベースの暗号化を行い、さらに、第２のユニバーサルハッシュ関数によって処理した結果を暗号文として出力する。
【００５７】
等長暗号化部１０３は、図４における第２のユニバーサルハッシュ関数による処理を省略しても、選択平文攻撃への安全性を保つことができる。
【００５８】
例えば、特許文献３に記載のHEHモードは、tweakをτとしたとき、任意のτをパラメータとして逆関数が存在する２つのユニバーサルハッシュ関数ψτ,β1およびψ-1τ,β2を用いるものである。HEHモードは、ψτ,β1で平文Xを処理（ただし出力長は平文長と同じ）したのち、ブロック暗号のECBモードへ処理結果を与え、さらにψ-1τ,β2を適用して暗号文Yを求める。すなわち、HEHモードでは、平文X、tweakτに対する暗号文Yは、
Y=ψ-1τ,β2 (ECB(ψτ,β1 (X)))
と表される。
【００５９】
このとき、ψ-1τ,β2を省略しても、選択平文攻撃への安全性が保たれる。したがって、等長暗号化部１０３は、ユニバーサルハッシュ関数ψτ,β1およびECBモードの合成によって構成されてもよい。この場合、等長暗号化部１０３は、次式によって中間平文MMから中間暗号文CCを生成する。
CC＝ECB(ψτ,β1(MM))
なお、等長暗号化部１０３は、ブロック暗号によるTESに限らず、等長暗号化を行うその他の技術を用いて実現されてもよい。
【００６０】
加法的暗号化部１０４は、乱数Uを用いて中間暗号文CCに対する加法的暗号化を行うことにより、暗号文Cを生成する。
【００６１】
例えば、加法的暗号化部１０４は、ブロック暗号によるXORモードに基づく処理を実行するよう構成されていてもよい。この場合、加法的暗号化部１０４は、乱数生成部１０１によって生成される乱数Uを初期ベクトルとして、中間暗号文CCと同じ長さの疑似乱数系列を生成する。そして、加法的暗号化部１０４は、疑似乱数系列と中間暗号文CCとの排他的論理和をとることで暗号文Cを生成する。生成される暗号文Cは次式で表される。なお、Fは、nビット入力可変長出力の疑似ランダム関数PRFを表し、KEは鍵を表す。
C=F(KE,U)+CC
ここで、疑似ランダム関数PRFは、図１に示したような、nビットブロック暗号EのXORモードによって構成してもよい。この場合、加法的暗号化部１０４は、中間暗号文CCがnビットごとに分割されたCC[1],CC[2],...,CC[L]について、
C[i]=E(KE,inc(U,i-1))+CC[i]
をi=1,...,Lについて求め、C[1],...,C[L]を連結することにより暗号文Cを生成する。なお、inc(A,B)はA,Bを整数とみたAとBの算術加算（mod・2n)を表す。ここで、inc(U,i+1)=inc(inc(U,i))であるため、加法的暗号化部１０４は、図１のようにUを逐次更新（１の算術加算）しながら暗号化してもよい。
【００６２】
なお、加法的暗号化部１０４は、ブロック暗号によるXORモードに限らず、その他の加法的暗号化の技術によって実現されてもよい。例えば、加法的暗号化部１０４は、初期ベクトルを持つストリーム暗号を疑似ランダム関数PRFとして用いて構成されていてもよい。
【００６３】
暗号文出力部１０５は、乱数生成部１０１によって生成される乱数Uと、加法的暗号化部１０４によって生成される暗号文Cを、出力装置１００６に出力する。なお、暗号文出力部１０５は、暗号文Cおよび乱数Uを、記憶装置１００４に記憶することにより出力してもよい。また、暗号文出力部１０５は、暗号文Cおよび乱数Uを、ネットワークインタフェース１００７を介して送信することにより出力してもよい。
【００６４】
以上のように構成された暗号化装置１０の動作について、図５を参照して説明する。
【００６５】
まず、平文取得部１００は、平文Mを取得する（ステップＳ１）。
【００６６】
次に、乱数生成部１０１は、nビットの乱数Uを生成する（ステップＳ２）。
【００６７】
次に、オフセット処理部１０２は、平文Mに対して、乱数Uを用いてオフセット処理を行うことにより、中間平文MMを生成する（ステップＳ３）。
【００６８】
次に、等長暗号化部１０３は、中間平文MMに対して等長暗号化を行うことにより、中間暗号文CCを生成する（ステップＳ４）。
【００６９】
次に、加法的暗号化部１０４は、中間暗号文CCに対して乱数Uを用いて加法的暗号化を行うことにより、暗号文Cを生成する（ステップＳ５）。
【００７０】
次に、暗号文出力部１０５は、暗号文Cおよび乱数Uを出力する（ステップＳ６）。
【００７１】
以上で、暗号化装置１０は動作を終了する。
【００７２】
なお、上述の説明において、平文Mの長さがnビット以上であるものとしているが、平文Mの長さがnビットより短い場合、暗号化装置１０は、パディング処理等により平文Mの長さをnビット以上とすればよい。例えば、平文取得部１００が、nビットより短い平文Mに対してパディング処理を行うことにより、平文Mの最小長nビットを保証するようにしてもよい。
【００７３】
次に、本発明の第１の実施の形態の効果について述べる。
【００７４】
本発明の第１の実施の形態としての暗号化装置は、乱数付き暗号化において、乱数長を増加したり状態変数を導入することなく、乱数の衝突が起きたときの平文に関する情報漏洩の防止性能を向上することができる。
【００７５】
その理由は、暗号化装置が、平文を等長暗号化した中間暗号文に対して加法的暗号化を行うため、乱数の衝突がおきた場合にも、暗号文の差分から知られるのは中間暗号文の差分でしかない。したがって、乱数の衝突がおきた場合にも、対応する２つの平文がまったく同じ情報でない限り、暗号文同士が重複しない乱数となり、攻撃者には、「２つの平文が異なる」という情報以外に知られないためである。
【００７６】
一方、一般的な加法的暗号化による乱数付き暗号化の場合、乱数の衝突がおきたときには、２つの平文の差分が、暗号文の差分から知られるという重大な情報漏洩が起きる。
【００７７】
なお、もし乱数衝突において対応する２つの平文がまったく同じ場合には、本発明の実施の形態としての暗号化装置でも、「２つの平文が同じ」という情報が攻撃者に知られる。
【００７８】
しかしながら、これは、あらゆる乱数付き暗号化における不可避の事象である。したがって、本発明の第１の実施の形態としての暗号化装置は、一般的な加法的暗号化による乱数付き暗号化の安全性の課題を、同じ乱数長のままで状態変数を導入することなく可能な限り改善することができる。
【００７９】
形式的には、乱数付き暗号化の安全性は、乱数をtweakとして用いた理想的なTESとの計算量的判別困難性において計ることが可能である。理想的なTESとの計算量的判別困難性は、暗号化の回数等の関数で表現される。計算量的判別困難性は、0に近いほど、安全であることを意味し、１に近いほど、危険であることを意味する。また、暗号化の回数に対して、計算量的判別困難性が１に近づく速度が遅いほど、安全であるといえる。
【００８０】
暗号化の回数をq、乱数長をnとした場合、一般的な加法的暗号化による乱数付き暗号化は、この計算量的判別困難性という指標においてO(q2/2n)である。
【００８１】
また、非特許文献１に記載のHCTRモード、非特許文献３に記載のHEHモード、または非特許文献４に記載のEMEモード等のTESでnビットブロック暗号を用いた乱数付き暗号化も、tweakを乱数とした理想的なTESとの計算量的判別困難性においてO(q2/2n)である。したがって、nビットブロック暗号によるTESを用いた乱数付き暗号化の安全性は、一般的な加法的暗号化による乱数付き暗号化と同等となる。
【００８２】
一方、本発明の第１の実施の形態における加法的暗号化部をnビットブロック暗号によるXORモードで実現し、等長暗号化部を同じくnビットブロック暗号によるTESで実現した（ただしtweakは任意の固定値）場合、平文の最小長がｎビットであれば、上述の計算量的判別困難性においてO(q4/23n)程度を達成する。O(q4/23n)は、O(q2/2n)と比べてqに対する増加のスピードが大幅に遅い。
【００８３】
したがって、理論的な意味でも、本発明の第１の実施の形態としての暗号化装置による乱数付き暗号化は、一般的な加法的暗号化による乱数付き暗号化およびnビットブロック暗号によるTESを用いた乱数付き暗号化に比べてより高い安全性を持つといえる。
【００８４】
また、本発明の第１の実施の形態としての暗号化装置は、乱数の衝突が起きたときの平文に関する情報漏洩の防止性能を向上する暗号化処理を、より効率的に実行することができる。
【００８５】
その理由は、本発明の第１の実施の形態としての暗号化装置において、等長暗号化部が実行する処理および加法的暗号化部が実行する処理を並列に実行可能なためである。具体的には、例えば、加法的暗号化部がブロック暗号によるXORモードに基づく処理を実行する場合、暗号化装置は、等長暗号化部が中間平文に対する等長暗号化処理を実行するのと並列に、加法的暗号化部が疑似乱数系列を生成する処理を実行することができるからである。
【００８６】
なお、本発明の第１の実施の形態としての暗号化装置１０は、オフセット処理部１０２を有していなくてもよい。その場合、等長暗号化部１０３は、平文取得部１００からの出力である平文Mに対して上述の等長暗号化を行えばよい。
【００８７】
このように構成された暗号化装置１０も、上述の効果を奏することができる。
【００８８】
しかしながら、本実施の形態としての暗号化装置は、オフセット処理部を有することにより、乱数の衝突が起きたときの平文に関する情報漏洩の防止性能をさらに向上することができる。
【００８９】
その理由について、４つの同じ長さの平文M1, M2, M3, M4 を暗号化する場合を例に説明する。平文M1, M2, M3, M4が、M1 = M2, M3 = M4 (M1 ≠ M3)という条件を満たし、これらを暗号化するのに用いる乱数U1, U2, U3, U4が、U1 = U2、および、U3 = U4 (U1 ≠ U3)という条件を満たす場合、C1 = C2, C3 = C4 となる。
【００９０】
このために、平文を知らない攻撃者にもM1 = M2, M3 = M4であるという情報が漏洩する。このとき、等長暗号化処理の前にオフセット処理を実行していないと、C1+C3 = C2+C4となることから、平文M1およびM3の差分が平文M2および平文M4の差分に等しいという情報がさらに漏洩する。
【００９１】
一方、本発明の第１の実施の形態としての暗号化装置が、上述の条件を満たす平文M1, M2, M3, M4および乱数U1, U2, U3, U4を用いて暗号化を行う場合について考える。この場合、オフセット処理部を有することにより、C1+C3 = C2+C4であることから漏洩するのは、中間平文MM1およびMM3の差分が中間平文MM2およびMM4の差分に等しいという情報に過ぎない。したがって、本発明の実施の形態としての暗号化装置は、オフセット処理部を有することにより、乱数の衝突が起きたときの平文に関する情報漏洩の防止性能をさらに向上することができる。
【００９２】
（第２の実施の形態）
次に、本発明の第２の実施の形態について図面を参照して詳細に説明する。本発明の第２の実施の形態としての復号装置２０は、本発明の第１の実施の形態としての暗号化装置１０によって暗号化された暗号文を復号する装置である。
【００９３】
復号装置２０は、本発明の第１の実施の形態としての暗号化装置１０と同様に、図２に示したハードウェア構成を備えた汎用的なコンピュータ装置によって構成されている。
【００９４】
ＲＯＭ１００３および記憶装置１００４には、コンピュータ装置を復号装置２０として機能させるためのコンピュータ・プログラムが記憶されている。すなわち、ＣＰＵ１００１がＲＡＭ１００２を作業領域としてＲＯＭ１００３および記憶装置１００４に記憶されたコンピュータ・プログラムを実行することにより、コンピュータ装置は、復号装置２０として機能する。
【００９５】
次に、復号装置２０の機能ブロック構成について、図６を参照して説明する。図６において、復号装置２０は、暗号文取得部２００と、加法的復号部２０４と、等長復号部２０３と、オフセット処理部２０２と、平文出力部２０５とを備えている。なお、本実施形態では、加法的復号部２０４が、第１の復号部に相当し、その後段にある等長復号部２０３が、第２の復号部に相当する。
【００９６】
ここで、暗号文取得部２００は、記憶装置１００４、および、コンピュータ・プログラムを実行するＣＰＵ１００１によって構成される。また、加法的復号部２０４、等長復号部２０３およびオフセット処理部２０２は、コンピュータ・プログラムを実行するＣＰＵ１００１によって構成される。平文出力部２０５は、出力装置１００６、および、コンピュータ・プログラムを実行するＣＰＵ１００１によって構成される。
【００９７】
暗号文取得部２００は、復号の対象となる暗号文Cおよび乱数Uを取得する。例えば、暗号文取得部２００は、記憶装置１００４に記憶された暗号文Cおよび乱数Uを取得してもよい。また、暗号文取得部２００は、暗号文Cおよび乱数Uを、ネットワークインタフェース１００７を介して受信することにより取得してもよい。
【００９８】
加法的復号部２０４は、乱数Uを用いて暗号文Cの加法的復号を行うことにより、中間暗号文CCを取得する。例えば、加法的復号部２０４は、ブロック暗号によるXORモードに基づく処理を実行するよう構成されていてもよい。この場合、加法的復号部２０４は、本発明の第１の実施の形態における加法的暗号化部１０４に対して、中間暗号文CCを入力として暗号文Cを出力とする代わりに、暗号文Cを入力として中間暗号文CCを出力とする点が異なる以外は、加法的暗号化部１０４と同様に構成される。すなわち、加法的復号部２０４は、暗号文Cに対する中間暗号文CCを次式によって求める。
CC= F(KE,U)+C
等長復号部２０３は、加法的復号部２０４によって取得された中間暗号文CCに対する等長復号を行うことにより、中間暗号文と同じ長さの中間平文MMを取得する。
【００９９】
例えば、等長復号部２０３は、ブロック暗号によるTESに基づく処理を実行するよう構成されていてもよい。例えば、等長復号部２０３を、非特許文献３に記載のHEHモードで構成する場合、中間暗号文CCに対する中間平文MMは次式で表される。
MM=ψ-1τ,β１ (ECB-1(ψτ,β２(CC)))
もし、本発明の第１の実施の形態としての暗号化装置１０の等長暗号化部１０３が、第２のユニバーサルハッシュ関数の処理を省略している場合、等長復号部２０３は、中間暗号文CCに対する中間平文MMを、次式によって求める。
MM=ψ-1τ,β１ (ECB-1(CC))
オフセット処理部２０２は、等長復号部２０３によって取得された中間平文MMに対して乱数Uを用いてオフセット処理を行うことにより、平文Mを取得する。オフセット処理部２０２は、本発明の第１の実施の形態におけるオフセット処理部１０２に対して、平文Mを入力として中間平文MMを出力とする代わりに、中間平文MMを入力として平文Mを出力とする点が異なる以外は、オフセット処理部１０２と同様に構成される。
【０１００】
平文出力部２０５は、オフセット処理部２０２によって取得された平文Mを、出力装置１００６に出力する。なお、平文出力部２０５は、平文Mを、記憶装置１００４に記憶することにより出力してもよい。また、平文出力部２０５は、平文Mを、ネットワークインタフェース１００７を介して送信することにより出力してもよい。
【０１０１】
以上のように構成された復号装置２０の動作について、図７を参照して説明する。
【０１０２】
まず、暗号文取得部２００は、復号の対象となる暗号文Cおよび乱数Uを取得する（ステップＳ１１）。
【０１０３】
次に、加法的復号部２０４は、乱数Uを用いて、暗号文Cの加法的復号を行うことにより、中間暗号文CCを取得する（ステップＳ１２）。
【０１０４】
次に、等長復号部２０３は、中間暗号文CCに対する等長復号を行うことにより、中間暗号文CCと同じ長さの中間平文MMを生成する（ステップＳ１３）。
【０１０５】
次に、オフセット処理部２０２は、中間平文MMに対して、乱数Uを用いてオフセット処理を行うことにより、平文Mを生成する（ステップＳ１４）。
【０１０６】
次に、平文出力部２０５は、平文Mを出力する（ステップＳ１５）。
【０１０７】
以上で、復号装置２０は動作を終了する。
【０１０８】
次に、本発明の第２の実施の形態の効果について述べる。
【０１０９】
本発明の第２の実施の形態としての復号装置は、乱数付き暗号化において、乱数長を増加したり状態変数を導入することなく、乱数の衝突が起きたときの平文に関する情報漏洩の防止性能を向上するよう暗号化された暗号文を復号することができる。
【０１１０】
その理由は、取得した暗号文に対して乱数を用いた加法的復号を行うだけでなく、加法的復号を行った結果の中間平文に対して等長復号を行うことにより平文を取得するからである。
【０１１１】
なお、本発明の第２の実施の形態としての復号装置２０は、本発明の第１の実施の形態としての暗号化装置１０がオフセット処理部１０２を有していない場合、オフセット処理部２０２を有していなくてもよい。その場合、平文出力部２０５は、等長復号部２０３からの出力を平文Mとして出力すればよい。
【０１１２】
（第３の実施の形態）
次に、本発明の第３の実施の形態について、図面を参照して詳細に説明する。
【０１１３】
本発明の第３の実施の形態としての暗号化装置３０は、本発明の第１の実施の形態としての暗号化装置１０と同様に、図２に示したハードウェア構成を備える汎用的なコンピュータ装置によって構成されている。
【０１１４】
ＲＯＭ１００３および記憶装置１００４には、コンピュータ装置を暗号化装置３０として機能させるためのコンピュータ・プログラムが記憶されている。すなわち、ＣＰＵ１００１がＲＡＭ１００２を作業領域としてＲＯＭ１００３および記憶装置１００４に記憶されたコンピュータ・プログラムを実行することにより、コンピュータ装置は、暗号化装置３０として機能する。
【０１１５】
次に、暗号化装置３０の機能ブロック構成について、図８を参照して説明する。なお、図８において、本発明の第１の実施の形態と同一の構成には同一の符号を付して本実施の形態における詳細な説明を省略する。暗号化装置３０は、平文取得部１００と、乱数生成部１０１と、加法的暗号化部３０４と、等長暗号化部３０３と、暗号文出力部１０５と、を備えている。なお、本実施形態では、加法的暗号化部３０４が、第１の暗号化部に相当し、その後段にある等長暗号化部３０３が、第２の暗号化部に相当する。
【０１１６】
ここで、加法的暗号化部３０４および等長暗号化部３０３は、コンピュータ・プログラムを実行するＣＰＵ１００１によって構成される。
【０１１７】
平文取得部１００は、本発明の第１の実施の形態と同様に構成されるが、安全性の観点から、乱数生成部１０１によって生成される乱数Uの長さがnビットのとき、２nビット以上の長さの平文Mを取得するのが好ましい。
【０１１８】
例えば、平文取得部１００は、平文Mの長さが2nビットより短い場合、パディング処理等を行うことにより、平文Mの最小長2nビットを保証するようにしてもよい。
【０１１９】
加法的暗号化部３０４は、乱数Uを用いて平文Mに対する加法的暗号化を行うことにより、中間平文MMを生成する。
【０１２０】
加法的暗号化部３０４は、本発明の第１の実施の形態における加法的暗号化部１０４に対して、中間暗号文CCを入力として暗号文Cを出力する代わりに、平文Mを入力として中間平文MMを出力する点が異なる以外は、加法的暗号化部１０４と同様に構成される。
【０１２１】
例えば、加法的暗号化部３０４は、乱数生成部１０１によって生成される乱数Uを初期ベクトルとして、平文取得部１００により取得された平文Mと同じ長さの疑似乱数系列を生成する。そして、加法的暗号化部３０４は、生成した疑似乱数系列と平文Mとの排他的論理和をとることで中間平文MMを生成してもよい。すなわち、加法的暗号化部３０４は、ブロック暗号によるXORモードに基づく処理を実行するよう構成されてもよい。
【０１２２】
なお、非特許文献６に記載のTweakable blockcipherでは、加法的暗号化に用いる暗号化関数に相当する処理として、ユニバーサルハッシュ関数を用いている。
【０１２３】
これに対して、加法的暗号化部３０４は、理論的安全性保証のために、暗号として十分な安全性を持った暗号化関数を用いることが好ましい。例えば、加法的暗号化部３０４は、ユニバーサルハッシュ関数で頻繁に用いられるガロア体上の乗算等を用いないことが好ましい。
【０１２４】
等長暗号化部３０３は、加法的暗号化部３０４によって生成された中間平文MMを、長さを変えずに暗号化することにより暗号文Cを生成する。
【０１２５】
また、等長暗号化部３０３は、本発明の第１の実施の形態における等長暗号化部１０３に対して、中間平文MMを入力として中間暗号文CCを出力する代わりに、中間平文MMを入力として暗号文Cを出力する点が異なる以外は、等長暗号化部１０３と同様に構成される。
【０１２６】
以上のように構成された暗号化装置３０の動作について図９を参照して説明する。
【０１２７】
まず、平文取得部１００は、暗号化対象の平文Mを取得する（ステップＳ２１）。
【０１２８】
次に、乱数生成部１０１は、nビットの乱数Uを生成する（ステップＳ２２）。
【０１２９】
次に、加法的暗号化部３０４は、平文Mに対して乱数Uを用いて加法的暗号化を行うことにより中間平文MMを生成する（ステップＳ２３）。
【０１３０】
次に、等長暗号化部３０３は、中間平文MMを等長暗号化することにより暗号文Cを生成する（ステップＳ２４）。
【０１３１】
次に、暗号文出力部１０５は、暗号文Cおよび乱数Uを出力する（ステップＳ２５）。
【０１３２】
以上で、暗号化装置３０は動作を終了する。
【０１３３】
次に、本発明の第３の実施の形態の効果について述べる。
【０１３４】
本発明の第３の実施の形態としての暗号化装置は、乱数付き暗号化において、乱数長を増加したり状態変数を導入することなく、乱数の衝突が起きたときの平文に関する情報漏洩の防止性能を向上することができる。
【０１３５】
その理由は、本発明の第３の実施の形態としての暗号化装置は、平文の最小長が2nビットの場合、計算量的判別困難性においてO(q2/22n)程度となり、本発明の第１の実施の形態に対して、さらに安全性を向上できるからである。
【０１３６】
なお、平文の最小長がnビットの場合、本発明の第３の実施の形態としての暗号化装置は、計算量的判別困難性においてO(q4/22n)となる。このため、本発明の第３の実施の形態としての暗号化装置は、平文の最小長がnビットの場合、本発明の第１の実施の形態ほどではないが、一般的な加法的暗号化による乱数付き暗号化やTESを用いた乱数付き暗号化に対して、より安全性を高めることができる。
【０１３７】
（第４の実施の形態）
次に、本発明の第４の実施の形態について、図面を参照して詳細に説明する。
【０１３８】
本発明の第４の実施の形態としての復号装置４０は、本発明の第３の実施の形態としての暗号化装置３０によって暗号化された暗号文を復号する装置である。
【０１３９】
復号装置４０は、本発明の第１の実施の形態としての暗号化装置１０と同様に、図２に示すハードウェア構成を備えた汎用的なコンピュータ装置によって構成されている。
【０１４０】
ＲＯＭ１００３および記憶装置１００４には、コンピュータ装置を復号装置４０として機能させるためのコンピュータ・プログラムが記憶されている。すなわち、ＣＰＵ１００１がＲＡＭ１００２を作業領域としてＲＯＭ１００３および記憶装置１００４に記憶されたコンピュータ・プログラムを実行することにより、コンピュータ装置は、復号装置４０として機能する。
【０１４１】
次に、復号装置４０の機能ブロック構成について、図１０を参照して説明する。なお、図１０において、本発明の第２の実施の形態と同一の構成には同一の符号を付して本実施の形態における詳細な説明を省略する。図１０において、復号装置４０は、暗号文取得部２００と、等長復号部４０３と、加法的復号部４０４と、平文出力部２０５と、を備えている。なお、本実施形態では、等長復号部４０３が、第１の復号部に相当し、その後段にある加法的復号部４０４が、第２の復号部に相当する。
【０１４２】
ここで、等長復号部４０３および加法的復号部４０４は、コンピュータ・プログラムを実行するＣＰＵ１００１によって構成される。
【０１４３】
等長復号部４０３は、暗号文取得部２００によって取得された暗号文Cに対する等長復号を行うことにより、暗号文Cと同じ長さの中間平文MMを取得する。
【０１４４】
また、等長復号部４０３は、本発明の第２の実施の形態における等長復号部２０３に対して、中間暗号文CCを入力として中間平文MMを出力する代わりに、暗号文Cを入力として中間平文MMを出力する点が異なる以外は、等長復号部２０３と同様に構成される。
【０１４５】
加法的復号部４０４は、暗号文取得部２００によって取得された乱数Uを用いて、等長復号部２０３によって取得された中間平文MMに対する加法的復号を行うことにより平文Mを取得する。
【０１４６】
また、加法的復号部４０４は、本発明の第２の実施の形態における加法的復号部２０４に対して、暗号文Cを入力として中間暗号文CCを出力する代わりに、中間平文MMを入力として平文Mを出力する点が異なる以外は、加法的復号部２０４と同様に構成される。
【０１４７】
以上のように構成された復号装置４０の動作について、図１１を参照して説明する。
【０１４８】
まず、暗号文取得部２００は、暗号文Cおよび乱数Uを取得する（ステップＳ３１）。
【０１４９】
次に、等長復号部４０３は、暗号文Cに対する等長復号を行うことにより、暗号文Cと同じ長さの中間平文MMを取得する（ステップＳ３２）。
【０１５０】
次に、加法的復号部４０４は、乱数Uを用いて、中間平文MMに対する加法的復号を行うことにより平文Mを取得する（ステップＳ３３）。
【０１５１】
次に、平文出力部２０５は、平文Mを出力する（ステップＳ３４）。
【０１５２】
以上で、復号装置４０は動作を終了する。
【０１５３】
次に、本発明の第４の実施の形態の効果について述べる。
【０１５４】
本発明の第４の実施の形態としての復号装置は、乱数付き暗号化において、乱数長を増加したり状態変数を導入することなく、乱数の衝突が起きたときの平文に関する情報漏洩の防止性能をさらに高めた暗号文を復号することができる。
【０１５５】
その理由は、取得した暗号文に対してまず等長復号を行うことにより中間平文を取得し、取得した中間平文に対して乱数を用いて加法的復号を行うことにより、平文を取得するからである。
【０１５６】
また、本発明の第４の実施の形態としての復号装置は、乱数の衝突が起きたときの平文に関する情報漏洩の防止性能をさらに高めた暗号文の復号処理をより効率的に実行することができる。
【０１５７】
その理由は、本発明の第４の実施の形態としての復号装置において、等長復号部が実行する処理および加法的復号部が実行する処理を並列に実行可能なためである。具体的には、例えば、加法的復号部がブロック暗号によるXORモードに基づく処理を実行する場合、復号装置は、等長復号部によって暗号文に対する等長復号処理を実行する処理と並列に、加法的復号部によって疑似乱数系列を生成する処理を実行することができるからである。
【０１５８】
なお、上述した本発明の各実施の形態において、等長暗号化部および加法的暗号化部は、互いに独立した鍵を用いることが好ましいが、同一の鍵を流用することも可能である。
【０１５９】
なお、上述した本発明の各実施の形態において、各フローチャートを参照して説明した暗号化装置および復号装置の動作を、本発明のコンピュータ・プログラムとして暗号化装置および復号装置の記憶装置（記憶媒体）に格納しておき、係るコンピュータ・プログラムを当該ＣＰＵが読み出して実行するようにしてもよい。そして、このような場合において、本発明は、係るコンピュータ・プログラムのコード或いは記憶媒体によって構成される。
【０１６０】
また、上述した各実施の形態は、適宜組み合わせて実施されることが可能である。
【０１６１】
また、本発明は、上述した各実施の形態に限定されず、様々な態様で実施されることが可能である。
【０１６２】
また、上記の実施形態の一部又は全部は、以下の付記のようにも記載されうるが、以下には限られない。
（付記１）
平文を取得する平文取得部と、
乱数を生成する乱数生成部と、
前記平文に対する等長暗号化を行うことにより、前記平文と同じ長さの中間暗号文を生成する等長暗号化部と、
前記乱数を用いて前記中間暗号文に対する加法的暗号化を行うことにより、暗号文を生成する加法的暗号化部と、
前記暗号文および前記乱数を出力する暗号文出力部と、
を備えた暗号化装置。
（付記２）
暗号文および乱数を取得する暗号文取得部と、
前記乱数を用いて前記暗号文の加法的復号を行うことにより、中間暗号文を取得する加法的復号部と、
前記中間暗号文に対する等長復号を行うことにより、前記中間暗号文と同じ長さの平文を取得する等長復号部と、
前記平文を出力する平文出力部と、
を備えた復号装置。
（付記３）
前記平文に対して前記乱数を用いてオフセット処理を行うことにより、中間平文を生成するオフセット処理部をさらに備え、
前記等長暗号化部は、前記中間平文に対する等長暗号化を行うことにより、前記中間暗号文を生成することを特徴とする付記１に記載の暗号化装置。
（付記４）
前記等長復号部は、前記中間暗号文に対して等長復号を行ったものを中間平文として取得し、
前記中間平文に対して前記乱数を用いてオフセット処理を行うことにより、前記平文を取得するオフセット処理部をさらに備えることを特徴とする付記２に記載の復号装置。
（付記５）
平文を取得する平文取得部と、
乱数を生成する乱数生成部と、
前記乱数を用いて前記平文に対する加法的暗号化を行うことにより、中間平文を生成する加法的暗号化部と、
前記中間平文に対する等長暗号化を行うことにより、前記中間平文と同じ長さの暗号文を生成する等長暗号化部と、
前記暗号文および前記乱数を出力する暗号文出力部と、
を備えた暗号化装置。
（付記６）
暗号文および乱数を取得する暗号文取得部と、
前記暗号文に対する等長復号を行うことにより、前記暗号文と同じ長さの中間平文を取得する等長復号部と、
前記乱数を用いて前記中間平文に対する加法的復号を行うことにより平文を取得する加法的復号部と、
前記平文を出力する平文出力部と、
を備えた復号装置。
（付記７）
前記加法的暗号化部は、ブロック暗号によるXORモードで前記加法的暗号化を実行することを特徴とする付記１、付記３および付記５のいずれかに記載の暗号化装置。
（付記８）
前記加法的復号部は、ブロック暗号によるXORモードで前記加法的復号を実行することを特徴とする付記２、付記４および付記６のいずれかに記載の復号装置。
（付記９）
前記等長暗号化部は、ブロック暗号によるＴＥＳ（Tweakable Enciphering Scheme）に基づき前記等長暗号化を実行することを特徴とする付記１、付記３、付記５および付記７のいずれかに記載の暗号化装置。
（付記１０）
前記等長復号部は、ブロック暗号によるＴＥＳに基づき前記等長復号を実行することを特徴とする付記２、付記４、付記６および付記８のいずれかに記載の復号装置。
（付記１１）
暗号化装置が、
平文を取得し、
乱数を生成し、
前記平文に対する等長暗号化を行うことにより、前記平文と同じ長さの中間暗号文を生成し、
前記乱数を用いて前記中間暗号文に対する加法的暗号化を行うことにより、暗号文を生成し、
前記暗号文および前記乱数を出力する、暗号化方法。
（付記１２）
復号装置が、
暗号文および乱数を取得し、
前記乱数を用いて前記暗号文の加法的復号を行うことにより、中間暗号文を取得し、
前記中間暗号文に対する等長復号を行うことにより、前記中間暗号文と同じ長さの平文を取得し、
前記平文を出力する、復号方法。
（付記１３）
前記暗号化装置が、
前記等長暗号化を行う前に、前記平文に対して前記乱数を用いてオフセット処理を行うことにより、中間平文を生成しておき、
前記中間平文に対する等長暗号化を行うことにより、前記中間暗号文を生成することを特徴とする付記１１に記載の暗号化方法。
（付記１４）
前記復号装置が、
前記中間暗号文に対して等長復号を行ったものを中間平文として取得し、
前記中間平文に対して前記乱数を用いてオフセット処理を行うことにより、前記平文を取得することを特徴とする付記１２に記載の復号方法。
（付記１５）
暗号化装置が、
平文を取得し、
乱数を生成し、
前記乱数を用いて前記平文に対する加法的暗号化を行うことにより、中間平文を生成し、
前記中間平文に対する等長暗号化を行うことにより、前記中間平文と同じ長さの暗号文を生成し、
前記暗号文および前記乱数を出力する、暗号化方法。
（付記１６）
復号装置が、
暗号文および乱数を取得し、
前記暗号文に対する等長復号を行うことにより、前記暗号文と同じ長さの中間平文を取得し、
前記乱数を用いて前記中間平文に対する加法的復号を行うことにより平文を取得し、
前記平文を出力する、復号方法。
（付記１７）
平文を取得する平文取得ステップと、
乱数を生成する乱数生成ステップと、
前記平文に対する等長暗号化を行うことにより、前記平文と同じ長さの中間暗号文を生成する等長暗号化ステップと、
前記乱数を用いて前記中間暗号文に対する加法的暗号化を行うことにより、暗号文を生成する加法的暗号化ステップと、
前記暗号文および前記乱数を出力する暗号文出力ステップと、
をコンピュータに実行させるコンピュータ・プログラム。
（付記１８）
暗号文および乱数を取得する暗号文取得ステップと、
前記乱数を用いて前記暗号文の加法的復号を行うことにより、中間暗号文を取得する加法的復号ステップと、
前記中間暗号文に対する等長復号を行うことにより、前記中間暗号文と同じ長さの平文を取得する等長復号ステップと、
前記平文を出力する平文出力ステップと、
をコンピュータに実行させるコンピュータ・プログラム。
（付記１９）
前記等長暗号化ステップの前に、前記平文に対して前記乱数を用いてオフセット処理を行うことにより、中間平文を生成するオフセット処理ステップをさらに前記コンピュータに実行させ、
前記等長暗号化ステップで、前記中間平文に対する等長暗号化を行うことにより、前記中間暗号文を生成することを特徴とする付記１７に記載のコンピュータ・プログラム。
（付記２０）
前記等長復号ステップで、前記中間暗号文に対して等長復号を行ったものを中間平文として取得し、
前記中間平文に対して前記乱数を用いてオフセット処理を行うことにより、前記平文を取得するオフセット処理ステップをさらに前記コンピュータに実行させることを特徴とする付記１８に記載のコンピュータ・プログラム。
（付記２１）
平文を取得する平文取得ステップと、
乱数を生成する乱数生成ステップと、
前記乱数を用いて前記平文に対する加法的暗号化を行うことにより、中間平文を生成する加法的暗号化ステップと、
前記中間平文に対する等長暗号化を行うことにより、前記中間平文と同じ長さの暗号文を生成する等長暗号化ステップと、
前記暗号文および前記乱数を出力する暗号文出力ステップと、
をコンピュータに実行させるコンピュータ・プログラム。
（付記２２）
暗号文および乱数を取得する暗号文取得ステップと、
前記暗号文に対する等長復号を行うことにより、前記暗号文と同じ長さの中間平文を取得する等長復号ステップと、
前記乱数を用いて前記中間平文に対する加法的復号を行うことにより平文を取得する加法的復号ステップと、
前記平文を出力する平文取得ステップと、
をコンピュータに実行させるコンピュータ・プログラム。
【０１６３】
また、上記の非特許文献の各開示を、本書に引用をもって繰り込むものとする。本発明の全開示（請求の範囲を含む）の枠内において、さらにその基本的技術思想に基づいて、実施形態の変更・調整が可能である。また、本発明の請求の範囲の枠内において種々の開示要素の多様な組み合わせないし選択が可能である。すなわち、本発明は、請求の範囲を含む全開示、技術的思想にしたがって当業者であればなし得るであろう各種変形、修正を含むことは勿論である。
【符号の説明】
【０１６４】
１０、３０    暗号化装置
２０、４０    復号装置
１００    平文取得部
１０１    乱数生成部
１０２、２０２    オフセット処理部
１０３、３０３    等長暗号化部
１０４、３０４    加法的暗号化部
１０５    暗号文出力部
２００    暗号文取得部
２０３、４０３    等長復号部
２０４、４０４    加法的復号部
２０５    平文出力部
１００１    ＣＰＵ
１００２    ＲＡＭ
１００３    ＲＯＭ
１００４    記憶装置
１００５    入力装置
１００６    出力装置
１００７    ネットワークインタフェース
【図１】
2012011455.tif 000003
【図２】
2012011455.tif 000004
【図３】
2012011455.tif 000005
【図４】
2012011455.tif 000006
【図５】
2012011455.tif 000007
【図６】
2012011455.tif 000008
【図７】
2012011455.tif 000009
【図８】
2012011455.tif 000010
【図９】
2012011455.tif 000011
【図１０】
2012011455.tif 000012
【図１１】
2012011455.tif 000013
【国際調査報告】
2012011455.tif 000014
2012011455.tif 000015
2012011455.tif 000016
2012011455.tif 000017