Optimal Asymmetric Encryption Padding

Optimal Asymmetric Encryption Padding (略称：OAEP、試訳：「最適非対称暗号化パディング」)は、暗号理論において特殊な確定的暗号系 (落とし戸付部分領域一方向性置換) を安全に利用するための平文パディング手法の一つである。とによって1994年に考案され、後に と RFC 2437において標準化された。この手法を用いた暗号系はランダムオラクルモデルで適応的選択暗号文攻撃の下で (IND-CCA2安全性) を持つ。RSA暗号と組み合わせて使われることが多く、その場合はRSA-OAEPと呼ばれる。
概要.
OAEPのアルゴリズムはFeistel構造の一種であり、非対称暗号化に先立って二つのランダムオラクルを用いて平文を加工する。この結果を何らかの安全な formula_1 と組み合わせれば、選択平文攻撃に対してランダムオラクルモデルで強秘匿性を持つ(IND-CPA)。また、ある種の落とし戸付き置換（例えばRSA）と共に実装された場合は、OAEPは選択暗号文攻撃に対しても安全であることが証明されている。OAEPはを構築するのに使うこともできる。
OAEPは次の二つの性質を満たす:
歴史.
OAEPの初期バージョン(Bellare/Rogaway, 1994)は、ランダムオラクルモデルで任意の落とし戸付き置換と組み合わせると""を持ち、これにより選択暗号文攻撃に対する識別不可能性（IND-CCA1安全性）を持つとされた。また当初は適応的選択暗号文攻撃に対しても識別不可能性（IND-CCA2安全性）を持つと考えられていた。しかし2001年にがIND-CCA2ではないことを示し、改良版としてOAEP+を提案した。同時期にもSAEPおよびSAEP+を提案した。但し、元のOAEPもランダムオラクルモデルで標準的な暗号化指数を用いたRSA置換と組み合わせた場合は、たまたま（主にOAEPではなくRSA関数の代数的な性質により）IND-CCA2になる。すなわち、藤崎、岡本、Pointcheval、Sternの4人は、OAEPは元となる暗号系が部分領域一方向性置換であるならばランダムオラクルモデルでIND-CCA2であること、およびRSA関数に関しては一方向性と部分領域一方向性が（多項式時間帰着の下で）等価であることを示した。結果、RSA-OAEPはランダムオラクルモデルでRSA仮定からIND-CCA2安全性を持つ。
近年では、標準モデル（即ち、ハッシュ関数がランダムオラクルではないモデル）においては、RSA問題の困難性が現在推測されている程度だと仮定した場合、RSA-OAEPのIND-CCA2安全性を証明することは不可能であることが示された。また、OAEPを含むパディング方式全般と理想的な落とし戸付き置換の組み合わせについて、標準モデルでは安全性を証明不可能とする結果が得られている。
OAEPの動作概念図.
図中に現れる記号の意味は次の通り。
平文の符号化手順
元の平文への復元手順
これが安全性を持つ理由は、m を復元するにはまず X 全体と Y 全体を復元しなければならないからである。Y から r を復元するには X が必要であり、X から m を復元するには r が必要である。暗号学的ハッシュ値が1ビットでも変わると結果は全く変わってしまうので、X 全体と Y 全体が両方とも完全に復元されなければならない。