cocolog:86516495

日本応用数理学会 監修『数理的技法による情報セキュリティ』を読んだ。最初のほうは、技法に興味を持って読めたが、途中からはザッと目を通すだけになった。 (JRF 2848)

JRF 2016年12月17日 (土) Tweet

『数理的技法による情報セキュリティ』(萩谷 昌己 and 塚田 恭章 編, 日本応用数理学会 監修, 共立出版, 2010年)
https://www.amazon.co.jp/dp/4320019504
https://7net.omni7.jp/detail/1102953609

JRF2016/12/176225

……。

keyword: α同値

「第2章 spi計算による暗号プロトコルの記号的検証」について。

私はラムダ計算のα同値に着目していて、それをオブジェクト指向に活かせないかとかなんとかやっていた。今回、π計算の解説を見て、π計算を知っていたはずなのに、そこに現れるα同値的技法の使い方に驚いた。それは変数束縛を秘密鍵を表すように使うものだった。(たぶん、ずっと昔にも気付いていたからπ計算に注目して、それを忘れていたのだと思う。)

JRF2016/12/172106

p.25 のプロセスの計算で、秘密鍵 K_{AB} が、最初はローカルに定義されていたのが、α同値性を守りながら、全プロセスに K_{AB} の束縛を広げたあと、前はその束縛に入ってなかったプロセスに変数名 K_{AB} を送り使っていた。…束縛を広げ、名前を使えるようにするのがおもしろい。

これを他のことに活かせるかはわからないが…。(もうそういうアイデアは私には出せない気がするが…。)

JRF2016/12/179592

……。

「第3章 ゲーム列による安全性証明の基礎」について。

3.3.5節の安全性証明(p.48-52)がまず納得できない。

Step 5 において、m^* が x^* の typo であろうことはまぁいいとして…。

JRF2016/12/170787

Step 5 において、x^* に対して y を返していたからといって、攻撃者 F は y 以前のパラメータ等も用いて (x^*, σ^*) を出力するはずだから、y がそのまま σ^* に反映しているとは限らない。OH(x^*) が y と同じ(ようなもの)とできる 3.6.6 節とは違う。OH(x^*) = y もまた判定しないとダメだろうと考えた。

JRF2016/12/170245

また、i^* 番目の x が偶然 x^* となる場合があるは、OH(x^*) を攻撃者 F が事前に要求する場合に限定される。そのような仮定は記されてなかったと思う。これも、検証オラクルのときに OH を必ず呼ぶ 3.6.6 節と違うところ。

JRF2016/12/170795

攻撃者 F の OH の要求にシミュレートされた解答を与えることで、答えが「本物でない」ために F の正答率が下がることがありうる。逆に、f(pk, z) という計算が偏りを生んでそこが F の学習をすすませ正答率を上げることにつながるかもしれない。仮に正答率が ε から ε_2 に下がったとすると、Pr[~Abort3 | ~Abort2] >= ε_2 までしか言えず、ε は ε > ε' >= 1/(q...)・ε_2 となり得、偽造成功率は無視しえなくなることもあるのではないか？

JRF2016/12/171674

もしかすると、「OH がランダムオラクルである」という前提によって、正答率が上がる(下がる)ことはないとできるのかもしれないが…。

JRF2016/12/179335

3.3.6 のゲーム列による検証(p.52-62)も完全に納得はできなかった。

Game 7 までのところで、何というか「観測選択効果」みたいなものはないのか…と思った。

まず abort が定義されていない。それが試行の数を減らすものなら分布の形を変えるからそういうものではなかろう。abort したらすべて Lose にするということなのだと思う。それはいいとして…。

JRF2016/12/172503

観測選択…かどうかはわからないが、m が失敗することで偶然学習が起こり、問われる m に偏りが出るということはないのか…。そもそも攻撃者が問う m に偏りがある…例えば攻撃しやすい m のみ攻撃しているといった場合、分布は変わることはないのか…と思う。その効果がここで Pr[S_7] を変えるかどうかはわからないが…。

Game 6 までは、攻撃者は OS(m^*) を(先に)必ず学習できていた。その学習が失敗することが出てくることで、のちの反応が変わる…分布が変わるということはないのだろうか？

JRF2016/12/173265

Game 7 から Game 8 への変換で、攻撃者は直接識別できないかもしれないが、変換によって正答率が下がるなら間接的・確率的に識別できるのではないだろうか？

…とは言え、こんな入門的なところの論理を間違っているとは思えず、私の間違い・考え違いなんだとは思う…。

JRF2016/12/175060

……。


第4章は、確率 Hoare 論理は、やりたいことはわかったが、具体例がよくわからなかった。確率プロセス計算は、「シンタックスシュガー」がいまいちよくわからず、系への確率の導入もよくわからなかった。

第5章以降は、そもそも、この本だけではダメで他の論文にあたらないとちゃんとわからないような書き振りだった。雰囲気だけつかむという感じ。ザッと目を通しただけ。

JRF2016/12/170583

例外的に、第7章の識別不能性に関する健全性の証明はわかったような気になったが、細かいところ、p.143 の無視できる関数の定義でどうして N_c の c が η^{-c} に使うことができるのかわからないなどがあった。まぁ、「無視できる」「圧倒的」という概念は、他の章でも定義されているからやりたいことはわかったけど。

JRF2016/12/174176

第6章は、ちゃんと読めばわかりそうでもあったが、しっかり読まなかった。

第8章の 8.1.7 節「マッピング補題」のところの多項式以下にして「無視できる」ことを示す論証はかっこよかったが、「わかった」とまでは言えない。

JRF2016/12/173491

……。

今回読んだことを使って、自分でプロトコルについて論証するみたいなことができればすごいんだけど、そんな実力は私にはない。「みんなすごいなぁ」と思うだけだ。この分野を振り返ることは、もう私はないかもな…と思う。

JRF2016/12/172380