TY - GEN

T1 - The optimal key estimation of stream ciphers and its approximation algorithm based on a probabilistic inference

AU - Iikubo, Yuji

AU - Horii, Shunsuke

AU - Matsushima, Toshiyasu

PY - 2012/12/1

Y1 - 2012/12/1

N2 - A stream cipher is an important class of encryption algorithms. Its safety depends on the structure of the pseudorandom number generator used. There are various types of pseudo-random number generators in existence, and attack algorithms used on them have been studied individually. In this paper, we express the problem of attacks on a general stream cipher as a probabilistic inference problem, and formulate the optimal key estimation. We also propose a unified framework of attack algorithms that can be applied to a wide variety of stream ciphers. The optimal key estimation, however, has computational complexity. To reduce the complexity, an approximation algorithm based on a probabilistic inference is proposed. We also describe some attack algorithms used on practical pseudorandom number generators. Finally, the proposed algorithm is evaluated by through a computer simulation.

AB - A stream cipher is an important class of encryption algorithms. Its safety depends on the structure of the pseudorandom number generator used. There are various types of pseudo-random number generators in existence, and attack algorithms used on them have been studied individually. In this paper, we express the problem of attacks on a general stream cipher as a probabilistic inference problem, and formulate the optimal key estimation. We also propose a unified framework of attack algorithms that can be applied to a wide variety of stream ciphers. The optimal key estimation, however, has computational complexity. To reduce the complexity, an approximation algorithm based on a probabilistic inference is proposed. We also describe some attack algorithms used on practical pseudorandom number generators. Finally, the proposed algorithm is evaluated by through a computer simulation.

UR - http://www.scopus.com/inward/record.url?scp=84873548587&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84873548587&partnerID=8YFLogxK

M3 - Conference contribution

AN - SCOPUS:84873548587

SN - 9784885522673

T3 - 2012 International Symposium on Information Theory and Its Applications, ISITA 2012

SP - 531

EP - 535

BT - 2012 International Symposium on Information Theory and Its Applications, ISITA 2012

T2 - 2012 International Symposium on Information Theory and Its Applications, ISITA 2012

Y2 - 28 October 2012 through 31 October 2012

ER -