Equivalent keys of a nonlinear filter generator using a power residue symbol (Q1995503)

Pseudorandom number generators (PRNGs) play a key role in cryptographic applications. In particular, stream ciphers are symmetric cipher exploiting the same random numbers for encryption and decryption and it may happen that a pair of distinct keys generates the same ciphertext, vulnerability that can be exploited by an attacker to reduce the sampling space concerning seed values. Such a pair of keys are called equivalent keys. In general, PRNGs are evaluated by focusing on several randomness properties such as low correlation with a large period, unpredictability, and uniformity, but these properties do not ensure the non-existence of equivalent keys. In this paper, the authors consider the existence of equivalent keys in a PRNG defined using a residue calculation based on a power residue symbol. There are several traditional approaches to generate random numbers used as stream ciphers, the one the authors focus on is the so-called nonlinear filter generator (NLFG) [\textit{M. Dichtl}, Lect. Notes Comput. Sci. 1267, 103--106 (1997; Zbl 1385.94027)], which is simply defined as a sequence \(S\) generated by applying a nonlinear function \(f\) to a maximum length sequence (\(m\)-sequence) [\textit{S. W. Golomb}, Lect. Notes Comput. Sci. 4086, 1--4 (2006; Zbl 1152.94383)]. In particular, the authors consider an NLFG dealing with a multi-value sequence proposed by \textit{Y. Nogami} et al. [``A multi-value sequence generated by power residue symbol and trace function over odd characteristic field'', IEICE Trans. Fundam. Electron. Commun. Comput. Sci. E99 A(12), 2226--2237 (2016; \url{doi:0.1587/transfun.E99.A.2226})]. NTU sequences employ the nonlinear function \[ f_k(x) =\left\{\begin{array}{ll} 0 & \text{if } x=0\\ \log_{\epsilon_k} \left(\frac{x}{p}\right)_k & \text{otherwise}, \end{array}\right. \] where \(x\in\mathbb{F}_p\), \(k\) is a positive integer dividing \(p-1\), \(\left(\frac{x}{p}\right)_k\) is the power residue symbol and \(\epsilon_k\) is a primitive \(k\)-th root of unity of \(\mathbb{F}_p\). The authors prove that the NTU sequences depend on an additive term \(a\in\mathbb{F}_p\) and they classify these sequences into \((k + 1)\) kinds of classes depending on the choice of this additive term \(a\). Consequently, if the additive term \(a\) is not equal to 0, then there are \(\frac{p-1}{k}\) numbers of equivalent keys for each \(a\), that generate the same class. Otherwise, if \(a = 0\), no pair of equivalent keys exists. In other words, if \(a\ne 0\), then an attacker can reduce the sampling space of the additive term from \(p\) to \(k\) to reproduce the same sequence. Hence, the authors think that in this way an attacker can reproduce a given sequence faster than the brute-force way, and recommend to use the additive term equal to 0. For the entire collection see [Zbl 1454.68007].