演習問題

1. ある効率的な確定的アルゴリズムAがあって、ある多項式p(n)について、
  • Pr[ r ← {0,1}n : A(r) = 1] ≧ 1/p(n)
をみたすとする。このとき、
  • 1n と p(n) を入力として、
  • (nについて)ネグリジブルな確率の例外を除き、A(r) = 1 となる r (∈{0,1}n) を出力する、
効率的なアルゴリズムKを構成せよ。


2. f(x) を一方向関数とするとき、g(x,r) = (f(x), r)も一方向関数となることを示せ。


3. 構成(CCAinRO) において、暗号文c を
  • c = (fi(r), G(r)+m, H(r,m))
の代わりに、
  • c = (fi(r), G(r)+m, H(r))
とした公開鍵暗号の安全性を検討せよ。


4. 構成(CCAinRO) において、暗号文c を
  • c = (fi(r), G(r)+m, H(r,m))
の代わりに、
  • c = (fi(r), G(r)+m, H(m))
とした公開鍵暗号の安全性を検討せよ。


5. 構成(GQプロトコル) を、
以下のように2ラウンドに変更した認証プロトコルGQもどきの安全性を検討せよ。

GQもどき (K, P, V):
  • 鍵生成 K、証明者Pの入力 sk = (N, e, x)、検証者Vの入力 pk = (N, e, X)はGQプロトコルと同じ。
  • [プロトコル]  ※ コミットメント (), チャレンジ (c), レスポンス (Y,z).
    • V → P : c ← {0,1}l, cを送る。  
    • P → V : y ← ZN*, Y = ye mod N, z = y xc mod N, (Y,z)を送る。
  • [検証者Vの出力] ze? YXc (mod N).


6. 定理(FS変換2) を証明せよ。


7. GQプロトコルやシュノアプロトコルが(妥当な仮定のもとで)Σプロトコルであることを示せ。


8. SK安全性をもつ鍵共有プロトコルの、既知鍵攻撃・未知鍵共有攻撃・鍵危殆化によるなりすまし
に対する安全性について考察せよ。


9. プロトコル2DHは、UMモデルではSK安全でないことを示せ。


10. Blumコミットメントは、マリアブルであることを示せ。


11. お気に入りの(広い意味での)暗号スキーム/プロトコルを一つ選択し、その構成と安全性についてまとめよ。


12. 自身の研究テーマまたは職務内容と暗号理論/技術の関わりについて述べよ。






















最終更新:2010年01月14日 16:18