We introduce an efficient interpolation attack which gives the tighter uppe
r bound of the complexity and the number of pairs of plaintexts and ciphert
exts required for the attack. In the previously known interpolation attack
there is a problem in that the required complexity for the attack can be ov
erestimated. We solve this problem by first, finding the actual number of c
oefficients in the polynomial used in the attack by using a computer algebr
a system, and second! by finding the polynomial with fewer coefficients by
choosing the plaintexts. We apply this interpolation attack to the block ci
pher SNAKE and succeeded in attacking many ciphers in the SNAKE family. Whe
n we evaluate the resistance of a block cipher to interpolation attack, it
is necessary to apply the interpolation attack described in this paper.