The Optimal Key Estimation of Stream Ciphers and Its Approximation Algorithm Based on a Probabilistic Inference | Toshiyasu Matsushima Laboratory

Title	The Optimal Key Estimation of Stream Ciphers and Its Approximation Algorithm Based on a Probabilistic Inference (in Japanese)
Authors	Yuji Iikubo 、Shunsuke Horii 、Toshiyasu Matsushima
Released Year	2012
Format	International Conference
Category	Information security
Jounal Name	Proceedings of the 2012 International Symposium on Information Theory and its Applications (ISITA2012)
Jounal Page	pp.531-535, Honolulu, USA
Published Year	2012
Published Month	10
Abstract （English）	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.
Note （English）	1
Manuscript
Presentation