(57)【要約】  可変入力長調整可能暗号（「ＶＩＬＴＣ」）の構造および使用における新技術。ある場合には、可変入力長調整可能暗号（「ＶＩＬＴＣ」）は、効率的な処理能力で安全性強化を図るために、暗号化／復号システム外部への露出から保護された初期化ベクトルを使用する。例えば、暗号化および／または復号システムは、２つの固定入力長調整可能ブロック暗号（「ＦＩＬ  ＴＢＣ」）と、可変入力長調整可能暗号（「ＶＩＬＴＣ」）とを含む。第１固定入力長調整可能ブロック暗号（「ＦＩＬ  ＴＢＣ」）は、固定長初期化ベクトルを生成するように構成されている。可変入力長調整可能暗号（「ＶＩＬＴＣ」）は、固定長初期化ベクトルをトウィークとして使用して、可変長出力文字列を生成するように構成されている。第２固定入力長調整可能ブロック暗号（「ＦＩＬ  ＴＢＣ」）は、固定長出力文字列を生成するように構成されている。このように、第１固定入力長調整可能ブロック暗号（「ＦＩＬ  ＴＢＣ」）および第２固定入力長調整可能ブロック暗号（「ＦＩＬ  ＴＢＣ」）は、固定長初期化ベクトルを、システム外部への露出から保護する。他の場合では、可変入力長調整可能暗号（「ＶＩＬＴＣ」）は、関連データ付き認証付暗号化／復号の信頼性があり効率的な実装のために使用される。【選択図】      図３Ａ
2016540266.tif 000002
【特許請求の範囲】
【請求項１】
暗号化および／または復号のためのコンピュータに実装されるシステムであって、
固定長初期化ベクトルを生成するように構成された第１固定入力長調整可能ブロック暗号（「ＦＩＬ  ＴＢＣ」）と、
前記固定長初期化ベクトルをトウィークとして使用して、可変長出力文字列を生成するように構成された可変入力長調整可能暗号（「ＶＩＬＴＣ」）と、
固定長出力文字列を生成するように構成された第２固定入力長調整可能ブロック暗号（「ＦＩＬ  ＴＢＣ」）と、
を含む、システム。
【請求項２】
請求項１に記載のシステムにおいて、前記第１固定入力長調整可能ブロック暗号（「ＦＩＬ  ＴＢＣ」）が、所与の固定入力長調整可能ブロック暗号（「ＦＩＬ  ＴＢＣ」）コンポーネントへの第１コールによって供給され、前記第２固定入力長調整可能ブロック暗号（「ＦＩＬ  ＴＢＣ」）が、前記所与の固定入力長調整可能ブロック暗号（「ＦＩＬ  ＴＢＣ」）コンポーネントへの第２コールによって供給される、システム。
【請求項３】
請求項２に記載のシステムにおいて、前記第１コールにおいて、前記所与の固定入力長調整可能ブロック暗号（「ＦＩＬ  ＴＢＣ」）コンポーネントが、固定長入力文字列を、前記所与の固定入力長調整可能ブロック暗号（「ＦＩＬ  ＴＢＣ」）コンポーネントに対する第１入力として受け入れ、更にトウィークおよび可変長入力文字列の組み合わせを前記所与の固定入力長調整可能ブロック暗号（「ＦＩＬ  ＴＢＣ」）コンポーネントに対する第１トウィークとして受け入れ、前記第２コールにおいて、前記所与の固定入力長調整可能ブロック暗号（「ＦＩＬ  ＴＢＣ」）コンポーネントが、前記固定長初期化ベクトルを、前記所与の固定入力長調整可能ブロック暗号（「ＦＩＬ  ＴＢＣ」）コンポーネントに対する第２入力として受け入れ、前記トウィークおよび前記可変長出力文字列の組み合わせを前記所与の固定入力長調整可能ブロック暗号（「ＦＩＬ  ＴＢＣ」）コンポーネントに対する第２トウィークとして受け入れる、システム。
【請求項４】
請求項１に記載のシステムにおいて、前記第１固定入力長調整可能ブロック暗号（「ＦＩＬ  ＴＢＣ」）および第２固定入力長調整可能ブロック暗号（「ＦＩＬ  ＴＢＣ」）が、異なる固定入力長調整可能ブロック暗号（「ＦＩＬ  ＴＢＣ」）コンポーネントを介して供給される、システム。
【請求項５】
請求項１に記載のシステムにおいて、前記第１固定入力長調整可能ブロック暗号（「ＦＩＬ  ＴＢＣ」）および前記第２固定入力長調整可能ブロック暗号（「ＦＩＬ  ＴＢＣ」）が、前記固定長初期化ベクトルを、前記システム外部への露出から保護する、システム。
【請求項６】
請求項１に記載のシステムにおいて、前記システムが、当該システムに対するトウィークとして、当該システムの環境的特徴に基づく値を受け入れる、システム。
【請求項７】
請求項１に記載のシステムにおいて、前記第１固定入力長調整可能ブロック暗号（「ＦＩＬ  ＴＢＣ」）、前記第２固定入力長調整可能ブロック暗号（「ＦＩＬ  ＴＢＣ」）、および可変入力長調整可能暗号（「ＶＩＬＴＣ」）が、特殊目的ハードウェアを使用して実装される、システム。
【請求項８】
請求項１に記載のシステムにおいて、前記第１固定入力長調整可能ブロック暗号（「ＦＩＬ  ＴＢＣ」）、前記第２固定入力長調整可能ブロック暗号（「ＦＩＬ  ＴＢＣ」）、および可変入力長調整可能暗号（「ＶＩＬＴＣ」）が、汎用ハードウェア上で実行するソフトウェアを使用して実装される、システム。
【請求項９】
請求項１に記載のシステムにおいて、前記固定長初期化ベクトルが、Ｎ−キャラクタ初期化ベクトルであり、前記固定長出力文字列が、Ｎ−キャラクタ出力文字列であり、
前記第１固定入力長調整可能ブロック暗号（「ＦＩＬ  ＴＢＣ」）が、前記Ｎ−キャラクタ初期化ベクトルを生成するように構成された第１Ｎ−キャラクタ調整可能ブロック暗号（「ＴＢＣ」）であり、
前記可変入力長調整可能暗号（「ＶＩＬＴＣ」）が、前記Ｎ−キャラクタ初期化ベクトルをトウィークとして使用して、前記可変長出力文字列を生成するように構成され、
前記第２固定入力長調整可能ブロック暗号（「ＦＩＬ  ＴＢＣ」）が、前記Ｎ−キャラクタ出力文字列を生成するように構成された第２Ｎ−キャラクタ調整可能ブロック暗号（「ＴＢＣ」）である、システム。
【請求項１０】
請求項９に記載のシステムであって、更に、
Ｎ−キャラクタ入力文字列および可変長入力文字列を格納する第１バッファと、
前記Ｎ−キャラクタ出力文字列および前記可変長出力文字列を格納する第２バッファと、
を含む、システム。
【請求項１１】
請求項１０に記載のシステムにおいて、前記Ｎ−キャラクタ入力文字列、前記可変長入力文字列、前記Ｎ−キャラクタ出力文字列、および前記可変長出力文字列のキャラクタが、所定の有限の１組の記号から選択される、システム。
【請求項１２】
請求項９に記載のシステムにおいて、前記第１Ｎ−キャラクタ調整可能ブロック暗号（「ＴＢＣ」）、前記可変入力長調整可能暗号（「ＶＩＬＴＣ」）、および前記第２Ｎ−キャラクタ調整可能ブロック暗号（「ＴＢＣ」）が、ランダム生成置換参照表から組み立てられる、システム。
【請求項１３】
請求項９に記載のシステムにおいて、
前記第１Ｎ−キャラクタ調整可能ブロック暗号（「ＴＢＣ」）が、Ｎ−キャラクタ入力文字列を前記第１Ｎ−キャラクタ調整可能ブロック暗号（「ＴＢＣ」）に対する入力として使用し、前記システムに対するトウィークおよび可変長入力文字列の組み合わせを前記第１Ｎ−キャラクタ調整可能ブロック暗号（「ＴＢＣ」）に対するトウィークとして使用して、前記Ｎ−キャラクタ初期化ベクトルを生成するように構成され、
前記可変入力長調整可能暗号（「ＶＩＬＴＣ」）が、前記Ｎ−ビット初期化ベクトルを前記可変入力長調整可能暗号（「ＶＩＬＴＣ」）に対するトウィークとして使用し、前記可変長入力文字列を前記可変入力長調整可能暗号（「ＶＩＬＴＣ」）に対する入力として使用して、前記可変長出力文字列を生成するように構成され、
前記第２Ｎ−キャラクタ調整可能ブロック暗号（「ＴＢＣ」）が、前記Ｎ−キャラクタ初期化ベクトルを前記第２Ｎ−キャラクタ調整可能ブロック暗号（「ＴＢＣ」）に対する入力として使用し、前記システムに対するトウィークおよび前記可変長出力文字列の組み合わせを前記第２Ｎ−キャラクタ調整可能ブロック暗号（「ＴＢＣ」）に対するトウィークとして使用して、前記Ｎ−キャラクタ出力文字列を生成するように構成される、システム。
【請求項１４】
請求項１に記載のシステムにおいて、前記固定長初期化ベクトルがＮ−ビット初期化ベクトルであり、前記固定長出力文字列がＮ−ビット出力文字列であり、
更に、前記第１固定入力長調整可能ブロック暗号（「ＦＩＬ  ＴＢＣ」）が、前記Ｎ−ビット初期化ベクトルを生成するように構成された第１Ｎ−ビット調整ブロック暗号（「ＴＢＣ」）であり、
前記可変入力長調整可能暗号（「ＶＩＬＴＣ」）が、前記Ｎ−ビット初期化ベクトルをトウィークとして使用して、前記可変長出力文字列を生成するように構成され、
前記第２固定入力長調整可能ブロック暗号（「ＦＩＬ  ＴＢＣ」）が、前記Ｎ−ビット出力文字列を生成するように構成された第２Ｎ−ビット調整可能ブロック暗号（「ＴＢＣ」）である、システム。
【請求項１５】
請求項１４に記載のシステムであって、更に、
Ｎ−ビット入力文字列および可変長入力文字列を格納する第１バッファと、
前記Ｎ−ビット出力文字列および前記可変長出力文字列を格納する第２バッファと、
を含む、システム。
【請求項１６】
請求項１４に記載のシステムにおいて、
前記第１Ｎ−ビット調整可能ブロック暗号（「ＴＢＣ」）が、Ｎ−ビット入力文字列を前記第１Ｎ−ビット調整可能ブロック暗号（「ＴＢＣ」）に対する入力として使用し、前記システムに対するトウィークおよび可変長入力文字列の組み合わせを前記第１Ｎ−ビット調整可能ブロック暗号（「ＴＢＣ」）に対するトウィークとして使用して、前記Ｎ−ビット初期化ベクトルを生成するように構成され、
前記可変入力長調整可能暗号（「ＶＩＬＴＣ」）が、前記Ｎ−ビット初期化ベクトルを前記可変入力長調整可能暗号（「ＶＩＬＴＣ」）に対するトウィークとして使用し、前記可変長入力文字列を前記可変入力長調整可能暗号（「ＶＩＬＴＣ」）に対する入力として使用して、前記可変長出力文字列を生成するように構成され、
前記第２Ｎ−ビット調整可能ブロック暗号（「ＴＢＣ」）が、前記Ｎ−ビット初期化ベクトルを前記第２Ｎ−ビット調整可能ブロック暗号（「ＴＢＣ」）に対する入力として使用し、前記システムに対するトウィークおよび前記可変長出力文字列の組み合わせを前記第２Ｎ−ビット調整可能ブロック暗号（「ＴＢＣ」）に対するトウィークとして使用して、前記Ｎ−ビット出力文字列を生成するように構成される、システム。
【請求項１７】
請求項１４に記載のシステムであって、更に、
安全性および実装効率のトレードオフを得るためにＮを調節するように構成されたコントローラを含み、Ｎの値が小さい程、安全性が悪化するが、安全性制約に応じた効率的な実装が簡素化し、Ｎの値が大きい程高い安全性が得られるが、安全性制約に応じた効率的な実装が複雑化する、システム。
【請求項１８】
請求項１４に記載のシステムにおいて、前記第１Ｎ−ビット調整可能ブロック暗号（「ＴＢＣ」）および前記第２Ｎ−ビット調整可能ブロック暗号（「ＴＢＣ」）が同一構造を有する、システム。
【請求項１９】
請求項１４に記載のシステムにおいて、前記第１Ｎ−ビットＴＣＢおよび前記第２Ｎ−ビット調整可能ブロック暗号（「ＴＢＣ」）の内少なくとも１つが、ＬＲＷ２  ＴＢＣ構造であり、
前記可変入力長調整可能暗号（「ＶＩＬＴＣ」）が、反復ＬＲＷ２  ＴＢＣ構造である、システム。
【請求項２０】
請求項１９に記載のシステムにおいて、前記ＬＲＷ２  ＴＢＣが、（１）（ａ）ｎ−ビットＬＲＷ２入力文字列と（ｂ）トウィーク入力のｎ−ビット・ハッシュとの間の排他的ＯＲの暗号化バージョンと、（２）前記トウィーク入力のｎ−ビット・ハッシュとの間の排他的ＯＲを計算することによって、ｎ−ビットＬＲＷ２出力文字列を生成するように構成される、システム。
【請求項２１】
請求項１４に記載のシステムにおいて、
前記第１Ｎ−ビット調整可能ブロック暗号（「ＴＢＣ」）および前記第２Ｎ−ビット調整可能ブロック暗号（「ＴＢＣ」）の内少なくとも１つが、ドメイン拡張ＣＬＲＷ２構造であり、
前記可変入力長調整可能暗号（「ＶＩＬＴＣ」）が、反復ＣＬＲＷ２構造である、システム。
【請求項２２】
請求項１４に記載のシステムにおいて、Ｎが１２８である、システム。
【請求項２３】
請求項１４に記載のシステムにおいて、Ｎが２５６である、システム。
【請求項２４】
コンピュータに実装される方法であって、
固定長入力文字列および可変長入力文字列を処理して、固定長出力文字列および可変長出力文字列を生成するステップであって、  
固定長初期化ベクトルを生成するステップと、
前記固定長初期化ベクトルをトウィークとして使用して、可変入力長調整可能暗号（「ＶＩＬＴＣ」）によって、前記可変長出力文字列を生成するステップと、
前記固定長初期化ベクトルを曖昧にするステップと、
を含む、ステップと、
前記固定長出力文字列および可変長出力文字列を出力するステップと、
を含む、方法。
【請求項２５】
請求項２４に記載の方法において、前記処理が、更に、
環境的特徴に基づいてシステム・レベルのトウィークを設定するステップを含む、方法。
【請求項２６】
請求項２４記載の方法において、前記固定長入力文字列がＮ−キャラクタ入力文字列であり、前記固定長出力文字列がＮ−キャラクタ出力文字列であり、前記固定長初期化ベクトルがＮ−キャラクタ初期化ベクトルである、方法。
【請求項２７】
請求項２６に記載の方法において、前記Ｎ−キャラクタ初期化ベクトルが、
第１Ｎ−キャラクタ調整可能ブロック暗号（「ＴＢＣ」）によって生成され、
前記Ｎ−キャラクタ出力文字列を生成する第２Ｎ−キャラクタ調整可能ブロック暗号（「ＴＢＣ」）によって曖昧にされる、方法。
【請求項２８】
請求項２６に記載の方法において、前記処理が、フォーマット保存暗号化の一部であり、前記Ｎ−キャラクタ入力文字列および前記可変長入力文字列が平文であり、前記Ｎ−キャラクタ出力文字列および可変長出力文字列が暗号文である、方法。
【請求項２９】
請求項２６に記載の方法において、前記処理が、フォーマット保存復号の一部であり、前記Ｎ−キャラクタ入力文字列および前記可変長入力文字列が暗号文であり、前記Ｎ−キャラクタ出力文字列および可変長出力文字列が平文である、方法。
【請求項３０】
請求項２４に記載の方法において、前記固定長入力文字列がＮ−ビット入力文字列であり、前記固定長出力文字列がＮ−ビット出力文字列であり、前記固定長初期化ベクトルがＮ−ビット初期化ベクトルである、方法。
【請求項３１】
請求項３０に記載の方法において、前記Ｎ−ビット初期化ベクトルが、
第１Ｎ−ビット調整可能ブロック暗号（「ＴＢＣ」）によって生成され、
前記Ｎ−ビット出力文字列を生成する第２Ｎ−ビット調整可能ブロック暗号（「ＴＢＣ」）によって曖昧にされる、方法。
【請求項３２】
請求項３０に記載の方法において、
前記Ｎ−ビット初期化ベクトルを前記第１Ｎ−ビット調整可能ブロック暗号（「ＴＢＣ」）によって生成するステップが、前記第１Ｎ−ビット調整可能ブロック暗号（「ＴＢＣ」）に対する入力である前記Ｎ−ビット入力文字列と、前記第１Ｎ−ビット調整可能ブロック暗号（「ＴＢＣ」）に対するトウィークである、前記システムに対するトウィークおよび前記可変長入力文字列の組み合わせとに基づき、
前記可変長出力文字列を前記可変入力長調整可能暗号（「ＶＩＬＴＣ」）によって生成するステップが、前記可変入力長調整可能暗号（「ＶＩＬＴＣ」）に対するトウィークである前記Ｎ−ビット初期化ベクトルと、前記可変入力長調整可能暗号（「ＶＩＬＴＣ」）に対する入力である前記可変長入力文字列とに基づき、
前記Ｎ−ビット出力文字列を前記第２Ｎ−ビット調整可能ブロック暗号（「ＴＢＣ」）によって生成するステップが、前記第２Ｎ−ビット調整可能ブロック暗号（「ＴＢＣ」）に対する入力である前記Ｎ−ビット初期化ベクトルと、前記第２Ｎ−ビット調整可能ブロック暗号（「ＴＢＣ」）に対するトウィークである、前記システムに対するトウィークおよび前記可変長出力文字列の組み合わせとに基づく、方法。
【請求項３３】
請求項３０に記載の方法において、前記処理が完全ディスク暗号化の一部であり、前記Ｎ−ビット入力文字列および前記可変長入力文字列が平文であり、前記Ｎ−ビット出力文字列および前記可変長出力文字列が暗号文である、方法。
【請求項３４】
請求項３０に記載の方法において、前記処理が完全ディスク復号の一部であり、前記Ｎ−ビット入力文字列および前記可変長入力文字列が暗号文であり、前記Ｎ−ビット出力文字列および前記可変長出力文字列が平文である、方法。
【請求項３５】
請求項３０に記載の方法において、前記処理が、関連データ付き認証付暗号化の一部であり、前記Ｎ−ビット入力文字列および前記可変長入力文字列が平文であり、前記Ｎ−ビット出力文字列および前記可変長出力文字列が暗号文である、方法。
【請求項３６】
請求項３０に記載の方法において、前記処理が、関連データによる認証復号の一部であり、前記Ｎ−ビット入力文字列および前記可変長入力文字列が暗号文であり、前記Ｎ−ビット出力文字列および前記可変長出力文字列が平文である、方法。
【請求項３７】
請求項３０に記載の方法であって、更に、安全性および実装効率のトレードオフを得るためにＮを調節するステップを含み、Ｎの値が小さい程、安全性が悪化するが、安全性制約に応じた効率的な実装が簡素化し、Ｎの値が大きい程高い安全性が得られるが、安全性制約に応じた効率的な実装が複雑化する、方法。
【請求項３８】
暗号化および／または復号のためのコンピュータに実装されるシステムであって、
Ｎ−ビット入力文字列および可変長入力文字列を格納する第１バッファと、
第１Ｎ−ビット調整可能ブロック暗号（「ＴＢＣ」）であって、前記Ｎ−ビット入力文字列を前記第１Ｎ−ビット調整可能ブロック暗号（「ＴＢＣ」）に対する入力として使用し、前記システムに対するトウィークおよび前記可変長入力文字列の組み合わせを前記第１Ｎ−ビット調整可能ブロック暗号（「ＴＢＣ」）に対するトウィークとして使用して、Ｎ−ビット初期化ベクトルを生成するように構成された、第１Ｎ−ビット調整可能ブロック暗号（「ＴＢＣ」）と、
可変入力長調整可能暗号（「ＶＩＬＴＣ」）であって、前記Ｎ−ビット初期化ベクトルを前記可変入力長調整可能暗号（「ＶＩＬＴＣ」）に対するトウィークとして使用し、前記可変長入力文字列を前記可変入力長調整可能暗号（「ＶＩＬＴＣ」）に対する入力として使用して、可変長出力文字列を生成するように構成された、可変入力長調整可能暗号（「ＶＩＬＴＣ」）と、
第２Ｎ−ビット調整可能ブロック暗号（「ＴＢＣ」）であって、前記Ｎ−ビット初期化ベクトルを前記第２Ｎ−ビット調整可能ブロック暗号（「ＴＢＣ」）に対する入力として使用し、前記システムに対するトウィークおよび前記可変長出力文字列の組み合わせを前記第２Ｎ−ビット調整可能ブロック暗号（「ＴＢＣ」）に対するトウィークとして使用して、Ｎ−ビット出力文字列を生成するように構成された、第２Ｎ−ビット調整可能ブロック暗号（「ＴＢＣ」）と、
前記Ｎ−ビット出力文字列および前記可変長出力文字列を格納する第２バッファと、
を含む、システム。
【請求項３９】
請求項３８に記載のシステムにおいて、前記システムに対するトウィークが、前記システムの環境的特徴に基づく値である、システム。
【請求項４０】
請求項３８に記載のシステムであって、更に、
安全性および実装効率のトレードオフを得るためにＮを調節するように構成されたコントローラを含み、Ｎの値が小さい程、安全性が悪化するが、安全性制約に伴う効率的な実装が簡素化し、Ｎの値が大きい程高い安全性が得られるが、安全性制約に伴う効率的な実装が複雑化する、システム。
【請求項４１】
コンピュータに実装される方法であって、
ヘッダおよびメッセージを受けるステップと、
可変入力長調整可能暗号（「ＶＩＬＴＣ」）を使用して前記メッセージを処理して、関連データ付き認証付暗号化を行うステップであって、前記可変入力長調整可能暗号（「ＶＩＬＴＣ」）に対するトウィークが、少なくとも部分的に前記ヘッダに基づき、前記処理が、暗号化メッセージを生成する、ステップと、
前記ヘッダおよび前記暗号化メッセージを出力するステップと、
を含む、方法。
【請求項４２】
請求項４１に記載の方法において、前記メッセージを処理するステップが、
前記ヘッダおよび再現情報を使用して修正ヘッダを決定するステップと、
前記メッセージおよび前記修正ヘッダを使用して修正メッセージを決定するステップと、
前記修正ヘッダを前記可変入力長調整可能暗号（「ＶＩＬＴＣ」）に対するトウィークとして、前記可変入力長調整可能暗号（「ＶＩＬＴＣ」）を使用して前記修正メッセージを暗号化するステップと、
を含む、方法。
【請求項４３】
請求項４２に記載の方法であって、更に、
前記再現情報を出力するステップを含む、方法。
【請求項４４】
コンピュータに実装される方法であって、
ヘッダおよび暗号化メッセージを受けるステップと、
可変入力長調整可能暗号（「ＶＩＬＴＣ」）を使用して前記暗号化メッセージを処理して、関連データ付き認証付復号を行うステップであって、前記可変入力長調整可能暗号（「ＶＩＬＴＣ」）に対するトウィークが少なくとも部分的に前記ヘッダに基づき、前記処理がメッセージを生成するステップと、
前記メッセージを出力するステップと、
を含む、方法。
【請求項４５】
請求項４４に記載の方法であって、更に、
再現情報を受けるステップを含む、方法。
【請求項４６】
請求項４５記載の方法において、前記暗号化メッセージを処理するステップが、
前記ヘッダおよび前記再現情報を使用して修正ヘッダを決定するステップと、
前記可変入力長調整可能暗号（「ＶＩＬＴＣ」）を使用して、前記修正ヘッダを前記可変入力長調整可能暗号（「ＶＩＬＴＣ」）に対するトウィークとして、前記暗号化メッセージを復号することによって、修正メッセージを生成するステップと、
前記修正メッセージおよび前記修正ヘッダを使用して、前記メッセージを決定するステップと、
を含む、方法。
【発明の詳細な説明】
【技術分野】
【０００１】
関連出願情報
[001]  本願は、２０１３年１１月２９日に出願された米国仮特許出願第６１／９１０，２９２号、および２０１４年１１月２０日に出願された米国特許出願第１４／５４９，５３１号に対する優先権を主張する。これらの出願の開示内容は、ここで引用したことにより、本願にも含まれるものとする。
分野
[002]  初期化ベクトルが保護された可変入力長調整可能暗号の構造および使用。
政府援助の承認
[003]  本発明は、全米科学財団(National Science Foundation)によって供与された CNS-0845610およびCNS-1319061の下で、政府支援によって行われた。政府は、本発明において一定の権利を保有する。
【従来技術】
【０００２】
[004]  一般に、暗号化は、許可された関係者のみが情報を読むことができ、第三者は読むことができないように、情報を符号化するプロセスである。ある暗号化方式では、暗号化アルゴリズムを使用して情報（平文と呼ぶ）を暗号化し、それを読み取り不可能な暗号文に変換する。許可された関係者は、復号アルゴリズムを使用して、この暗号文をデコードすることができる。コンピュータ・システムでは、暗号化アルゴリズムは情報の二進値（即ち、ビット）を暗号化する。
【０００３】
[005]  ブロック暗号は、固定長ブロックのビットに対して動作する暗号化アルゴリズムである。ｎ−ビット・ブロック暗号は、ｎ−ビットのブロックを暗号化して、ｎ−ビットの暗号文を生成する。ブロック暗号は広く使用されており、ブロック暗号には多くの効率的な実施態様がある。ブロック暗号は暗号化鍵を使用する。ブロック暗号の安全性は、特定の鍵の下で暗号化されるブロックの数が増えるに連れて低下することが分かっている。ブロック暗号に対して鍵を変更することは、それ自体困難ではないが、様々な重要な用途では、新たなブロック暗号鍵の頻繁な生成および配布は実現可能ではない。
【０００４】
[006]  調整可能ブロック暗号（「ＴＢＣ」：tweakable block cypher）は、ブロック暗号の一般化である。ｎ個のキャラクタから成る調整可能ブロック暗号（「ＴＢＣ」）
【０００５】
【数１】
2016540266.tif 000003
【０００６】
は、Σｎにわたる置換の一群であり(a family of permutations over Σn)、調整可能ブロック暗号（「ＴＢＣ」）における各置換は、鍵およびトウィーク(tweak)に関連付けられる。多くの場合、Σ＝｛０，１｝であり、この場合、調整可能ブロック暗号（「ＴＢＣ」）をｎ−ビット調整可能ブロック暗号（「ＴＢＣ」）  
【０００７】
【数２】
2016540266.tif 000004
【０００８】
と呼ぶことができる。入力文字列について、鍵およびトウィーク双方によって、調整可能ブロック暗号（「ＴＢＣ」）によって生成された入力文字列の置換を指定する。典型的な使用では、鍵は調整可能ブロック暗号（「ＴＢＣ」）に対する多くのコールにわたって秘密でありそして固定であるが、トウィークは秘密ではなくコール毎に変化することができる。これにより、鍵が固定であってもトウィークの値を変化させることによって、調整可能ブロック暗号（「ＴＢＣ」）の挙動における可変性をサポートする。変化するトウィークの値が十分に単純である場合（鍵設定および更新のプロセスと比較して）、調整可能ブロック暗号（「ＴＢＣ」）を使用することは、ブロック暗号によって安全に暗号化されるデータの分量を拡充する効率的な方法となることができる。調整可能ブロック暗号（「ＴＢＣ」）を使用すると、アルゴリズムの設計および分析を単純化することができる（例えば、大量のデータを安全に処理することができるアルゴリズム）。調整可能ブロック暗号（「ＴＢＣ」）は、暗号化されようとするデータの分量が、利用可能な鍵素材(key material)と比較して、非常に大きいときに有用であると考えられ、ブロック暗号鍵を変更することは望ましくなく、更に実現可能でもない。処理すべきデータの分量が過剰に大きくない用途においてであっても、トウィーク入力は、様々な暗号の使用にわたって、または多数のユーザにわたって固定の鍵と共に調整可能ブロック暗号（「ＴＢＣ」）を使用するというような、実際の用途においても有用な特徴を付与することができる。
【発明の概要】
【発明が解決しようとする課題】
【０００９】
[007]  調整可能暗号は、調整可能暗号化方式または大型ブロック暗号と呼ばれることもあり、調整可能ブロック暗号（「ＴＢＣ」）の可変入力長（「ＶＩＬ」）設定に対する拡張である。一般に、可変入力長調整可能暗号（「ＶＩＬＴＣ」）は、長さ保存置換(length-preserving permutations)の一群であり、平文入力と同じ長さの暗号文出力を生成する。可変入力長調整可能暗号（「ＶＩＬＴＣ」）を実現する一般的な１つの手法は、基礎となるｎ−ビット・ブロック暗号から、ときには１つ以上のハッシング動作と合わせて、可変入力長調整可能暗号（「ＶＩＬＴＣ」）プリミティブを組み立てることであった。この手法にしたがって組み立てられた可変入力長調整可能暗号（「ＶＩＬＴＣ」）は、ある重要な使用事例シナリオに対して、特に、ｎが小さいとき（例えば、６４）、または１つの鍵によって処理されるべきデータ量が非常に大きいときには、十分な安全性保証を提供できないことがある。
【課題を解決するための手段】
【００１０】
[008]  要約すると、詳細な説明では、可変入力長調整可能暗号（「ＶＩＬＴＣ」）の構造および使用における新技術について紹介する。場合によっては、これらの可変入力長調整可能暗号（「ＶＩＬＴＣ」）は、効率的な処理遂行(performance)と共に安全性強化を提供するために、暗号／復号システム外部への露出から保護された初期化ベクトルを使用する。他の場合では、関連データ付き認証付暗号化／復号を信頼性高くしかも効率的に実現するために、可変入力長調整可能暗号（「ＶＩＬＴＣ」）を使用する。
【００１１】
[009]  本明細書において説明する新技術の一態様によれば、暗号化および／または復号システムは、２つの固定入力長調整可能ブロック暗号（「ＦＩＬ  ＴＢＣ」）と可変入力長調整可能暗号（「ＶＩＬＴＣ」）とを含む。通例、２つの固定入力長調整可能ブロック暗号（「ＦＩＬ  ＴＢＣ」）は、１つの固定入力長調整可能ブロック暗号（「ＦＩＬ  ＴＢＣ」）コンポーネントに対する２回のコールによって供給される。しかしながら、代わりに、２つの固定入力長調整可能ブロック暗号（「ＦＩＬ  ＴＢＣ」）コンポーネントによって２つの異なる固定入力長調整可能ブロック暗号（「ＦＩＬ  ＴＢＣ」）を供給することもできる。
【００１２】
[010]  第１固定入力長調整可能ブロック暗号（「ＦＩＬ  ＴＢＣ」）（例えば、所与の固定入力長調整可能ブロック暗号（「ＦＩＬ  ＴＢＣ」）コンポーネント、または第１の異なる固定入力長調整可能ブロック暗号（「ＦＩＬ  ＴＢＣ」）コンポーネントへの第１コール）は、固定長初期化ベクトルを生成するように構成されている(adapted to)。例えば、第１コールにおいて、所与の固定入力長調整可能ブロック暗号（「ＦＩＬ  ＴＢＣ」）コンポーネントは、固定長入力文字列を所与の固定入力長調整可能ブロック暗号（「ＦＩＬ  ＴＢＣ」）コンポーネントに対する第１入力として受け入れ、システムに対するトウィークおよび可変長入力文字列の組み合わせを、所与の固定入力長調整可能ブロック暗号（「ＦＩＬ  ＴＢＣ」）コンポーネントに対する第１トウィークとして受け入れる。可変入力長調整可能暗号（「ＶＩＬＴＣ」）は、固定長初期化ベクトルをトウィークとして使用して、可変長出力文字列を生成するように構成されている。第２固定入力長調整可能ブロック暗号（「ＦＩＬ  ＴＢＣ」）（例えば、所与の固定入力長調整可能ブロック暗号（「ＦＩＬ  ＴＢＣ」）コンポーネント、または第２の異なる固定入力長調整可能ブロック暗号（「ＦＩＬ  ＴＢＣ」）コンポーネントに対する第２コール）は、固定長出力文字列を生成するように構成されている。例えば、第２コールにおいて、所与の固定入力長調整可能ブロック暗号（「ＦＩＬ  ＴＢＣ」）コンポーネントは、固定長初期化ベクトルを所与の固定入力長調整可能ブロック暗号（「ＦＩＬ  ＴＢＣ」）コンポーネントに対する第２入力として受け入れ、システム・トウィークおよび可変長出力文字列の組み合わせを、所与の固定入力長調整可能ブロック暗号（「ＦＩＬ  ＴＢＣ」）コンポーネントに対する第２トウィークとして受け入れる。第１固定入力長調整可能ブロック暗号（「ＦＩＬ  ＴＢＣ」）および第２固定入力長調整可能ブロック暗号（「ＦＩＬ  ＴＢＣ」）は、固定長初期化ベクトルを、システム外部への露出から保護する。システム・トウィークは、システムの環境的特徴に基づくことができる。
【００１３】
[011]  本明細書において説明する新技術の他の態様によれば、暗号化および／または復号システムは、２つのＮ−キャラクタ調整可能ブロック暗号（「ＴＢＣ」）と可変入力長調整可能暗号（「ＶＩＬＴＣ」）とを含む。第１Ｎ−キャラクタ調整可能ブロック暗号（「ＴＢＣ」）（例えば、所与のＮ−キャラクタ調整可能ブロック暗号（「ＴＢＣ」）コンポーネントまたは第１の異なるＮ−キャラクタ調整可能ブロック暗号（「ＴＢＣ」）コンポーネントに対する第１コール）は、Ｎ−キャラクタ初期化ベクトルを生成するように構成されている。可変入力長調整可能暗号（「ＶＩＬＴＣ」）は、Ｎ−キャラクタ初期化ベクトルをトウィークとして使用して、可変長出力文字列を生成するように構成されている。第２Ｎ−キャラクタ調整可能ブロック暗号（「ＴＢＣ」）（例えば、所与のＮ−キャラクタ調整可能ブロック暗号（「ＴＢＣ」）コンポーネントまたは第２の異なるＮ−キャラクタ調整可能ブロック暗号（「ＴＢＣ」）コンポーネントに対する第２コール）は、Ｎ−キャラクタ出力文字列を生成するように構成されている。このように、第１Ｎ−キャラクタ調整可能ブロック暗号（「ＴＢＣ」）および第２Ｎ−キャラクタ調整可能ブロック暗号（「ＴＢＣ」）は、システム外部への露出からＮ−キャラクタ初期化ベクトルを保護する。
【００１４】
[012]  本システムは多数のバッファを含むことができる。例えば、第１バッファがＮ−キャラクタ入力文字列および可変長入力文字列を格納し、第２バッファがＮ−キャラクタ出力文字列および可変長出力文字列を格納する。Ｎ−キャラクタ入力文字列、可変長入力文字列、Ｎ−キャラクタ出力文字列、および可変長出力文字列のキャラクタは、所定の有限な１組のシンボル（例えば、数値０から９、文字ＺからＺおよび数値０から９）から選択される。また、本システムの入力は、１つ以上の鍵およびトウィーク値も含む。第１Ｎ−キャラクタ調整可能ブロック暗号（「ＴＢＣ」）、可変入力長調整可能暗号（「ＶＩＬＴＣ」）、および第２Ｎ−キャラクタ調整可能ブロック暗号（「ＴＢＣ」）は、ランダムに生成された置換参照表から組み立てることができる。更に一般的には、第１Ｎ−キャラクタ調整可能ブロック暗号（「ＴＢＣ」）、第２Ｎ−キャラクタ調整可能ブロック暗号（「ＴＢＣ」）、および可変入力長調整可能暗号（「ＶＩＬＴＣ」）は、特殊目的ハードウェアを使用して実装することができ、または汎用ハードウェア上で実行するソフトウェアを使用して実装することができる。
【００１５】
[013]  実施態様例では、第１Ｎ−キャラクタ調整可能ブロック暗号（「ＴＢＣ」）は、Ｎ−キャラクタ入力文字列を第１Ｎ−キャラクタ調整可能ブロック暗号（「ＴＢＣ」）に対する入力として使用し、システムに対するトウィークおよび可変長入力文字列の組み合わせを第１Ｎ−キャラクタ調整可能ブロック暗号（「ＴＢＣ」）に対するトウィークとして使用して、Ｎ−キャラクタ初期化ベクトルを生成するように構成されている。可変入力長調整可能暗号（「ＶＩＬＴＣ」）は、Ｎ−ビット初期化ベクトルを可変入力長調整可能暗号（「ＶＩＬＴＣ」）に対するトウィークとして使用し、更に可変長入力文字列を可変入力長調整可能暗号（「ＶＩＬＴＣ」）に対する入力として使用して、可変長出力文字列を生成するように構成されている。 第２Ｎ−キャラクタ調整可能ブロック暗号（「ＴＢＣ」）は、Ｎ−キャラクタ初期化ベクトルを第２Ｎ−キャラクタ調整可能ブロック暗号（「ＴＢＣ」）に対する入力として使用し、システムに対するトウィークおよび可変長出力文字列の組み合わせを第２Ｎ−キャラクタ調整可能ブロック暗号（「ＴＢＣ」）に対するトウィークとして使用して、Ｎ−キャラクタ出力文字列を生成するように構成されている。
【００１６】
[014]  本明細書において説明する新技術の他の態様によれば、暗号化および／または復号システムは、２つのＮ−ビット調整可能ブロック暗号（「ＴＢＣ」）および可変入力長調整可能暗号（「ＶＩＬＴＣ」）を含む。第１Ｎ−ビット調整可能ブロック暗号（「ＴＢＣ」）（例えば、所与のＮ−ビット調整可能ブロック暗号（「ＴＢＣ」）コンポーネントまたは第１の異なるＮ−ビット調整可能ブロック暗号（「ＴＢＣ」）コンポーネントに対する第１コール）は、Ｎ−ビット初期化ベクトルを生成するように構成されている。可変入力長調整可能暗号（「ＶＩＬＴＣ」）は、Ｎ−ビット初期化ベクトルをトウィークとして使用して、可変長出力文字列を生成するように構成されている。第２Ｎ−ビット調整可能ブロック暗号（「ＴＢＣ」）（例えば、所与のＮ−ビット調整可能ブロック暗号（「ＴＢＣ」）コンポーネントまたは第２の異なるＮ−ビット調整可能ブロック暗号（「ＴＢＣ」）コンポーネントに対する第２コール）は、Ｎ−ビット出力文字列を生成するように構成されている。このように、第１Ｎ−ビット調整可能ブロック暗号（「ＴＢＣ」）および第２Ｎ−ビット調整可能ブロック暗号（「ＴＢＣ」）は、システム外部への露出からＮ−ビット初期化ベクトルを保護する。
【００１７】
[015]  本システムは多数のバッファを含むことができる。例えば、第１バッファがＮ−ビット入力文字列および可変長入力文字列を格納し、第２バッファがＮ−ビット出力文字列および可変長出力文字列を格納する。また、本システムの入力は１つ以上の鍵およびトウィーク値も含む。また、本システムは、安全性および実装効率のトレードオフを得るためにＮを調節するように構成されたコントローラも含むことができる。Ｎの値が小さい程、安全性が悪化するが、安全性制約に伴い効率的な実装が簡素化する。他方で、Ｎの値が大きい程高い安全性が得られるが、安全性制約に伴い効率的な実装が複雑化する。
【００１８】
[016]  実施態様例では、第１Ｎ−ビット調整可能ブロック暗号（「ＴＢＣ」）は、Ｎ−ビット入力文字列を第１Ｎ−ビット調整可能ブロック暗号（「ＴＢＣ」）に対する入力として使用し、システムに対するトウィークおよび可変長入力文字列の組み合わせを第１Ｎ−ビット調整可能ブロック暗号（「ＴＢＣ」）に対するトウィークとして使用して、Ｎ−ビット初期化ベクトルを生成するように構成されている。可変入力長調整可能暗号（「ＶＩＬＴＣ」）は、Ｎ−ビット初期化ベクトルを可変入力長調整可能暗号（「ＶＩＬＴＣ」）に対するトウィークとして使用し、可変長入力文字列を可変入力長調整可能暗号（「ＶＩＬＴＣ」）に対する入力として使用して、可変長出力文字列を生成するように構成されている。第２Ｎ−ビット調整可能ブロック暗号（「ＴＢＣ」）は、Ｎ−ビット初期化ベクトルを第２Ｎ−ビット調整可能ブロック暗号（「ＴＢＣ」）に対する入力として使用し、システムに対するトウィークおよび可変長出力文字列の組み合わせを第２Ｎ−ビット調整可能ブロック暗号（「ＴＢＣ」）に対するトウィークとして使用して、Ｎ−ビット出力文字列を生成するように構成されている。例えば、トウィークＴおよびＢビット入力Ｘ（Ｂ＞Ｎ）を仮定すると、入力Ｘの最初のＮ−ビット（ＸＬ）は、第１Ｎ−ビット調整可能ブロック暗号（「ＴＢＣ」）（例えば、Ｎ−ビット調整可能ブロック暗号（「ＴＢＣ」）に対するコール）に対する入力として役割を果たし、残りの（Ｂ−Ｎ）入力−ビット（ＸＲ）およびＴの組み合わせは、第１Ｎ−ビット調整可能ブロック暗号（「ＴＢＣ」）に対するトウィークとして役割を果たす。この調整可能ブロック暗号（「ＴＢＣ」）のＮ−ビット出力は、可変入力長調整可能暗号（「ＶＩＬＴＣ」）コールに対する初期化ベクトルとして役割を果たし、（Ｂ−Ｎ）−ビット出力（ＹＲ）を生成する。最後に、ＹＲおよびＴの組み合わせは、第２Ｎ−ビット調整可能ブロック暗号（「ＴＢＣ」）（例えば、Ｎ−ビット調整可能ブロック暗号（「ＴＢＣ」）に対するコール）に対するトウィークとして役割を果たす。第２Ｎ−ビット調整可能ブロック暗号（「ＴＢＣ」）は、初期化ベクトルを入力として取り込み、Ｎ−ビット出力（ＹＬ）を生成する。ＹＬとＹＲとの連結(concatenation)が、結果的に得られる出力となる。この連結の長さは正確にＢビットであるので、処理全体は入力から出力まで長さを保存することになる。
【００１９】
[017]  第１Ｎ−ビット調整可能ブロック暗号（「ＴＢＣ」）および第２Ｎ−ビット調整可能ブロック暗号（「ＴＢＣ」）は、同一の構造または異なる構造(structure)を有することができる。注記したように、第１Ｎ−ビット調整可能ブロック暗号（「ＴＢＣ」）および第２Ｎ−ビット調整可能ブロック暗号（「ＴＢＣ」）は、同じＮ−ビット調整可能ブロック暗号（「ＴＢＣ」）コンポーネントに対する２回のコールによって、異なる入力および出力を用いて、供給することができる。一実施態様では、第１Ｎ−ビット調整可能ブロック暗号（「ＴＢＣ」）および第２Ｎ−ビット調整可能ブロック暗号（「ＴＢＣ」）の内少なくとも１つはＬＲＷ２  ＴＢＣ構造(construction)（以下で定義する）であり、可変入力長調整可能暗号（「ＶＩＬＴＣ」）は反復ＬＲＷ２  ＴＢＣ構造（以下で定義する）である。他の実施態様では、第１Ｎ−ビット調整可能ブロック暗号（「ＴＢＣ」）および第２Ｎ−ビット調整可能ブロック暗号（「ＴＢＣ」）の内少なくとも１つはドメイン拡張ＣＬＲＷ２構造（以下で定義する）であり、可変入力長調整可能暗号（「ＶＩＬＴＣ」）は反復ＣＬＲＷ２構造（以下で定義する）である。更に一般的には、第１Ｎ−ビット調整可能ブロック暗号（「ＴＢＣ」）、第２Ｎ−ビット調整可能ブロック暗号（「ＴＢＣ」）、および可変入力長調整可能暗号（「ＶＩＬＴＣ」）は、特殊目的ハードウェアを使用して実装することができ、または汎用ハードウェア上で実行するソフトウェアを使用して実装することができる。
【００２０】
[018]  本明細書において説明する新技術の他の態様によれば、暗号化システムまたは復号システムのようなシステムが、固定長入力文字列、システムに対するトウィーク、および可変長入力文字列を処理して、固定長出力文字列および可変長出力文字列を生成する。システムに対するトウィークは、環境的特徴に基づいて設定することができる。この処理の一部として、本システムは、固定長初期化ベクトルを生成し、この固定長初期化ベクトルをトウィークとして使用して、可変入力長調整可能暗号（「ＶＩＬＴＣ」）によって可変長出力文字列を生成し、次いで固定長初期化ベクトルを曖昧にする。本システムは、固定長出力文字列および可変長出力文字列を出力する。
【００２１】
[019]  本明細書において説明する新技術の他の態様によれば、暗号化システムまたは復号システムのようなシステムが、Ｎ−キャラクタ入力文字列、システムに対するトウィーク、および可変長入力文字列を処理して、Ｎ−キャラクタ出力文字列および可変長出力文字列を生成する。この処理の一部として、本システムは、Ｎ−キャラクタ初期化ベクトルを生成し、このＮ−キャラクタ初期化ベクトルをトウィークとして使用して、可変入力長調整可能暗号（「ＶＩＬＴＣ」）によって可変長出力文字列を生成し、次いでＮ−キャラクタ初期化ベクトルを曖昧にする。本システムは、Ｎ−キャラクタ出力文字列および可変長出力文字列を出力する。
【００２２】
[020]  この処理は、例えば、（１）フォーマット保存暗号化、（２）フォーマット保存復号、または（３）何らかの他の暗号化または復号動作(activity)の一部にすることができる。暗号化では、Ｎ−キャラクタ入力文字列および可変長入力文字列は平文であり、Ｎ−キャラクタ出力文字列および可変長出力文字列は暗号文である。復号では、Ｎ−キャラクタ入力文字列および可変長入力文字列は暗号文であり、Ｎ−キャラクタ出力文字列および可変長出力文字列は平文である。
【００２３】
[021]  実施態様例では、Ｎ−キャラクタ初期化ベクトルは、第１固定入力長調整可能ブロック暗号（「ＦＩＬ  ＴＢＣ」）によって生成され、第２固定入力長調整可能ブロック暗号（「ＦＩＬ  ＴＢＣ」）によって曖昧にされて、Ｎ−キャラクタ出力文字列を生成する。Ｎ−キャラクタ初期化ベクトルは、第１固定入力長調整可能ブロック暗号（「ＦＩＬ  ＴＢＣ」）に対する入力であるＮ−キャラクタ入力文字列に基づいて、そして第１固定入力長調整可能ブロック暗号（「ＦＩＬ  ＴＢＣ」）に対するトウィークである、システムに対するトウィークおよび可変長入力文字列の組み合わせに基づいて、第１固定入力長調整可能ブロック暗号（「ＦＩＬ  ＴＢＣ」）によって生成される。可変長出力文字列は、可変入力長調整可能暗号（「ＶＩＬＴＣ」）に対するトウィークであるＮ−キャラクタ初期化ベクトルに基づいて、そして可変入力長調整可能暗号（「ＶＩＬＴＣ」）に対する入力である可変長入力文字列に基づいて、可変入力長調整可能暗号（「ＶＩＬＴＣ」）によって生成される。Ｎ−キャラクタ出力文字列は、第２固定入力長調整可能ブロック暗号（「ＦＩＬ  ＴＢＣ」）に対する入力であるＮ−キャラクタ初期化ベクトルに基づいて、そして第２固定入力長調整可能ブロック暗号（「ＦＩＬ  ＴＢＣ」）に対するトウィークである、システムに対するトウィークおよび可変長出力文字列の組み合わせに基づいて、第２固定入力長調整可能ブロック暗号（「ＦＩＬ  ＴＢＣ」）によって生成される。システム・トウィークは、環境的特徴に基づいて設定することができる。
【００２４】
[022]  本明細書において説明する新技術の他の態様によれば、暗号化システムまたは復号システムのようなシステムは、N−ビット入力文字列、システムに対するトウィークおよび可変長入力文字列を処理して、N−ビット出力文字列および可変長出力文字列を生成する。この処理の一部として、本システムは、N−ビット初期化ベクトルを生成し、Ｎ−ビット初期化ベクトルをトウィークとして使用して、可変入力長調整可能暗号（「ＶＩＬＴＣ」）によって可変長出力文字列を生成し、次いでＮ−ビット初期化ベクトルを曖昧にする。本システムは、Ｎ−ビット出力文字列および可変長出力文字列を出力する。
【００２５】
[023]  この処理は、例えば、（１）ディスク全体の暗号化、（２）ディスク全体の復号、（３）関連データ付き認証付暗号化、（４）関連データによる認証復号、あるいは（５）他の何らかの暗号化または復号動作の一部にすることができる。暗号化では、Ｎ−ビット入力文字列および可変長入力文字列は平文であり、Ｎ−ビット出力文字列および可変長出力は暗号文である。復号では、Ｎ−ビット入力文字列および可変長入力文字列は暗号文であり、Ｎ−ビット出力文字列および可変長出力文字列は平文である。
【００２６】
[024]  実施態様例では、Ｎ−ビット初期化ベクトルは、第１Ｎ−ビット調整可能ブロック暗号（「ＴＢＣ」）によって生成され、第２Ｎ−ビット調整可能ブロック暗号（「ＴＢＣ」）によって曖昧にされて、Ｎ−ビット出力文字列を生成する。Ｎ−ビット初期化ベクトルは、第１Ｎ−ビット調整可能ブロック暗号（「ＴＢＣ」）に対する入力であるＮ−ビット入力文字列に基づいて、そして第１Ｎ−ビット調整可能ブロック暗号（「ＴＢＣ」）に対するトウィークである、システムに対するトウィークおよび可変長入力文字列の組み合わせに基づいて、第１Ｎ−ビット調整可能ブロック暗号（「ＴＢＣ」）によって生成される。可変長出力文字列は、可変入力長調整可能暗号（「ＶＩＬＴＣ」）に対するトウィークであるＮ−ビット初期化ベクトルに基づいて、そして可変入力長調整可能暗号（「ＶＩＬＴＣ」）に対する入力である可変長入力文字列に基づいて、可変入力長調整可能暗号（「ＶＩＬＴＣ」）によって生成される。Ｎ−ビット出力文字列は、第２Ｎ−ビット調整可能ブロック暗号（「ＴＢＣ」）に対する入力であるＮ−ビット初期化ベクトルに基づいて、そして第２Ｎ−ビット調整可能ブロック暗号（「ＴＢＣ」）に対するトウィークである、システムに対するトウィークおよび可変長出力文字列の組み合わせに基づいて、第２Ｎ−ビット調整可能ブロック暗号（「ＴＢＣ」）によって生成される。システム・トウィークは、環境的特徴に基づいて設定することができる。
【００２７】
[025]  本明細書において説明する新技術の他の態様によれば、暗号化システムは、ヘッダおよびメッセージを受ける。この暗号化システムは、可変入力長調整可能暗号（「ＶＩＬＴＣ」）を使用してこのメッセージを処理し、関連データ付き認証付暗号化を行う。可変入力長調整可能暗号（「ＶＩＬＴＣ」）に対するトウィークは、少なくとも部分的にヘッダに基づく。暗号化システムは、ヘッダおよび暗号化メッセージ(encrypted message)を出力する。
【００２８】
[026]  実施態様例では、メッセージを処理するとき、暗号化システムは、ヘッダおよび再現情報(reconstruction information)を使用して修正ヘッダを決定し、メッセージおよび修正ヘッダを使用して修正メッセージを決定し、可変入力長調整可能暗号（「ＶＩＬＴＣ」）を、この可変入力長調整可能暗号（「ＶＩＬＴＣ」）に対するトウィークである修正ヘッダと共に使用して修正メッセージを暗号化する。暗号化システムは、再現情報を出力する。
【００２９】
[027]  対応する復号システムは、ヘッダおよび暗号化メッセージを受ける（任意の再現情報と共に）。復号システムは、可変入力長調整可能暗号（「ＶＩＬＴＣ」）を使用して暗号化メッセージを処理して、関連データによる認証復号を行う。可変入力長調整可能暗号（「ＶＩＬＴＣ」）に対するトウィークは、少なくとも部分的にヘッダに基づく。復号システムはメッセージを出力する。
【００３０】
[028]  実施態様例では、暗号化メッセージを処理するとき、復号システムは、ヘッダおよび再現情報を使用して修正ヘッダを決定し、修正ヘッダを可変入力長調整可能暗号（「ＶＩＬＴＣ」）に対するトウィークとして可変入力長調整可能暗号（「ＶＩＬＴＣ」）を使用して、暗号化メッセージを復号し、修正メッセージおよび修正ヘッダを使用してメッセージを決定する。
【００３１】
[029]  任意に、認証ステップのため、復号システムはメッセージが有効であるか否か確認するチェックを行う。例えば、所定数の「０」ビットが暗号化の間にメッセージに添付された場合、復号では、これらのビットの存在をチェックすることができる。このチェックが失敗した場合、復号はエラーを出力する。メッセージを通すためには多数の異なるチェックがあってもよく、出力されるエラー（１つまたは複数）は、どのチェック（の組み合わせ）が失敗したのかに応じて、異なってもよい。（これは、認証付暗号化の「認証」部分である。攻撃者が暗号化メッセージを改竄した場合、一旦復号されたなら、恐らくもはや有効ではなくなるであろう。）
[030]  可変入力長調整可能暗号（「ＶＩＬＴＣ」）を組み立てて使用する新技術は、方法の一部として、この方法を実行するように構成された計算システムの一部として、または計算システムにこの方法を実行させるコンピュータ実行可能命令を格納する有形コンピュータ読み取り可能媒体の一部として実現することができる。種々の新技術は、組み合わせてまたは別個に使用することができる。
【００３２】
[031]  本発明の以上のおよびその他の目的、特徴、ならびに利点は、以下の詳細な説明から一層明らかになるであろう。詳細な説明は、添付図面を参照しながら進められる。
【図面の簡単な説明】
【００３３】
【図１】図１は、本明細書において説明する、ある実施形態を実現することができる計算システムを一般化して示す図である。
【図２】図２は、可変入力長調整可能暗号（「ＶＩＬＴＣ」）の組み立ておよび使用のためのアーキテクチャ例を示す図である。
【図３Ａ】図３Ａ〜図３Ｃは、初期化ベクトルの保護を伴う、可変入力長調整可能暗号（「ＶＩＬＴＣ」）の組み立てを一般化して示す図である。
【図３Ｂ】図３Ａ〜図３Ｃは、初期化ベクトルの保護を伴う、可変入力長調整可能暗号（「ＶＩＬＴＣ」）の組み立てを一般化して示す図である。
【図３Ｃ】図３Ａ〜図３Ｃは、初期化ベクトルの保護を伴う、可変入力長調整可能暗号（「ＶＩＬＴＣ」）の組み立てを一般化して示す図である。
【図４】図４は、初期化ベクトルを保護して、可変入力長調整可能暗号（「ＶＩＬＴＣ」）を使用するための技法を一般化して示すフローチャートである。
【図５Ａ】図５Ａ〜図５Ｃは、初期化ベクトルを保護する可変入力長調整可能暗号（「ＶＩＬＴＣ」）の第１実施例を示す図である。
【図５Ｂ】図５Ａ〜図５Ｃは、初期化ベクトルを保護する可変入力長調整可能暗号（「ＶＩＬＴＣ」）の第１実施例を示す図である。
【図５Ｃ】図５Ａ〜図５Ｃは、初期化ベクトルを保護する可変入力長調整可能暗号（「ＶＩＬＴＣ」）の第１実施例を示す図である。
【図６Ａ】図６Ａ〜図６Ｃは、初期化ベクトルを保護する可変入力長調整可能暗号（「ＶＩＬＴＣ」）の第２実施例を示す図である。
【図６Ｂ】図６Ａ〜図６Ｃは、初期化ベクトルを保護する可変入力長調整可能暗号（「ＶＩＬＴＣ」）の第２実施例を示す図である。
【図６Ｃ】図６Ａ〜図６Ｃは、初期化ベクトルを保護する可変入力長調整可能暗号（「ＶＩＬＴＣ」）の第２実施例を示す図である。
【図７】図７は、可変入力長調整可能暗号（「ＶＩＬＴＣ」）を使用する、関連データ付き認証付暗号化の技法を一般化して示すフローチャートである。
【図８】図８は、可変入力長調整可能暗号（「ＶＩＬＴＣ」）を使用する、関連データによる認証復号の技法を一般化して示すフローチャートである。
【図９】図９は、本明細書において説明する新技術の一部について理論的正当化の態様を示す擬似コード・リストである。
【図１０】図１０は、本明細書において説明する新技術の一部について理論的正当化の態様を示す擬似コード・リストである。
【図１１】図１１は、本明細書において説明する新技術の一部について理論的正当化の態様を示す擬似コード・リストである。
【発明を実施するための形態】
【００３４】
[040]  詳細な説明では、可変入力長調整可能暗号（「ＶＩＬＴＣ」）の構造および使用における新技術を紹介する。場合によっては、これらの可変入力長調整可能暗号（「ＶＩＬＴＣ」）は、効率的な処理遂行(performance)で安全性強化を提供するために、暗号化／復号システム外部への露出から保護された初期化ベクトルを使用する。他の場合では、関連データ付き認証付暗号化／復号を信頼性高くしかも効率的に実現するために、可変入力長調整可能暗号（「ＶＩＬＴＣ」）を使用する。
【００３５】
[041]  本明細書において説明する新技術の一態様によれば、可変入力長調整可能暗号（「ＶＩＬＴＣ」）は、保護された初期化ベクトル（「ＩＶ」）を使用する。ある例では、保護された初期化ベクトル（「ＩＶ」）によって可変入力長調整可能暗号（「ＶＩＬＴＣ」）を組み立てることによって、長さを保存する調整可能暗号を構築するための簡素なモジュール型手法を提供する。この調整可能暗号は、（１）本質的に任意の長さの平文入力を取り込むことができ、（２）このタイプのプリミティブに対してできるだけ強い安全性プロパティ（強調整可能擬似ランダム置換（「ＳＴＰＲＰ」：strong, tweakable-pseudorandom permutation）であること）を達成し、（３）保護された初期化ベクトル（「ＩＶ」）による（以下「ＩＶ保護」と称する）可変入力長調整可能暗号（「ＶＩＬＴＣ」）の２ｎ／２回の呼び出し(invocation)という「誕生日限界」(birthday-bound)をはるかに超えて、初期化ベクトル（「ＩＶ」）・強調整可能擬似ランダム置換（「ＳＴＰＲＰ」）保護可変入力長調整可能暗号（「ＶＩＬＴＣ」）を強調整可能擬似ランダム置換（「ＳＴＰＲＰ」）−安全にするために、ｎ−ビット・プリミティブによって実現することができる（誕生日限界という用語は、攻撃に対抗する安全性のレベルを意味する。誕生日限界の安全性を有する可変入力長調整可能暗号（「ＶＩＬＴＣ」）構造では、２ｎ／２ビットが暗号化された(enciphered)時間によって安全性保証が劇的に弱化される。誕生日限界を超えた(beyond-birthday-bound)安全性を有する可変入力長調整可能暗号（「ＶＩＬＴＣ」）構造は、２ｎ／２個のビットが暗号化された後も長く安全なままであり続けることができる）。ある効率の尺度によって、初期化ベクトル（「ＩＶ」）保護可変入力長調整可能暗号（「ＶＩＬＴＣ」）の誕生日を超えて安全なインスタンス化(beyond-birthday secure instantiation)は、誕生日限界までしか安全でない既存の構造に負けない。
【００３６】
[042]  初期化ベクトル（「ＩＶ」）保護可変入力長調整可能暗号（「ＶＩＬＴＣ」）には多くの暗号関連用途がある。具体的には、大規模な保存データのシナリオでは、１つの鍵によって保護されるべきデータ量が、通例、鍵を容易に再交渉することができるシナリオにおけるよりも多く、初期化ベクトル（「ＩＶ」）保護可変入力長調整可能暗号（「ＶＩＬＴＣ」）は適したレベルの安全性を効率的に提供することができる。例えば、初期化ベクトル（「ＩＶ」）保護可変入力長調整可能暗号（「ＶＩＬＴＣ」）は、完全ディスク暗号化（「ＦＤＥ」：full-disk encryption）および復号、フォーマット保存暗号化（「ＦＰＥ」）および復号、または関連データ付き認証付暗号化（「ＡＥＡＤ」）および復号に使用することができる。あるいは、初期化ベクトル（「ＩＶ」）保護可変入力長調整可能暗号（「ＶＩＬＴＣ」）は、他の暗号化／復号の用途にも使用することができる。
【００３７】
[043]  本明細書において説明する新技術の他の態様によれば、調整可能暗号が関連データ付き認証付暗号化（「ＡＥＡＤ」）および対応する復号に使用される。関連データ付き認証付暗号化（「ＡＥＡＤ」）に使用される可変入力長調整可能暗号（「ＶＩＬＴＣ」）は、保護された初期化ベクトル（「ＩＶ」）構造または何らかの他の可変入力長調整可能暗号（「ＶＩＬＴＣ」）構造を使用してインスタンス化することができる。調整可能暗号を関連データ付き認証付暗号化（「ＡＥＡＤ」）に使用することにより、多くの利点を得ることができる。例えば、調整可能暗号を関連データ付き認証付暗号化（「ＡＥＡＤ」）に使用することにより、多数のタイプの復号エラーの報告を安全に扱うのに役立てることができる。更に、平文または関連するデータ入力のいずれかに現れる既存のノンス（nonces）、ランダム性、または冗長性の内任意のものを利用することによって、暗号文の膨張(expansion)を排除することができる。初期化ベクトル（「ＩＶ」）保護可変入力長調整可能暗号（「ＶＩＬＴＣ」）を（そのパラメータをしかるべく設定して）使用することにより、誕生日限界を超えた安全性を有する関連データ付き認証付暗号化（「ＡＥＡＤ」）方式が可能になる。
【００３８】
[044]  本明細書において説明した例には、種々の代替物が可能である。開示した技術の種々の態様は、組み合わせてまたは別個に使用することができる。異なる実施形態は、説明した新技術の内１つ以上を使用する。本明細書において説明する新技術の一部は、背景において注記した問題の内１つ以上に取り組む。通例、所与の技法／ツールはこのような問題の全てを解決するのではない。
【００３９】
Ｉ．計算システム例
[045]  図１は、説明する新技術の内いくつかを実現することができる、適した計算システム（１００）を一般化した例を示す。計算システム（１００）は、使用範囲や機能に関して何ら限定を示唆することを意図するのではない。何故なら、本願の新技術は多様な汎用または特殊目的計算システムにおいて実現できるからである。
【００４０】
[046]  図１を参照すると、計算システム（１００）は、１つ以上の処理ユニット（１１０、１１５）およびメモリ（１２０、１２５）を含む。処理ユニット（１１０、１１５）は、コンピュータ実行可能命令を実行する。処理ユニットは、汎用中央処理ユニット（「ＣＰＵ」）、特定用途集積回路（「ＡＳＩＣ」）におけるプロセッサ、または任意の他のタイプのプロセッサとすることができる。多重処理システムでは、処理パワーを増大するために、多数の処理ユニットがコンピュータ実行可能命令を実行する。例えば、図１は、中央処理ユニット（１１０）、およびグラフィクス処理ユニットまたは補助処理ユニット（１１５）も示す。有形メモリ（１２０、１２５）は、揮発性メモリ（例えば、レジスタ、キャッシュ、ＲＡＭ）、不揮発性メモリ（例えば、ＲＯＭ、ＥＥＰＲＯＭ、フラッシュ・メモリ等）、または処理ユニット（１つまたは複数）によってアクセス可能な、これら２つの何らかの組み合わせであってもよい。メモリ（１２０、１２５）は、処理ユニット（１つまたは複数）による実行に適したコンピュータ実行可能命令の形態で、可変入力長調整可能暗号（「ＶＩＬＴＣ」）を組み立てるまたは使用するための１つ以上の新技術を実現するソフトウェア（１８０）を格納する。
【００４１】
[047]  計算システムは、追加の機構を有することもできる。例えば、計算システム（１００）は、ストレージ（１４０）、１つ以上の入力デバイス（１５０）、１つ以上の出力デバイス（１６０）、および１つ以上の通信接続（１７０）を含む。バス、コントローラ、またはネットワークのような相互接続メカニズム（図示せず）が、計算システム（１００）のコンポーネントを相互接続する。通例、オペレーティング・システム・ソフトウェア（図示せず）が、計算システム（１００）において実行する他のソフトウェアのために動作環境を提供し、計算システム（１００）のコンポーネントの動作(activity)を調整する。
【００４２】
[048]  有形ストレージ（１４０）（コンピュータ読み取り可能ストレージとも呼ぶ）は、リムーバブルまたは非リムーバブルでもよく、磁気ディスク、磁気テープまたはカセット、ＣＤ−ＲＯＭ、ＤＶＤ、または情報を格納するために使用することができ更に計算システム（１００）内においてアクセスすることができる任意の他の媒体を含む。ストレージ（１４０）は、可変入力長調整可能暗号（「ＶＩＬＴＣ」）を組み立てるまたは使用するための１つ以上の新技術を実現するソフトウェア（１８０）の命令を格納する。
【００４３】
[049]  入力デバイス（１つまたは複数）（１５０）は、キーボード、マウス、ペンまたはトラックボール、音声入力デバイス、ジェスチャ入力を受けるためのタッチスクリーン、スキャン・デバイス、あるいは計算システム（１１０）に入力を供給するその他のデバイスというようなタッチ入力デバイスであってもよい。出力デバイス（１つまたは複数）（１６０）は、ディスプレイ（例えば、タッチスクリーン）、プリンタ、スピーカ、ＣＤ−ライタ、または計算システム（１００）からの出力を供給する他のデバイスであってもよい。
【００４４】
[050]  通信接続（１つまたは複数）（１７０）は、通信媒体を通じての他の計算エンティティへの通信を可能にする。通信媒体は、コンピュータ実行可能命令のような情報、オーディオまたはビデオ入力または出力、あるいは変調データ信号における他のデータを伝達する。変調データ信号とは、この信号内に情報をエンコードするようなやり方で、その特性の内１つ以上が設定されたまたは変化させられた信号である。一例として、そして限定ではなく、通信媒体は電気、光、ＲＦ、または他のキャリアを使用することができる。
【００４５】
[051]  本願の新技術については、コンピュータ読み取り可能媒体という一般的なコンテキストで説明することができる。コンピュータ読み取り可能媒体は、計算環境内においてアクセスすることができる、任意の入手可能な有形媒体である。一例として、そして限定ではなく、計算システム（１００）では、コンピュータ読み取り可能媒体はメモリ（１２０、１２５）、ストレージ（１４０）、および以上の内任意のものの組み合わせを含む。
【００４６】
[052]  本願の新技術については、計算システムにおいて目標の実プロセッサまたは仮想プロセッサ上で実行されるプログラム・モジュール（コンピュータ・プログラム製品とも呼ぶ）に含まれるような、コンピュータ実行可能命令（マシン読み取り可能命令とも呼ぶ）という一般的なコンテキストで説明することができる。一般に、プログラム・モジュールは、ルーチン、プログラム、ライブラリ、オブジェクト、クラス、コンポーネント、データ構造等を含み、特定のタスクを実行するか、または特定の抽象データ型を実装する。プログラム・モジュールの機能は、種々の実施形態において望まれる通りに組み合わされてもよく、またはプログラム・モジュール間で分割されてもよい。プログラム・モジュールのコンピュータ実行可能命令は、ローカルまたは分散型計算システム内において実行されてもよい。
【００４７】
[053]  「システム」および「デバイス」という用語は、本明細書では相互交換可能に使用される。コンテキストが明らかに別のことを示さなければ、いずれの用語も計算システムや計算デバイスのタイプについて何の限定も暗示しない。一般に、計算システムまたは計算デバイスは、ローカルまたは分散型であることができ、特殊目的ハードウェアおよび／または汎用ハードウェアの任意の組み合わせを含むことができ、本明細書において説明する機能をソフトウェアが実現する。
【００４８】
[054]  また、開示する方法は、開示する方法の内任意のものを実行するように構成された特殊計算ハードウェアを使用して実現することもできる。例えば、開示する方法は、開示する方法の内任意のものを実現するように特別に設計または構成された集積回路によって実現することができる（例えば、ＡＳＩＣディジタル信号処理ユニットのようなＡＳＩＣ、グラフィクス処理ユニット、またはフィールド・プログラマブル・ゲート・アレイのようなプログラマブル・ロジック・デバイス）。
【００４９】
[055]  提示の目的上、詳細な説明では、計算システムにおけるコンピュータ動作を説明するために、「判定する」、「供給する」、および「使用する」というような用語を使用する。これらの用語は、コンピュータによって実行される動作に対する上位抽象化であり、人間によって行われる行為と混同されるべきでない。これらの用語に対応する実際のコンピュータ動作は、実施態様に応じて様々に変化する。
【００５０】
ＩＩ．可変入力長調整可能暗号（「ＶＩＬＴＣ」）の組み立てまたは使用のためのアーキテクチャ例
[056]  図２は、可変入力長調整可能暗号（「ＶＩＬＴＣ」）の組み立ておよび使用のためのアーキテクチャ例（２００）を示す。具体的には、このアーキテクチャは可変入力長調整可能暗号（「ＶＩＬＴＣ」）を使用する暗号化／復号サービス（２２２）を含む。
【００５１】
[057]  図２において、アプリケーション（２１０、２１２）は、オペレーティング・システム（２２０）と相互作用するソフトウェアを表す。アプリケーション（２１０、２１２）は、データベース・トランザクション処理または分析アプリケーション、ウェブ・ブラウザ、ワード・プロセッサまたはその他の生産性ソフトウェア（ファイル探索機能付き）、メッセージ・サービスあるいは暗号化または復号を使用する任意の他のタイプのアプリケーションを含むことができる。図２は２つのアプリケーションを示すが、アーキテクチャ（２００）はそれよりも多いまたは少ないアプリケーションを含むことができる。
【００５２】
[058]  アプリケーション（２１０、２１２）は、暗号化／復号サービス（２２２）を使用するために、オペレーティング・システム（２２０）と相互作用する。アプリケーション（２１０、２１２）またはオペレーティング・システム（２２０）の内１つによって要求されると、暗号化／復号サービス（２２２）は、ディスク・ストレージ（２３０）または主メモリ（２４０）に格納されているデータ（例えば、データベース用）を暗号化することができる。逆に、暗号化／復号サービス（２２２）は、アプリケーション（２１０、２１２）またはオペレーティング・システム（２２０）の内１つによって要求されたデータを復号することができる。例えば、完全ディスク暗号化（「ＦＤＥ」）では、暗号化／復号サービス（２２２）は、透過的に、ディスク・ストレージ（２３０）に格納されているデータを暗号化し、ディスク・ストレージ（２３０）から戻されたデータを復号する。また、フォーマット保存暗号化（「ＦＰＥ」）では、暗号化／復号サービス（２２２）は、暗号化されないデータと同じフォーマットを有するように、ディスク・ストレージ（２３０）または主メモリ（２４０）に格納されているデータを暗号化する。例えば、クレジット・カード番号のようなデータは、暗号化された値もクレジット・カード番号としてフォーマットされたままとなるように暗号化される。他の例として、関連データ付き認証付暗号化（「ＡＥＡＤ」）では、暗号化／復号サービス（２２２）は、アプリケーション（２１０、２１２）の内１つに対するヘッダを有するメッセージを暗号化し、アプリケーション（２１０、２１２）の１つのために暗号化メッセージを復号する。
【００５３】
ＩＩＩ．表記法および原理
[059]  この章では、詳細な説明の残りの部分において使用される表記法について説明する。また、本明細書において説明する暗号化／復号システムのある種の態様について、動作原理も説明する。
【００５４】
[060]  一般に、
【００５５】
【数３】
2016540266.tif 000005
【００５６】
は、負でない整数の集合を表す。
【００５７】
【数４】
2016540266.tif 000006
【００５８】
（集合
【００５９】
【数５】
2016540266.tif 000007
【００６０】
のメンバである数ｎ）について、｛０，１｝ｎは、全てのｎ−ビット二進文字列の集合を示し、｛０，１｝＊は、全ての（有限）二進文字列の集合を示す。記号εは空文字列を示す。
【００６１】
[061]  文字列ｓおよびｔは有限二進文字列（即ち、ｓ、ｔ∈｛０，１｝＊）であると仮定する。値|ｓ|は、ビットを単位としたｓの長さである。値
【００６２】
【数６】
2016540266.tif 000008
【００６３】
であり、ここで、ｓ||ｔは、文字列ｓおよびｔを連結することによって形成される文字列を示す。ｓ∈｛０，１｝ｎｍの場合、ある
【００６４】
【数７】
2016540266.tif 000009
【００６５】
について、式
【００６６】
【数８】
2016540266.tif 000010
【００６７】
は、各ｓｉが、長さ｜ｓｉ｜＝ｎ、ｓ＝ｓ１，ｓ２，．．．ｓｍとなるように定義されることを意味する。コンテキストからｎが暗黙的である場合、この表記から省略されてもよい。ｓ＝ｂ１，ｂ２，．．．ｂｎがｎ−ビット文字列（各ｂｉ∈｛０，１｝）である場合、文字列sの一部は以下のように表される。
【００６８】
【数９】
2016540266.tif 000011
【００６９】
【数１０】
2016540266.tif 000012
【００７０】
【数１１】
2016540266.tif 000013
【００７１】
[062]  文字列
【００７２】
【数１２】
2016540266.tif 000014
【００７３】
は、文字列ｓおよびｔのビット毎の排他的論理和（「ＸＯＲ」）である。例えば、｜ｓ｜＜｜ｔ｜の場合、
【００７４】
【数１３】
2016540266.tif 000015
【００７５】
はｓおよび
【００７６】
【数１４】
2016540266.tif 000016
【００７７】
のビット毎のＸＯＲである。
[063]  ｎ≦ｍｉｎ（Ｒ）として、
【００７８】
【数１５】
2016540266.tif 000017
【００７９】
および
【００８０】
【数１６】
2016540266.tif 000018
【００８１】
と仮定すると、文字列
【００８２】
【数１７】
2016540266.tif 000019
【００８３】
が得られ、記号の濫用により、
【００８４】
【数１８】
2016540266.tif 000020
【００８５】
となる。有限集合
【００８６】
【数１９】
2016540266.tif 000021
【００８７】
を仮定すると、式
【００８８】
【数２０】
2016540266.tif 000022
【００８９】
は、ランダム変数Ｘが
【００９０】
【数２１】
2016540266.tif 000023
【００９１】
からランダムに均一にサンプリングされることを意味する。全域にわたり、区別される記号⊥は、｛⊥｝を除いていずれの集合の一部でもないと仮定する。ある範囲内にあることが分かっている整数ｎを仮定すると、＜ｎ＞は、ｎのある固定長（例えば、６４ビット）のエンコード処理(encoding)を示す。例えば、＜０＞は値０の６４−ビット・エンコード処理を示すことができる。
【００９２】
[064]  関数
【００９３】
【数２２】
2016540266.tif 000024
【００９４】
その第１引数を添え字付き鍵として書くと、
【００９５】
【数２３】
2016540266.tif 000025
【００９６】
の全ての別個の値について確率が、
【００９７】
【数２４】
2016540266.tif 000026
【００９８】
（ここで、確率は、
【００９９】
【数２５】
2016540266.tif 000027
【０１００】
を超える）である場合、関数Ｈは∈−殆ど不偏的(∈-almost universal)（∈−ＡＵ））となる。同様に、全ての別個のＸ，
【０１０１】
【数２６】
2016540266.tif 000028
【０１０２】
および
【０１０３】
【数２７】
2016540266.tif 000029
【０１０４】
について確率が、
【０１０５】
【数２８】
2016540266.tif 000030
【０１０６】
である場合、 関数Ｈは∈−殆ど２−ＸＯＲ不偏的(∈-almost 2-XOR universal)となる。
[065]  アドバーサリー(adversary)とは、０個以上のオラクル(oracle)を入力として取り込むアルゴリズムのことである。アドバーサリーは、何らかの出力を戻す前に、ブラックボックス的に質問する。アドバーサリーはランダムであってもよい。表記Ａｆ⇒ｂは、アドバーサリーＡが、オラクルｆをその入力として実行した後に、ｂを出力するというイベントを示す。
【０１０７】
[066]  ときには、アドバーサリーが相互作用することができるオラクルの擬似コード記述、およびこのような相互作用を設定するまたそうでなければ関係付ける手順を与えると便利である。これらの記述をゲームと呼ぶ。ゲームは、１組の手順を含み、アドバーサリーＡを入力として取り込む特殊な「主」手順を含む。
【０１０８】
【数２９】
2016540266.tif 000031
【０１０９】
は、ゲームＧの主手順が、アドバーサリーＡが入力として与えられたときにｙを出力する確率である。主手順が明示的に与えられない場合、Ｍａｉｎ（Ａ）は単にＡを実行し、（コンテキストから明確になるある順序で）残りの手順をオラクルとしてそれに供給し、次いでＡの出力を戻す。
[067]  
【０１１０】
【数３０】
2016540266.tif 000032
【０１１１】
は、非空集合であり、そして文字列
【０１１２】
【数３１】
2016540266.tif 000033
【０１１３】
である。調整可能暗号は、マッピング
【０１１４】
【数３２】
2016540266.tif 000034
【０１１５】
であり、全ての
【０１１６】
【数３３】
2016540266.tif 000035
【０１１７】
について、調整可能暗号
【０１１８】
【数３４】
2016540266.tif 000036
【０１１９】
は 
【０１２０】
【数３５】
2016540266.tif 000037
【０１２１】
上の置換であるというプロパティを有する。鍵は、通例、添え字として示されるので、
【０１２２】
【数３６】
2016540266.tif 000038
【０１２３】
となる。調整可能暗号
【０１２４】
【数３７】
2016540266.tif 000039
【０１２５】
は、反転可能であり、
【０１２６】
【数３８】
2016540266.tif 000040
【０１２７】
で示される。
【０１２８】
【数３９】
2016540266.tif 000041
【０１２９】
は、鍵空間を示し、
【０１３０】
【数４０】
2016540266.tif 000042
【０１３１】
はトウィーク空間を示し、
【０１３２】
【数４１】
2016540266.tif 000043
【０１３３】
はメッセージ空間を示す。調整可能暗号
【０１３４】
【数４２】
2016540266.tif 000044
【０１３５】
は、全ての
【０１３６】
【数４３】
2016540266.tif 000045
【０１３７】
について、
【０１３８】
【数４４】
2016540266.tif 000046
【０１３９】
である場合、長さを保存する。調整可能暗号のトウィークまたはメッセージ空間を制限すると他のオブジェクトが生ずる。あるｎ＞０についてメッセージ空間
【０１４０】
【数４５】
2016540266.tif 000047
【０１４１】
であるとき、
【０１４２】
【数４６】
2016540266.tif 000048
【０１４３】
はブロック・サイズがｎの調整可能ブロック暗号（「ＴＢＣ」）である。更に一般化すると、ｎーキャラクタ
【０１４４】
【数４７】
2016540266.tif 000049
【０１４５】
は、メッセージ空間
【０１４６】
【数４８】
2016540266.tif 000050
【０１４７】
にわたる置換の一群であり、調整可能ブロック暗号（「ＴＢＣ」）における各置換は、鍵およびトウィークに関連付けられる。
【０１４８】
【数４９】
2016540266.tif 000051
【０１４９】
のとき、トウィークは暗示的であり、暗号
【０１５０】
【数５０】
2016540266.tif 000052
【０１５１】
を与える。ここでＥＫ（・）は、
【０１５２】
【数５１】
2016540266.tif 000053
【０１５３】
上の（長さ保存）置換であり、ＥＫ−１はその逆である。最後に、メッセージ空間
【０１５４】
【数５２】
2016540266.tif 000054
【０１５５】
および
【０１５６】
【数５３】
2016540266.tif 000055
【０１５７】
のとき、従来のブロック暗号は、
【０１５８】
【数５４】
2016540266.tif 000056
【０１５９】
となる。
[068]  値Ｎ（大文字）は、Ｎ−ビット調整可能ブロック暗号（「ＴＢＣ」）またはＮキャラクタ調整可能ブロック暗号（「ＴＢＣ」）について入力文字列の長さ、または可変入力長調整可能暗号（「ＶＩＬＴＣ」）について初期化ベクトル（「ＩＶ」）の長さを示す。Ｎ−ビット調整可能ブロック暗号（「ＴＢＣ」）および可変入力長調整可能暗号（「ＶＩＬＴＣ」）は、ｎ−ビット・ブロック暗号から組み立てることができ、ここでｎ（小文字）はブロック暗号のブロック・サイズを示す。ある例では、Ｎ＝ｎとなる。他の例では、Ｎ＝２ｎとなる。
【０１６０】
[069]  
【０１６１】
【数５５】
2016540266.tif 000057
【０１６２】
は、
【０１６３】
【数５６】
2016540266.tif 000058
【０１６４】
上における全ての置換の集合を示す。
【０１６５】
【数５７】
2016540266.tif 000059
【０１６６】
は、鍵空間
【０１６７】
【数５８】
2016540266.tif 000060
【０１６８】
およびメッセージ空間
【０１６９】
【数５９】
2016540266.tif 000061
【０１７０】
を有する全ての暗号の集合である。
【０１７１】
【数６０】
2016540266.tif 000062
【０１７２】
が集合であるとき、
【０１７３】
【数６１】
2016540266.tif 000063
【０１７４】
は、全ての関数
【０１７５】
【数６２】
2016540266.tif 000064
【０１７６】
の集合である。調整可能暗号は次の通りである
【０１７７】
【数６３】
2016540266.tif 000065
【０１７８】
調整可能擬似ランダム置換（「ＴＰＲＰ」）および強いＴＰＲＰ（強調整可能擬似ランダム置換（「ＳＴＰＲＰ」））の利点尺度(advantage measure)は、次のようになる。
【０１７９】
【数６４】
2016540266.tif 000066
【０１８０】
ここで、各場合において、アドバーサリーＡは、指示された数のオラクルを取り込む。調整可能擬似ランダム置換（「ＴＰＲＰ」）および強調整可能擬似ランダム置換（「ＳＴＰＲＰ」）実験双方に対して、アドバーサリーＡは決してオラクルに対する質問を繰り返さない。また、強調整可能擬似ランダム置換（「ＳＴＰＲＰ」）利点尺度について、これは、アドバーサリーＡがその最も左側のオラクルに（Ｔ，Ｘ）を質問し、見返りにＹを受けた場合、アドバーサリーＡは決してその最も右のオラクルに（Ｔ，Ｙ）を質問しないこと、そしてその逆も意味する。
【０１８１】
[070]  関連尺度、ＳＲＮＤ利点は、次のように定義される。
【０１８２】
【数６５】
2016540266.tif 000067
【０１８３】
ここで、
【０１８４】
【数６６】
2016540266.tif 000068
【０１８５】
オラクルは、全てのＴおよびＸに対して、その第２入力｜＄（Ｔ，Ｘ）｜＝｜Ｘ｜と長さが等しいランダム文字列を出力する。以上の３つの利点に対するアドバーサリーは、それらのオラクル・質問（Ｔ１，Ｘ１）、．．．（Ｔｑ，Ｘｑ）のトランスクリプト(transcript)が任意のｉ≠ｊに対してＴｉ＝Ｔｊを含まない場合、ノンス制約付き(nonce-respecting)である。
【０１８６】
[071]  暗号
【０１８７】
【数６７】
2016540266.tif 000069
【０１８８】
について、擬似ランダム置換（「ＰＲＰ」）および強擬似ランダム置換（「ＳＰＲＰ」）の利点尺度は、次のように定義される。
【０１８９】
【数６８】
2016540266.tif 000070
【０１９０】
ここで、各場合において、アドバーサリーＡは、示された数のオラクルを取り込む。
[072]  ３つのアドバーサリー・リソース(adversarial resource)を追跡する。時間複雑性ｔ、オラクルの質問数ｑ、およびこれらの質問の全長μとする。アドバーサリーＡの時間複雑性は、その包絡確率実験（鍵のサンプリング、オラクルの計算等を含む）の複雑性を含むと定義され、パラメータｔは、利点尺度において双方の実験に要した、アドバーサリーＡの最大時間複雑性であると定義される。
【０１９１】
ＩＶ．初期化ベクトル（「ＩＶ」）保護可変入力長調整可能暗号（「ＶＩＬＴＣ」）の一般化された構造および使用
[073]  図３ａから図３ｃは、初期化ベクトルが保護された可変入力長調整可能暗号（「ＶＩＬＴＣ」）の構造（３００、３０１、３０２）を一般化して示す。一般化された構造（３００、３０１、３０２）は、暗号化に使用することができ、平文の固定長入力文字列ＸＬおよび可変長入力文字列ＸＲが、暗号文の固定長出力文字列ＹＬおよび可変長出力文字列ＹＲに変換される。また、一般化された構造（３００、３０１、３０２）は、復号にも使用することができ、暗号文の固定長入力文字列ＹＬおよび可変長入力文字列ＹＲが、平文の固定長出力文字列ＸＬおよび可変長出力文字列ＸＲに変換される。
【０１９２】
[074]  図３ａの構造（３００）では、第１固定入力長調整可能ブロック暗号（「ＦＩＬ  ＴＢＣ」）（３２０ａ）および第２固定入力長調整可能ブロック暗号（「ＦＩＬ  ＴＢＣ」）（３４０ａ）が、固定長初期化ベクトル（３２８ａ）をシステム外部への露出から保護する。バッファ（３１０）が、固定長入力文字列（３１１ａ）および可変長入力文字列（３１２）を格納する。第１固定入力長調整可能ブロック暗号（「ＦＩＬ  ＴＢＣ」）（３２０ａ）は、固定長初期化ベクトル（３２８ａ）を生成するように構成されている。例えば、第１固定入力長調整可能ブロック暗号（「ＦＩＬ  ＴＢＣ」）（３２０ａ）は、固定長入力文字列（３１１ａ）が入力される毎にこれを使用して固定長初期化ベクトル（３２８ａ）を生成し、更にシステムに対するトウィーク（３１８）および可変長入力文字列（３１２）の組み合わせ（例えば、連結(concatenation)または他の調節）をそのトウィークとして生成するように構成されている。図３ａでは、第１固定入力長調整可能ブロック暗号（「ＦＩＬ  ＴＢＣ」）（３２０ａ）（および第２固定入力長調整可能ブロック暗号（「ＦＩＬ  ＴＢＣ」）（３４０ａ））の網掛け部分(filled-in portion)は、トウィーク入力を表す。トウィーク（３１８）の値は、システムの環境的特徴（例えば、完全ディスク暗号化（「ＦＤＥ」）では論理ハード・ディスク・セクタＩＤ、メモリ・アドレス、フォーマット保存暗号化（「ＦＰＥ」）ではクレジット・カード番号の下４桁）に基づくことができる。
【０１９３】
[075]  図３ａでは、可変入力長調整可能暗号（「ＶＩＬＴＣ」）（３３０）は、固定長初期化ベクトル（３２８ａ）をトウィークとして使用して、可変長出力文字列（３５２）を生成するように構成されている。例えば、可変入力長調整可能暗号（「ＶＩＬＴＣ」）（３３０）は、固定長初期化ベクトル（３２８ａ）をそのトウィークとして使用し、可変長入力文字列（３１２）をその入力として使用し、可変長出力文字列（３５２）を生成するように構成されている。
【０１９４】
[076]  図３ａでは、第２固定入力長調整可能ブロック暗号（「ＦＩＬ  ＴＢＣ」）（３４０ａ）は、固定長出力文字列（３５１ａ）を生成するように構成されている。例えば、第２固定入力長調整可能ブロック暗号（「ＦＩＬ  ＴＢＣ」）（３４０ａ）は、固定長初期化ベクトル（３２８ａ）をその入力として使用し、トウィーク（３１８）および可変長出力文字列（３５２）の組み合わせ（例えば、連結またはその他の調節）をそのトウィークとして使用して、固定長出力文字列（３５１ａ）を生成するように構成されている。通例、第１固定入力長調整可能ブロック暗号（「ＦＩＬ  ＴＢＣ」）（３２０ａ）および第２固定入力長調整可能ブロック暗号（「ＦＩＬ  ＴＢＣ」）（３４０ａ）は、トウィーク（３１８）に対して同じ値を使用する。他のバッファ（３５０）が、固定長出力文字列（３５１ａ）および可変長出力文字列（３５２）を格納する。
【０１９５】
[077]  図３ｂは、フォーマット保存暗号化および復号に適応する構成とした構造（３００）の変種を示す。図３ｂの構造（３０１）では、第１Ｎ−キャラクタ調整可能ブロック暗号（「ＴＢＣ」）（３２０ｂ）および第２Ｎ−キャラクタ調整可能ブロック暗号（「ＴＢＣ」）（３４０ｂ）が、Ｎ−キャラクタ初期化ベクトル（３２８ｂ）をシステム外部への露出から保護する。バッファ（３１０）が、Ｎ−キャラクタ入力文字列（３１１ｂ）および可変長入力文字列（３１２）を格納する。第１Ｎ−キャラクタ調整可能ブロック暗号（「ＴＢＣ」）（３２０ｂ）は、Ｎ−キャラクタ初期化ベクトル（３２８ｂ）を生成するように構成されている。例えば、第１Ｎ−キャラクタ調整可能ブロック暗号（「ＴＢＣ」）（３２０ｂ）は、Ｎ−キャラクタ入力文字列（３１１ｂ）をその入力として使用し、システムに対するトウィーク（３１８）および可変長入力文字列（３１２）の組み合わせ（例えば、連結またはその他の調節）をそのトウィークとして使用して、Ｎ−キャラクタ初期化ベクトル（３２８ｂ）を生成するように構成されている。トウィーク（３１８）の値は、システムの環境的特徴（例えば、フォーマット保存暗号化（「ＦＰＥ」）では、クレジット・カード番号の下４桁）に基づくことができる。
【０１９６】
[078]  図３ｂでは、可変入力長調整可能暗号（「ＶＩＬＴＣ」）（３３０）は、Ｎ−キャラクタ初期化ベクトル（３２８ｂ）をトウィークとして使用して、可変長出力文字列（３５２）を生成するように構成されている。例えば、可変入力長調整可能暗号（「ＶＩＬＴＣ」）（３３０）は、Ｎ−キャラクタ初期化ベクトル（３２８ｂ）をそのトウィークとして使用し、可変長入力文字列（３１２）をその入力として使用して、可変長出力文字列（３５２）を生成するように構成されている。
【０１９７】
[079]  図３ｂでは、第２Ｎ−キャラクタ調整可能ブロック暗号（「ＴＢＣ」）（３４０ｂ）は、Ｎ−キャラクタ出力文字列（３５１ｂ）を生成するように構成されている。例えば、第２Ｎ−キャラクタ調整可能ブロック暗号（「ＴＢＣ」）（３４０ｂ）は、Ｎ−キャラクタ初期化ベクトル（３２８ｂ）をその入力として使用し、トウィーク（３１８）および可変長出力文字列（３５２）の組み合わせ（例えば、連結またはその他の調節）をそのトウィークとして使用して、Ｎ−キャラクタ出力文字列（３５１ｂ）を生成するように構成されている。通例、第１Ｎ−キャラクタ調整可能ブロック暗号（「ＴＢＣ」）（３２０ｂ）および第２Ｎ−キャラクタ調整可能ブロック暗号（「ＴＢＣ」）（３４０ｂ）は、システムに対するトウィーク（３１８）に同じ値を使用する。他のバッファ（３５０）が、Ｎ−キャラクタ出力文字列（３５１ｂ）および可変長出力文字列（３５２）を格納する。
【０１９８】
[080]  Ｎ−キャラクタ入力文字列（３１１ｂ）、可変長入力文字列（３１２）、Ｎ−キャラクタ出力文字列（３５１ｂ）、および可変長出力文字列（３５２）のキャラクタ は、所定の有限な１組の記号（例えば、数値０．．．９、文字Ａ．．．Ｚおよび数値０．．．９）から選択される。Ｎ−キャラクタ入力文字列（３１１ｂ）、Ｎ−キャラクタ初期化ベクトル（３２８ｂ）、およびＮ−キャラクタ出力文字列（３５１ｂ）のＮの数値例は、Ｎ＝１またはＮ＝２である。更に一般的には、Ｎは任意の正の整数とすることができる。
【０１９９】
[081]  一般化された構造（３０１）は、種々の方法で実現することができる。例えば、第１Ｎ−キャラクタ調整可能ブロック暗号（「ＴＢＣ」）（３２０ｂ）、可変入力長調整可能暗号（「ＶＩＬＴＣ」）（３３０）、および第２Ｎ−キャラクタ調整可能ブロック暗号（「ＴＢＣ」）（３４０ｂ）は、ランダム生成置換参照表から組み立てることができる。一般に、調整可能ブロック暗号（「ＴＢＣ」）における各置換にはトウィークおよび鍵が関連付けられることを思い出すこと。トウィークおよび鍵は、調整可能ブロック暗号（「ＴＢＣ」）への入力として、調整可能ブロック暗号（「ＴＢＣ」）に対する特定の置換を指定する。ある実施態様では（例えば、規制圧力が強いクレジット・カード支払い業界におけるフォーマット保存暗号化（「ＦＰＥ」）の応用）、ユーザは明示的な鍵を避ける方を好む場合がある。このような場合、トウィークが、ランダム生成置換参照表の一群から選択するために使用される。
【０２００】
[082]  更に一般的には、第１Ｎ−キャラクタ調整可能ブロック暗号（「ＴＢＣ」）（３２０ｂ）、第２Ｎ−キャラクタ調整可能ブロック暗号（「ＴＢＣ」）（３４０ｂ）、および可変入力長調整可能暗号（「ＶＩＬＴＣ」）（３３０）は、特殊目的ハードウェアを使用して実現することができ、または汎用ハードウェア上で実行するソフトウェアを使用して実現することができる。通例、２つのＮ−キャラクタ調整可能ブロック暗号（「ＴＢＣ」）（３２０ｂ、３４０ｂ）は、前述のように、１つのＮ−キャラクタ調整可能ブロック暗号（「ＴＢＣ」）コンポーネントに対する、異なる入力および出力を用いた、２回のコールによって供給される。代わりに、しかしながら、Ｎ−キャラクタ調整可能ブロック暗号（「ＴＢＣ」）（３２０ｂ、３４０ｂ）に２つの異なるＮ−キャラクタ調整可能ブロック暗号（「ＴＢＣ」）コンポーネントを供給することもできる。 
【０２０１】
[083]  図３ｃは、完全ディスク暗号化および復号に適応する構成とした構造（３００）の変種を示す。図３ｃの構造（３０２）では、第１Ｎ−ビット調整可能ブロック暗号（「ＴＢＣ」）（３２０ｃ）および第２Ｎ−ビット調整可能ブロック暗号（「ＴＢＣ」）（３４０ｃ）が、Ｎ−ビット初期化ベクトル（３２８ｃ）をシステム外部への露出から保護する。バッファ（３１０）が、Ｎ−ビット入力文字列（３１１ｃ）および可変長入力文字列（３１２）を格納する。Ｎの数値例は、１２８および２５６ビットである。可変長入力文字列（３１２）の長さの値の例は、４０９６バイトおよび８１９２バイトである。
【０２０２】
[084]  図３ｃでは、第１Ｎ−ビット調整可能ブロック暗号（「ＴＢＣ」）（３２０ｃ）は、Ｎ−ビット初期化ベクトル（３２８ｃ）を生成するように構成されている。例えば、第１Ｎ−ビット調整可能ブロック暗号（「ＴＢＣ」）（３２０ｃ）は、Ｎ−ビット入力文字列（３１１ｃ）をその入力として使用し、システムに対するトウィーク（３１８）および可変長入力文字列（３１２）の組み合わせ（例えば、連結またはその他の調節）をそのトウィークとして使用して、Ｎ−ビット初期化ベクトル（３２８ｃ）を生成するように構成されている。トウィーク（３１８）の値は、システムの環境的特徴（例えば、完全ディスク暗号化（「ＦＤＥ」）では、論理的ハード・ディスク・セクタＩＤ）に基づくことができる。
【０２０３】
[085]  図３ｃでは、可変入力長調整可能暗号（「ＶＩＬＴＣ」）（３３０）は、Ｎ−ビット初期化ベクトル（３２８ｃ）をトウィークとして使用して、可変長出力文字列（３５２）を生成するように構成されている。例えば、可変入力長調整可能暗号（「ＶＩＬＴＣ」）（３３０）は、Ｎ−ビット初期化ベクトル（３２８ｃ）をそのトウィークとして使用し、可変長入力文字列（３１２）をその入力として使用して、可変長出力文字列（３５２）を生成するように構成されている。
【０２０４】
[086]  図３ｃでは、第２Ｎ−ビット調整可能ブロック暗号（「ＴＢＣ」）（３４０ｃ）は、Ｎ−ビット出力文字列（３５１ｃ）を生成するように構成されている。例えば、第２Ｎ−ビット調整可能ブロック暗号（「ＴＢＣ」）（３４０ｃ）は、Ｎ−ビット初期化ベクトル（３２８ｃ）をその入力として使用し、トウィーク（３１８）および可変長出力文字列（３５２）の組み合わせ（例えば、連結またはその他の調節）をそのトウィークとして使用して、Ｎ−ビット出力文字列（３５１ｃ）を生成するように構成されている。通例、第１Ｎ−ビット調整可能ブロック暗号（「ＴＢＣ」）（３２０ｃ）および第２Ｎ−ビット調整可能ブロック暗号（「ＴＢＣ」）（３４０ｃ）は、システムに対するトウィーク（３１８）に同じ値を使用する。他のバッファ（３５０）が、Ｎ−ビット出力文字列（３５１ｃ）および可変長出力文字列（３５２）を格納する。
【０２０５】
[087]  一般化された構造（３０２）は、以下で詳述するように、多くの方法で実現することができる。第１Ｎ−ビット調整可能ブロック暗号（「ＴＢＣ」）および第２Ｎ−ビット調整可能ブロック暗号（「ＴＢＣ」）は、同じ構造を有する。あるいは、これらは異なる構造を有する。
【０２０６】
[088]  例えば、一実施態様では、第１Ｎ−ビット調整可能ブロック暗号（「ＴＢＣ」）（３２０ｃ）および／または第２Ｎ−ビット調整可能ブロック暗号（「ＴＢＣ」）（３４０ｃ）は、ＬＲＷ２  ＴＢＣ構造（以下で詳述する。章Ｖ．Ａ．を参照のこと）であり、可変入力長調整可能暗号（「ＶＩＬＴＣ」）（３３０）は、反復ＬＲＷ２  ＴＢＣ構造である。以下で更に詳述するが、ＬＲＷ２  ＴＢＣ構造は、（１）（ａ）ｎ−ビットＬＲＷ２入力文字列と（ｂ）トウィーク入力のｎ−ビット・ハッシュとの間のＸＯＲの暗号化バージョンと、（２）トウィーク入力のｎ−ビット・ハッシュとの間のＸＯＲを計算することによって、ｎ−ビットＬＲＷ２出力文字列を生成するように構成されている。他の例として、他の実施態様では、第１Ｎ−ビット調整可能ブロック暗号（「ＴＢＣ」）（３２０ｃ）および／または第２Ｎ−ビット調整可能ブロック暗号（「ＴＢＣ」）（３４０ｃ）は、ドメイン拡張ＣＬＲＷ２構造（以下で定義する。章Ｖ．Ａ．を参照のこと）であり、可変入力長調整可能暗号（「ＶＩＬＴＣ」）（３３０）は反復ＣＬＲＷ２構造である。
【０２０７】
[089]  構造（３０２）は、安全性と実装効率とのトレードオフを得るためにＮ（固定長入力文字列および固定長出力文字列のビット数）を調節するように構成されたコントローラ（図示せず）も含むことができる。Ｎの値が小さい程（例えば、１２８）、安全性が悪化するが、安全性制約に伴い効率的な実装が簡素化する。他方で、Ｎの値が大きい程（例えば、２５６）高い安全性が得られるが、安全性制約に伴い効率的な実装が複雑化する。
【０２０８】
[090]  一般に、Ｎは任意の正の整数とすることができる。保護された初期化ベクトル（「ＩＶ」）の構造の固定入力長（「ＦＩＬ」）および可変入力長（「ＶＩＬ」）コンポーネントが基礎の１２８−ビット・ブロック暗号（例えば、ＡＥＳ）から組み立てられるとき、Ｎ＝１２８およびＮ＝２５６という数値が相応しい。ＰＩＶ構造が、他のサイズのブロック暗号（ブロック・サイズが６４ビットのＤＥＳのような）を使用して実現される場合、Ｎには他の値が適していることもある（例えば、６４または１２８ビット）。
【０２０９】
[091]  第１Ｎ−ビット調整可能ブロック暗号（「ＴＢＣ」）（３２０ｃ）、第２Ｎ−ビット調整可能ブロック暗号（「ＴＢＣ」）（３４０ｃ）、および可変入力長調整可能暗号（「ＶＩＬＴＣ」）（３３０）は、特殊目的ハードウェアを使用して実装することができる。また、第１Ｎ−ビット調整可能ブロック暗号（「ＴＢＣ」）（３２０ｃ）、第２Ｎ−ビット調整可能ブロック暗号（「ＴＢＣ」）（３４０ｃ）、および可変入力長調整可能暗号（「ＶＩＬＴＣ」）（３３０）は、汎用ハードウェア上で実行するソフトウェアを使用して実装することもできる。通例、２つのＮ−ビット調整可能ブロック暗号（「ＴＢＣ」）（３２０ｃ、３４０ｃ）は、前述のように、１つのＮ−ビット調整可能ブロック暗号（「ＴＢＣ」）コンポーネントに対する２回のコールによって、異なる入力および出力を用いて、供給される。代わりに、しかしながら、Ｎ−ビット調整可能ブロック暗号（「ＴＢＣ」）（３２０ｃ、３４０ｃ）に２つの異なるＮ−ビット調整可能ブロック暗号（「ＴＢＣ」）コンポーネントを供給することもできる。
【０２１０】
[092]  構造（３０２）は、一種の３ラウンド、不均衡ファイステル・ネットワーク(three-round, unbalanced  Feistel network)として解釈することができ、入力の左部が固定ビット長Ｎであり、右部が可変長を有する。１回目および３回目のラウンド関数が、Ｎ−ビット
【０２１１】
【数６９】
2016540266.tif 000071
【０２１２】
（３２０ｃ、３４０ｃ）となる。実施態様例では、ビット長Ｎは、この構造の調整可能な（tunable)パラメータであり、Ｎ＝１２８またはＮ−２５６というような値を有することができる。可変入力長調整可能暗号（「ＶＩＬＴＣ」）（３３０）は、中間ラウンド関数
【０２１３】
【数７０】
2016540266.tif 000072
【０２１４】
を提供し、そのトウィークは、最初のラウンドの出力、即ち、初期化ベクトルＩＶ（３２８ｃ）となる。
[093]  初期化ベクトル（「ＩＶ」）が保護されない従来の
【０２１５】
【数７１】
2016540266.tif 000073
【０２１６】
と比較すると、初期化ベクトル（「ＩＶ」）が保護される可変入力長調整可能暗号（「ＶＩＬＴＣ」）
【０２１７】
【数７２】
2016540266.tif 000074
【０２１８】
における可変入力長調整可能暗号（「ＶＩＬＴＣ」）モジュール
【０２１９】
【数７３】
2016540266.tif 000075
【０２２０】
は、安全性要件を低く抑えることができる。
【０２２１】
【数７４】
2016540266.tif 000076
【０２２２】
に対する目標安全性プロパティは、強調整可能擬似ランダム置換（「ＳＴＰＲＰ」）安全(STPRP-secure)であるということである。非公式には、強調整可能擬似ランダム置換（「ＳＴＰＲＰ」）安全であるとは、攻撃者も全ての入力にわたって完全な制御を有する、選択暗号文攻撃に耐えることを意味する。攻撃者は、例えば、トウィークを任意の回数繰り返すことができる。章ＶＩＩにおいて詳述するが、
【０２２３】
【数７５】
2016540266.tif 000077
【０２２４】
が、Ｎ−ビット文字列のドメインにわたって強調整可能擬似ランダム置換（「ＳＴＰＲＰ」）安全であり、調整可能暗号
【０２２５】
【数７６】
2016540266.tif 000078
【０２２６】
が、トウィークを決して繰り返さない攻撃に対して安全である場合、
【０２２７】
【数７７】
2016540266.tif 000079
【０２２８】
は強調整可能擬似ランダム置換（「ＳＴＰＲＰ」）安全となる。定性的に、初期化ベクトル（「ＩＶ」）保護構造は、制限された種類の攻撃者に対する安全性を、任意の選択暗号文攻撃に対する安全性に高める（大きなドメインにわたって）。定量的に、
【０２２９】
【数７８】
2016540266.tif 000080
【０２３０】
に対する安全性限界(security bound)は、加算項ｑ２／２Ｎを有し、ｑは、
【０２３１】
【数７９】
2016540266.tif 000081
【０２３２】
が質問される回数である。Ｎは、ある基礎のブロック暗号のブロック・サイズｎとすることができる。この場合、
【０２３３】
【数８０】
2016540266.tif 000082
【０２３４】
は、既存の構造によって得られるものに比肩し得る限界(bound)を達成する。Ｎ＝２ｎの場合、ｎ−ビット・プリミティブを使用して
【０２３５】
【数８１】
2016540266.tif 000083
【０２３６】
および
【０２３７】
【数８２】
2016540266.tif 000084
【０２３８】
をインスタンス化することができ、なおも 
【０２３９】
【数８３】
2016540266.tif 000085
【０２４０】
は、２ｎ／２回の質問という誕生日超え(beyond-birthday)を遙かに超える安全性を有する調整可能暗号を提供する。
[094]  公式的には、実施形態例では、 
【０２４１】
【数８４】
2016540266.tif 000086
【０２４２】
は、以下に基づいて組み立てられる。 あるｔ≧０について、トウィーク空間
【０２４３】
【数８５】
2016540266.tif 000087
【０２４４】
とする。
【０２４５】
【数８６】
2016540266.tif 000088
【０２４６】
である場合、
【０２４７】
【数８７】
2016540266.tif 000089
【０２４８】
となるように、
【０２４９】
【数８８】
2016540266.tif 000090
【０２５０】
とする。
【０２５１】
【数８９】
2016540266.tif 000091
【０２５２】
Ｎ＞０の整数について、
【０２５３】
【数９０】
2016540266.tif 000092
【０２５４】
および
【０２５５】
【数９１】
2016540266.tif 000093
【０２５６】
これらから、
【０２５７】
【数９２】
2016540266.tif 000094
【０２５８】
ここで、
【０２５９】
【数９３】
2016540266.tif 000095
【０２６０】
[095]  
【０２６１】
【数９４】
2016540266.tif 000096
【０２６２】
のＰＩＶ組成(composition)は、３ラウンド・ファイステル構造であり、以下のように動作する。入力（Ｔ、Ｘ）上において、平文入力文字列Ｘ＝ＸＬ||ＸＲ、ここで固定長部の長さは｜ＸＬ｜＝Ｎである。第１
【０２６３】
【数９５】
2016540266.tif 000097
【０２６４】
は、鍵Ｋ’を使用して、初期化ベクトル
【０２６５】
【数９６】
2016540266.tif 000098
【０２６６】
に対してＮ−ビット文字列を作成する。次に、
【０２６７】
【数９７】
2016540266.tif 000099
【０２６８】
はこの初期化ベクトル（「ＩＶ」）を使用して、鍵Ｋを用いて可変長入力文字列ＸＲを暗号化し、可変長出力文字列
【０２６９】
【数９８】
2016540266.tif 000100
【０２７０】
を作成する。第２
【０２７１】
【数９９】
2016540266.tif 000101
【０２７２】
は、Ｎ−ビット出力文字列
【０２７３】
【数１００】
2016540266.tif 000102
【０２７４】
を作成する。暗号文出力文字列ＹＬ||ＹＲは、
【０２７５】
【数１０１】
2016540266.tif 000103
【０２７６】
の値として戻される。
[096]  逆に、反転構造(inverse construction)
【０２７７】
【数１０２】
2016540266.tif 000104
【０２７８】
は、次のように動作する。入力（Ｔ，Ｙ）上において、暗号文入力文字列はＹ＝ＹＬ||ＹＲであり、ここで固定長部の長さは｜ＹＬ｜＝Ｎである。第１
【０２７９】
【数１０３】
2016540266.tif 000105
【０２８０】
は、鍵Ｋ’を使用して、初期化ベクトル
【０２８１】
【数１０４】
2016540266.tif 000106
【０２８２】
に対してＮ−ビット文字列を作成する。次に、
【０２８３】
【数１０５】
2016540266.tif 000107
【０２８４】
はこの初期化ベクトル（「ＩＶ」）を使用して、鍵Ｋを用いて可変長入力文字列ＹＲを復号し、可変長出力文字列
【０２８５】
【数１０６】
2016540266.tif 000108
【０２８６】
を作成する。第２
【０２８７】
【数１０７】
2016540266.tif 000109
【０２８８】
は、Ｎ−ビット出力文字列
【０２８９】
【数１０８】
2016540266.tif 000110
【０２９０】
を作成する。平文出力文字列ＸＬ||ＸＲは、
【０２９１】
【数１０９】
2016540266.tif 000111
【０２９２】
の値として戻される。
[097]  図３ｃでは、構造は３つのラウンドを含む。あるいは、構造はもっと多くのラウンド（例えば、５ラウンドまたは７ラウンド）を含むことができ、Ｎ−ビット
【０２９３】
【数１１０】
2016540266.tif 000112
【０２９４】
がこの構造を開始および終了し、多数の
【０２９５】
【数１１１】
2016540266.tif 000113
【０２９６】
コンポーネントがＮ−ビット
【０２９７】
【数１１２】
2016540266.tif 000114
【０２９８】
の間で交互に現れる。
[098]  図４は、初期化ベクトル（「ＩＶ」）保護可変入力長調整可能暗号（「ＶＩＬＴＣ」）を使用するための技法（４００）を一般化して示す。暗号化システムまたは復号システムは、技法（４００）を実行する。
【０２９９】
[099]  本システムは、固定長入力文字列（例えば、Ｎ−ビット入力文字列、Ｎ−キャラクタ入力文字列）、および可変長入力文字列を受ける（４１０）。暗号化では（例えば、完全ディスク暗号化（「ＦＤＥ」）、フォーマット保存暗号化（「ＦＰＥ」）、関連データ付き認証付暗号化（「ＡＥＡＤ」）、または他の暗号化のシナリオの間）、固定長入力文字列および可変長入力文字列は平文である。対応する復号では、固定長入力文字列および可変長入力文字列は暗号文である。
【０３００】
[0100]  本システムは、固定長初期化ベクトル（例えば、Ｎ−ビット初期化ベクトル、Ｎ−キャラクタ初期化ベクトル）を生成する（４２０）。例えば、固定長初期化ベクトルは、固定入力長調整可能ブロック暗号（「ＦＩＬ  ＴＢＣ」）に対する入力である固定長入力文字列に基づき、更に固定入力長調整可能ブロック暗号（「ＦＩＬ  ＴＢＣ」）に対するトウィークである、システムに対するトウィークおよび可変長入力文字列の組み合わせに基づいて、固定入力長調整可能ブロック暗号（「ＦＩＬ  ＴＢＣ」）によって生成される。固定入力長調整可能ブロック暗号（「ＦＩＬ  ＴＢＣ」）は、例えば、Ｎ−ビット調整可能ブロック暗号（「ＴＢＣ」）またはＮ−キャラクタ調整可能ブロック暗号（「ＴＢＣ」）とすることができる。固定入力長調整可能ブロック暗号（「ＦＩＬ  ＴＢＣ」）に対して、本システムは、システムの環境的特徴（例えば、ディスク・セクタ、メモリ・アドレス）に基づいてトウィークの値を設定するか、または何らかの他の方法でトウィークの値を設定することができる。あるいは、固定長初期化ベクトルは、何らかの他の方法で生成される。
【０３０１】
[0101]  また、本システムは、固定長初期化ベクトルをトウィークとして使用する可変入力長調整可能暗号（「ＶＩＬＴＣ」）によって、可変長出力文字列を生成する（４３０）。例えば、可変入力長調整可能暗号（「ＶＩＬＴＣ」）は、固定長初期化ベクトル（可変入力長調整可能暗号（「ＶＩＬＴＣ」）に対するトウィークとして）および可変長入力文字列（可変入力長調整可能暗号（「ＶＩＬＴＣ」）に対する入力として）に基づいて、可変長出力文字列を生成する。あるいは、可変長出力文字列は、何らかの他の方法で生成される。
【０３０２】
[0102]  本システムは、固定長初期化ベクトルを曖昧にする（４４０）。例えば、固定長初期化ベクトルは、固定入力長調整可能ブロック暗号（「ＦＩＬ  ＴＢＣ」）によって曖昧にされ、固定入力長調整可能ブロック暗号（「ＦＩＬ  ＴＢＣ」）に対する入力である固定長初期化ベクトル、および固定入力長調整可能ブロック暗号（「ＦＩＬ  ＴＢＣ」）に対するトウィークである、システム・トウィークおよび可変長出力文字列の組み合わせに基づいて、固定長出力ストリング（例えば、Ｎ−ビット出力文字列、Ｎ−キャラクタ出力文字列）を生成する。固定入力長調整可能ブロック暗号（「ＦＩＬ  ＴＢＣ」）は、例えば、Ｎ−ビット調整可能ブロック暗号（「ＴＢＣ」）またはＮ−キャラクタ調整可能ブロック暗号（「ＴＢＣ」）とすることができる。あるいは、固定長初期化ベクトルは、何らかの他の方法で曖昧にされる。
【０３０３】
[0103]  最後に、本システムは、固定長出力文字列および可変長出力文字列を出力する（４５０）。暗号化では（例えば、完全ディスク暗号化（「ＦＤＥ」）、フォーマット保存暗号化（「ＦＰＥ」）、関連データ付き認証付暗号化（「ＡＥＡＤ」）、または他の暗号化のシナリオの間）、固定長出力文字列および可変長出力文字列は暗号文である。対応する復号では、固定長出力文字列および可変長出力文字列は平文である。
【０３０４】
Ｖ．初期化ベクトル（「ＩＶ」）保護可変入力長調整可能暗号（「ＶＩＬＴＣ」）の実施態様例
[0104]  初期化ベクトル（「ＩＶ」）保護可変入力長調整可能暗号（「ＶＩＬＴＣ」）に対する一般的なフレームワーク内において、固定入力長（「ＦＩＬ」）部
【０３０５】
【数１１３】
2016540266.tif 000115
【０３０６】
および可変入力長（「ＶＩＬ」）部
【０３０７】
【数１１４】
2016540266.tif 000116
【０３０８】
を独立して組み立てることができる。このモジュール型手法は、トウィークが繰り返さないと仮定できるときには、可変入力長（「ＶＩＬ」）部
【０３０９】
【数１１５】
2016540266.tif 000117
【０３１０】
の効率的で安全なインスタンス化を組み立てることが容易であるのが通例なので、有効である。トウィークが繰り返されるかもしれないときに安全であり続ける
【０３１１】
【数１１６】
2016540266.tif 000118
【０３１２】
を組み立てることは、固定ビット長Ｎ（即ち、Ｎ−ビット・ブロック・サイズ）の平文入力をそれに処理させることによって、簡略化される。実際には、N=１２８または２５６のとき、
【０３１３】
【数１１７】
2016540266.tif 000119
【０３１４】
によって生ずる非効率は、
【０３１５】
【数１１８】
2016540266.tif 000120
【０３１６】
における効率利得によって相殺することができる。
[0105]  ブロック・サイズＮをできるだけ大きく設定することには、安全性上の利点があるが、大きなＮに対してドメイン｛０，１｝Nを有し、
【０３１７】
【数１１９】
2016540266.tif 000121
【０３１８】
がｑ２／２Ｎに接近する
【０３１９】
【数１２０】
2016540266.tif 000122
【０３２０】
を構築すると、複雑になる。具体的には、現在では、ｎ−ビット・ブロック暗号を開始点として使用するとき、
【０３２１】
【数１２１】
2016540266.tif 000123
【０３２２】
が、
【０３２３】
【数１２２】
2016540266.tif 000124
【０３２４】
よりも小さくなることを可能にする効率的な構造がない。しかしながら、以下ではＮ＝２ｎである構造について説明する。
[0106]  しがたって、この章は、Ｎが比較的小さい（例えば、１２８、２５６）
【０３２５】
【数１２３】
2016540266.tif 000125
【０３２６】
を組み立てることを中心に据える。具体的には、Ｎ−ビット調整可能ブロック暗号（「ＴＢＣ」）を、ブロック暗号から組み立てる。ｎをブロック暗号のブロック・サイズ、Ｎ＝ｎ、およびＮ＝２ｎとする。この章では、各々ｎ−ビット・ブロック暗号を使用し、初期化ベクトル（「ＩＶ」）保護可変入力長調整可能暗号（「ＶＩＬＴＣ」）の２つの実施態様について説明する。
【０３２７】
[0107]  第１の実施態様例（ＴＣＴ１）は、誕生日限界の安全性を提供する。Ｎ＝ｎのとき、この実施態様は、大まかに、ブロック暗号に関する誕生日限界であるｑ＝２ｎ／２回まで安全である。この安全性限界を念頭に入れ、この実施態様は、
【０３２８】
【数１２４】
2016540266.tif 000126
【０３２９】
および
【０３３０】
【数１２５】
2016540266.tif 000127
【０３３１】
双方の簡単で効率的な構造を使用する。第１の実施態様例（ＴＣＴ１）は、入力のｎ−ビット・ブロック毎に、１回だけのブロック暗号呼び出し(invocation)、および２のべき乗を法とする(modulo powers of two)ある算術演算を使用する。対照的に、可変入力長調整可能暗号（「ＶＩＬＴＣ」）を実装する以前の手法は、ｎ−ビット・ブロック毎に２回のブロック暗号呼び出しを使用するか、またはブロック毎に有限界動作を使用する。
【０３３２】
[0108]  第２の実施態様例（ＴＣＴ２）は、誕生日限界を超えた安全性を提供する。Ｎ＝２ｎのとき、この実施態様は大まかにｑ＝２ｎ回の質問まで安全である。この厳格化した安全性限界を念頭に入れて、なおもそれなりに効率的な構造がある。以前の可変入力長調整可能暗号（「ＶＩＬＴＣ」）が誕生日限界の安全性だけであるのと比較すると、第２の実施態様例（ＴＣＴ２）は、入力のｎ−ビット・ブロック毎に、単純な算術演算の僅かな追加を招くに過ぎない。この場合も、この算術演算は、有限界においてではなく、２のべき乗を法として実行される。
【０３３３】
[0109]   第１の実施態様例（ＴＣＴ１）および第２の実施態様例（ＴＣＴ２）では、可変入力長（「ＶＩＬ」）コンポーネント
【０３３４】
【数１２６】
2016540266.tif 000128
【０３３５】
は、調整可能ブロック暗号（「ＴＢＣ」）に対するカウンタ・モード暗号化(counter-mode encryption)を使用してインスタンス化される。調整可能ブロック暗号（「ＴＢＣ」）の追加のトウィーク入力は、種々の「トウィーク・スケジューリング」手法を可能にする。例えば、全てのブロックにわたって１つのメッセージ毎にトウィークを固定する、またはメッセージ・ブロック毎にトウィークを変化させる。（調整可能ブロック暗号（「ＴＢＣ」）のトウィークを変化させることとブロック暗号の鍵を変化させることの間には、自然な繋がりがある。双方共、安全性を高めるために使用することができるが、トウィークは秘密にする必要がないので、トウィークを変化させる方が影響が少ない(clean)。）ブロック毎に再調整すると、少なくともＮの任意の長さの文字列を受け入れ、初期化ベクトル（「ＩＶ」）が保護され、誕生日限界を超えて安全な可変入力長調整可能暗号（「ＶＩＬＴＣ」）構造が得られる。
【０３３６】
[0110]  手順ＴＣＴＲは、ｎ−ビット
【０３３７】
【数１２７】
2016540266.tif 000129
【０３３８】
にカウンタ・モード暗号化を提供する。ＴＣＴＲへのコール内において、入力Ｘの各ｎ−ビット・ブロックＸｉが、ブロック毎のトウィークＴｉを使用して処理され、以下のように、入力トウィークＴの関数
【０３３９】
【数１２８】
2016540266.tif 000130
【０３４０】
およびブロック・インデックスｉによって決定される。
【０３４１】
【数１２９】
2016540266.tif 000131
【０３４２】
[0111]  反転ＴＣＴＲの手順では、入力Ｙの各ｎ−ビット・ブロックＹｉが、以下のように、ブロック毎のトウィークＴｉを使用して処理される。
【０３４３】
【数１３０】
2016540266.tif 000132
【０３４４】
[0112]  初期化ベクトル（「ＩＶ」）保護可変入力長調整可能暗号（「ＶＩＬＴＣ」）では、
【０３４５】
【数１３１】
2016540266.tif 000133
【０３４６】
は長いトウィークを扱う。これらのトウィークは、∈−ＡＵハッシュ関数を使用して、ｑ２∈項を調整可能暗号の調整可能擬似ランダム置換（「ＴＰＲＰ」）安全性限界に追加することを犠牲にして圧縮することができる。具体的には、ある実施態様例では、ＮＨハッシュの変種を使用する。関数ＮＨ［ｒ，ｓ］Ｌは、ｒビットの鍵（｜Ｌ｜＝ｒ）を取り込み、ｒ−ビット文字列をｓ−ビット文字列にマッピングし、２Ｓ／２−ＡＵである。
【０３４７】
【数１３２】
2016540266.tif 000134
【０３４８】
が与えられると、
【０３４９】
【数１３３】
2016540266.tif 000135
【０３５０】
は、結果的に得られる調整可能ブロック暗号（「ＴＢＣ」）を示し、ここでは、そのトウィーク空間は、それの範囲ではなく、ＮＨのドメインとなる。
Ａ．第１の実施態様例（ＴＣＴ１）および第２の実施態様例（ＴＣＴ２）のコンポーネント
[0113]   第１の実施態様例（ＴＣＴ１）および第２の実施態様例（ＴＣＴ２）は、以下のコンポーネントを使用する。
【０３５１】
[0114]  コンポーネントＬＲＷ２は、ブロック暗号Ｅおよび∈−ＡＸＵ２関数Ｈを使用する誕生日限界調整可能ブロック暗号（「ＴＢＣ」）を示す。
【０３５２】
【数１３４】
2016540266.tif 000136
【０３５３】
[0115]  コンポーネントＣＬＲＷ２は、誕生日限界を超える安全性を有する調整可能ブロック暗号（「ＴＢＣ」）であり、ブロック暗号Ｅおよび∈−ＡＸＵ２関数Ｈを使用する。
【０３５４】
【数１３５】
2016540266.tif 000137
【０３５５】
[0116]  コンポーネントｐｏｌｙＨｍｎは、ドメイン（｛０，１｝ｎ）ｍおよび∈＝ｍ／２ｎを有する∈−ＡＸＵ２関数である。全ての動作は、Ｆ２ｎ内にある。
【０３５６】
【数１３６】
2016540266.tif 000138
【０３５７】
[0117]  コンポーネントＮＨ（ｖｗ、２ｔｗ）は、∈＝１／２ｔｗである∈−ＡＸＵ２関数である。入力はｖｗビットであり、ｖは偶数、ｗ＞０に固定される。
【０３５８】
【数１３７】
2016540266.tif 000139
【０３５９】
ここで、
【０３６０】
【数１３８】
2016540266.tif 000140
【０３６１】
[0118]  コンポーネントＣＤＭＳは、
【０３６２】
【数１３９】
2016540266.tif 000141
【０３６３】
に対するファイステル型ドメイン・エクステンダ(domain extender)である。
【０３６４】
【数１４０】
2016540266.tif 000142
【０３６５】
ここで、
【０３６６】
【数１４１】
2016540266.tif 000143
【０３６７】
および
【０３６８】
【数１４２】
2016540266.tif 000144
【０３６９】
Ｂ．第１の実施態様例（ＴＣＴ１）
[0119]   第１の実施態様例（ＴＣＴ１）は、平文メッセージが小さな用途のための誕生日型安全性を備えた効率的な実施態様である（例えば、完全ディスク暗号化（「ＦＤＥ」））。この実施態様では、Ｎ−ビット調整可能ブロック暗号（「ＴＢＣ」）のサイズはＮ＝ｎ、そしてｎ−ビット
【０３７０】
【数１４３】
2016540266.tif 000145
【０３７１】
はコンポーネントＬＲＷ２を使用する。ブロック暗号Ｅに加えて、ＬＲＷ２［Ｈ，Ｅ］は、∈−ＡＸＵ２ハッシュ関数Ｈを使用する。理論上、コンポーネントＬＲＷ２は大きなトウィークに対応することができる。しかしながら、実用的な目的では、小さなトウィーク空間のＬＲＷ２を実装し、次いで高速∈−ＡＵハッシュ関数を使用してこの小さなトウィーク空間を拡張する方が効率的である。∈−ＡＸＵ２ハッシュ関数自体に対しては、第１実施態様例は多項数ハッシュｐｏｌｙＨを使用する。
【０３７２】
[0120]  図５ａから図５ｃは、トウィークＴおよびメッセージＸを入力として取り込む第１の実施態様例（ＴＣＴ１）（５００）のコンポーネントを示す。メッセージＸは、ブロックＸ１、Ｘ２、．．．、ＸＶに分割され、最後のブロックＸｖを除く全てのブロックの長さはｎであり、最後のブロックＸＶの長さはｎ以下である。第１の実施態様例（ＴＣＴ１）は、出力文字列Ｙ＝Ｙ１、Ｙ２、．．．ＹＶを生成する。固定入力長（「ＦＩＬ」）コンポーネントのブロック・サイズはＮ＝ｎである。ｋ、ｎ＞０に対して、
【０３７３】
【数１４４】
2016540266.tif 000146
【０３７４】
がブロック暗号である。
【０３７５】
【数１４５】
2016540266.tif 000147
【０３７６】
ここで、τｎビットのトウィーク空間およびドメイン
【０３７７】
【数１４６】
2016540266.tif 000148
【０３７８】
を得るために、ｎ−ビット
【０３７９】
【数１４７】
2016540266.tif 000149
【０３８０】
および
【０３８１】
【数１４８】
2016540266.tif 000150
【０３８２】
を次のように設定する。
[0121]  ｎ−ビット
【０３８３】
【数１４９】
2016540266.tif 000151
【０３８４】
【数１５０】
2016540266.tif 000152
【０３８５】
即ち、ｎ−ビット
【０３８６】
【数１５１】
2016540266.tif 000153
【０３８７】
は、ＮＨを使用してそのトウィーク空間が拡張されたコンポーネントＬＲＷ２である。
【０３８８】
【数１５２】
2016540266.tif 000154
【０３８９】
の鍵空間は、
【０３９０】
【数１５３】
2016540266.tif 000155
【０３９１】
であり、鍵Ｋ’は、Ｅの鍵ＰｏｌｙＨ２ｎ、および
【０３９２】
【数１５４】
2016540266.tif 000156
【０３９３】
に区分される。ＮＨは固定長入力しかサポートしないので、ＮＨ入力には暗黙的に１がパディングされ、次いで十分な０がパディングされて、
【０３９４】
【数１５５】
2016540266.tif 000157
【０３９５】
ビットの全長になる。
【０３９６】
【数１５６】
2016540266.tif 000158
【０３９７】
のトウィーク空間は、
【０３９８】
【数１５７】
2016540266.tif 000159
【０３９９】
となる。
[0122]  図５ａは、トウィーク入力（５１０）およびメッセージ入力を受け入れる第１ｎ−ビット
【０４００】
【数１５８】
2016540266.tif 000160
【０４０１】
（５２０）を示す。メッセージ入力は、第１ｎ−ビット・ブロックＸ１である。トウィーク入力（５１０）は、メッセージＸの残りのブロックのパディング・バージョンと連結されたトウィーク値Ｔである。関数Ｐａｄ（）は、ｓを、
【０４０２】
【数１５９】
2016540266.tif 000161
【０４０３】
にマッピングする。第１ｎ−ビット
【０４０４】
【数１６０】
2016540266.tif 000162
【０４０５】
（５２０）は、ｎ−ビット初期化ベクトル（「ＩＶ」）（５３８）を生成する。
[0123]  また、図５ａは、トウィーク入力（５６０）およびメッセージ入力を受け入れる第２ｎ−ビット
【０４０６】
【数１６１】
2016540266.tif 000163
【０４０７】
（５２０）も示す。メッセージ入力は、ｎ−ビット初期化ベクトル（「ＩＶ」）（５３８）である。トウィーク入力（５６０）は、可変長出力文字列ＹのブロックＹ２．．．ＹＶのパディング・バージョンと連結されたトウィーク値Ｔである。第２ｎ−ビット
【０４０８】
【数１６２】
2016540266.tif 000164
【０４０９】
（５２０）は、可変長出力文字列Ｙの第１ブロックＹ１を生成する。
[0124]  図５ｂは、ｎ−ビット
【０４１０】
【数１６３】
2016540266.tif 000165
【０４１１】
（５２０）の詳細を示す。ＮＨ関数（５２１）は、（ｌ＋ｒ）×ｎビットのトウィーク値を受け入れ、２ｎビットのトウィーク値を生成する。ＰｏｌｙＨ２ｎ関数（５２２）は、２ｎ−ビット・トウィーク値からｎ−ビット・トウィーク値を生成する。ブロック暗号（５２３）は、ｎ−ビット入力値とのＸＯＲを取ったｎ−ビット・トウィーク値（これは、第１ｎ−ビット
【０４１２】
【数１６４】
2016540266.tif 000166
【０４１３】
と第２ｎ−ビット
【０４１４】
【数１６５】
2016540266.tif 000167
【０４１５】
（ｎ−ビット初期化ベクトル（「ＩＶ」））との間で変化する）を暗号化する。次いで、ブロック暗号（５２３）の出力は、ｎ−ビット・トウィーク値とのＸＯＲが取られ、ｎ−ビット出力を生成する。
【０４１６】
[0125]  
【０４１７】
【数１６６】
2016540266.tif 000168
【０４１８】
ＴＣＴＲ手順では、ｇ（Ｔ，ｉ）＝Ｔであるので、
【０４１９】
【数１６７】
2016540266.tif 000169
【０４２０】
【数１６８】
2016540266.tif 000170
【０４２１】
の鍵空間は、｛０，１｝ｋ×｛０，１｝ｎであり、鍵ＫはＥの鍵およびＰｏｌｙＨｎに区分される。
【０４２２】
【数１６９】
2016540266.tif 000171
【０４２３】
のトウィーク空間は、｛０，１｝ｎであり、そのドメインは、
【０４２４】
【数１７０】
2016540266.tif 000172
【０４２５】
である。
[0126]  図５ａに示すように、
【０４２６】
【数１７１】
2016540266.tif 000173
【０４２７】
に対するＴＣＴＲは、一連のコンポーネント
【０４２８】
【数１７２】
2016540266.tif 000174
【０４２９】
（５４０）として実装される。各
【０４３０】
【数１７３】
2016540266.tif 000175
【０４３１】
（５４０）は、トウィーク入力として、ｎ−ビット初期化ベクトル（「ＩＶ」）（５３８）を受け入れる。また、各
【０４３２】
【数１７４】
2016540266.tif 000176
【０４３３】
（５４０）は、メッセージ入力として、０≦ｉ≦ｖ−２に対して、パディング・カウンタ値＜ｉ＞も受け入れる。各
【０４３４】
【数１７５】
2016540266.tif 000177
【０４３５】
（５４０）の出力は、メッセージＸのｎ−ビット・ブロックＸｉ＋２とＸＯＲが取られ、可変長出力文字列YのブロックＹｉ＋２を生成する。
[0127]  図５ｃは、ｎ−ビット
【０４３６】
【数１７６】
2016540266.tif 000178
【０４３７】
（５４０）の詳細を示す。ｐｏｌｙＨｎ関数（５４２）は、入力ｎ−ビット・トウィーク値から結果的に得られるｎ−ビット・トウィーク値を生成する。ブロック暗号（５４３）は、結果的に得られたｎ−ビット・トウィーク値とｎ−ビット入力値（パディング・カウンタ値）とのＸＯＲを取って暗号化する。次いで、ブロック暗号（５４３）の出力は、結果的に得られたｎ−ビット・トウィーク値とＸＯＲが取られ、ｎ−ビット出力を生成する。
【０４３８】
ｃ．第２の実施態様例（ＴＣＴ２）
[0128]   第２の実施態様例（ＴＣＴ２）は、誕生日限界を超えた安全性を提供する。この実施態様では、Ｎ−ビット
【０４３９】
【数１７７】
2016540266.tif 000179
【０４４０】
のサイズは、Ｎ＝２ｎである。この２ｎ−ビット
【０４４１】
【数１７８】
2016540266.tif 000180
【０４４２】
は、ＣＤＭＳコンポーネントの変種を使用し、これは誕生日限界を超える安全性を提供するために、数個のｎ−ビット調整可能ブロック暗号（「ＴＢＣ」）をＣコンポーネントＬＲＷ２の一部として含む。トウィーク空間は、ＮＨを使用して拡張され、ＮＨの範囲は｛０，１｝２ｎに設定される。最終的に、設定
【０４４３】
【数１７９】
2016540266.tif 000181
【０４４４】
は、約２２ｎ／３回までの質問に対して安全である。また、ＣコンポーネントＬＲＷ２は、誕生日限界を超えて安全な可変入力長調整可能暗号（「ＶＩＬＴＣ」）コンポーネントにおいても使用される。即ち、少なくとも、
【０４４５】
【数１８０】
2016540266.tif 000182
【０４４６】
に対して、
【０４４７】
【数１８１】
2016540266.tif 000183
【０４４８】
となる。第２の実施態様例（ＴＣＴ２）は、τｎビットのトウィークをサポートし、ドメイン
【０４４９】
【数１８２】
2016540266.tif 000184
【０４５０】
を有する。
[0129]  図６ａから図６ｃは、トウィークＴおよびメッセージＸを入力として取り込む第２の実施態様例（ＴＣＴ２）（６００）のコンポーネントを示す。メッセージＸは、ブロックＸ１、Ｘ２、．．．、ＸＶに分割され、最後のブロックＸｖを除く全てのブロックの長さはｎであり、最後のブロックＸＶの長さはｎ以下である。メッセージＸの長さは、２ｎビットと
【０４５１】
【数１８３】
2016540266.tif 000185
【０４５２】
ビットとの間である。第２の実施態様例（ＴＣＴ２）は、出力文字列Ｙ＝Ｙ１、Ｙ２、．．．ＹＶを生成する。固定入力長（「ＦＩＬ」）コンポーネントのブロック・サイズはＮ＝２ｎである。
【０４５３】
【数１８４】
2016540266.tif 000186
【０４５４】
に対して、
【０４５５】
【数１８５】
2016540266.tif 000187
【０４５６】
がブロック暗号となる。
【０４５７】
【数１８６】
2016540266.tif 000188
【０４５８】
ここで、２ｎ−ビット
【０４５９】
【数１８７】
2016540266.tif 000189
【０４６０】
および
【０４６１】
【数１８８】
2016540266.tif 000190
【０４６２】
は、次のように設定される。
[0130]  ｎ−ビット
【０４６３】
【数１８９】
2016540266.tif 000191
【０４６４】
【数１９０】
2016540266.tif 000192
【０４６５】
即ち、２ｎ−ビット
【０４６６】
【数１９１】
2016540266.tif 000193
【０４６７】
は、そのトウィーク空間がＮＨを使用して拡張された、
【０４６８】
【数１９２】
2016540266.tif 000194
【０４６９】
コンポーネントである。
【０４７０】
【数１９３】
2016540266.tif 000195
【０４７１】
の鍵空間は、
【０４７２】
【数１９４】
2016540266.tif 000196
【０４７３】
であり、鍵Ｋ’は、Ｅに対する２つの鍵、ｐｏｌｙＨ６ｎに対する２つの鍵、および
【０４７４】
【数１９５】
2016540266.tif 000197
【０４７５】
に対する鍵に区分される。
【０４７６】
【数１９６】
2016540266.tif 000198
【０４７７】
のトウィーク空間は、｛０，１｝τｎである。
[0131]  図６ａは、トウィーク入力（６１０）およびメッセージ入力を受け入れる第２ｎ−ビット
【０４７８】
【数１９７】
2016540266.tif 000199
【０４７９】
（６２０）を示す。メッセージ入力は、２つの第１ｎ−ビット・ブロックＸ１およびＸ２である。トウィーク入力（６１０）は、メッセージＸの残りのブロックのパディング・バージョンと連結されたトウィーク値Ｔである。第１の２ｎ−ビット
【０４８０】
【数１９８】
2016540266.tif 000200
【０４８１】
（６２０）は、２ｎ−ビット初期化ベクトル（「ＩＶ」）（６３８）を生成する。
[0132]  また、図６ａは、トウィーク入力（６６０）およびメッセージ入力を受け入れる第２ｎ−ビット
【０４８２】
【数１９９】
2016540266.tif 000201
【０４８３】
（６２０）も示す。メッセージ入力は、は、２ｎ−ビット初期化ベクトル（「ＩＶ」）（６３８）である。トウィーク入力（６６０）は、可変長出力文字列ＹのブロックＹ３．．．ＹＶのパディング・バージョンと連結されたトウィーク値Ｔである。第２の２ｎ−ビット
【０４８４】
【数２００】
2016540266.tif 000202
【０４８５】
（５２０）は、可変長出力文字列Ｙの２つの第１ブロックＹ１およびＹ２を生成する。
[0133]  図６ｂは、２ｎ−ビット
【０４８６】
【数２０１】
2016540266.tif 000203
【０４８７】
（６２０）の詳細を示す。ＨＮ関数（６２１）は、（ｌ＋ｒ−１）×ｎビットのトウィーク値を受け入れ、４ｎビットのトウィーク値Ｔ’を生成する。２ｎ−ビット入力は、第１の２ｎ−ビット
【０４８８】
【数２０２】
2016540266.tif 000204
【０４８９】
（Ｘ１およびＸ２）と第２の２ｎ−ビット
【０４９０】
【数２０３】
2016540266.tif 000205
【０４９１】
（２ｎ−ビット初期化ベクトル（「ＩＶ」））との間で変化し、２つのｎ−ビット入力に分割される。第１ｎ−ビット入力は、第１
【０４９２】
【数２０４】
2016540266.tif 000206
【０４９３】
コンポーネント（６２２）に供給される。このコンポーネント（６２２）は、６ｎビットのトウィーク値も受け入れる。６ｎ−ビット・トウィーク値は、４ｎ−ビット・トウィーク値Ｔ’のパディング・バージョン（ｎ個のゼロ・ビットがパディングされ、５ｎビットの長さになる）および第２ｎ−ビット入力を連結することによって決定される。第１
【０４９４】
【数２０５】
2016540266.tif 000207
【０４９５】
コンポーネント（６２２）は、ｎ−ビット出力値を生成し、４ｎ−ビット・トウィーク値Ｔ’のパディング・バージョン（ｎ個のゼロ・ビットがパディングされて５ｎビットの長さになる）の後ろに連結され、第２
【０４９６】
【数２０６】
2016540266.tif 000208
【０４９７】
コンポーネント（６２２）のために６ｎ−ビット・トウィーク値を形成する。また、第２
【０４９８】
【数２０７】
2016540266.tif 000209
【０４９９】
コンポーネント（６２２）は、第２ｎ−ビット入力も受け入れ、ｎ−ビット出力を生成する。同様に、第３
【０５００】
【数２０８】
2016540266.tif 000210
【０５０１】
コンポーネント（６２２）も第１ＣコンポーネントＬＲＷ２（６２２）からのｎ−ビット出力値、および６ｎ−ビット・トウィーク値（図６ｂに示すように形成される）を処理して、他のｎ−ビット出力を生成する。第２および第３ＣコンポーネントＬＲＷ２（６２２）からのｎ−ビット出力は、ＣＤＭＳコンポーネント（６２０）の２ｎ−ビット出力に連結される。
【０５０２】
[0134]  図６ｃは、
【０５０３】
【数２０９】
2016540266.tif 000211
【０５０４】
コンポーネントの詳細を示し、ここでｒは６（図６ｂのコンポーネント（６２２）におけるように）、または２（図６ａのコンポーネント（６４０）におけるように）とすることができる。第１ｐｏｌｙＨｒｎ関数（６４２）は、入力ｒ・ｎ−ビット・トウィーク値からｎ−ビット・トウィーク値を生成する。第１ブロック暗号（６４３）（鍵Ｋ１を有する）は、ｎ−ビット入力値とＸＯＲが取られたｎ−ビット・トウィーク値を暗号化する。次いで、ブロック暗号（６４３）の出力は、ｎ−ビット・トウィーク値とＸＯＲが取られ、ｎ−ビット中間値を生成する。第２ｐｏｌｙＨｒｎ関数（６４２）は、入力ｒ・ｎ−ビット・トウィーク値からｎ−ビット・トウィーク値を生成する。第２ブロック暗号（６４３）（鍵Ｋ２を有する）は、ｎ−ビット中間値とＸＯＲが取られたｎ−ビット・トウィーク値を暗号化する。次いで、第２ブロック暗号（６４３）の出力は、ｎ−ビット・トウィーク値とＸＯＲが取られ、ｎ−ビット出力値を生成する。
【０５０５】
[0135]  
【０５０６】
【数２１０】
2016540266.tif 000212
【０５０７】
ＴＣＴＲ関数では、ｇ（Ｔ，ｉ）＝Ｔであるので、
【０５０８】
【数２１１】
2016540266.tif 000213
【０５０９】
【数２１２】
2016540266.tif 000214
【０５１０】
の鍵空間は、｛０，１｝２ｋ×｛０，１｝４ｎであり、鍵ＫはＥの２つの鍵およびＰｏｌｙＨ２ｎの２つの鍵に区分される。
【０５１１】
【数２１３】
2016540266.tif 000215
【０５１２】
のトウィーク空間は、｛０，１｝２ｎであり、そのドメインは、
【０５１３】
【数２１４】
2016540266.tif 000216
【０５１４】
である。第２の実施態様例（ＴＣＴ２）は、鍵素材の
【０５１５】
【数２１５】
2016540266.tif 000217
【０５１６】
ビットを使用する。
[0136]  図６ａに示すように、
【０５１７】
【数２１６】
2016540266.tif 000218
【０５１８】
に対するＴＣＴＲは、一連のコンポーネント
【０５１９】
【数２１７】
2016540266.tif 000219
【０５２０】
（６４０）として実装される。各
【０５２１】
【数２１８】
2016540266.tif 000220
【０５２２】
（６４０）は、
【０５２３】
【数２１９】
2016540266.tif 000221
【０５２４】
コンポーネントとして実装される。また、各
【０５２５】
【数２２０】
2016540266.tif 000222
【０５２６】
（６４０）は、トウィーク入力として、２ｎ−ビット初期化ベクトル（「ＩＶ」）（６３８）を受け入れる。また、各
【０５２７】
【数２２１】
2016540266.tif 000223
【０５２８】
（６４０）は、メッセージ入力として、０≦ｉ≦ｖ−３に対して、ｎビットのパディング・カウンタ値＜ｉ＞も受け入れる。各
【０５２９】
【数２２２】
2016540266.tif 000224
【０５３０】
（６４０）のｎ−ビット出力は、メッセージＸのｎ−ビット・ブロックＸｉ＋３とＸＯＲが取られ、可変長出力文字列ＹのブロックＹｉ＋３を生成する。図６ｃは、
【０５３１】
【数２２３】
2016540266.tif 000225
【０５３２】
（６４０）に対する
【０５３３】
【数２２４】
2016540266.tif 000226
【０５３４】
コンポーネントの詳細を示す。ここでは、ｒ＝２である。
Ｄ．変種および実用上の考慮点
[0137]  この章では、第１の実施態様例（ＴＣＴ１）および第２の実施態様例（ＴＣＴ２）の様々な変種について説明する。これらの変更はいずれも、別段注記されなければ、これらの実施態様に対する安全性限界に著しい影響を及ぼすことはない。
【０５３５】
[0138]  ブロック暗号鍵の数量削減  第１の実施態様例（ＴＣＴ１）の場合、トウィークによってドメイン分離が実施されることを条件に、１つの鍵を双方のＬＲＷ２インスタンスに使用することができる。これによって、基礎のブロック暗号に対して１つの鍵の使用が可能となり、状況によっては、著しい実施の効果が見込まれる（例えば、１つのＡＥＳパイプラインを可能にすることによって）。これを遂行する１つの方法は、
【０５３６】
【数２２５】
2016540266.tif 000227
【０５３７】
を、
【０５３８】
【数２２６】
2016540266.tif 000228
【０５３９】
と交換し、更に、
【０５４０】
【数２２７】
2016540266.tif 000229
【０５４１】
を、
【０５４２】
【数２２８】
2016540266.tif 000230
【０５４３】
と交換することである。ここで、ｆは、鍵空間
【０５４４】
【数２２９】
2016540266.tif 000231
【０５４５】
を有する２−ｎ−ＡＵ関数であり、形式（Ｘ，ε）（あるＸ∈｛０，１｝ｎに対して）または（ε，Ｙ）（ある
【０５４６】
【数２３０】
2016540266.tif 000232
【０５４７】
に対して）の入力を取り込み、３ｎ−ビット文字列を出力する。
【０５４８】
【数２３１】
2016540266.tif 000233
【０５４９】
とする。ここで説明する関数ｆは、２つのＬＲＷ２インスタンスのシグネチャー(signature)を統一するための数学的な便宜であり、これによってトウィーク・ベースのドメイン分離を範囲内に持ち込む。実際には、２つのインスタンスは、共有ブロック暗号鍵を除いて、独立に実装することができる。第２の実施態様例（ＴＣＴ２）は、２つのブロック暗号鍵だけを必要とするように同様に変更することができる。
【０５５０】
[0139]  処理能力向上  固定入力長調整可能ブロック暗号（「ＦＩＬ  ＴＢＣ」）では、パディング方式をしかるべく調節することによって、
【０５５１】
【数２３２】
2016540266.tif 000234
【０５５２】
の代わりに、
【０５５３】
【数２３３】
2016540266.tif 000235
【０５５４】
を使用することができる。また、第２の実施態様例（ＴＣＴ２）のＴＣＴＲ部分では、各ＬＲＷ２呼び出しが同じトウィークを使用するので、ＣコンポーネントＬＲＷ２毎にｐｏｌｙＨ関数を１回計算することができる。
【０５５５】
[0140]   第２の実施態様例（ＴＣＴ２）の１つの可能な実施態様では、２回の固定入力長（「ＦＩＬ」）フェーズ（ｐｏｌｙＨ６ｎを１２回評価する結果）の間に７２回の有限界乗算を使用する。あるいは、ある実施態様では、ＣＤＭＳの内部で使用されるｐｏｌｙＨ６ｎハッシュの中間値をキャッシュし（呼び出し毎に、４つのｎ−ビット・トウィーク・ブロックが一定である）、３２回の有限界乗算をしないで済む。ドメイン分離定数に対応する多項式ハッシュの項を予め計算することによって、更に１２回の乗算をなくし、合計で２８回だけが残る。可変入力長（「ＶＩＬ」）フェーズ中において４つ更に使用するので、数量は３２となる。
【０５５６】
[0141]  大きなメッセージ空間の処理(handling)   第１の実施態様例（ＴＣＴ１）および第２の実施態様例（ＴＣＴ２）の双方は、完全ディスク暗号化（「ＦＤＥ」）への応用を念頭に入れて設計される。具体的には、これらは、時間に先立って(ahead of time)固定される値
【０５５７】
【数２３４】
2016540266.tif 000236
【０５５８】
を使用し、
【０５５９】
【数２３５】
2016540266.tif 000237
【０５６０】
ビットより多くの鍵素材(key material)を使用する。これらの制限は、ＮＨハッシュ関数を使用することの結果である。しかしながら、単純なＮＨへの拡張が、任意に長い文字列を収容する。正の整数ｒに対して、
【０５６１】
【数２３６】
2016540266.tif 000238
【０５６２】
ここで、ｉ＜ｖに対して｜Ｍｉ｜＝ｒｎ、｜Ｍｖ｜≦ｒｎ、そしてＮＨＬはＮＨＬ［ｒｎ，２Ｎ］の省略である。このように定義すると、ＮＨ＊は２−Ｎ−殆ど普遍であり(-almost universal)、ドメイン｛０，１｝＊を有し、ｒｎビットの鍵素材を必要とする。この変更は、ｐｏｌｙＨハッシュに対する重みの一部を移転させる。入力の追加のｒｎビット毎に、８回の余分な有限長乗算が使用される。
【０５６３】
[0142]  これらの変更によって、第１の実施態様例（ＴＣＴ１）の安全性限界における最終的な２つの項（第７章参照）は、
【０５６４】
【数２３７】
2016540266.tif 000239
【０５６５】
となる。ここで、
【０５６６】
【数２３８】
2016540266.tif 000240
【０５６７】
は、ここでは、アドバーサリーの最も長い質問の長さであり、
【０５６８】
【数２３９】
2016540266.tif 000241
【０５６９】
、そして残りの項は、基礎のブロック暗号の（Ｓ）擬似ランダム置換（「ＰＲＰ」）安全性を測定する(measure)。２ｎ≧ｒｎと仮定すると、|M| mod rnを１つのｎ−ビット・ブロック内でエンコードすることができる。６００という定数は大きいが、例えば、ｒ＝１６と設定すると、もっと快適なサイズに、この場合では３未満に縮小することができる。同様に、第２の実施態様例（ＴＣＴ２）に対する限界も変化する。（また、２ｎ−２≧ｒｎである場合、トウィーク・ドメイン分離定数および＜|M| mod rn＞の双方に１つのｎ−ビット・ブロックを使用することができる。）
[0143]  長いメッセージに対する誕生日限界を超える安全性
【０５７０】
【数２４０】
2016540266.tif 000242
【０５７１】
が何らかの小さい値または中位の値に制限されない(bound)場合、第２の実施態様例（ＴＣＴ２）はもはや誕生日限界を超える安全性を提供しない。安全性限界において問題となる項は、
【０５７２】
【数２４１】
2016540266.tif 000243
【０５７３】
である。これに取り組むために、ＴＣＴＲ手順において、異なるブロック毎トウィーク関数を使用することができる。具体的には、
【０５７４】
【数２４２】
2016540266.tif 000244
【０５７５】
となる。ノンス制約付きの場合では、基礎の
【０５７６】
【数２４３】
2016540266.tif 000245
【０５７７】
が、次に、各メッセージ・ブロック上でこれまで見られなかった値によって、再調整される。
【０５７８】
【数２４４】
2016540266.tif 000246
【０５７９】
が理想的な暗号Πと交換されようとする場合、ノンス制約付きの場合では、平文の各ブロックが、新鮮なランダム置換の出力によってマスクされる。言い換えると、戻される各ブロックは、均一にランダムとなる。つまり、きつい制限(tight bound)がこの場合には予期される。あるいは、
【０５８０】
【数２４５】
2016540266.tif 000247
【０５８１】
を使用することができ、同じことが当てはまる。
Ｅ．従来の暗号化を使用して、初期化ベクトル（「ＩＶ」）保護可変入力長調整可能暗号（「ＶＩＬＴＣ」）をインスタンス化する
[0144]  あるいは、
【０５８２】
【数２４６】
2016540266.tif 000248
【０５８３】
は、直接従来のブロック暗号に基づく暗号化を使用して実現することもできる。以下の
【０５８４】
【数２４７】
2016540266.tif 000249
【０５８５】
および
【０５８６】
【数２４８】
2016540266.tif 000250
【０５８７】
の実施態様について検討する。
【０５８８】
【表１】
2016540266.tif 000251
【０５８９】
[0145]  この
【０５９０】
【数２４９】
2016540266.tif 000252
【０５９１】
の実施態様は、カウンタ・モード暗号化を使用するが、初期値Ｔが入力として表出され、それを調整可能暗号にする。生憎、この
【０５９２】
【数２５０】
2016540266.tif 000253
【０５９３】
の実施態様は、ノンス制約付きアドバーサリーに対抗するＳＲＮＤ安全性に欠ける。しかしながら、以下のように安全に変更することができる。
【０５９４】
【数２５１】
2016540266.tif 000254
【０５９５】
トウィーク空間
【０５９６】
【数２５２】
2016540266.tif 000255
【０５９７】
およびメッセージ空間
【０５９８】
【数２５３】
2016540266.tif 000256
【０５９９】
を有する
【０６００】
【数２５４】
2016540266.tif 000257
【０６０１】
を想定すると、オラクル
【０６０２】
【数２５５】
2016540266.tif 000258
【０６０３】
は質問
【０６０４】
【数２５６】
2016540266.tif 000259
【０６０５】
を取り込み、（１）
【０６０６】
【数２５７】
2016540266.tif 000260
【０６０７】
をサンプルし、
（２）ＥＫ（Ｔ，Ｘ）を戻す。オラクル
【０６０８】
【数２５８】
2016540266.tif 000261
【０６０９】
は、入力
【０６１０】
【数２５９】
2016540266.tif 000262
【０６１１】
上でも同様に振る舞い、サンプリング
【０６１２】
【数２６０】
2016540266.tif 000263
【０６１３】
を行い、
【０６１４】
【数２６１】
2016540266.tif 000264
【０６１５】
を戻す。
ＶＩ．可変入力長調整可能暗号（「ＶＩＬＴＣ」）を使用した、関連データ付き認証付暗号化／復号
[0146]  関連データ付き認証付暗号化（「ＡＥＡＤ」）は、ヘッダと共に送られるメッセージを認証する方法を提供する。例えば、平文メッセージが、その守秘性および真正性を保護する方法で暗号文に変換されるとき、このメッセージに付随し、メッセージと共に認証されなければならないパッカ・ヘッダ(packer header)または他の補助情報がある場合もある。メッセージがノンスおよび冗長性によって補強される場合、符号化メッセージを直接、十分に広いドメインを有する強擬似ランダム置換いＰＲＰ（「ＳＰＲＰ」）−安全ブロック暗号に通すことによって、認証付暗号化を得ることができる。
【０６１６】
[0147]  この章では、可変入力長調整可能暗号（「ＶＩＬＴＣ」）コンポーネントを使用して関連データ付き認証付暗号化（「ＡＥＡＤ」）を実現する方法について説明する。可変入力長調整可能暗号（「ＶＩＬＴＣ」）コンポーネントは、初期化ベクトル（「ＩＶ」）保護可変入力長調整可能暗号（「ＶＩＬＴＣ」）コンポーネント、または初期化ベクトル（「ＩＶ」）が保護されない可変入力長調整可能暗号（「ＶＩＬＴＣ」）コンポーネントを含むことができる。具体的には、この章では、ヘッダ−メッセージ対（Ｈ、Ｍ）から調整可能暗号入力（Ｔ、Ｘ）へのマッピングの傑出したプロパティを特定する。その簡素さに加えて、可変入力長調整可能暗号（「ＶＩＬＴＣ」）によって関連データ付き認証付暗号化（「ＡＥＡＤ」）を実現することには、様々な実用的な利点がある。
【０６１７】
[0148]  可変入力長調整可能暗号（「ＶＩＬＴＣ」）による認証付暗号化は、関連データを受け入れ、ノンス誤用(nonce-misuse)に耐えることができる。メッセージ・ヘッダを暗号文に結び付ける(bind)ために、トウィークを効果的に使用することができる。
【０６１８】
[0149]  加えて、メッセージおよびヘッダ入力内にあるランダム性、状態、または冗長性の効果を探ることができる。例えば、安全性の損失なくランダム性および状態をヘッダに移すことができ、暗号的に処理しなければならないビット数を削減できる潜在的可能性がある。具体的には、これは、平文入力内に既に存在するノンス、ランダム性、および冗長性を利用することによって、帯域幅オーバーヘッドを削減することができる。シーケンス番号、人間読み取り可能フィールド、または詰め物(padding)を含むプロトコルのメッセージは、有用なノンスおよび冗長性を含むことが多い。
【０６１９】
[0150]  また、可変入力長調整可能暗号（「ＶＩＬＴＣ」）による関連データ付き認証付暗号化（「ＡＥＡＤ」）は、サイド・チャネル攻撃に対してロバストであり続けながら、多数の復号エラー・メッセージに対処する。サイド・チャネル攻撃は、これらを利用しようとする（例えば、オラクルを詰まらせる）。多数の記述式エラー・メッセージの使用は、実用上非常に有用であり得るが、多くの場合有害な攻撃を強めることになる(empower)。これらの攻撃は、可変入力長調整可能暗号（「ＶＩＬＴＣ」）による関連データ付き認証付暗号化（「ＡＥＡＤ」）方式に対しては失敗する。何故なら、暗号文の任意のビットを緩やかに変化させると、復号された平文文字列のあらゆるビットをランダム化するからである。つまり、可変入力長調整可能暗号（「ＶＩＬＴＣ」）による関連データ付き認証付暗号化（「ＡＥＡＤ」）は、ある種のサイド・チャネルおよび共通の実装誤りに直面しても、ロバスト性を提供する。記述式エラー・メッセージ（例えば、bad_paddingまたはbad_seq_number）は、有用な今後の暗号文を形作るために利用することはできない。更に、ノンスの繰り返しは平文の等しいこと(equality)を漏らすに過ぎない。
【０６２０】
[0151]   この関連データ付き認証付暗号化（「ＡＥＡＤ」）手法は、フォーマット保存暗号化（「ＦＰＥ」）にも有効に作用する。変更を最小限に抑えて、透過的に暗号レイヤを旧来のシステムに挿入するために（例えば、データベース方式またはプロトコル仕様）、フォーマット保存暗号化（「ＦＰＥ」）は、平文と同じフォーマットを有する暗号文を使用する。例えば、ある（多くの場合非二進）アルファベットΣに対して、双方共集合Σｎに制限される可能性がある。これは、専用初期化ベクトル（「ＩＶ」）を暗号文に挿入することを除外する。暗号化を調整するために関連データを使用することによって補償することができ、調整可能暗号およびそれらの安全性定義を自然に調和させる。一意の関連データは、更に標準的な意味で守秘性を保証し、冗長性（クレジット・カード発行者識別番号およびチェックサムのような）をチェックすることによって、認証付暗号化を提供する。
【０６２１】
[0152]  一般に、ヘッダＨおよびメッセージＭを想定すると、可変入力長調整可能暗号（「ＶＩＬＴＣ」）による関連データ付き認証付暗号化（「ＡＥＡＤ」）方式は、（Ｈ，Ｍ）を調整可能暗号入力（Ｔ，Ｘ）にエンコードする。ある固定長のノンスについて、Ｔ＝ノンス||Ｈ、およびＸ＝ノンス||Ｍと仮定する。ヘッダＨは送信される。しかしながら、ノンス値も復号には必要とされるので、暗号文を単純に、
【０６２２】
【数２６２】
2016540266.tif 000265
【０６２３】
とすることはできない。したがって、暗号文は（ノンス，Ｃ）でなければならない。この例では、Ｔ＝ノンス||Ｈはエンコードされたヘッダであり、Ｘ＝ノンス||Ｍはエンコードされたメッセージであった。記号ＴおよびＸは、それぞれ、
【０６２４】
【数２６３】
2016540266.tif 000266
【０６２５】
および
【０６２６】
【数２６４】
2016540266.tif 000267
【０６２７】
と置き換えられる。Ｈから
【０６２８】
【数２６５】
2016540266.tif 000268
【０６２９】
へのマッピングは非決定論的であるが、ノンスを知っていれば、完全に再生することができる。ノンスは再現情報として役立つ。メッセージ・エンコード機能は、この再現情報を使用し、したがってヘッダ・エンコード機能とは異なるシグネチャーを有する。また、再現情報はＭに依存してはならない。受信側は、
【０６３０】
【数２６６】
2016540266.tif 000269
【０６３１】
を計算し、ノンスが
【０６３２】
【数２６７】
2016540266.tif 000270
【０６３３】
におけるＭのプレフィクスであることを確認する。
[0153]  更に形式的には、関連データ付き認証付暗号化（「ＡＥＡＤ」）方式は、鍵生成アルゴリズム
【０６３４】
【数２６８】
2016540266.tif 000271
【０６３５】
、暗号化アルゴリズム
【０６３６】
【数２６９】
2016540266.tif 000272
【０６３７】
、および復号アルゴリズム
【０６３８】
【数２７０】
2016540266.tif 000273
【０６３９】
を含むタプル
【０６４０】
【数２７１】
2016540266.tif 000274
【０６４１】
である。簡略化のために、鍵生成アルゴリズム
【０６４２】
【数２７２】
2016540266.tif 000275
【０６４３】
は、同じ名称の空でない集合からの鍵をサンプリングすると仮定する。暗号化アルゴリズムは、ランダム化されてもステートフルでもよく、マッピング
【０６４４】
【数２７３】
2016540266.tif 000276
【０６４５】
である。つまり、暗号化は、鍵
【０６４６】
【数２７４】
2016540266.tif 000277
【０６４７】
ヘッダ
【０６４８】
【数２７５】
2016540266.tif 000278
【０６４９】
およびメッセージ、
【０６５０】
【数２７６】
2016540266.tif 000279
【０６５１】
を取り込み、ある再現情報
【０６５２】
【数２７７】
2016540266.tif 000280
【０６５３】
を、暗号文Ｃと共に戻す。
【０６５４】
【数２７８】
2016540266.tif 000281
【０６５５】
は、
（Ｈ，Ｍ）上で実行中の
【０６５６】
【数２７９】
2016540266.tif 000282
【０６５７】
を表し、（Ｒ，Ｃ）を戻す。決定論的復号アルゴリズムは、マッピング、
【０６５８】
【数２８０】
2016540266.tif 000283
【０６５９】
であり、Errorsは、
【０６６０】
【数２８１】
2016540266.tif 000284
【０６６１】
となるような集合である。（｜Errors｜は１に等しい必要はない。）適正な動作のためには、全ての
【０６６２】
【数２８２】
2016540266.tif 000285
【０６６３】
について、
【０６６４】
【数２８３】
2016540266.tif 000286
【０６６５】
となる。
【０６６６】
【数２８４】
2016540266.tif 000287
【０６６７】
がステートフルである場合、これは全ての状態に該当する。
[0154]  実際には、ヘッダＨは、通例、暗号文と共に安全に(in the clear)送信される（例えば、ヘッダがルーティングに必要とされるとき）が、可変入力長調整可能暗号（「ＶＩＬＴＣ」）による関連データ付き認証付暗号化（「ＡＥＡＤ」）方式は、Ｈを内部の使用のための何らかの関係する
【０６６８】
【数２８５】
2016540266.tif 000288
【０６６９】
にエンコードすることもできる。このエンコード処理が非決定論的である場合、再現情報Ｒは、この
【０６７０】
【数２８６】
2016540266.tif 000289
【０６７１】
をＨから適正に再生するために復号によって使用されるあらゆるものを提供する。例えば、Ｒは、カウンタ、いくつかのランダム・ビット、または何らかの冗長性を含むことができる。また、これは空文字列であってもよい。
【０６７２】
[0155]  メッセージまたは鍵ビットをＲに書き込むことのために自動的に(trivially)危険になる構造を避けるために、以下の条件を適用する。任意の入力のシーケンス｛（Ｈｉ，Ｍｉ）｝ｉ≦ｑ、および任意の２つの可能な成果のシーケンス｛（Ｒｉ，Ｃｉ）｝ｉ≦ｑおよび｛（Ｒ’ｉ，Ｃ’ｉ）｝ｉ≦ｑを仮定し、次いで、任意の
【０６７３】
【数２８７】
2016540266.tif 000290
【０６７４】
について、
【０６７５】
【数２８８】
2016540266.tif 000291
【０６７６】
ここで、
【０６７７】
【数２８９】
2016540266.tif 000292
【０６７８】
および
【０６７９】
【数２９０】
2016540266.tif 000293
【０６８０】
状態
【０６８１】
【数２９１】
2016540266.tif 000294
【０６８２】
および
【０６８３】
【数２９２】
2016540266.tif 000295
【０６８４】
は、それぞれ、２つのトランスクリプト(transcript)が条件とされている。即ち、Ｒ（したがって、Ｒ’）は、Ｈ、ｑ、およびＲを生成する質問上で
【０６８５】
【数２９３】
2016540266.tif 000296
【０６８６】
によって投げられたコインのみに依存することができる。
[0156]  |Errors|>1を許すことによって、関連データ付き認証付暗号化（「ＡＥＡＤ」）方式は、多数の全く異なるエラー・メッセージを戻すことができる。これは、実際には、例えば、プロトコル・セッション内部における診断に有用となることができる。
【０６８７】
[0157]  理想的には、暗号文はランダム・ビットから区別不可能である。再現情報は、ランダムでないかもしれない（例えば、Ｒがカウンタであるかもしれない）。しかしながら、そのためにＩＮＤ＄−ＣＰＡ観念(notion)が修正される。具体的には、関連データ付き認証付暗号化（「ＡＥＡＤ」）方式Ψの守秘性は、以下のアドバンテージによって測定される。
【０６８８】
【数２９４】
2016540266.tif 000297
【０６８９】
【数２９５】
2016540266.tif 000298
【０６９０】
は、オラクルであり、入力（Ｈ，Ｍ）上で、
【０６９１】
【数２９６】
2016540266.tif 000299
【０６９２】
を計算し、
【０６９３】
【数２９７】
2016540266.tif 000300
【０６９４】
をサンプリングし、（Ｒ，Ｙ）を戻す。真正性の目標は暗号文の完全性である。即ち、
【０６９５】
【数２９８】
2016540266.tif 000301
【０６９６】
ここで、ブール事象Ｆｏｒｇｅｓは、
（１）
【０６９７】
【数２９９】
2016540266.tif 000302
【０６９８】
および、（２）
【０６９９】
【数３００】
2016540266.tif 000303
【０７００】
に対する以前の質問がいずれも（Ｈ，Ｒ，Ｃ）を戻さないように、Ａが質問（Ｈ，Ｒ，Ｃ）をその
【０７０１】
【数３０１】
2016540266.tif 000304
【０７０２】
オラクルに尋ねた場合にのみに限って、真となる。汎用性を失うことなく、Ｆｏｒｇｅｓが真になると直ぐに、Ａは停止する。
Ａ．エンコードおよびデコード方式
[0158]  非公式的には、エンコード・アルゴリズムはその入力をフォーマットし直し、ランダム性、状態、または冗長性を注入する。一方、デコード・アルゴリズムは元の入力データの有効性を判断して抜き出す。
【０７０３】
[0159]  更に形式的には、実施態様例において、関連データ付き認証付暗号化（「ＡＥＡＤ」）方式（および対応する復号）は、メッセージ空間
【０７０４】
【数３０２】
2016540266.tif 000305
【０７０５】
、ヘッダ・スペース
【０７０６】
【数３０３】
2016540266.tif 000306
【０７０７】
、エンコード・メッセージ空間
【０７０８】
【数３０４】
2016540266.tif 000307
【０７０９】
およびエンコード・ヘッダ
【０７１０】
【数３０５】
2016540266.tif 000308
【０７１１】
を使用する。これらの集合は、空ではないが、
【０７１２】
【数３０６】
2016540266.tif 000309
【０７１３】
に等しい可能性がある。集合Ｅrrorsについて、
【０７１４】
【数３０７】
2016540266.tif 000310
【０７１５】
である。
[0160]  ヘッダ・エンコード関数
【０７１６】
【数３０８】
2016540266.tif 000311
【０７１７】
は、ヘッダをエンコードされたヘッダに、恐らくは何らかのランダムなまたはステートフルな様式でマッピングする。非空集合
【０７１８】
【数３０９】
2016540266.tif 000312
【０７１９】
および全単射
【０７２０】
【数３１０】
2016540266.tif 000313
【０７２１】
があり、全てのＨに対して、ある
【０７２２】
【数３１１】
2016540266.tif 000314
【０７２３】
に対して、
【０７２４】
【数３１２】
2016540266.tif 000315
【０７２５】
というプロパティを有する。言い換えると、ＨはEncodeH(H)から復元することができ、EncodeH(H)の任意の特定の出力は、対応するＲが与えられると、Ｈから再生することができる。EncodeHは、
【０７２６】
【数３１３】
2016540266.tif 000316
【０７２７】
−エンコーダである（
【０７２８】
【数３１４】
2016540266.tif 000317
【０７２９】
を暗示的のままにしておく）。
[0161]  メッセージ・エンコード方式EncodeMsg=(EncodeM, DecodeM)は、メッセージ・エンコード機能
【０７３０】
【数３１５】
2016540266.tif 000318
【０７３１】
およびメッセージ・デコード機能
【０７３２】
【数３１６】
2016540266.tif 000319
【０７３３】
から構成されている。EncodeMは、ランダム化することができ、またはステートフルにすることができる。EncodeMのある状態に対して、
【０７３４】
【数３１７】
2016540266.tif 000320
【０７３５】
となる場合にのみに限って、
【０７３６】
【数３１８】
2016540266.tif 000321
【０７３７】
となる。それ以外の場合は、
【０７３８】
【数３１９】
2016540266.tif 000322
【０７３９】
となる。例えば、
【０７４０】
【数３２０】
2016540266.tif 000323
【０７４１】
となることが可能である。DecodeMアルゴリズムは決定論的であり、全てのアルゴリズムは線形時間で実行しなければならない。EncodeMsgは、
【０７４２】
【数３２１】
2016540266.tif 000324
【０７４３】
−エンコード方式である。
[0162]  エンコード機能は、最大ストレッチ(maximal stretch)が関連付けられている。これは、
【０７４４】
【数３２２】
2016540266.tif 000325
【０７４５】
の全てに対して、
【０７４６】
【数３２３】
2016540266.tif 000326
【０７４７】
および
【０７４８】
【数３２４】
2016540266.tif 000327
【０７４９】
となるような、最も小さい
【０７５０】
【数３２５】
2016540266.tif 000328
【０７５１】
であると定義される。
[0163]  エンコード・メカニズムの鍵となる１つのプロパティは、エンコード方式が出力を繰り返すように作ることができる尤度に関係する。Ａを、ｑ回の質問（必ずしも別個でなくてもよい）をオラクルｆに尋ね、
【０７５２】
【数３２６】
2016540266.tif 000329
【０７５３】
を応答で受け、これらの値を出力することによって停止するアドバーサリーであるとする。（ｆはメッセージ−またはヘッダ−エンコード関数とすることができる）。Ａは決定論的であると仮定することができる。
【０７５４】
【数３２７】
2016540266.tif 000330
【０７５５】
は関数である。ｆは、
【０７５６】
【数３２８】
2016540266.tif 000331
【０７５７】
である場合、（ｄ、δ）−衝突(-colliding)となる。この観念は、ｄ≧２に対してのみ定義される。（ｄ、δ）−衝突オラクルを想定すると、δ（０）＝δ（１）＝０であると仮定することができる。
【０７５８】
[0164]  第２の鍵となるプロパティは、ランダムな文字列（所与の長さの）が有効なエンコード処理である確率を捕らえる。本質的に、これは、エンコード処理の密度の尺度である。
【０７５９】
【数３２９】
2016540266.tif 000332
【０７６０】
は実数である。全ての正の整数ｎ、および全ての
【０７６１】
【数３３０】
2016540266.tif 000333
【０７６２】
に対して、
【０７６３】
【数３３１】
2016540266.tif 000334
【０７６４】
である場合、
【０７６５】
【数３３２】
2016540266.tif 000335
【０７６６】
エンコード方式EncodeMsg=(EncodeM, DecodeM)は、∈−疎(∈-sparse)となる。
Ｂ．エンコード−次いで−暗号化、対応する復号−次いで−デコードによる関連データ付き認証付暗号化（「ＡＥＡＤ」）
[0165]  図７は、可変入力長調整可能暗号（「ＶＩＬＴＣ」）を使用する、関連データ付き認証付暗号化のための技法（７００）を一般化して示す。暗号化システムは技法（７００）を実行する。
【０７６７】
[0166]  暗号化システムは、ヘッダおよびメッセージを受ける（７１０）。暗号化システムは、可変入力長調整可能暗号（「ＶＩＬＴＣ」）を使用してこのメッセージを処理し（７２０）、関連データ付き認証付暗号化を行う。可変入力長調整可能暗号（「ＶＩＬＴＣ」）は、保護された初期化ベクトル（「ＩＶ」）を使用する。あるいは、可変入力長調整可能暗号（「ＶＩＬＴＣ」）は従来の可変入力長調整可能暗号（「ＶＩＬＴＣ」）である。可変入力長調整可能暗号（「ＶＩＬＴＣ」）に対するトウィークは、少なくとも部分的にヘッダに基づく。この処理により、暗号化メッセージが生成される。暗号化システムは、ヘッダおよび暗号化メッセージを出力する（７３０）。
【０７６８】
[0167]  例えば、メッセージの処理（７２０）の一部として、暗号化システムは、ヘッダおよび再現情報を使用して修正ヘッダを決定し、次いでメッセージおよび修正ヘッダを使用して修正メッセージを決定する。暗号化システムは、可変入力長調整可能暗号（「ＶＩＬＴＣ」）を使用して修正メッセージを暗号化し、修正ヘッダは可変入力長調整可能暗号（「ＶＩＬＴＣ」）に対するトウィークを供給する。暗号化システムは、再現情報を、ヘッダおよび暗号化メッセージと共に出力する（７３０）。
【０７６９】
[0168]  暗号化システムは、１つ以上の他のメッセージのために技法（７００）を繰り返すことができる。
[0169]  図８は、可変入力長調整可能暗号（「ＶＩＬＴＣ」）を使用した、関連データによる認証復号のための技法（８００）を一般化して示す。復号システムは技法（８００）を実行する。
【０７７０】
[0170]  復号システムは、ヘッダおよび暗号化メッセージを受ける（８１０）。復号システムは、可変入力長調整可能暗号（「ＶＩＬＴＣ」）を使用して、暗号化メッセージを処理し（８２０）、関連データによる認証復号を行う。可変入力長調整可能暗号（「ＶＩＬＴＣ」）は、保護された初期化ベクトル（「ＩＶ」）を使用する。あるいは、可変入力長調整可能暗号（「ＶＩＬＴＣ」）は従来の可変入力長調整可能暗号（「ＶＩＬＴＣ」）である。可変入力長調整可能暗号（「ＶＩＬＴＣ」）に対するトウィークは、少なくとも部分的にヘッダに基づく。この処理により復号メッセージが生成され、復号システムはこれを出力する（８３０）。
【０７７１】
[0171]  復号システムは、再現情報も受けることができる。暗号化メッセージの処理（８２０）の一部として、例えば、復号システムは、ヘッダおよび再現情報を使用して修正ヘッダを決定し、次いで可変入力長調整可能暗号（「ＶＩＬＴＣ」）を使用して、暗号化メッセージを復号し、修正ヘッダが可変入力長調整可能暗号（「ＶＩＬＴＣ」）に対するトウィークを供給することによって、修正メッセージを生成する。復号システムは、修正メッセージおよび修正ヘッダを使用して、メッセージを決定する。
【０７７２】
[0172]  任意に、認証ステップの間に、復号システムはメッセージが有効であるか否か確認するためにチェックを行う。例えば、所定数の「０」ビットが暗号化の間にメッセージに添付されていた場合、復号はこれらのビットの存在をチェックすることができる。このチェックに失敗した場合、復号はエラーを出力する。メッセージを通すためには多数の異なるチェックがあってもよく、出力されるエラー（１つまたは複数）は、どのチェック（の組み合わせ）が失敗したのかに応じて、異なってもよい。（これは、認証付暗号化の「認証」部分である。攻撃者が暗号化メッセージを改竄した場合、一旦復号されたなら、恐らくもはや有効ではなくなるであろう。）
[0173]  復号システムは、１つ以上の他のメッセージのために技法（８００）を繰り返すことができる。
【０７７３】
[0174]  更に形式的には、実施態様例において、
【０７７４】
【数３３３】
2016540266.tif 000336
【０７７５】
は、調整可能暗号である。ある非空集合
【０７７６】
【数３３４】
2016540266.tif 000337
【０７７７】
に対して、EncodeＨは、
【０７７８】
【数３３５】
2016540266.tif 000338
【０７７９】
エンコーダであり、EncodeMsg=(EncodeM, DecodeM)は、
【０７８０】
【数３３６】
2016540266.tif 000339
【０７８１】
エンコード方式である。これらから、エンコード−次いで−暗号化関連データ付き認証付暗号化（「ＡＥＡＤ」）方式
【０７８２】
【数３３７】
2016540266.tif 000340
【０７８３】
を次のように定義する。
【０７８４】
【表２】
2016540266.tif 000341
【０７８５】
[0175]  再現情報Ｒは、復号がヘッダから
【０７８６】
【数３３８】
2016540266.tif 000342
【０７８７】
を再生することを可能にする（
【０７８８】
【数３３９】
2016540266.tif 000343
【０７８９】
を暗号文の一部として送る代わりに、またはコール側アプリケーションに、Ｈを
【０７９０】
【数３４０】
2016540266.tif 000344
【０７９１】
と交換させる代わりに）。
[0176]  単純な例として、EncodeＨは６４−ビット・カウンタRをヘッダＨに予め添付し、
【０７９２】
【数３４１】
2016540266.tif 000345
【０７９３】
はM||0８０を戻す。次いで、EncodeＨは（２，０）−衝突となり、EncodeMは２−８０−疎（しかし（２，１）−衝突）となる。真正性チェックは、DecodeM関数内部で暗示的に行われる。
【０７９４】
ＶＩＩ．結果の説明
[0177]  この章では、以上で提示した結果に対する詳細な正当とする理由を示す。
【０７９５】
[0178]  定理１−初期化ベクトル（「ＩＶ」）保護可変入力長調整可能暗号（「ＶＩＬＴＣ」）に対する安全性
初期化ベクトル（「ＩＶ」）保護可変入力長調整可能暗号（「ＶＩＬＴＣ」）はなおもその内部に可変入力長調整可能暗号（「ＶＩＬＴＣ」）モジュールを含む。初期化ベクトル（「ＩＶ」）保護可変入力長調整可能暗号（「ＶＩＬＴＣ」）は、より大きなドメインを有し、Ｎ−ビット調整可能ブロック暗号（「ＴＢＣ」）は安全性に関して利点が得られる。
【０７９６】
[0179]  ＩＶ章において定義したトウィーク空間およびメッセージ空間
【０７９７】
【数３４２】
2016540266.tif 000346
【０７９８】
について、そして調整可能ブロック暗号（「ＴＢＣ」）長Ｎについて、
【０７９９】
【数３４３】
2016540266.tif 000347
【０８００】
は、調整可能ブロック暗号であり、
【０８０１】
【数３４４】
2016540266.tif 000348
【０８０２】
は可変入力長調整可能暗号（「ＶＩＬＴＣ」）である。
【０８０３】
【数３４５】
2016540266.tif 000349
【０８０４】
Ａは、ｑ＜２Ｎ／４回の質問を行い、合計してμビットとなり、時間ｔにおいて実行するアドバーサリーである。それぞれｑ回および２ｑ回の質問を行い、双方共Ｏ（ｔ）時間において実行するアドバーサリーＢおよびＣについて、
【０８０５】
【数３４６】
2016540266.tif 000350
【０８０６】
ここで、Ｂはノンス制約付きであり、その質問の長さは合計してμ−ｑＮビットになる。
[0180]  ＰＩＶ組成の可変入力長（「ＶＩＬ」）部分
【０８０７】
【数３４７】
2016540266.tif 000351
【０８０８】
は、ノンス制約付きアドバーサリーのみに対してＳＲＮＤ−安全である必要がある。この要件を満たす効率的な方式を構築することは容易である。固定入力長（「ＦＩＬ」）部分
【０８０９】
【数３４８】
2016540266.tif 000352
【０８１０】
だけが、任意の質問戦略を使用することができる強調整可能擬似ランダム置換（「ＳＴＰＲＰ」）アドバーサリーに対して安全であればよい。つまり、ＰＩＶ組成は、大きなドメインに渡るノンス制約付きの安全性を、それよりも多少大きなドメインに渡る完全な強調整可能擬似ランダム置換（「ＳＴＰＲＰ」）安全性に昇級させる。
【０８１１】
【数３４９】
2016540266.tif 000353
【０８１２】
が相応しい強調整可能擬似ランダム置換（「ＳＴＰＲＰ」）である場合、ＴまたはＸの任意の部分が「新鮮」であるなら、初期化ベクトル（「ＩＶ」）に対する文字列はランダムなはずである。したがって、初期化ベクトル（「ＩＶ」）値は繰り返されそうもなく、したがって可変入力長（「ＶＩＬ」）組成のノンス制約付きの安全性は十分である。同じことは、Ｔ、Ｙの任意の部分が「新鮮」である場合、復号のときにも当てはまる。
【０８１３】
[0181]  項４ｑ２／２Ｎは、初期化ベクトル（「ＩＶ」）における衝突、および
【０８１４】
【数３５０】
2016540266.tif 000354
【０８１５】
とランダム関数との間の差を考慮する。これは、Ｎにおける誕生日限界項、
【０８１６】
【数３５１】
2016540266.tif 000355
【０８１７】
のブロック・サイズである。殆どの調整可能ブロック暗号（「ＴＢＣ」）設計は（１つ以上の）基礎のブロック暗号を採用するので、
【０８１８】
【数３５２】
2016540266.tif 000356
【０８１９】
のブロック・サイズＮは、それを構築するかもしれないいずれかの基礎のブロック暗号のブロック・サイズｎよりも大きくすることができる。実際、ｎ−ビット・ブロック暗号（およびハッシュ関数）を想定すると、
【０８２０】
【数３５３】
2016540266.tif 000357
【０８２１】
をＮ＝２ｎで構築することができる。
[0182]  下位
【０８２２】
【数３５４】
2016540266.tif 000358
【０８２３】
呼び出し(lower F invocation)を除去し（
【０８２４】
【数３５５】
2016540266.tif 000359
【０８２５】
の後）、
【０８２６】
【数３５６】
2016540266.tif 000360
【０８２７】
を戻す場合、結果的に得られる組成は、一般に安全な強調整可能擬似ランダム置換（「ＳＴＰＲＰ」）を提供しない。一方で、これは調整可能擬似ランダム置換（「ＴＰＲＰ」）としては安全である（単に強い調整可能擬似ランダム置換（「ＴＰＲＰ」）ではない）。メッセージ空間
【０８２８】
【数３５７】
2016540266.tif 000361
【０８２９】
トウィーク空間
【０８３０】
【数３５８】
2016540266.tif 000362
【０８３１】
、および負でない整数ｎ≦ｍｉｎ（Ｓ）に対して、Ａはせいぜいｑ回の質問を行い時間ｔにおいて実行するアドバーサリーとする。
【０８３２】
【数３５９】
2016540266.tif 000363
【０８３３】
この結果は、本質的に、調整可能ブロック暗号（「ＴＢＣ」）に対するＰＲＦ−擬似ランダム置換（「ＰＲＰ」）切り替え命題であり、問題を境界(bounding)
【０８３４】
【数３６０】
2016540266.tif 000364
【０８３５】
のそれに縮減する。
[0183]  
【０８３６】
【数３６１】
2016540266.tif 000365
【０８３７】
について検討する。ここで、
【０８３８】
【数３６２】
2016540266.tif 000366
【０８３９】
は理想的な暗号である。ゲーム１（「Ｇ１」）（図９に示す）におけるオラクルは、Πを定義するために、レイジー・サンプリング(lazy sampling)を使用して、
【０８４０】
【数３６３】
2016540266.tif 000367
【０８４１】
および
【０８４２】
【数３６４】
2016540266.tif 000368
【０８４３】
をシミュレーションする。したがって、
【０８４４】
【数３６５】
2016540266.tif 000369
【０８４５】
となる。図９において、ゲーム１はボックス状ステートメント(boxed statements)を含む。
[0184]  ゲーム２（「Ｇ２」）（これも図９に示す）において、Πを定義するとき、「違法な」値はもはや再サンプリングされない。図９において、ゲーム２はボックス状ステートメントを含まない。コードにおける唯一の変化が起こるのは、ブール「悪い」フラグが真に設定された後である。ゲーム−プレーイングの基礎命題によって、
【０８４６】
【数３６６】
2016540266.tif 000370
【０８４７】
ゲーム２において、
【０８４８】
【数３６７】
2016540266.tif 000371
【０８４９】
は、決して同じトウィークを２回使用して質問されず、ゲームにおけるオラクルはランダムなｎ−ビット・プレフィックスを有する値を戻す。ゲーム１および２において、ブール変数は偽に初期化される。
【０８５０】
[0185]  第３ゲーム（「Ｇ３」）（図９には示されていない）では、
【０８５１】
【数３６８】
2016540266.tif 000372
【０８５２】
はオラクル
【０８５３】
【数３６９】
2016540266.tif 000373
【０８５４】
によって交換される。このオラクルは、常に、その第２入力と長さが等しいランダム文字列を返す。標準的な引数によって、
【０８５５】
【数３７０】
2016540266.tif 000374
【０８５６】
となるように、ｑ回の質問を行い、
【０８５７】
【数３７１】
2016540266.tif 000375
【０８５８】
時間において実行する何らかのノンス制約付きアドバーサリーＢが存在する。これから次の式が得られる。
【０８５９】
【数３７２】
2016540266.tif 000376
【０８６０】
各オラクル出力（Ｚ’ｉに対応する）の各最初のＮビットは、常にゲーム２では均一にランダムである。ゲーム３において
【０８６１】
【数３７３】
2016540266.tif 000377
【０８６２】
が
【０８６３】
【数３７４】
2016540266.tif 000378
【０８６４】
に切り替わるとき、残りのビットも均一にランダムになる。したがって、
【０８６５】
【数３７５】
2016540266.tif 000379
【０８６６】
となる。
[0186]  最後のタスクは、Ａがゲーム２において悪いフラグを設定する確率を制限することである。ｂａｄ１が質問ｊの間に設定される確率は、ｊ／（２Ｎ−２ｊ）未満である。同様に、ｂａｄ２およびｂａｄ３が設定される確率も、それぞれ、高々２ｊ／（２Ｎ−２ｊ）および２ｊ／２Ｎである。したがって、少なくとも１つのフラグが質問ｊの間に設定される確率は、高々３ｊ／（２Ｎ−２ｊ）＋２ｊ／２Ｎである。
【０８６７】
[0187]  ｊ∈１，２，．．．、ｑに対して結合限界(union bound)を取ると、
【０８６８】
【数３７６】
2016540266.tif 000380
【０８６９】
となる。ｑ＜２Ｎ／４であるので、１．５／（２Ｎ−２ｑ）＜３／２Ｎとなる。直前の結果により、標準的な引数を使用して、計算設定に戻ると、証明が完成する。
【０８７０】
【数３７７】
2016540266.tif 000381
【０８７１】
ここで、Ｃは２ｑ回の質問を行い、Ｂは、トウィークを繰り返さずに、合計で長さμ−ｑＮビットとなるｑ回の質問を行い、双方共
【０８７２】
【数３７８】
2016540266.tif 000382
【０８７３】
時間において実行する。
[0188]  定理２−ＴＣＴＲ  ｇ（Ｔ，ｉ）＝Ｔのときの手順ＴＣＴＲの挙動について検討する。Ｖ章のＴＣＴＲ疑似コードの一覧におけるように、
【０８７４】
【数３７９】
2016540266.tif 000383
【０８７５】
として、
【０８７６】
【数３８０】
2016540266.tif 000384
【０８７７】
ならびに
【０８７８】
【数３８１】
2016540266.tif 000385
【０８７９】
および
【０８８０】
【数３８２】
2016540266.tif 000386
【０８８１】
を定義する。Ａは、時間ｔにおいて実行し、ｑ回の質問を尋ねるノンス制約付きアドバーサリーであり、各質問の長さは高々
【０８８２】
【数３８３】
2016540266.tif 000387
【０８８３】
ビットである（したがって、
【０８８４】
【数３８４】
2016540266.tif 000388
【０８８５】
。次いで、高々
【０８８６】
【数３８５】
2016540266.tif 000389
【０８８７】
回の質問を行い時間
【０８８８】
【数３８６】
2016540266.tif 000390
【０８８９】
において実行するあるアドバーサリーＢについて、
【０８９０】
【数３８７】
2016540266.tif 000391
【０８９１】
となる。
【０８９２】
【数３８８】
2016540266.tif 000392
【０８９３】
であるとき、限界は誕生日型挙動を呈し、
【０８９４】
【数３８９】
2016540266.tif 000393
【０８９５】
が小さな定数であるときに最も厳しくなる。定数
【０８９６】
【数３９０】
2016540266.tif 000394
【０８９７】
が小さい重要な用途に、完全ディスク暗号化がある。ここでは、平文Ｘは通例長さが４０９６バイトであり、したがって基礎の調整可能ブロック暗号（「ＴＢＣ」）がサイズｎ＝１２８のブロック・サイズを有する場合、大まかに
【０８９８】
【数３９１】
2016540266.tif 000395
【０８９９】
ブロックがある。
[0189]  定理３−第１の実施態様例（ＴＣＴ１）の強調整可能擬似ランダム置換（「ＳＴＰＲＰ」）安全性  Ｖ．Ｂ章において定義したＴＣＴ1について、Ａは、ｑ＜２ｎ／４回の質問を行い時間ｔにおいて実行するアドバーサリーである。アドバーサリーＢおよびＣは、双方共
【０９００】
【数３９２】
2016540266.tif 000396
【０９０１】
となるように、時間
【０９０２】
【数３９３】
2016540266.tif 000397
【０９０３】
において実行し、
【０９０４】
【数３９４】
2016540266.tif 000398
【０９０５】
回および２ｑ回の質問をそれぞれ行う。したがって、以下の式が得られる。
【０９０６】
【数３９５】
2016540266.tif 000399
【０９０７】
[0190]  このアルゴリズムは、
【０９０８】
【数３９６】
2016540266.tif 000400
【０９０９】
の２つの鍵を含む、
【０９１０】
【数３９７】
2016540266.tif 000401
【０９１１】
ビットの鍵素材を必要とする。安全性限界に重大な損傷がなければ、Ｅには１つの鍵で十分であろうが、しかしながら、この改善は主に処理能力の問題から関心が寄せられている。つまり、第１の実施態様例（ＴＣＴ１）は、以前の構造の安全性を保持し、有限界におけるのではなく、法に対する２の冪(powers-of-two moduli)を有するリング(ring)における算術演算を使用する。これは、潜在的に、あるアーキテクチャにおいて処理能力を高めることができる。
【０９１２】
[0191]  定理４−第２の実施態様例（ＴＣＴ２）の強調整可能擬似ランダム置換（「ＳＴＰＲＰ」）安全性  Ｖ．Ｃ章において定義したＴＣＴ２について、Ａは、ｑ回の質問を行い時間ｔにおいて実行するアドバーサリーであり、ここで、
【０９１３】
【数３９８】
2016540266.tif 000402
【０９１４】
である。アドバーサリーＢおよびＣは、双方共、
【０９１５】
【数３９９】
2016540266.tif 000403
【０９１６】
となるように、
【０９１７】
【数４００】
2016540266.tif 000404
【０９１８】
時間において実行し、それぞれ、
【０９１９】
【数４０１】
2016540266.tif 000405
【０９２０】
および６ｑ回質問を行う。したがって、以下の式が得られる。
【０９２１】
【数４０２】
2016540266.tif 000406
【０９２２】
[0192]  この限界における定数の一部が重要である。しかしながら、第２の実施態様例（ＴＣＴ２）は、第１の実施態様例（ＴＣＴ１）および以前の構造よりもはるかに優れた安全性限界を提供する。
【０９２３】
[0193]  定理５−長いメッセージに対する誕生日限界を超える安全性
【０９２４】
【数４０３】
2016540266.tif 000407
【０９２５】
は調整可能ブロック暗号（「ＴＢＣ」）であり、
【０９２６】
【数４０４】
2016540266.tif 000408
【０９２７】
および
【０９２８】
【数４０５】
2016540266.tif 000409
【０９２９】
もＶ．Ｄ章におけるように定義し、
【０９３０】
【数４０６】
2016540266.tif 000410
【０９３１】
は、任意の注入マッピング(injective mapping)である。Ａは、時間ｔにおいて実行し、全長が高々μ＝σｎビットであるｑ回の質問を尋ねるノンス制約付きアドバーサリーである。あるアドバーサリーＢは、
【０９３２】
【数４０７】
2016540266.tif 000411
【０９３３】
となるように、高々σ回の質問を行い時間
【０９３４】
【数４０８】
2016540266.tif 000412
【０９３５】
において実行する。第１の実施態様例（ＴＣＴ１）および第２の実施態様例（ＴＣＴ２）に対する安全性証明のためにＴＣＴＲのこの変種を使用すると、限界から
【０９３６】
【数４０９】
2016540266.tif 000413
【０９３７】
項が除去され、これによってメッセージ長の問題が持ち上がる。この変更が行われる場合、単に１回だけではなく、呼び出し毎に
【０９３８】
【数４１０】
2016540266.tif 000414
【０９３９】
回までｇ（Ｔ，ｉ）が計算される。この問題は、ＬＲＷ２の代わりに、他の調整可能ブロック暗号（「ＴＢＣ」）を使用することによって軽減することができる（Rogaway, "Efficient Instantiations of Tweakable  Blockciphers and Refinements to Modes OCB and PMAC"（調整可能ブロック暗号の効率的なインスタンス化およびモードＯＣＢおよびＰＭＡＣに対する精緻化）(2004)に記載されているように）。これは、安全性限界を著しく変化させることなく、トウィークを非常に速く増分させる。以上の変更がなされるとき、第１の実施態様例（ＴＣＴ１）および第２の実施態様例（ＴＣＴ２）は、有界でない領域において効率的な調整可能暗号を提供し、
【０９４０】
【数４１１】
2016540266.tif 000415
【０９４１】
ビット（それぞれ、
【０９４２】
【数４１２】
2016540266.tif 000416
【０９４３】
）が暗号化された後でなければ安全性保証を失わない。
[0194]  定理６および命題−従来の暗号化による、初期化ベクトル（「ＩＶ」）保護可変入力長調整可能暗号（「ＶＩＬＴＣ」）
【０９４４】
【数４１３】
2016540266.tif 000417
【０９４５】
、整数Ｎを仮定する。
【０９４６】
【数４１４】
2016540266.tif 000418
【０９４７】
および調整可能暗号
【０９４８】
【数４１５】
2016540266.tif 000419
【０９４９】
については定理１において説明した。Ａは、ｑ＜２Ｎ／４回の質問を行い時間ｔにおいて実行するアドバーサリーである。アドバーサリーＢおよびＣは、
【０９５０】
【数４１６】
2016540266.tif 000420
【０９５１】
となるように、それぞれｑ回および２ｑ回の質問を行い、時間
【０９５２】
【数４１７】
2016540266.tif 000421
【０９５３】
において実行する。ここでＢはノンス制約付きである。標準的な証明では、Ｅが擬似ランダム置換（「ＰＲＰ」）のように安全である場合、Ｖ．Ｅ章における擬似コード一覧における調整可能ブロック暗号（「ＴＢＣ」）が、誕生日限界までＳＲＮＤ＄−安全であることを示す。
【０９５４】
[0195]  
【０９５５】
【数４１８】
2016540266.tif 000422
【０９５６】
はブロック暗号であると仮定し、
【０９５７】
【数４１９】
2016540266.tif 000423
【０９５８】
および
【０９５９】
【数４２０】
2016540266.tif 000424
【０９６０】
はＶ．Ｅ章における擬似コード一覧におけるように定義する。Ａは、時間ｔにおいて実行しｑ回の質問を尋ねるアドバーサリーであるとし、これらは合計で高々μ＝σｎビットである。次いで、
【０９６１】
【数４２１】
2016540266.tif 000425
【０９６２】
ここで、Ｂは、高々ａ回質問を尋ね、時間
【０９６３】
【数４２２】
2016540266.tif 000426
【０９６４】
において実行する。
[0196]  このように、効率的な誕生日限界−安全な強調整可能擬似ランダム置換（「ＳＴＰＲＰ」）を構築するために、ＬＲＷ２に基づいて
【０９６５】
【数４２３】
2016540266.tif 000427
【０９６６】
によってカウンタ・モード暗号化を構成する(compose)ことができる。
【０９６７】
【数４２４】
2016540266.tif 000428
【０９６８】
を特殊な種類のＰＲＦ（逆転可能性プロパティを有するもの）として見ることができ、入力（Ｔ，Ｘ）を取り込み、カウンタ・モードにおける使用のために「合成初期化ベクトル（「ＩＶ」）」を戻す。次いで、
【０９６９】
【数４２５】
2016540266.tif 000429
【０９７０】
の２回目の適用は、鍵Ｋ’を有する者には復元可能なまま残すようにこの合成初期化ベクトル（「ＩＶ」）を隠す役割を果たす。
[0197]  このカウンタ−モード構造の安全性は、章Ｖ．Ｅ．の擬似コード一覧における
【０９７１】
【数４２６】
2016540266.tif 000430
【０９７２】
の構造において示すように、基礎のブロック暗号を「リキーイング」(re-keying)し、
【０９７３】
【数４２７】
2016540266.tif 000431
【０９７４】
を使用してメッセージ毎の鍵を生成することによって高めることができる。
【０９７５】
【数４２８】
2016540266.tif 000432
【０９７６】
を、（１）
【０９７７】
【数４２９】
2016540266.tif 000433
【０９７８】
として計算し、（２）
【０９７９】
【数４３０】
2016540266.tif 000434
【０９８０】
を戻すようにして計算できる。任意の関数
【０９８１】
【数４３１】
2016540266.tif 000435
【０９８２】
について、ｆに対するアドバーサリーＡの擬似乱数関数（ＰＲＦ）の利点は、
【０９８３】
【数４３２】
2016540266.tif 000436
【０９８４】
と定義されることを思い出すこと。次に、定理理論６に進む。
[0198]  定理６
【０９８５】
【数４３３】
2016540266.tif 000437
【０９８６】
はブロック暗号であり、
【０９８７】
【数４３４】
2016540266.tif 000438
【０９８８】
および
【０９８９】
【数４３５】
2016540266.tif 000439
【０９９０】
はＶ．Ｅ章における擬似コード一覧におけるように定義する。
【０９９１】
【数４３６】
2016540266.tif 000440
【０９９２】
は関数であり、
【０９９３】
【数４３７】
2016540266.tif 000441
【０９９４】
および
【０９９５】
【数４３８】
2016540266.tif 000442
【０９９６】
は、Ｖ．Ｅ章の擬似コード一覧におけるように定義する。Ａは、時間ｔにおいて実行し、ｑ回の質問を尋ねるノンス制約付きアドバーサリーであり、質問は、各々、高々ｍｎビットの長さである（したがって、μ≦ｑｍｎ）。
【０９９７】
【数４３９】
2016540266.tif 000443
【０９９８】
ここで、（１）Ｂは高々ｍ回の質問を尋ね、時間
【０９９９】
【数４４０】
2016540266.tif 000444
【１０００】
において実行し、（２）Ｃはｑ回の質問を尋ね、高々時間
【１００１】
【数４４１】
2016540266.tif 000445
【１００２】
において実行する。
[0199]  メッセージｍにおけるブロックの最大数が小さい場合、このリキーイング手法は、ノンス制約付きアドバーサリーに対して、誕生日限界を超えるＳＲＮＤ−安全性を与える潜在的可能性がある。完全ディスク暗号化（「ＦＤＥ」）の場合、例えば、
【１００３】
【数４４２】
2016540266.tif 000446
【１００４】
は、ｎ＝１２８のとき非常に小さく見えるので、ｑ＞＞２６４に対する安全性が可能に思われる。この実施態様は、このようなｑのいずれに対しても安全であり続けるＰＲＦｆを使用する。
【１００５】
[0200]  いずれの場合でも、
【１００６】
【数４４３】
2016540266.tif 000447
【１００７】
の構造は、調整可能プリミティブ抽象化の中核原理を破る。即ち、トウィークの変更は速くなければならず、鍵を変更するよりも遙かに速くなければならない。
[0201]  定理７−関連データ付き認証付暗号化（「ＡＥＡＤ」）に対する守秘性  ＶＩ．Ｂ章における擬似コード一覧において定義したように、
【１００８】
【数４４４】
2016540266.tif 000448
【１００９】
ｓはEncodeMsgの最大ストレッチであり、ｓ’はEncodeＨの最大ストレッチであり、ｍは、ある
【１０１０】
【数４４５】
2016540266.tif 000449
【１０１１】
に対して、
【１０１２】
【数４４６】
2016540266.tif 000450
【１０１３】
を満たす、最も短い
【１０１４】
【数４４７】
2016540266.tif 000451
【１０１５】
の長さである。Ａは、合計でμビットとなるｑ回の質問を行い、時間ｔにおいて実行するアドバーサリーである。δMが増大しつつあり、｛０，１，．．．，ｑ｝上で凸であるとき、このδMに対してEncodeHが（ｄ，δH)−衝突であり、EncodeMが（２，δM)−衝突である場合、
【１０１６】
【数４４８】
2016540266.tif 000452
【１０１７】
となるようなアドバーサリーＢがある。ここで、Ｂは全長が高々μ＋ｑ（ｓ＋ｓ’）ビットであるｑ回の質問を行い、時間
【１０１８】
【数４４９】
2016540266.tif 000453
【１０１９】
において実行する。
[0202]  定理８-関連データ付き認証付暗号化（「ＡＥＡＤ」）に対する真正性  ＶＩ．Ｂ章の擬似コード一覧において定義したように、
【１０２０】
【数４５０】
2016540266.tif 000454
【１０２１】
ｓはEncodeMsgのストレッチであり、ｓ’はEncodeHの最大ストレッチであり、ｍは、ある
【１０２２】
【数４５１】
2016540266.tif 000455
【１０２３】
について
【１０２４】
【数４５２】
2016540266.tif 000456
【１０２５】
を満たす最も短い
【１０２６】
【数４５３】
2016540266.tif 000457
【１０２７】
の長さである。Ａは、その暗号化（それぞれ、復号）オラクルに、合計でμε（それぞれ、
【１０２８】
【数４５４】
2016540266.tif 000458
【１０２９】
）ビットとなるｑε（それぞれ、
【１０３０】
【数４５５】
2016540266.tif 000459
【１０３１】
）回の質問を行い、時間ｔにおいて実行するアドバーサリーである。EncodeMが ∈−疎で、
【１０３２】
【数４５６】
2016540266.tif 000460
【１０３３】
である場合、
【１０３４】
【数４５７】
2016540266.tif 000461
【１０３５】
となるようなアドバーサリーＢがあり、ここで、Ｂは、全長（με＋ｑεｓ）ビットのｑε回の順方向質問(forward-query)、全長
【１０３６】
【数４５８】
2016540266.tif 000462
【１０３７】
ビットのｑＤ回の逆方向−質問を行い、
【１０３８】
【数４５９】
2016540266.tif 000463
【１０３９】
時間において実行する。
[0203]  EncodeHが（２，０）−衝突である場合について検討する。この場合、守秘性限界（定理７）は、
【１０４０】
【数４６０】
2016540266.tif 000464
【１０４１】
に簡略化する。これは直観的である。何故なら、トウィーク
【１０４２】
【数４６１】
2016540266.tif 000465
【１０４３】
が決して繰り返さない場合、出力
【１０４４】
【数４６２】
2016540266.tif 000466
【１０４５】
は（Ｈ，Ｍ）の任意の有効な
【１０４６】
【数４６３】
2016540266.tif 000467
【１０４７】
へのエンコードに対して、均一なランダム文字列となるからであり、EncodeH（Ｈ，Ｍ）＝Ｍで十分である。つまり、ヘッダＨを正しくエンコードすると、（Ｈ，Ｍ）の
【１０４８】
【数４６４】
2016540266.tif 000468
【１０４９】
へのエンコードにかかる負担を大幅に低減することができる。
[0204]  更に一般的には、ある小さな定数ｄ＜＜ｑに対して、EncodeHが任意の
【１０５０】
【数４６５】
2016540266.tif 000469
【１０５１】
をｄ回よりも多く生成する確率は、無視し得ると仮定する。すると、限界における最終項を事実上無視することができる。第２項は、大まかに、
【１０５２】
【数４６６】
2016540266.tif 000470
【１０５３】
となる。ここで、δMはｑではなくｄにおいて評価され、したがってｑδＭ（ｄ）は、適度な量のランダム性を
【１０５４】
【数４６７】
2016540266.tif 000471
【１０５５】
にエンコードすることによって（例えば、ｌｏｇ（ｑ）ビット）無視可能にできることに注意すること。次いで、ある自然なEncodeMsgの選択では、ｑ／２ｍ＋１が優勢項となり、ここでｍは
【１０５６】
【数４６８】
2016540266.tif 000472
【１０５７】
の最も短い長さである。しかし、正しい真正性限界を達成するために、ｍがｑ／２ｍ＋１に限界を破壊させる(ruin)ことはありそうもない。
[0205]  トウィークが存在することによって、ランダム性または状態のための「余分な」ビットを、ヘッダのエンコードに移すことが可能になり、潜在的に、暗号的に処理しなければならないビット数が減少する。
【１０５８】
[0206]  これより真正性限界（定理８）に移り、EncodeMがｂ冗長ビット（したがって、∈≒２−ｂ）およびｑε＋ｑD＜＜２ｍを挿入する場合、真正性限界の第２項は、近似的にｑＤ／２ｂとなることを注記しておく。つまり、調整可能暗号
【１０５９】
【数４６９】
2016540266.tif 000473
【１０６０】
が、例えば、２８０回の質問まで強調整可能擬似ランダム置換（「ＳＴＰＲＰ」）−安全性を有する場合（例えば、ＰＩＶをＮ＝２５６でしかるべくインスタンス化する）、ノンスによってヘッダをエンコードし、８０ビットの冗長性でメッセージをエンコードすると、大凡８０ビットの守秘性および真正性保証がある関連データ付き認証付暗号化（「ＡＥＡＤ」）方式、およびノンス−誤用に耐えることができるものが得られる。
【１０６１】
[0207]  定理８の証明は、アドバーサリーがEncodeMおよびEncodeHのコインおよび状態を制御するのであっても、先に述べた限界がそのままである(hold)ことを示すために容易に修正することができる。加えて、復号オラクルの質問のみが冗長でないと仮定し、アドバーサリーは、ヘッダまたはメッセージにエンコードされるいずれのノンスにも配慮しないと仮定する。
【１０６２】
[0208]  定理７の証明
【１０６３】
【数４７０】
2016540266.tif 000474
【１０６４】
はランダム暗号である。Ψ[Π]は、
【１０６５】
【数４７１】
2016540266.tif 000475
【１０６６】
のアルゴリズムにおけるいずれかの場所で、
【１０６７】
【数４７２】
2016540266.tif 000476
【１０６８】
および
【１０６９】
【数４７３】
2016540266.tif 000477
【１０７０】
をΠおよびΠ−１でぞれぞれ置き換えることによって得られた関連データ付き認証付暗号化（「ＡＥＡＤ」）方式である。εΠは、対応する暗号化アルゴリズムである。それ自体のオラクルに応じてεＫまたはεΠをシミュレーションする標準的なアドバーサリーＢに対して、
【１０７１】
【数４７４】
2016540266.tif 000478
【１０７２】
これは、
【１０７３】
【数４７５】
2016540266.tif 000479
【１０７４】
を残す。
[0209]  図１０における３つのゲームのシーケンスは、証明を例示するのに役立つ。図１０において、四角く囲ったコマンドは、ゲーム１には含まれるがゲーム２からは省略され、εΠオラクルに常にランダム文字列を返させる。ゲーム３は、この変化をアドバーサリーが検出することができる確率を制限する(bound)（「悪い」値が設定される確率によって測定されるように）。
【１０７５】
[0210]  ｓは、EncodeMのストレッチである。ゲーム１（図１０における）は、Πを定義するためにレイジー・サンプリングを使用してεΠを実装する。具体的には、ｉ番目の質問（Ｈｉ，Ｍｉ）において、ゲーム１はエンコード
【１０７６】
【数４７６】
2016540266.tif 000480
【１０７７】
を計算し、次いで、
【１０７８】
【数４７７】
2016540266.tif 000481
【１０７９】
に割り当てるための潜在的な値Ｓｉをサンプリングする。この値は、
【１０８０】
【数４７８】
2016540266.tif 000482
【１０８１】
が未だ設定されていない限り、そして以前にＳｉが
【１０８２】
【数４７９】
2016540266.tif 000483
【１０８３】
と共に使用されていない限り有効である。そうでない場合、ゲーム１はｂａｄ１またはｂａｄ２を設定し、次いでＳｉにしかるべき値を割り当て直す。
[0211]  ゲーム２（図１０における）は、ｂａｄ１またはｂａｄ２が設定されるまで、ゲーム１と同一であるので、
【１０８４】
【数４８０】
2016540266.tif 000484
【１０８５】
ここで、最終ライン(final line)は、ゲーム−プレーイングの基本的命題の代替定式化(formulation)を使用する。ゲーム２では、Ｓｉの値は
【１０８６】
【数４８１】
2016540266.tif 000485
【１０８７】
において常に均一にランダムであり、εΠの出力は、各Ｍｉとは独立である。その結果、Ａが停止した後まで、各Ｍｉへの値の割り当てを遅らせることができる。一方、このために、ｂａｄ１またはｂａｄ２を設定すべきか確認するためのチェックを、これらがそうなる確率を変えることなく、遅らせることが可能になる。これらの変更双方を行うことによって、ゲーム３（図１０における）が求められるので、
【１０８８】
【数４８２】
2016540266.tif 000486
【１０８９】
となる。つまり、
【１０９０】
【数４８３】
2016540266.tif 000487
【１０９１】
ここで、最後の式は、ゲーム３において、各Ｓｉが独立して、そして均一にランダムに、しかるべき大きさにされた文字列の集合からサンプリングされるという事実から得られる。要点を纏めると、この時点において、
【１０９２】
【数４８４】
2016540266.tif 000488
【１０９３】
となる。
[0212]  
【１０９４】
【数４８５】
2016540266.tif 000489
【１０９５】
に対して上界を確立するために、ゲーム３において実行した後に、Ａがその出力を丁度生成したところであると仮定する。ｂａｄ１が設定される確率を制限する(bound)ために、
【１０９６】
【数４８６】
2016540266.tif 000490
【１０９７】
はゲームの間に生成された別個のトウィーク・エンコード(tweak encodings)の数である。
【１０９８】
【数４８７】
2016540266.tif 000491
【１０９９】
は、
【１１００】
【数４８８】
2016540266.tif 000492
【１１０１】
である場合のみに限ってｉおよびｊが同じクラス内にあるというプロパティによって特徴付けられる等価クラス(equivalence class)である。ｂａｄ１が設定される確率は、高々
【１１０２】
【数４８９】
2016540266.tif 000493
【１１０３】
である。上界は、時点
【１１０４】
【数４９０】
2016540266.tif 000494
【１１０５】
において増加凸関数δＭの値を総和することによって得られ、ここで、
【１１０６】
【数４９１】
2016540266.tif 000495
【１１０７】
である。したがって、Ｎ＝１およびＲ１＝（１，２，．．．，ｑ｝であるときに、限界は最も大きくなる（固定のｑに対して）。しかし、各｜ＲＫ｜＜ｄとなる、Ｃａｐｐｅｄと称されるイベントを仮定する。この場合、
【１１０８】
【数４９２】
2016540266.tif 000496
【１１０９】
Ｃａｐｐｅｄが発生したと想定すると、
【１１１０】
【数４９３】
2016540266.tif 000497
【１１１１】
および、ｋ＝１，２，．．．、Ｎ−１について、
【１１１２】
【数４９４】
2016540266.tif 000498
【１１１３】
であるときに、
【１１１４】
【数４９５】
2016540266.tif 000499
【１１１５】
は最大になる。これから、次の式が得られる。
【１１１６】
【数４９６】
2016540266.tif 000500
【１１１７】
同様に、
【１１１８】
【数４９７】
2016540266.tif 000501
【１１１９】
標準(standard)
【１１２０】
【数４９８】
2016540266.tif 000502
【１１２１】
であるので、誕生日限界（｛０，１｝ｍから均一にサンプリングされたｉ個の独立したランダム変数間における衝突の確率に対する）は、増加凸関数の判断基準を満たす。
[0213]  定理８の証明  Ｂは、ＡについてのＩＮＴ−ＣＴＸＴ実験をシミュレーションし、ＡがＦｏｒｇｅｓを真に設定する場合に１を出力する強調整可能擬似ランダム置換（「ＳＴＰＲＰ」）アドバーサリーであるとする。すると、
【１１２２】
【数４９９】
2016540266.tif 000503
【１１２３】
となり、ここで、Ψ [Π]は、Ψのアルゴリズムにおけるいずれかの場所で、
【１１２４】
【数５００】
2016540266.tif 000504
【１１２５】
および
【１１２６】
【数５０１】
2016540266.tif 000505
【１１２７】
をΠおよびΠ−１でぞれぞれ置き換えることによって得られた方式であり、
【１１２８】
【数５０２】
2016540266.tif 000506
【１１２９】
は、自然な方法で定義される（Ｋではなく、Πのランダム選択に対する確率で）。
[0214]  ゲーム４（図１１）は、
【１１３０】
【数５０３】
2016540266.tif 000507
【１１３１】
に対するＩＮＤ−ＣＴＸＴ実験をシミュレーションする。レイジー・サンプリングによってΠを定義することによって、
【１１３２】
【数５０４】
2016540266.tif 000508
【１１３３】
となる。
【１１３４】
【数５０５】
2016540266.tif 000509
【１１３５】
オラクルに対するコードにおいて、
【１１３６】
【数５０６】
2016540266.tif 000510
【１１３７】
が既に定義されているか否かチェックする必要はない。この可能性は、Ａが
【１１３８】
【数５０７】
2016540266.tif 000511
【１１３９】
への質問を繰り返さず、εΠによって以前に戻された値を
【１１４０】
【数５０８】
2016540266.tif 000512
【１１４１】
に送らないという事実によって除外される（一方、ヘッダは保存される）。
【１１４２】
【数５０９】
2016540266.tif 000513
【１１４３】
へのある質問に対して、Ａがこの質問上で偽造する(forge)確率は、対応してランダムに選択された
【１１４４】
【数５１０】
2016540266.tif 000514
【１１４５】
の値が有効なエンコードである確率に等しい。正しい長さの有効なエンコードは、高々２｜Ｙ｜∈個であり、
【１１４６】
【数５１１】
2016540266.tif 000515
【１１４７】
は、サイズが少なくとも
【１１４８】
【数５１２】
2016540266.tif 000516
【１１４９】
である集合からサンプリングされる。その結果、Ａがこの質問上で偽装する確率は、高々
【１１５０】
【数５１３】
2016540266.tif 000517
【１１５１】
である。結合限界が証明を完成させる。
[0215]  開示した発明の原理を適用することができる多くの可能な実施形態があることに鑑み、例示した実施形態は、単に発明の好ましい例に過ぎず、発明の範囲を限定するように捕らえてはならないことは認められてしかるべきである。むしろ、本発明の範囲は以下の請求項によって定められるものとする。したがって、これらの請求項の範囲および主旨に該当する全てを、本発明者の発明として特許請求する。
【図１】
2016540266.tif 000518
【図２】
2016540266.tif 000519
【図３Ａ】
2016540266.tif 000520
【図３Ｂ】
2016540266.tif 000521
【図３Ｃ】
2016540266.tif 000522
【図４】
2016540266.tif 000523
【図５Ａ】
2016540266.tif 000524
【図５Ｂ】
2016540266.tif 000525
【図５Ｃ】
2016540266.tif 000526
【図６Ａ】
2016540266.tif 000527
【図６Ｂ】
2016540266.tif 000528
【図６Ｃ】
2016540266.tif 000529
【図７】
2016540266.tif 000530
【図８】
2016540266.tif 000531
【図９】
2016540266.tif 000532
【図１０】
2016540266.tif 000533
【図１１】
2016540266.tif 000534
【国際調査報告】
2016540266.tif 000535
2016540266.tif 000536