『Foundation of Cryptography』

2020-06-18

• デジタル署名: 自分のみが認証
• メッセージ認証: 2者間で正当性を証明

P, NP, NP-完全 の説明

• ランダムアルゴリズム

  • 効率的な計算の言語クラス: BPP
  • ランダムアルゴリズムを多項式時間でできる
  • 確率的チューリングマシンで実行できる

• Negligible Function

2章

• 一方向関数 の話
  P != NP だけでは現代の暗号理論では十分でない
  NP完全を99%でうまく計算できたら意味ない -> 平均の難しさ

• 強方向性

• 弱方向性

• universal TM : 任意のTMを模倣できるTM

  • Trapdoor 一方向関数
  • PPT: 多項式時間アルゴリズム