Non-overlapping template matching test を用いたテンプレートの同定法の改善案

摘要

Non-overlapping template matching test は、0 と 1 が1/2の確率で独立に出現する数列より、未知のビット数を持つ 0 と 1 からなる特定のパターンが多く含まれているかどうかを検定する方法で、NIST SP-800-22 で提案された方法である。Non-overlapping template matching tes では検定を行うテンプレートをどのように決めるか重要であるが、NIST SP-800-22 では特に述べていない。過去の ISEC において我々はこの点を考慮した Non-overlapping template matching tes の改良型を提案し、さらに多く含まれているパターンの同定方法を提案した。そこで提案した手法は、調べる数列に含まているパターンの個数が多くなるとともに同定できる割合が上昇することが確認できたが、求めるべきパターンの型によっては同定できる割合に差があることをシミュレーション実験で示した。本発表ではこの原因を示すとともに、同定方法の改良案を提案し、シミュレーション実験でその有効性を確認する。