暗号理論
暗号学的ハッシュ関数は、可変長入力、固定長出力の関数で、入力から出力を求めることは容易であるが、出力から入力(あるいは出力が同じになる入力の一つ)を求めること、出力が同一になるような2個の入力を求めることが計算量的に困難である等の性質を満たすハッシュ関数である。
ほとんどのハッシュ関数は、可変長の入力メッセージ m をブロック単位に分割(最初のブロックをm_1、最後のブロックをm_nとする。m_0は所定の初期値)し、圧縮関数 H を h_i = H(h_{i-1}, m_i) のように繰り返し使って、出力 h_n を求める構成になっている。代表的にはMerkle-Damgård constructionがある。SHA-3はそれとは異なり、出力よりも大きい内部状態を持ち、出力の時点で大きな内部状態を圧縮するスポンジ構造をしている。
(「暗号の連鎖(chain)の強さは、最も弱い環(link)の強さしかない」ということは変わっていない。)
コンピュータセキュリティやネットワークセキュリティ、より総合的には情報セキュリティと暗号や暗号理論とは密接な関わりがある。例えば、(論理的な)アクセス制御は、「ユーザが誰であるか」という認証(authentication)に従ってOSの機能などによって制御される。しかし、認証自体には、例えばユーザ本人だけが知り得る秘密情報(パスワードなど)を使うといった暗号的な手法が必要であるし、無線や公衆網を通してコンピュータを利用する場合には、そのパスワードを直接やりとりしてしまうようなことは避けなければならない。そういったプロトコルの設計には、暗号理論に従った裏付けが必要である。
暗号学には総合の学であるという面がある。暗号理論にもそれは言えて、情報理論や符号理論、計算複雑性理論といった理論計算機科学などと、合同算術、数論、代数幾何、離散数学といった数学などが広く関係する。
一般に、安全性の目標と攻撃条件をモデル化することで暗号を攻撃する問題を定義し、それが誰もが難しいと想定している問題(安全性の根拠となる問題)と等価であることを示すことで、安全性の評価とする。その際、攻撃条件だけではなく攻撃アルゴリズムも限定して「その範囲」で安全である(目標が達成されている)ということもある。証明の際にさらに仮定やモデルを導入することもある(問題が等価であることの定義など)。また、現代暗号では、計算量的安全性(解読に要する計算量が膨大であること、例:指数時間要する)があることを安全性の前提としているものが多い。このことは計算機の進歩や時間の経過により安全性が低下していくことを意味する。
安全性の表現の例:「○○○暗号は、ROM仮定の下、DLPが困難であれば、IND-CCA2 の安全性証明がある(計算量的安全性)」
暗号の安全性では、上記のような安全性に影響する事項を見出して、より厳密な定義を構築していくことと、その定義を満たす暗号の性質が研究されている。
その他、実際の暗号の安全性は、暗号方式の理論的安全性よりも、実装上、運用上の問題の有無によってより大きく影響を受けることがある。安全とされる暗号方式や暗号製品を採用するだけではなく、平文の管理(例えば個人情報の扱い)や鍵の管理などにも注意が必要である。
根拠となる問題 / それに関する仮定 素因数分解問題 (IFP) RSA問題 / RSA仮定 en:RSA problem flexible RSA問題 / 強RSA仮定 en:strong RSA assumption 離散対数問題 (DLP) DH問題 / Diffie-Hellman仮定 DDH問題 / Decision-Diffie-Hellman仮定 en:decisional Diffie-Hellman assumption ナップサック問題 en:knapsack problem 部分和問題 en:subset sum problem ラティス問題 SVP / CVP 巡回セールスマン問題 en:traveling salesman problem
証明に関する手法 / 仮定 / モデル 確率的証明 probabilistically cheacable proofs ランダムオラクルモデル (ROM) / ランダムオラクル仮定 シミュレーション手法 ハイブリッドアーギュメント 形式的手法 formal method 帰着の効率 識別不能 negligible(無視できる) / overwhelming(圧倒的)
電子署名を実現する一番有力な方法がディジタル署名である。一般的に言って原理上、公開鍵暗号の発見によりディジタル署名が可能になった。
通常の署名 添付型署名 (素因数分解問題) RSA署名 / RSA-PSS (en:RSA-PSS) / ACE Sign ESIGN (離散対数問題) ElGamal署名 / Schnorr署名 / DSA (行列分解問題) FLASH / SFLASH (格子問題) NSS / NTRU-SIGN (楕円離散対数問題) / ECDSA メッセージリカバリ署名 RSA-PSS-R
特殊機能な署名 ブラインド署名 (blind signature) 否認不可署名 (undeniable signature) フェイルストップ署名 (fail-stop signature) 多重署名 リング署名 グループ署名 代理署名 検証者指定可能署名 designated verifier signature オブリビアス署名