■
符号
Singleton限界とRS, RM, Hadamardを話した. 今度BCH符号. 未だにデコードの話が出てこない.
ROMと証明の話
HさんとNyさんの話を横で聞いていたのでメモ.
署名の安全性を証明するときにROMで以下のセッティングを考える.
- 署名オラクルとランダムオラクル
- 署名オラクルとシミュレートされたランダムオラクル
- 両方ともシミュレート
1はランダムオラクルを選んだ時点でハッシュ値が固定されている. したがって署名の分布と言ってもハッシュの値は確率的ではない. そこで, 2番を間に挟んで, 2と3の間で見る. すると, 2と3の分布の差は議論出来るので, ここを完全/統計的/計算量的に抑えてしまうと.
統計的に距離を抑える方針だと, これが必要. 計算量的に抑える場合は, 直接1と3を比べても良さげ.