メモ: Closure of SZK
SZKがORについて閉じているのは A. De Santis, G. Di Crescenzo, G. Perisiano, M. Yung "On Monotone Formula Closure of SZK" (FOCS 1994) で示されていると思っていた. 読み直したら, RSRがある問題のSZKだけだった. 騙された.
RSRがある問題のSZKだと検証者は1ビットのチャレンジを送るだけ (写像を送らせるか写像後の証拠を送らせるに対応している.) なので, チャレンジをxor取れば出来る.
元がSZKPOKだったらOR取ってもSZKPOKになるな. 証明者を巻き戻してチャレンジが0の場合と1の場合の両方を試す. すると証明者の内部のチャレンジのどちらかは0と1の両方取れるのでレスポンスの差分を取って知識が引き出せる.
一般のSZKって閉じて無いんだっけか? 困ったな.