smoking186 https://blog.hatena.ne.jp/smoking186/ 186 @ hatenablog https://186.hatenablog.com/ crypt 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… 190 <iframe src="https://hatenablog-parts.com/embed?url=https%3A%2F%2F186.hatenablog.com%2Fentry%2F20070608%2F1181312657" title=" メモ: Closure of SZK - 186 @ hatenablog" class="embed-card embed-blogcard" scrolling="no" frameborder="0" style="display: block; width: 100%; height: 190px; max-width: 500px; margin: 10px 0px;"></iframe> Hatena Blog https://hatena.blog 2007-06-08 23:24:17 rich https://186.hatenablog.com/entry/20070608/1181312657 1.0 100%