セキュリティの基礎
セキュリティの基礎は、暗号学の厳密な数学的基盤を提供します。これには、セキュリティが何を意味するのかの正確な定義、セキュリティが依拠する困難性仮定、およびスキームの安全性を証明する帰着が含まれます。
Definition
セキュリティの基礎は、セキュリティ目標を正確に特定し、暗号学的構成がそれらを達成することを厳密に実証するために使用される、定義的枠組み、計算仮定、および証明技術から構成されます。
Scope
この分野は、暗号学を単なる技術ではなく科学たらしめる理論を扱います。具体的には、形式的なセキュリティ定義と攻撃者モデル、計算困難性仮定、証明可能セキュリティの帰着に基づく方法論、および乱数と擬似乱数の中心的役割です。ここでは、「安全」がどのように定義され、実証されるかについて考察します。これらのアイデアを具体化する具体的なプリミティブやプロトコルは除外され、それらは暗号学に特化した分野で扱われます。
Sub-topics
Core questions
- 暗号スキームが「安全」であるとは、形式的に何を意味するのか？
- 攻撃者の能力と目標は、どのようにして正確なモデルで捉えられるのか？
- セキュリティは、どのような未証明だが妥当な困難性仮定に依拠しているのか？
- スキームを破ることが困難な問題を解決することになるという帰着は、どのように証明されるのか？
- 乱数と擬似乱数は、なぜ暗号学の基礎となるのか？
Key concepts
- セキュリティ定義
- 攻撃者モデル
- セマンティックセキュリティと不可分性
- 計算困難性仮定
- 帰着
- 一方向関数
- 擬似乱数性
- 無視できる確率
- 計算論的セキュリティと情報理論的セキュリティ
Key theories
- セマンティックセキュリティと不可分性
- GoldwasserとMicaliは、暗号化のセキュリティをセマンティックセキュリティとして定義しました。これは、暗号文が平文について計算上役立つ情報を何も漏らさないことを意味し、暗号文の不可分性と等価であることが示され、曖昧な直感を正確で達成可能な目標に置き換えました。
- 帰着による証明可能セキュリティ
- スキームは、それを破る効率的な攻撃者が、仮定された困難な問題を解決するアルゴリズムに変換できることを示す帰着によって安全性が証明されます。したがって、セキュリティは仮定に条件付けられますが、厳密です。
Clinical relevance
基礎的な視点こそが、現代暗号が信頼される理由です。スキームが攻撃に耐えることを期待するのではなく、設計者は、それを破ることが、正確に述べられた攻撃者モデルの下で十分に研究された問題と同じくらい難しいことを証明します。この方法論は、すべての標準化されたプリミティブとプロトコルのセキュリティ主張の根底にあり、規制当局や標準化団体がどのスキームを承認するかを導き、アドホックで未証明の設計が非推奨とされる理由を説明します。
Evidence & guidelines
現在、暗号の標準化においては、証明可能セキュリティ分析が期待されています（AES、SHA-3、およびポスト量子スキームに関するNISTのコンペティションはすべて、セキュリティ証明と帰着を重視しました）。機械検証された証明（EasyCrypt）と標準化されたモデル（ランダムオラクルモデル、標準モデル）は厳密性を提供しますが、理想化された仮定については議論が続いています。ヒューリスティックのみにセキュリティが依拠する構成は推奨されません。
History
暗号学は、GoldwasserとMicaliが確率的暗号化とセマンティックセキュリティを導入した1980年代初頭（1982-1984年）に厳密な科学となりました。これにより、最初の正確な定義と証明が提供されました。YaoとBlum-Micaliは擬似乱数性を形式化し、帰着に基づく方法論は1980年代から1990年代にかけて広まり、Goldreichの「Foundations of Cryptography」で統合されました。この定義の革命は、現代暗号を初期のコード作成と区別するものです。
Key figures
- Shafi Goldwasser
- Silvio Micali
- Oded Goldreich
- Andrew Yao
- Manuel Blum
Related topics
Seminal works
- goldwasser1984
- goldreich2001
- katz2020
Frequently asked questions
- 「証明可能に安全」とは具体的に何を意味するのですか？
- これは、ある攻撃者モデルの下で、スキームを破ることが、解決不可能であると信じられているある問題を解くことと少なくとも同じくらい難しいという数学的証明が存在することを意味します。これは絶対的な保証ではありません。セキュリティは、困難性仮定と、モデルが現実を忠実に反映しているかどうかに条件付けられます。
- なぜ未証明の困難性仮定に依拠する必要があるのですか？
- ほとんどの有用な暗号は、無条件に安全であることを証明できません。そうすることは、P対NP問題のような主要な未解決問題を解決することになるでしょう。代わりに、セキュリティは、数十年にわたる攻撃の失敗によってその困難性が裏付けられている、少数の長年研究されてきた問題（素因数分解、離散対数、格子問題）に帰着されます。