丸めパス探索における虚パスの排除法

摘要

丸めパス探索は、暗号系の最大差分（線形）特性確率の上界を簡易に評価する手法である。線形部の丸めパスの接続の可否を丸め差分（マスク）の演算規則で判断すると、本来のパスとして、存在しない虚パスを許容し、結果として、得られる差分（線形）確率の上界は、緩いものとなる。ここでは、線形部の伝達行列が与えられたとき、丸め差分（マスク）の演算規則を使わずして、行列の操作により、虚パスを排除したパス導出手法を導く。%Truncate path search is an effective method to evaluate an upper bound of the maximum characteristic probability of the cipher. If connection rule for a truncate path based on truncate difference (mask) addition is simply used, an imaginary path, which cannot be connected as a real one, will be included in the resultant optimum path. The upper bound of the maximum characteristic probability will be a loose one. In this paper, we propose a decision rule for a truncate path with real connectivity by applying elementary operations for the transfer matrix without using truncate difference (mask) addition rule.