%0 Journal Article %T On the computational complexity of finding a minimal basis for the guess and determine attack %J The ISC International Journal of Information Security %I Iranian Society of Cryptology %Z 2008-2045 %A Khazaei, Sh. %A Moazami, F. %D 2017 %\ 07/12/2017 %V 9 %N 2 %P 101-110 %! On the computational complexity of finding a minimal basis for the guess and determine attack %K Guess-and-determine Attack %K Computational Complexity %K NP-complete %K Fixed Parameter Tractable %K Uniquely Restricted Matching %K Alternating Cycle Free Matching %K perfect matching %K Jump Number %K Forcing Number %R 10.22042/isecure.2017.79681.373 %X Guess-and-determine attack is one of the general attacks on stream ciphers. It is a common cryptanalysis tool for evaluating security of stream ciphers. The effectiveness of this attack is based on the number of unknown bits which will be guessed by the attacker to break the cryptosystem. In this work, we present a relation between the minimum numbers of the guessed bits and uniquely restricted matching of a graph. This leads us to see that finding the minimum number of the guessed bits is NP-complete. Although fixed parameter tractability of the problem in term of minimum number of the guessed bits remains an open question, we provide some related results. Moreover, we introduce some closely related graph concepts and problems including alternating cycle free matching, jump number and forcing number of a perfect matching. %U https://www.isecure-journal.com/article_49118_dba8b0a005401e76ae90b0bb72b3c475.pdf