Existence of Equivalent Keys in a Random Number Generator with Field Trace and a Dynamic Mapping

Cryptographic applications are essential primitives in our lives, and random numbers have played an inseparable role in many fields. Designing cryptographic applications is difficult because of the need to have appropriate randomness for security. An M-sequence is a representative pseudo-random number generator that is linearly generable and has some ideal properties as a random number sequence. However, it is not suitable for cryptographic applications due to the ease of prediction. To address this drawback, various methods have been developed, and non-linear filter generators (NLFGs) are one of the efficient solutions. In this paper, the authors focus on an NLFG and find that it has a kind of vulnerability called equivalent keys in stream cipher. Thus, we theoretically prove the conditions of keys that induce the same sequences.