演習問題
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)も一方向関数となることを示せ。
- c = (fi(r), G(r)+m, H(r,m))
の代わりに、
- c = (fi(r), G(r)+m, H(r))
とした公開鍵暗号の安全性を検討せよ。
- 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).
11. お気に入りの(広い意味での)暗号スキーム/プロトコルを一つ選択し、その構成と安全性についてまとめよ。
12. 自身の研究テーマまたは職務内容と暗号理論/技術の関わりについて述べよ。
最終更新:2010年01月14日 16:18