Cheat-Sensitive Quantum Protocols
ドイツのLuebeck大学から Maciej Liskiewicz 先生をお迎えする機会がありまして，セミナーで最近の研究のお話をして頂きました．内容は cheat sensitivity という安全性概念を考えて，その安全性を満たすような oblivious transfer や bit commitment protocol を構成する，という話題でした．
cheat sensitivity というのは情報の漏れから安全性を定義するのではなく，二者間プロトコルにおいて片方がチートした場合，そのチートの成功確率に応じて高い確率でチート検出ができる，という概念です．古典にはこのような安全性概念はなく，量子特有のものとなります．
oblivious transfer や bit commitment protocol は量子情報を利用しても情報理論的に安全なものは実現できないことがすでに証明されていますが，cheat sensitivity のような安全性概念に緩めるとこれらの不可能性定理には引っ掛からないようです．（ちなみに STOC 2000 の Aharonov, Ta-Shma, Vazirani, Yao の quantum bit escrow も部分的にこの機能を実現している bit commitment と言えるそうです．）この cheat sensitivity は（陽に考え始められてから）まだ新しい安全性概念であり，まだまだ未解決問題も多いそうで（ coin flipping などの実現はできてない），今後の発展がとても面白そうです．
なお，論文はプレプリントサーバから手に入ります．
- Andreas Jakoby, Maciej Liskiewicz, Aleksander Madry
