--- title: "Nostalgia Cipher: Can Filtered LFSRs Be Secure Again? An Application to Hybrid Homomorphic Encryption with Sub-50 ms Latency" authors: "Nabil Chacal, Antonio Guimarães, Ange Martinelli, Pierrick Méaux, Romain Poussier" venue: "IACR Transactions on Symmetric Cryptology, 2025(4), 1–30" source: "IACR ePrint 2025/2140 (author copy)" source_version: 2025-11-23 canonical: https://antonioguimaraes.org/publications/nostalgia-cipher/ pdf: https://eprint.iacr.org/2025/2140.pdf generator: scripts/fulltext.py (pdftotext) --- # Nostalgia Cipher: Can Filtered LFSRs Be Secure Again? An Application to Hybrid Homomorphic Encryption with Sub-50 ms Latency *Nabil Chacal, Antonio Guimarães, Ange Martinelli, Pierrick Méaux, Romain Poussier*. IACR Transactions on Symmetric Cryptology, 2025(4), 1–30. > Automatic plain-text transcript of the author version, provided for search and AI assistants. Formulas, tables, figures and footnotes are not reproduced faithfully. Read and cite the paper: https://eprint.iacr.org/2025/2140.pdf Nostalgia Cipher: Can Filtered LFSRs Be Secure Again? An Application to Hybrid Homomorphic Encryption with Sub-50 ms Latency Nabil Chacal 1,2,4 , Antonio Guimarães 3 , Ange Martinelli 4 , Pierrick Méaux 2 , and Romain Poussier 4 Université de Versailles UVSQ, Versailles, France, University of luxembourg, Esch-sur-Alzette, Luxembourg, IMDEA Software Institute, Madrid, Spain, Agence nationale de la sécurité des systèmes d’information, Paris, France Abstract. Linear Feedback Shift Registers (LFSRs) combined with non linear filtering functions have long been a fundamental design for stream ciphers, offering a well-understood structure that remains easy to analyze. However, the introduction of algebraic attacks in 2003 shifted the focus toward more complex designs, as filtered LFSRs required larger registers to maintain security. While this was seen as a drawback at the time, it is no longer a limiting factor, and emerging cryptographic applications benefit from specialized designs—challenges that filtered LFSRs can effectively address. In this work, we propose a new filtered LFSR design, called Nostalgia, tailored for Hybrid Homomorphic Encryption (HHE). We use a weightwise quadratic function as filtering function, leveraging its efficiency in the HHE setting while ensuring security against classical attacks. We also discuss the parameter selection of our design and demonstrate its efficiency in this setting by providing a proof-of-concept implementation. In terms of latency, our HHE solution outperforms current state-of-the-art for TFHE-based HHE (Baudrin et al., Crypto 2025) by a factor of 6.1 times. By revisiting filtered LFSRs in light of modern security requirements, we aim to renew interest in their potential applications and stimulate further cryptanalysis efforts. Keywords: LFSR, Stream Cipher, Weightwise quadratic functions, Hybrid Homomorphic Encryption. Introduction Filtered LFSRs: a simple yet abandoned stream cipher paradigm Filtered linear feedback shift registers are among the simplest stream cipher designs, relying on the well-understood structure of Linear Feedback Shift Registers (LFSRs) combined with a nonlinear filtering function. Their appeal lies in the deterministic nature of LFSRs, which generate sequences based on recurrence relations over finite fields. These sequences have been extensively studied in sequence theory, particularly in terms of periodicity, linear complexity, and correlation properties (e.g. , [Gol82]). Maximum-length LFSR sequences (m-sequences) exhibit long periods and uniform statistical distributions, making them fundamental in cryptography and other fields. Additionally, LFSRs are well known for their implementation efficiency, as they require only simple shift operations and XORs, making them highly suited for hardware and lightweight cryptographic applications. By applying a nonlinear filtering function to the LFSR output, filtered LFSRs introduce additional complexity while preserving the efficiency and predictability of the underlying sequence [Sie84]. This simplicity, along with their well-developed theoretical foundation, makes filtered LFSRs a natural subject for security investigations. However, despite their apparent robustness, filtered LFSRs have largely been abandoned due to the devastating impact of algebraic attacks. While early attacks, such as correlation attacks [Sie85], demonstrated statistical weaknesses in certain designs, it was the advent of algebraic attacks [CM03] and fast algebraic attacks [Cou03] that ultimately led to the paradigm shift away from filtered LFSRs. These attacks exploit the algebraic structure of the filtering function, constructing an overdefined system of equations that can be efficiently solved, leading to the recovery of the internal LFSR state. Critically, security is not determined solely by the nonlinearity or degree of the filtering function but also by its deeper algebraic properties, such as algebraic immunity and the complexity of expressing its output in terms of low-degree equations. As a result, the cryptographic community moved toward more complex stream cipher designs, such as those incorporating nonlinear feedback shift registers (NFSRs) (e.g. Trivium [CP08]) or irregular clocking mechanisms. However, these designs introduce components whose security justification is often more difficult to formalize, making it less clear whether they truly prevent known attacks or simply increase the complexity of analysis without offering provable resistance. In contrast, filtered LFSRs are based on a well-studied theory, where every component’s impact on security can be analyzed in a structured way. Despite the success of algebraic attacks against traditional filtered LFSRs, no fundamental result rules out the possibility of making them secure—provided that they are properly dimensioned to resist these attacks. By moving away from historically small register sizes and reconsidering filtering functions with improved algebraic properties, filtered LFSRs could once again be viable. This work revisits filtered LFSRs in light of modern applications, introducing a new instance designed to resist known attacks and explore its potential for recently developed cryptographic primitives. Why revisit filtered LFSRs now? Filtered LFSRs with significantly larger sizes than those considered in the 2000s are now worth revisiting because these sizes no longer present an efficiency bottleneck. Moreover, in several modern cryptographic contexts, the state size and number of variables have a minimal impact on performance. Since the introduction of LowMC [ARS + 15] in 2015, many advanced cryptographic primitives have benefited from symmetric schemes specifically designed for their intended applications, rather than relying on standardized block or stream ciphers. New symmetric encryption schemes have been developed for various domains, including multiparty computation [ARS + 15,AGR + 16,AGP + 19,GLR + 20,GØSW23,DKR + 22,KHS + 23,APRR24], Fully Homomorphic Encryption (FHE) [ARS + 15,CCF + 16,MJSC16,DEG + 18,MCJS19,CHK + 21,HKL + 22] [AMT22,CHMS22,DGH + 23,HMS23,CCH + 24], and zero-knowledge proofs [GKR + 21,GHR + 23,BBC + 23]. Additionally, some symmetric primitives have been designed to facilitate masking and enhance resistance against side-channel attacks [MMMS23,GMM + 24]. The recent rise of arithmeticoriented ciphers and specialized symmetric primitives in general suggests that it may be worthwhile to revisit older designs—such as filtered LFSRs—that were abandoned for reasons that may no longer be relevant. One particularly relevant use case is Hybrid Homomorphic Encryption [NLV11] (HHE), which combines an FHE scheme with a symmetric encryption scheme to significantly reduce both computation and communication costs on the client side in FHE-based protocols. In this context, some of the most efficient results have been achieved using stream ciphers inspired by the filtered LFSR paradigm. For example, FiLIP [MCJS19] achieves homomorphic evaluation with a latency below 3 ms per bit [CDPP22,MPP24], while Margrethe [HMS23] attains a throughput exceeding 1200 bits/s [AGHM25]. These results suggest that, with current techniques for homomorphic evaluation, the simplicity of filtered LFSRs could serve as a strong foundation for designing even more efficient HHE protocols. Toward a secure filtered LFSR: contributions and roadmap In this article, we propose to revisit filtered LFSRs as a viable basis for secure stream ciphers. We consider significantly larger parameter choices than those explored in previous decades, arguing that state-of-the-art attacks do not fundamentally rule out the possibility of achieving security with this primitive. By doing so, we aim to rekindle cryptanalysis efforts, inspire new designs, and encourage further study of this elegant and well-understood theoretical foundation. To achieve this, we first review the state of the art in attacks against filtered LFSRs, leading us to explore the impact of increasing both the LFSR length and the number of variables in the filtering function. As a filtering function, we employ a function from a recent generalization of the Hamming weight bit function [Car22,MO24,CS24,MST24], chosen from a class of functions that are both efficiently computable and possess desirable cryptographic properties. We also estimate its relevant cryptographic parameters. In Section 3, we introduce the Nostalgia instance and discuss its implementation. The main parameters of Nostalgia are set to N = 1024 for the LFSR state and n = 128 for the filtering function. The filtering function itself is a weightwise quadratic function, meaning that for each Hamming weight w of the input, it applies a quadratic function indexed by w. Our design choices prioritize simplicity and compatibility with HHE. The rationale behind these choices is developed in Section 4, where we also analyze the cryptographic properties of the filtering function and the taps’ distribution. A security analysis of Nostalgia is presented in Section 5. We first revisit the main attacks considered in the literature against filtered LFSRs and analyze their complexity to determine the minimal parameter sizes required to withstand them. We show that the chosen parameters of Nostalgia exceed these security thresholds. Additionally, we introduce and examine dedicated attacks that could apply to alternative filtered LFSR designs but do not compromise the security of Nostalgia. In Section 6, we present the evaluation of Nostalgia in the context of hybrid homomorphic encryption. We implement its homomorphic evaluation using the TFHE-scheme [CGGI16] in leveled-mode and compare performance against several state-of-the-art solutions for TFHE- based HHE. Compared with other recent designs in terms of latency, our implementation is 151 times faster than FRAST [CCH + 24] and 6.1 times faster than Transistor [BBB + 25]. Other aspects, such as throughput-optimized version, multi-threaded implementation, and key compression, are left as future work. Our implementation is available at https:// github.com/antoniocgj/Nostalgia-cipher. Preliminaries P For readability, L we use the notation + instead of ⊕ to denote the addition in F 2 , and instead of . In addition to classic notations, we denote by [n, m] the subset of all integers between n and m: {n, n+1, . . . , m}. For a vector a ∈ F n 2 we use w H (a) to denote its Hamming weight w H (a) = |{i ∈ [1, n] | a i = 1}|. For two vectors a and b in F n 2 we denote by d H (a, b) the Hamming distance between a and b, that is, d H (a, b) = w H (a + b). For two functions f and g we denote by d H (f, g) the Hamming distance between their value vectors. Boolean functions and cryptographic criteria We give some preliminaries on Boolean functions and their cryptographic criteria, for a deeper introduction on these notions we refer to the book of Carlet [Car21]. Definitions and criteria Definition 1 (Boolean Function). A Boolean function f in n variables is a function from F n 2 to F 2 . The set of all Boolean functions in n variables is denoted by B n . Definition 2 (Balancedness). A Boolean function f ∈ B n is said to be balanced if |{x ∈ F n 2 | f (x) = 0}| = |{x ∈ F n 2 | f (x) = 1}| = 2 n−1 . Definition 3 (Nonlinearity). The nonlinearity NL(f ) of a Boolean function f ∈ B n , where n is a positive integer, is the minimum Hamming distance (d H ) between f and all the affine functions in B n : NL(f ) = min g, deg(g)≤1 {d H (f, g)}, where g(x) = a · x + ε, a ∈ F n 2 , ε ∈ F 2 (where · is an inner product in F n 2 , any choice of inner product will give the same value of NL(f )). Definition 4 (Algebraic Normal Form (ANF), degree and monomials). We call Algebraic Normal Form of a Boolean function f its n-variable polynomial representation P Q over F 2 (i.e. belonging to F 2 [x 1 , . . . , x n ]/(x 21 + x 1 , . . . , x 2 n + x n )): f (x 1 , . . . , x n ) = I⊆[1,n] a I i∈I x i where a I ∈ F 2 . The (algebraic) degree of a Q non-zero function f is deg(f ) = max I⊆[1,n] {|I| | a I = 1}. If f = 0, deg(f ) = 0. Each term i∈I x i is called a monomial. Definition 5 (Algebraic Immunity [MPC04]). The algebraic immunity of a Boolean function f ∈ B n , denoted as AI(f ), is defined as: AI(f ) = min g6 =0 {deg(g) | f g = 0 or (f + 1)g = 0}. Weightwise quadratic functions Weightwise quadratic functions are a subfamily of Boolean functions that can be seen as a generalization of symmetric functions. The n-variable Boolean symmetric functions are those that are constant on each slice E k,n = {x ∈ F n 2 | w H (x) = k} for k ∈ [0, n]. This class has been assiduously studied in the context of cryptography, see e.g. [Car04,CV05,BP05,SM07,QFLW09,CL11,Méa19,Méa21,CM21]. A basis of the n-variable Boolean symmetric functions is given by the n + 1 functions called the slices indicators. For k ∈ [0, n] the slice indicator ϕ k,n is such that: ∀x ∈ F n 2 , ϕ k,n (x) = 1 ⇔ w H (x) = k. The generalization from symmetric functions to weightwise quadratic functions comes from considering functions of bounded degree on each slice. It corresponds to the concept of weightwise degree-d function introduced in [GM22] for d = 1 and [MO24] for the general case. Definition 6 (Weightwise degree-d functions P ( [MO24] Definition 12)). Let n ∈ N ∗ . An n-variable Boolean function f , written as f = nk=0 f k ϕ k,n , is called weightwise degree-d if and only if for each k ∈ [0, n] f k coincide with a function of degree at most d over E k,n . The set of weightwise degree-d functions is denoted by WD dn . In this context, symmetric functions are simply weightwise degree-0 functions. The Hidden Weight Bit Function [Bry91] (HWBF) is a famous example of weightwise degree-1 function, whose cryptographic properties are studied in [WCST14]. Recently, various generalization of the HWBF have been studied [Car22], various of them being WeightWise Quadratic (WWQ) [MO24,MST24] or weightwise degree-d with a small d [CS24]. We highlight that a function of weightwise degree d is not necessarily of degree d, in particular for uses in cryptography we focus on weightwise degree-d functions with degree close to n. Filtered linear feedback shift registers A Linear Feedback Shift Register (LFSR) is a finite state machine updated by a linear function of its previous state. Formally, Definition 7. (Linear Feedback Shift Register). An LFSR of length N over F q is a finite state automaton which produces a semi-infinite sequence of elements of F q , s = (s i ) i≥0 satisfying a linear recurrence relation of degree N over F q : N X s t+N = c i s t+N −i . i=1 The N coefficients c 1 , . . . , c N are elements of F q . They are called the feedback coefficients (t) of the LFSR. We use the notation (s i ) 0≤i≤N −1 for (s t+i ) 0≤i≤N −1 . In this article we will only consider binary LFSRs, that is with coefficients over F 2 . (t) (t) ... ... ... (t) (t) s N −1 s N −2 s 0 s 1 ... ... ... c N −1 c N c 2 c 1 (a) Representation of an LFSR of length N z t (key stream) f (t) (t) ... ... ... (t) (t) s N −1 s N −2 s 0 s 1 ... ... ... c N −1 c N c 2 c 1 (b) Filtered LFSR Fig. 1. LFSR designs Definition 8 (Feedback polynomial). An LFSR can be represented by its feedback polynomial defined by: N X P (X) = 1 + c i X i . i=1 Note that the sequence generated by an LFSR is uniquely determined by its feedback polynomial P and its initial state (values of (s 0 , . . . , s N −1 )). A primitive feedback polynomial is sufficient to ensure the LFSR has maximal period. LFSRs alone cannot generate cryptographically strong output sequences, as they lack any nonlinear component. The most straightforward way to use LFSRs in stream ciphers is to combine them with a nonlinear filtering function f . This is typically done by selecting certain positions in the LFSR state, known as taps, and using their values as inputs to the nonlinear function. The output of this function then forms the keystream. Figure 1b provides an overview of a filtered LFSR. The hybrid homomorphic encryption framework The Hybrid Homomorphic Encryption (HHE) protocol has been introduced in [NLV11], we refer to e.g. [NLV11,MJSC16,CCF + 16] for a detailed description. The HHE protocol aims at allowing a low resources user to delegate confidential data and computations on a high resources untrusted (honest but curious) server. To achieve this goal the protocol can be separated in three phases: a pre-processing phase, a computation phase and a recovering phase. Both the pre-processing and recovering phases are done by the user while the heavy computation phase is processed by the server. 1. Pre-processing: The user generates a homomorphic key pair (K pub , K priv ) and a secret key K sym . She encrypts her data d using the symmetric cryptosystem E and key K sym and the key with the homomorphic scheme H under key K pub . She then sends (K pub , E(d), H(K sym )) to the server. 2. Computation: The server homomorphically decrypts E(d) using H(K sym ) resulting in H(d) then homomorphically evaluates the function f on it to obtain H(f (d)) and sends it (or a compressed version) to the user. 3. Recovering: The user decrypts H(f (d)) using K priv and gets f (d). The HHE protocol is as efficient as the homomorphic evaluation of the decryption of the symmetric encryption scheme is simply performed. The Nostalgia instance In this section, we present the chosen parameters to instantiate Nostalgia, along with a short description of its public reference implementation. We chose these parameters to resist existing attacks, which will be detailed further in Section 5. Instance The main parameters of Nostalgia are summarized in Table 1. We set N = 1024 (both as LFSR and key size) and n = 128 to achieve a security level λ of 128 bits (2 128 in time complexity and 2 64 in data), as further detailed in Section 5. Following Definition 6, we use a WWQ function f that is defined by its (quadratic) slice functions f k for k ∈ [1, n]. the filter function is designed to include a large portion of bits x i on each slice, but not all. The rationale behind the choice of function and taps is discussed in Section 4. LFSR and key size N LFSR polynomial + x + x 1+ x + x WWQ function size n filter f: slice functions f k P b n 3 c x k + i=1 x k−i x k+2i−1 Table 1. Main parameters of Nostalgia. We define the taps as the indexes of the bits of the LFSR given as input for the filtering function. The set of taps for the Nostalgia instance is given as the index 0 and then the first n − 1 unique numbers that P are the sum of the first consecutive primes modulo N . That is, taps T = {0} ∪ {x | x = p i mod N } where the p i are all the first prime numbers, and such that |T | = n. The complete list of tap indexes is given in Appendix A.1. The LFSR is initialized directly with the 1024-bit key and the keystream is directly generated without any preprocessing. Unlike standard stream ciphers, where the IV can be varied while the key remains fixed for efficiency, this initialization provides a suitable and efficient approach in the HHE setting. With this design, we consider that up to 2 λ/2 bits of data can be encrypted under the same key. To avoid regenerating a new key for each message, the client transmits to the server the index of the LFSR state at which it stopped. The same key can then be reused until the 2 64 -bit limit is reached. This strategy notably avoids the costly homomorphic encryption of a fresh key on the client side at every restart. Instead, the server can advance the LFSR to the specified state using the homomorphically encrypted key, since this update is publicly derivable. For completeness, alternative designs are discussed in Appendix B. A high-level description of Nostalgia is provided in Algorithm 1. The LFSR state is first initialized with the N -bit key K. To generate each bit of the keystream, the n-bit filter state is extracted from the LFSR using the specified taps (via the function get filter state from taps). Then, the Hamming weight k of the filter state is computed using Hamming weight, and the corresponding slice function f k of the WWQ function f is applied. The output is XORed into the keystream using add to bitstream. Finally, the LFSR state is updated via update lfsr state. Algorithm 1 High-level description of Nostalgia’s encryption Input: key K of N bits, filter size n, taps T , filter f given by its slice functions f k Output: b-bit keystream B B ← {} LF SR ← K . initialize LFSR state with the key for i = 0 to b − 1 do F ILT ER ← get filter state from taps(LF SR, T, n) k ← Hamming weight(F ILT ER) B ← add to bitstream(B, f k (F ILT ER)) LF SR ← update lfsr state(LF SR) end for return B Implementation We provide two C reference implementations of the Nostalgia instance along with the submission. It consists of two folders with a few files each. The first one, nostalgia clean, considers a straightforward 32-bit implementation. The filtering part significantly increases the time execution of this version, as it requires accessing 128 bits of the LFSR state, which is encoded in 32-bit values. The second implementation, nostalgia faster, provides a faster time execution at the cost of more memory. In this case, each bit of the LFSR or the filter is encoded in a whole unsigned char, which speeds up the access to each single bit. Moreover, the LFSR state size is increased up to a user-chosen size ADD BUFF SIZE defined in define.h. This allows to perform almost instant shift operation for the LFSR, as we only need to update the pointer to the initial sequence and add the last element. We then only need to copy the whole state every ADD BUFF SIZE cycles, which is chosen by the user. For all implementations, define.h contains the parameters of Nostalgia and the structure of the filtered LFSR. util.c/h files include utility functions, and nostalgia.c/h files contain the core implementation of the instance. Finally, a usage example is given in main.c. The implementation does not rely on non-standard C libraries and can be simply compiled using gcc. We ran our implementations on an Intel(R) Core(TM) i7-10510U CPU, compiled with -O3 optimization for speed. The first one achieved throughput of 284 KB/sec, while the second one achieved 1.3 MB/sec. Note that these implementations are not fully optimized and are primarily intended as references. Design rationale The main design principles behind Nostalgia are simplicity, targeting a clear understanding of its security, and high compatibility with hybrid homomorphic encryption. The first principle of simplicity is based on the assumption that simpler building blocks can be more thoroughly analyzed both theoretically and across various studies. This approach differs from modern constructions, which frequently incorporate various modifications to address potential attacks observed in other ciphers. Such complexities are introduced under the assumption of ’better safe than sorry,’ yet they may ultimately compromise the security of the resulting cipher. The second principle focuses on identifying a function that combines operations efficient to evaluate with an homomorphic encryption scheme. The goal is to ensure that these operations remain efficient across the varying performance metrics of most fully homomorphic encryption schemes and their evolving designs. Reviving filtered linear feedback shift registers Filtered LFSRs are among the simplest stream cipher designs, combining the well-studied structure of linear feedback shift registers with a nonlinear filtering function. Their simplicity stems from the deterministic nature of LFSRs, which generate sequences based on recurrence relations over finite fields. These sequences, particularly maximum-length LFSRs (m-sequences), are well understood in terms of periodicity, linear complexity, and correlation properties (e.g. [Gol82]). For instance, selecting a primitive polynomial with a degree equal to the LFSR length ensures that the LFSR generates a maximum-length sequence. Applying a nonlinear filtering function to the LFSR output increases complexity while maintaining efficiency. The simplicity and well-developed theoretical foundation of filtered LFSRs provide a strong starting point for investigating the security of such designs. Since the early 2000s, numerous attacks have been demonstrated against ciphers following the filtered LFSR paradigm. The (fast) correlation attack [Sie85] exploits the statistical dependence between the LFSR state and the keystream to recover the internal state when the filtering function lacks sufficient nonlinearity. Further advancements in cryptanalysis introduced algebraic attacks [CM03] and fast algebraic attacks [Cou03], revealing that security does not depend solely on the nonlinearity or degree of the filtering function but also on its broader algebraic properties, such as its algebraic immunity and the complexity of expressing its output as a system of low-degree equations. Beyond these, various time-memory tradeoff attacks have been applied to filtered LFSRs, leveraging precomputed tables to drastically reduce the complexity of recovering the internal state. Additionally, other attacks such as guess-and-determine and divide-and-conquer techniques exploit the relatively small internal states used in these designs, allowing attackers to reconstruct the keystream by progressively revealing bits of the LFSR state. We note that all these attacks remain feasible with relatively low time or data complexity, primarily because the targeted LFSRs and filtering functions are typically of limited size—generally constrained to a few hundred bits for the LFSR and a filtering function acting on only around 20 bits. Due to the strength of these attacks, particularly the fast algebraic ones, filtered LFSRs have largely been abandoned in favor of more complex designs, such as those incorporating nonlinear feedback shift registers (NFSRs) (e.g. Trivium [CP08]) or irregular clocking mechanisms. However, our point here is that no known attack fundamentally rules out the possibility of a secure filtered LFSR, provided that it is appropriately dimensioned. By lifting the constraint of small register sizes, it is possible to design filtered LFSRs that achieve the security levels currently required while offering greater efficiency than more complex stream ciphers for certain applications. The LFSR is entirely defined by its size, which will be discussed in section 5, and its feedback polynomial. The choice of this last one induced the period of the output. The only requirement is to ensure that the polynomial is primitive to have maximal period. Choice of the filtering function For the filtering function, we consider the family of weightwise quadratic functions, first studied in [MO24]. These functions are evaluated by first computing the Hamming weight of the input and then applying a different quadratic function based on this weight. From a homomorphic evaluation perspective, computing the Hamming weight is relatively inexpensive (e.g. [HMR20]), and quadratic functions require only a single level of multiplication. As a result, these functions are well-suited for efficient evaluation across various FHE schemes. From a symmetric security perspective, the idea of applying different low-degree functions based on the Hamming weight has already been explored in the hidden weight bit function [Bry91]. This function exhibits relatively good cryptographic properties, as analyzed in [WCST14], and recent works have proposed various generalizations [Car22,MO24,CS24,MST24]. In particular, generalizations incorporating addressing and quadratic functions, such as those in [MO24,CS24,MST24], achieve improved nonlinearity compared to the HWBF, which is often considered its main vulnerability. For the specific WWQ function used as Nostalgia’s filter, we first present its relevant cryptographic parameters for up to n = 17 variables. Since the computation of algebraic immunity and nonlinearity is inherently exponential in n we then analyze these parameters for larger values of n. In particular, we establish a bound on the nonlinearity and propose a conjecture regarding the algebraic immunity, as exact computation remains impractical for values suitable for a secure streamcipher. Parameters for small values of n The concrete values (determined with Sage) for n up to 17 are presented in Table 2. These results show that the function exhibits high nonlinearity, a quasi-optimal degree (the optimal being n − 1 for a balanced function, which f attains except when n = 8, where its degree is n − 2), and quasi-optimal algebraic immunity, as it reaches or closely approaches the ceiling of n/2. We add an example of the algebraic normal form of f for n = 6 in Appendix A.2. We highlight that f takes the same value as a different quadratic function on each slice, and is not a quadratic function over F n 2 . n NL deg AI Table 2. Nonlinearity, degree and algebraic immunity of f for different n values. Balancedness Regarding the balancedness of f we can use directly the following result from [MO24]: Property 1 ([MO24], Proposition 4). Let n ∈ N ∗ , let P i for i ∈ [0, 1] be n + 1 permutations from the permutation group S n , the function g ∈ B n is balanced if and only if the weightwise degree-d function h defined by h i = g(P i (x)) is balanced. P b n 3 c x P (2i) x P (2i+1) for a permutation On each slice the function f takes the value of x P (1) + i=1 P ∈ S n . Since this function is a direct sum of monomials containing a linear part it is balanced (e.g. [CM21]), and using Property 1, f is balanced. Nonlinearity For larger values of n, we can establish a lower bound on the nonlinearity of f using a result from [MST24]. Specifically, we first recall their theorem (Theorem 1), which bounds the absolute value of the Walsh transform for any function constructed using quadratic terms in a direct sum over each slice. Then, using the relationship between the Walsh transform and nonlinearity, we derive a lower bound on the nonlinearity of f . Since nonlinearity values can be difficult to interpret directly, we express it in terms of the parameter r, defined by the relation NL(f ) = 2 n−1 − 2 r . The parameter r is a real number belonging to the range [n/2 − 1, n − 1], where n/2 − 1 corresponds to the best possible value (achieved by a bent function, impossible here since the function is balanced), while n − 1 represents the worst case (corresponding to an affine function). Theorem 1 (Adapted from [MST24] Theorem 3 ). Let n > 0 be an even integer, let t ∈ [0, n/2] and let f be a weightwise quadratic function with t quadratic terms in direct sum on each slice. We define λ = t/n, as well as:  √ λ λ 2 −4λ+2 )  λ+1 + 1 log ( −λ 2 +2λ+λ if λ > 16 , √ 2λ−1 ( 1−λ+ λ −4λ+2 ) µ = µ(λ) =  1 − λ if λ ≤ 6 1 . Then, for all a ∈ F n 2 , the following holds: |W f (a)| ≤ 1 + n · 2 µn , where W f (a) denotes the value of the Walsh transform of f in a. It allows to derive the following proposition for the chosen filtering function: Proposition 1. Let f be the weightwise quadratic function as defined in Section 3, its nonlinearity follows the following bound: 1 + n · 2 0.537n 1 + n · 2 0.537n n−1 NL(f ) ≥ 2 − , or equivalently r ≤ log 2 , and in particular for n = 128: r ≤ 74.753, where r = log 2 (2 n−1 − NL(f )). Proof. Since f is a weightwise quadratic function with bn/3c quadratic terms in direct sum on each slice we can apply Theorem 1. Taking λ = 42/128 we obtain µ(λ) ≈ 0.537. Using the relation between nonlinearity and Walsh transform: max |W a (f )|, 2 a∈F n 2 max a∈F n 2 |W a (f )| 1 + n · 2 0.537n n−1 r = log 2 (2 − NL(f )) = log 2 ≤ log 2 . Replacing µ by 0.537 and n by 128 gives the particular result. NL(f ) = 2 n−1 − From Proposition 1, we obtain the bound r ≤ 0.537 · n + log 2 (n/2), which represents a strong asymptotic value for a family of functions that are computationally efficient. In Section 5, we will see how this bound helps determine the appropriate choice of n to achieve the desired security level. Algebraic immunity Concerning algebraic immunity, asymptotic values are known only for a few specific constructions, and determining it for arbitrary functions remains a difficult problem. Since WWQ functions generalize HWBFs, we expect their algebraic immunity to follow a comparable or even stronger trend. The algebraic immunity of HWBFs was initially stated as at least bn/3c + 1 (Theorem 4 [WCST14]), but this result was later disproved in [Méa25], which also provided new upper bounds for weightwise degree-d functions. In particular, √ Section 4.5 of [Méa25] establishes that the AI of our filter f is bounded above by √ 2n(1 + 2) − 1). For n = 128, applying Theorem 1 of [Méa25] yields the tighter bound AI ≤ 31 5 . Based on the experimental values obtained for n between 4 and 17, we adopt the following conservative assumption on the algebraic immunity of f : Conjecture 1. Let n ∈ N ∗ and f be the weightwise quadratic function as defined in Section 3, we conjecture the following bound on its algebraic immunity: √ AI(f ) ≥ min(bn/3c, 2 · n). √ √ The bound 2n(1 + 2) − 1 can be slightly improved for certain values of n, such as powers of two, which explains the discrepancy. As observed in [Méa25], the new upper bounds do not contradict Conjecture 1. Furthermore, we highlight that the conjecture is both consistent with the experimental values of the AI obtained for n between 4 and 17, reported in Table 2 and the new upper bounds. We summarize in Table 3 the values given by the conjecture, the actual values and the upper bound from Section 4.5 of [Méa25]. n Conjecture 1 (≥) AI measured (=) Bound [Méa25] (≤) ··· Table 3. Algebraic immunity of f , measured, conjectured and bounded. Choice of the taps The choice of taps used as inputs to the filtering function can have a significant impact on the security of the scheme. When taps are chosen at regular intervals within the LFSR state, the resulting outputs depends on subsets of state bits with limited renewal, which weakens the overall resistance of the cipher. To mitigate this issue, we consider tap distributions designed to break such regular patterns. Since the filtering function takes n variables as input and the LFSR consists of N registers, there are Nn possible ways to select them. This number grows rapidly, making it impractical to analyze all possible distributions exhaustively. It is therefore necessary to adopt a selection strategy, for which we take the regularity as an indicator of poor quality. To assess this regularity, we measure the distances between each tap and the others to determine which distances appear most frequently. For a given tap distribution, the script iterates through all possible pairs of taps and computes the absolute difference between their positions. These distances are then used to update a frequency table, where each entry corresponds to the number of occurrences of a particular distance, ultimately producing a histogram of distances. The more frequently a particular distance occurs, the worse it is for the security of the scheme (see the example in Section 5.3). We give hereafter some distributions of the taps. Sums of primes distribution: let (p i ) 0≤i be the increasing sequence of prime numbers, N ∈ N ∗ and n ≤ N , we then define P the sequence of the increasing sums of prime numbers (sp i ) 0≤i by: sp 0 = 0, ∀i ∈ N ∗ , sp i = ik=1 p i . Using that sequence, we choose the positions of the taps (γ i ) 0≤i≤n−1 , by getting the sorted list of the n first distinct values of this sequence sp modulo N . Fig. 2. Occurrences of the distances between taps, for various distributions with N = 1024 and n = 128. Figure 2 illustrates the distribution of distances between two taps for four different tap placement strategies. Figure 2.a shows the worst possible distribution, which is a regular placement. In this case, the most frequent distance, 8 positions, appears up to 128 times. Figure 2.b presents the distribution when taps are placed at the indices corresponding to the first 128 prime numbers. While this distribution is an improvement, it still exhibits a peak with more than 70 occurrences. Additionally, odd distances appear at most once. Figure 2.c provides an example of a random tap placement, serving as a baseline for comparison. Finally, Figure 2.d shows the distribution obtained using the sums of primes method, which achieves the best balance among all tested approaches, minimizing repetition in distances and providing a more uniform spread. We emphasize that the sum of primes strategy is not claimed to be optimal, as no provable criterion for perfect tap selection is available. At best, one can aim to reduce the frequency of undesirable occurrences, as illustrated above. Conversely, the weakness of a given distribution can only be established through cryptanalysis, as in Section 5.3, where we present an attack on a regular tap distribution. Security analysis In this section, we analyze the security of Nostalgia by applying known cryptanalysis. We focus on key recovery attacks in the known-plaintext model, where the adversary has access to the keystream. For a (bit)-security parameter λ, we set a time complexity limit of 2 λ basic operations and a data complexity limit of 2 λ/2 keystream bits. The parameters of Nostalgia are chosen to target λ = 128. In section 5.1 we recall the main attacks known on filtered LFSR and relevant cryptographic parameters for the filtering function. We argue that, differently from the more standards designs of block ciphers, we cannot study the security and its margin of the cipher by increasing or decreasing the number of rounds. The analog in our case consists in studying variations of the design. We analyze dedicated attacks on variants of the scheme and explain how the chosen instance mitigates these attacks. In Section 5.2, we show how a simpler function than f (from the same family) leads to an insecure instance. Then, we provide in Section 5.3 an instance where the choice of taps leads to an attack. Filtered LFSR and secure parameters Based on the book of Carlet [Car21] we survey the different attacks known to apply to filtered LFSR, and then determine the sufficient parameters a function should have to be out of reach for these attacks. Algebraic attacks Algebraic attacks and fast algebraic attacks were introduced on filtered LFSRs by Courtois and Meyer in [CM03] and fast algebraic attacks (respectively by Courtois in [Cou03]), leading to some of the most efficient attacks on these stream ciphers. The main idea behind algebraic attacks, as defined in [CM03], is to construct an overdefined system of equations where the unknowns correspond to the initial state of the LFSR. This system is then solved using Gaussian elimination. The core principle is to find a nonzero function g such that both g and h = gf (where f is the filtering function) have a low algebraic degree, enabling the derivation of multiple equations of small degree d. The resulting degreed algebraic system is then solved—either through linearization, using Gröbner basis methods (e.g. [Fau99,Fau02]), or SAT solvers. Notably, linearization is the only method for which complexity estimates are straightforward. In practice, the degree of g is at least AI(f ), the algebraic immunity of f , and g is chosen as a nonzero annihilator of either f or f + 1 with minimal degree. This allows the adversary to derive a system of equations from the keystream, containing monomials of degree up to AI(f ) in the key bit variables. After linearization, the P AI(f ) N N variables. Consequently, the adversary obtains a system of equations in D AI(f i=0 ) = i ω N time complexity of the algebraic attack is O((D AI(f ) ) ), where ω is the complexity parameter for solving a linear system (2 ≤ ω ≤ 3). Fast algebraic attacks [Cou03,HR04] are variant of standard algebraic attacks. Still relying on the relation gf = h, their objective is to find and use functions g of low algebraic degree e (possibly smaller than AI(f )) and h of low but potentially higher degree d. The attacker then reduces the degree of the resulting equations by performing an offline elimination of monomials of degree greater than e, leveraging the feedback properties of the LFSR. This process requires multiple equations to generate each equation of degree at most e. Following the analysis in [ACG + 06], the time complexity of fast algebraic attacks is given by: O(D d N log 22 (D d N ) + E e N D d N log 2 (D d N ) + (E e N ) ω ), P d N P e N N where D d N = i=0 i , and E e = i=0 i . For simplicity, we use the facts that e = N deg(g) ≥ 1, implying E e ≥ N , and that d = deg(f g) ≥ AI(f ) when 0 < deg(g) < AI(f ), N which ensures D d N ≥ D AI(f ) . This allows us to bound the complexity of both the algebraic attack and the fast algebraic attack in terms of the algebraic immunity. For a security parameter λ, the function f must satisfy the following requirements: N N N ω λ N ω λ N O((D AI(f ) ) ) > 2 and O(D AI(f ) log 2 (D AI(f ) ) + N D AI(f ) log 2 (D AI(f ) ) + N ) > 2 . Figure 3 shows the complexity of the algebraic attack (in blue) and the fast algebraic attack (in orange) on a logarithmic scale. Both complexities depend solely on the algebraic immunity, with N fixed at 1024 and a conservative ω = 2 used in the calculations. Fig. 3. Logarithmic complexities of the algebraic and fast algebraic attacks depending on the algebraic immunity, with N = 1024. Figure 3 shows that for N = 1024, a function with algebraic immunity of at least 16 is sufficiently resistant to (fast) algebraic attacks. From Section 4.2, we know that the 17-variable version of f already has an algebraic immunity of 9. Moreover, assuming Conjecture 1, f has an AI of at least 23. Correlation attacks (Fast) Correlation attacks cover a wide range of different attacks focusing on the correlation between the input (here the output of the LFSR) and the output of the filtering function. It was introduced in [Sie85] for the combiner model and later improved and generalized to any LFSR-based generators [MS88,CS91]. A pseudorandom sequence s generated by the cipher can be viewed as a noisy version of a linear sequence σ, enabling error-correction methods to recover σ. This involves treating s as being transmitted over a noisy channel, where the probability of errors depends on the Hamming distance between the filtering function f and the affine approximation `. By correcting these errors, the attacker can approximate the linear sequence σ, facilitating the recovery of the cipher’s internal state. There are multiple decoding algorithms, as in [Car21] we consider the approach of [MS88,CS91] using parity check polynomials of bounded degree and at most t ≥ 3 coefficients. From [CT00], we obtain the following complexities for this attack on a filtered LFSR: ! 2(t−2) 2t(t−2) t−2 t−1 t−1 N N D , P = , and T = 2 t−1 , D = 2 t−1 2ε (t − 2)! 2ε n−1 ) where D is the amount of data, ε = 2 −NL(f , P is the time complexity of the pre- 2 n computation step and T the time complexity of the online phase of the attack. We analyze the value of nonlinearity sufficient to achieve a time complexity T greater than 2 λ in this context. For simplicity, we use the parameter r, defined as r = log(2 n−1 − NL(f )), which ranges from n/2 − 1 when f is bent to n − 1 when the function is affine. In Figure 4, we represent the minimal complexity obtained for n = 128 and N = 1024, varying r and t ∈ [3, 1024]. For these parameters, an r value relatively close to n − 1 is sufficient from the analysis in [CT00]. For instance, from the figure, r = n − 4 is adequate. Since other decoding techniques are possible, or alternative approaches to solving the Learning Parity with Noise (LPN) problem exist (e.g. [BV16]), we prefer functions with an r value that grows as a fraction of n. In particular, the filtering function considered here, achieving r ≤ 0.537 · n + log 2 (n/2), guarantees a bias of 2 −53 for n = 128. This bias already requires 2 106 keystreams to distinguish the output from a truly random binary string. Other attacks We also considered other attacks on filtered LFSRs, as detailed in [Car21], but they result in higher complexities than the attack described above in this section. Below, we summarize the considered attacks and refer to e.g. [Car21] for full details. The linearization attack always has a higher complexity than the algebraic attack since, for any Boolean function, AI(f ) ≤ deg(f ). The Rønjom-Helleseth attack [RH07], later improved in P ) N e.g. [GRHH11,Røn17], has a complexity of deg(f . Since N is significantly larger than i=1 i 128 for any filtering function with a degree close to n = 128, as considered in this work, the resulting complexity is far greater than 2 128 . Time/memory/data trade-off attacks can also be applied to stream ciphers [BS00]. To prevent these attacks, it is recommended to select an LFSR length N at least twice the security parameter [BS00,HS05]. This requirement is met in the design of Nostalgia, where N = 1024 for a target security level of 128 bits. Recent attacks based on monomial mappings, such as those presented in [CR16], leverage the univariate representation of the LFSR, over F N . However, since the filtering function 2 = F 2 is described in its multivariate representation, we assume that a transformation, such as the discrete Fourier transform, would be required to obtain the polynomial coefficients in univariate. This transformation would necessitate a precomputation step of complexity at least 2 n log 2 (2 n ) = n2 n > 2 128 in our context. This situation differs from previously studied λ y = 128 y = 256 correlation attack complexity 127 126 125 124 123 122 121 120 119 118 117 116 115 114 r Fig. 4. Correlation attack time complexity in function of r for n = 128, N = 1024 filtered LFSRs, where both N and n were significantly smaller for the same security level. Differential attacks are also common against stream ciphers [BD07]. In this context, the principle is to exploit the difference between two keystreams generated using the same key but different IVs. Such attacks do not apply to Nostalgia, as it does not use an IV. Specific weightwise quadratic function weakness The choice of the filtering function within the weightwise quadratic family has a significant impact on the overall security of the cipher. In particular, the number of second-degree terms and their periodicity within the index range can be an asset. To illustrate the importance of selecting a well-designed WWQ function, we present a practical attack against the WWQ function defined by f i (x) = x i + x i+1 x i+2 , where i represents the Hamming weight of the 128-bits input. For clarity, probabilities have been simplified in this exposition. The probability that f i (x) = x i is 3/4, since the product 128 of two bits is zero with probability 3/4 Moreover, the probability of i = 64 is 64 /2 ≈ 0.070 while the probability of i = 63 is approximately 0.069. Let α denote the distance between the 64 th and the 63 rd taps. Suppose we have two inputs of weight 64 and 63, respectively, occurring at iterations t and t + α (with a combined probability of approximately 0.005). Then, f takes the same value on both inputs with probability 9/16, since they correspond to x 64 in the first iteration and x 63 in the second. It follows that the probability of two bits separated by α positions in the output stream being equal is approximately 0.502 > 0.5. This provides a distinguisher on the keystream. In fact, this attack strategy is mitigated by the correlation attack analysis in Section 5.1. The nonlinearity of f represents the distance between f and its best affine approximation; hence, it already accounts for the fact that f 64 (x) = x 64 + x 65 x 66 correlates with x 64 on 3/4 of the inputs in F n 2 . Since f 64 is only used on E 64,128 , the correlation may not be exactly 3/4 on this subset. Moreover, the previous analysis does not consider that the correlation might be lower than 1/2 on some other slices. Conversely, the nonlinearity already incorporates this information. The WWQ function f i (x) = x i + x i+1 x i+2 corresponds to a function with t = 1 under Theorem 1. Applying the same reasoning as in Proposition 1 from Section 4.1, we obtain: 1 + 128 · 2 127 ≈ 133, r ≤ log 2 where r = log 2 (2 n−1 − NL(f )). This bound on r provides no guarantee against correlation attacks, unlike the case studied in Proposition 1. For security, a value close to 64 is desirable, whereas a value close to 128 is unfavorable. Therefore, these results discourage the use of such function for the given choices of n and N . Cryptanalysis on regular tap distribution The most straightforward way to select the taps is to place them at regular intervals of distance δ, smaller than N/n, between consecutive positions. In this case, denoting γ 0 as the first index, the list of taps is defined by ∀i ∈ [1, n − 1], γ i = γ 0 + i · δ. We show that such a distribution, when paired with certain weightwise degree-d functions, leads to a simple attack. Let f ∈ WD dn be defined on each slice E k,n by f k = g(x k , . . . , x k+r ), where the indices are taken modulo n. Such functions correspond to cyclic weightwise degree-d functions as defined in [MO24], with some also analyzed in [CS24]. We denote by x (t) the n-bit state given by the taps at time t. The keystream bits are given by z t = f (x (t) ) and z t+δ = f (x (t+δ) ), where z t+δ is obtained δ shifts of the LFSR later. (t+δ) (t) Using the properties of the LFSR, for all i ∈ [1, n − 1], we have x i = x i+1 . Accordingly, the Hamming weights of x (t) and x (t+δ) differ by at most one. (t+δ) (t) Now, suppose that 2 ≤ w H (x (t) ) = j ≤ n − r. If x 1 = 1 and x n = 0, then w H (x (t) ) = j (t+δ) and w H (x ) = j − 1, which gives: (t) (t) z t = f (x (t) ) = g(x j , . . . , x j+r ), and (t+δ) (t) (t) (t+δ) z t+δ = f (x (t+δ) ) = g(x j−1 , . . . , x j−1+r ) = g(x j , . . . , x j+r ) = z t . Thus, when x (t) has a Hamming weight in the range [2, n − r], we have: (t) (x 1 , x (t+δ) ) = (1, 0) =⇒ z t = z t+δ . n (t) (t+δ) Conversely, z t 6 = z t+δ implies (x 1 , x n ) 6 = (1, 0), which is satisfied if the quadratic equation (t+δ) (t) (x n +1)x 1 = 0 holds. Therefore, each time z t and z t+δ differ (which occurs with probability 0.5, as otherwise there would be a distinguisher on the keystream), we obtain quadratic equations in the key bits, provided the Hamming weight of x (t) belongs to a specific range. The probability that the weight of x (t) falls within [2, n − r] is X n . p r = 1 − n i i∈{0,1}∪[n−r+1,n] For simplicity, we assume that each quadratic equation obtained from cases where z t 6 = z t+δ (t) (t+δ) is valid with probability p r (this is an approximation, as the values of x 1 and x n are not (t) entirely independent of the weight of x ). Accordingly, an adversary can obtain degree-2 equations, linearize them, and solve the resulting linear system with probability N p = (p r ) 1+N + ( 2 ) . For a cyclic WWQ function with small r, such as the example in Section 5.2 where r = 2, the attack is efficient since p r is very close to 1. Conversely, this attack strategy is ineffective when r ≥ n/2, as in this case, p r is already below 1/2. Efficient homomorphic evaluation Assuming Nostalgia is a stream cipher secure in the known-plaintext model, it can be used as the symmetric encryption component of an HHE protocol such as in previous works e.g. [CCF + 16,MJSC16,DEG + 18,DGH + 23]. HHE ciphers are often optimized for either lowlatency or high-throughput. In this work, we focus on the first, and implement the homomorphic evaluation of Nostalgia using the TFHE scheme [CGGI16] in leveled mode [CGGI17]. Our implementation is available at https://github.com/antoniocgj/Nostalgia-cipher. FHE preliminaries We start with a brief overview of the GSW scheme [GSW13] and leveled-mode TFHE [CGGI17]. To avoid confusion with the variables of the cipher, we denote all parameters defining the FHE scheme with the hat modifier. Our evaluation approach is based mostly on well-known components from the FHE literature. Therefore, we present only a high-level description of the FHE scheme, referring the reader to [CGGI20] for more details. Let R q̂ = Z q̂ [X]/(X N̂ + 1) be a polynomial ring over the integers modulo q̂ for some power-of-two value N̂ , we define the following sets of ciphertexts: – MLWE ξ (m) ⊂ R r̂+1 is the set of Module-LWE ciphertexts encrypting some message q̂ m ∈ R p̂ with parameters ξ = ( N̂ , r̂, σ̂), where σ̂ is the noise standard deviation. `(r̂+1)×(r̂+1) – Similarly, MGSW ξ (m) ⊂ R q̂ is the set of Module-GSW ciphertexts encrypting ˆ N̂ , r̂, σ̂), where β̂ and ` ˆ are gadget some message m ∈ R with parameters ξ = ( β̂, `, decomposition parameters (see details in Section 3 of [CGGI20]). Additionally, we define the set of LWE ciphertexts encrypting messages m ∈ Z p̂ as the subset of MLWE ciphertexts such that N̂ = 1. Over these ciphertexts, we define: – Addition and scaling, denoted (+, ·) respectively, can be performed over any ciphertexts of the same type and parameters. – Multiplications, denoted , can only be performed with at least one MGSW operand. More precisely, we define the following two product operations. Notice that parameters can differ, preserving the parameters of the first operand. • internal product : MGSW ξ 1 MGSW ξ 2 7→ MGSW ξ 1 • external product : MLWE ξ 1 MGSW ξ 2 7→ MLWE ξ 1 – Extractions: Given a ciphertext c ∈ MGSW ξ 1 (m), c 0 ← ExtractMLWE(c) produces a ciphertext c 0 ∈ MLWE ξ 1 (m). Similarly, given c 0 ∈ MLWE ξ 1 (m), c 00 ← ExtractLWE(c 0 ) produces a ciphertext c 00 ∈ LWE ξ 1 (m 0 ), where m 0 ∈ Z p̂ is constant term of the polynomial m ∈ R p̂ . – Packing Key Switching [CGGI17]: Given a list of k < N̂ LWE ciphertexts c i ∈ LWE ξ 1 (m i ) for m i ∈ Z p̂ , c 0 ← PackingKS(c 0 , c 1 , . . . , c k−1 ) produces c 0 ∈ MLWE ξ 1 (m) such that P i m = k−1 i=0 m i X . Multiplications, and in particular internal products, are the most expensive operations, whereas additions, scaling, and extractions have almost negligible cost. Packing Key Switching, although also expensive, will only be used once in our evaluation approach. Leveled evaluation We divide our evaluation into two main procedures that run with two different sets of HE parameters, denoted ξ 1 and ξ 2 . As in any module-LWE [Reg05,LPR10] scheme, fresh ciphertexts contain a small amount of noise for security, which increases as we perform operations. In leveled schemes, one typically establishes a chain of parameters (e.g. ξ 1 , ξ 2 , ξ 3 , . . . ), one set per multiplication level, for working with ciphertexts with increasingly more noise. Our evaluation approach only requires two levels, regardless of the size of the output stream. LFSR step Let K, K̃ ∈ Z N 2 be, respectively, the secret key and the current state of an LFSR, p = 1 + x + x + x + x 1024 be its polynomial, and idx(p) be the set of exponents of the non-zero coefficients of p except 1024. Suppose we are at the j-th LFSR update. One could P compute the new state by rotating the current one and replacing the last bit with K̂ ← i∈idx(p) K̃ i . This process is interactive over the current state, does not require keep tracking of j, and works well on cleartext. When homomorphically evaluated, however, it leads to noise that grows exponentially with the number of LFSR updates. In particular, K̃ would have O(2 j/2 ) times more noise than K. Instead, given only p, one can produce a new polynomial p 0 j for round j, such that the new LFSR bit K̂ can be produced directly from the P secret key, i.e. , K̂ ← i∈idx(p 0 ) K i (notice that K̂ is now computed from the original secret key K). This new polynomial can be significantly more dense than the original p, but, on the positive side, we can establish an upper bound for the noise of the current LFSR state independently of the number of updates. Algorithm 2 describes our LFSR update step. The update polynomial p 0 can be trivially (and inexpensively) computed (or precomputed) on plaintext since it does not depend on any secret information. Algorithm 2 Homomorphic evaluation of the LFSR step Input: A list C i ∈ MGSW ξ 1 (K i ) for i ∈ [0, N ) encrypting the symmetric secret key. Input: A list C̃ i ∈ MGSW ξ 2 ( K̃ i ) P for i ∈ [0, N ) encrypting the current state of the LFSR −1 0 i Input: Update polynomial p 0 = N i=0 p i X Output: A list Ĉ i ∈ MGSW ξ 2 ( K̃ i ) for i ∈ [0, N ) encrypting the new state of the LFSR 1: for i = 0 to N − 2 do Ĉ i ← C̃ i+1 3: end for 4: c ← MGSW ξ 2 (0) 5: for i = 0 to N − 1 do if p 0 i = 1 then c ← (MGSW ξ 2 (1) − 2 · c) C i + c end if 9: end for 10: Ĉ N −1 ← c 11: return Ĉ . Rotate LFSR . Compute new bit . Emulate XOR P Filter function Our goal is to compute the function f (x 0 , . . . , x n−1 ) = x h + bn/3c i=1 x (h−i) · x (h+2i−1) for every possible value of h. Notice that this can be represented as an inner product of two vectors. Let u = [x 0 , x 1 , . . . , x n−1 ] and v ← {0} n , for some given h, we set v h−i ← x 2i−1+h for i ∈ [1, bn/3c] and v h = 1. The function f can now be computed as f = hu, vi. Inner products, in turn, can be computed as polynomial multiplications. Con- P n−1 P n−1 v i X N̂ −i v i X i and g 1 (v) = v 0 − i=1 sider the coefficient embedding functions g 0 (v) = i=0 on power-of-two cyclotomic rings. Let u and v be vectors defined as before, the constant term of the product g 0 (u) · g 1 (v) is the result of the inner product between u and v. This is how we homomorphically evaluate each possible function for the filter, as Algorithm 3 shows. In lines 1 to 4, we build the MGSW ciphertext p 0 , which encrypts g 0 (u). Then, for each possible value of h (Line 6), we build an MLWE ciphertext t (Lines 7 to 9), encrypting g 1 (v). These two ciphertexts are multiplied, and the constant term is extracted and stored in F h . Finally, after computing all possible functions (stored as LWE ciphertexts P in the i vector F ), we embed the results back into the MLWE ciphertext p 1 = MLWE ξ 2 ( h−1 i=0 F i X ) using a packing key switching. In lines 14 to 16, we rotate this polynomial by multiplying it by X −h , where h is the Hamming Weight of the filter state. This brings the correct result to the constant term of p 1 , which is extracted (Line 17) and returned. Results We implemented our HHE evaluation using the MOSFHET library [GBA24] and benchmarked it on an AWS r7i.metal-24xl instance (Intel Xeon Platinum 8488C at 3.2GHz). Our implementation is single-threaded, and we report the average of 1000 executions. Table 4 Algorithm 3 Homomorphic evaluation of the filter function Input: A list C i ∈ MGSW ξ 2 ( K̂ i ) for i ∈ [0, n) encrypting the current filter state, as given by the taps. Output: a ciphertext c ∈ LWE ξ 2 (m) encrypting the output bit m ∈ Z 2 1: p 0 ← MGSW ξ 2 (0) 2: for i = 0 to n − 1 do p 0 ← p 0 + C i · X i 4: end for 5: F ← {0} . Vector to store the result of each possible function 6: for h = 0 to n − 1 do t ← MLWE ξ 2 (X N −h ) for j = 1 to bn/3c do t ← t + ExtractMLWE(C (2j−1+h) mod n ) · X N̂ −((h−j) mod n) end for F h ← ExtractLWE(t p 0 ) . F h stores an LWE with the result for HW = h 12: end for 13: p 1 ← PackingKS(F 0 , F 1 , . . . , F n−1 ) · X 14: for i = 0 to n − 1 do . Select the correct result based on HW p 1 ← p 1 C i · X −1 + (1 − C i ) 16: end for 17: return ExtractLWE(p 1 ) presents the HE parameters, selected for 128-bit security and negligible (< 2 −128 ) probability of failure. Using these parameters, the symmetric key encryption takes 80MB, which could be reduced to kilobytes by using compression techniques for GSW encryption [KLD + 23]. Table 4. Parameters for the HE evaluation of Nostalgia. ĥ ∗ N̂ Parameter Set r̂ ξ 1 ξ 2 ` ˆ q̂ β̂ σ̂ 2 9 2 12 2 17 2 64 ∗ We use ternary secrets with Hamming weight ĥ. HHE performance Table 5 presents our results and compares with other state-of-the-art implementations of latency-optimized ciphers evaluated with TFHE. We reproduce results as reported by each implementation. Whenever possible, we take implementations that are single-threaded and present negligible probability of failure, and we indicate it otherwise. As we focus on optimizing latency, our homomorphic evaluation of Nostalgia is significantly faster than previous literature, being 6.1 times faster than the recently-introduced Transistor [BBB + 25]. Margrethe [AGHM25] is an exception to that, presenting 1.5 lower latency than Nostalgia. It should be noted, however, that their efficient evaluation is the result of a long line of research on efficient MFP-based HHE [MCJS19,CHMS22,MPP24,AGHM25], and includes many techniques that could also be considered for optimizing LFSR-based ciphers. We refer to [NWH + 25] for comparisons with HHE using other HE schemes. In particular, we note that ciphers such as FiLIP can be much faster with NTRU-based HE schemes, as shown in [MPP24]. Nostalgia could also be evaluated using the same techniques, but we leave further optimizations as future work. Table 5. Performance results and comparison with other ciphers evaluated with TFHE. Cipher Implementation CHMS22 [CHMS22] CHMS22 [CHMS22] † CCH + 24 [CCH + 24] † CCH + 24 [CCH + 24] † BOS23 [BOS23] † AGHM24 [AGHM25] CCH + 24 [CCH + 24] † BBB + [BBB + 25] This work FiLIP 144 [MCJS19] Elisabeth [CHMS22] Elisabeth [CHMS22] Elisabeth-b [HMS23] Kreyvium [CCF + 18] Margrethe [HMS23] FRAST [CCH + 24] Transistor [BBB + 25] Nostalgia ∗ Results from multi-threaded implementations. † Nonnegligible probability of failure. Conclusion Latency (ms) Throughput (bits/s) 91 ∗ 150 ∗ 43.96 ∗ 427.00 ∗ 20.66 ∗ In this work, we introduced Nostalgia, a new filtered LFSR designed to provide 128-bit security. We analyzed state-of-the-art attacks on this class of constructions and proposed a design with a larger register size and an increased number of variables in the filtering function to enhance resistance against known attacks. By carefully selecting the filter function and increasing the register size, Nostalgia mitigates the weaknesses that led to the decline of filtered LFSRs following the introduction of (fast) algebraic attacks. We selected a weightwise quadratic function as the filtering function and demonstrated that its standard cryptographic properties are sufficient for the targeted security level. Additionally, we examined how alternative filtering functions could lead to dedicated attacks that do not apply to Nostalgia. Furthermore, we showed that the proposed stream cipher, particularly the chosen WWQ function, has the potential to be efficient for future applications in hybrid homomorphic encryption. The rise of arithmetic-oriented cryptographic primitives and specialized symmetric designs suggests that filtered LFSRs, once considered obsolete, may be reconsidered in modern settings where their structure and efficiency offer new advantages. This is particularly the case for HHE applications, where the homomorphic evaluation of our design provides competitive performance compared to other recent proposals, being 6.1 times faster than Transistor [BBB + 25]. We hope that this work will revive interest in filtered LFSRs, encouraging further research into secure instances and fostering cryptanalysis efforts to refine and strengthen their security. An interesting direction for future work is to develop more efficient homomorphic implementations of Nostalgia, highlighting the practical relevance of our design in privacy-preserving applications. Furthermore, implementing Nostalgia in a standard (non-homomorphic) context—by fine-tuning the initialization process—would allow for a meaningful comparison with other stream cipher designs, offering insights into the practical value of filtered LFSRs. ## Acknowledgments Antonio Guimarães was funded by the PICOCRYPT project, funded by the European Research Council (ERC) under the European Unions Horizon 2020 research and innovation programme (Grant agreement No. 101001283), and by grant CEX2024-001471-M, funded by MICIU/AEI/10.13039/501100011033. Pierrick Méaux was funded by the European Research Council (ERC) under the Advanced Grant program (reference number: 787390). ## References ACG + 06. Frederik Armknecht, Claude Carlet, Philippe Gaborit, Simon Künzli, Willi Meier, and Olivier Ruatta. Efficient computation of algebraic immunity for algebraic and fast algebraic attacks. In Serge Vaudenay, editor, Advances in Cryptology - EUROCRYPT 2006, 25th Annual International Conference on the Theory and Applications of Cryptographic Techniques, St. Petersburg, Russia, May 28 - June 1, 2006, Proceedings, volume 4004 of Lecture Notes in Computer Science, pages 147–164. Springer, 2006. AGHM25. Diego F. Aranha, Antonio Guimarães, Clément Hoffmann, and Pierrick Méaux. Secure and efficient transciphering for FHE-based MPC. IACR Transactions on Cryptographic Hardware and Embedded Systems, 2025(3):745–780, 2025. AGP + 19. Martin R. Albrecht, Lorenzo Grassi, Léo Perrin, Sebastian Ramacher, Christian Rechberger, Dragos Rotaru, Arnab Roy, and Markus Schofnegger. Feistel structures for mpc, and more. In Kazue Sako, Steve A. Schneider, and Peter Y. A. Ryan, editors, ESORICS 2019, Part II, volume 11736 of LNCS, pages 151–171. Springer, 2019. AGR + 16. Martin R. Albrecht, Lorenzo Grassi, Christian Rechberger, Arnab Roy, and Tyge Tiessen. Mimc: Efficient encryption and cryptographic hashing with minimal multiplicative complexity. In Jung Hee Cheon and Tsuyoshi Takagi, editors, ASIACRYPT 2016, Part I, volume 10031 of LNCS, pages 191–219, 2016. AMT22. Tomer Ashur, Mohammad Mahzoun, and Dilara Toprakhisar. Chaghri - A FHE-friendly block cipher. In Heng Yin, Angelos Stavrou, Cas Cremers, and Elaine Shi, editors, CCS 2022, pages 139–150. ACM, 2022. APRR24. Navid Alamati, Guru-Vamsi Policharla, Srinivasan Raghuraman, and Peter Rindal. Improved alternatingmoduli prfs and post-quantum signatures. In Leonid Reyzin and Douglas Stebila, editors, CRYPTO 2024, Part VIII, volume 14927 of LNCS, pages 274–308. Springer, 2024. ARS + 15. Martin R. Albrecht, Christian Rechberger, Thomas Schneider, Tyge Tiessen, and Michael Zohner. Ciphers for MPC and FHE. In Elisabeth Oswald and Marc Fischlin, editors, EUROCRYPT 2015, Part I, volume 9056 of LNCS, pages 430–454. Springer, 2015. BBB + 25. Jules Baudrin, Sonia Belaı̈d, Nicolas Bon, Christina Boura, Anne Canteaut, Gaëtan Leurent, Pascal Paillier, Léo Perrin, Matthieu Rivain, Yann Rotella, and Samuel Tap. Transistor: a TFHE-Friendly Stream Cipher. In Yael Tauman Kalai and Seny F. Kamara, editors, Advances in Cryptology - CRYPTO 2025, pages 530–565, Cham, 2025. Springer Nature Switzerland. BBC + 23. Clémence Bouvier, Pierre Briaud, Pyrros Chaidos, Léo Perrin, Robin Salen, Vesselin Velichkov, and Danny Willems. New design techniques for efficient arithmetization-oriented hash functions: Anemoi permutations and Jive compression mode. In Helena Handschuh and Anna Lysyanskaya, editors, CRYPTO 2023, Part III, volume 14083 of LNCS, pages 507–539. Springer, 2023. BD07. Eli Biham and Orr Dunkelman. Differential cryptanalysis in stream ciphers. IACR Cryptol. ePrint Arch., page 218, 2007. BOS23. Thibault Balenbois, Jean-Baptiste Orfila, and Nigel P. Smart. Trivial transciphering with trivium and TFHE. In Michael Brenner, Anamaria Costache, and Kurt Rohloff, editors, Proceedings of the 11th Workshop on Encrypted Computing & Applied Homomorphic Cryptography, Copenhagen, Denmark, 26 November 2023, pages 69–78. ACM, 2023. BP05. An Braeken and Bart Preneel. On the algebraic immunity of symmetric boolean functions. In Progress in Cryptology - INDOCRYPT 2005, 6th International Conference on Cryptology in India, Bangalore, India, December 10-12, 2005, Proceedings, pages 35–48, 2005. Bry91. Randal E. Bryant. On the complexity of VLSI implementations and graph representations of boolean functions with application to integer multiplication. IEEE Trans. Computers, pages 205–213, 1991. BS00. Alex Biryukov and Adi Shamir. Cryptanalytic time/memory/data tradeoffs for stream ciphers. In Tatsuaki Okamoto, editor, Advances in Cryptology — ASIACRYPT 2000, pages 1–13, Berlin, Heidelberg, 2000. Springer Berlin Heidelberg. BV16. Sonia Bogos and Serge Vaudenay. Optimization of \mathsf LPN solving algorithms. In Jung Hee Cheon and Tsuyoshi Takagi, editors, Advances in Cryptology - ASIACRYPT 2016 - 22nd International Conference on the Theory and Application of Cryptology and Information Security, Hanoi, Vietnam, December 4-8, 2016, Proceedings, Part I, volume 10031 of Lecture Notes in Computer Science, pages 703–728, 2016. Car04. Claude Carlet. On the degree, nonlinearity, algebraic thickness, and nonnormality of boolean functions, with developments on symmetric functions. IEEE Trans. Information Theory, pages 2178–2185, 2004. Car21. Claude Carlet. Boolean Functions for Cryptography and Coding Theory. Cambridge University Press, 2021. Car22. Claude Carlet. A wide class of boolean functions generalizing the hidden weight bit function. IEEE Trans. Inf. Theory, 68(2):1355–1368, 2022. CCF + 16. Anne Canteaut, Sergiu Carpov, Caroline Fontaine, Tancrède Lepoint, Marı́a Naya-Plasencia, Pascal Paillier, and Renaud Sirdey. Stream ciphers: A practical solution for efficient homomorphic-ciphertext compression. In Thomas Peyrin, editor, Fast Software Encryption - 23rd International Conference, FSE 2016, Bochum, Germany, March 20-23, 2016, Revised Selected Papers, volume 9783 of Lecture Notes in Computer Science, pages 313–333. Springer, 2016. CCF + 18. Anne Canteaut, Sergiu Carpov, Caroline Fontaine, Tancrède Lepoint, Marı́a Naya-Plasencia, Pascal Paillier, and Renaud Sirdey. Stream Ciphers: A Practical Solution for Efficient Homomorphic-Ciphertext Compression. Journal of Cryptology, 31(3):885–916, July 2018. CCH + 24. Mingyu Cho, Woohyuk Chung, Jincheol Ha, Jooyoung Lee, Eun-Gyeol Oh, and Mincheol Son. FRAST: TFHE-friendly cipher based on random S-boxes. IACR Trans. Symmetric Cryptol., 2024(3):1–43, 2024. CDPP22. Kelong Cong, Debajyoti Das, Jeongeun Park, and Hilder V. L. Pereira. Sortinghat: Efficient private decision tree evaluation via homomorphic encryption and transciphering. In Heng Yin, Angelos Stavrou, Cas Cremers, and Elaine Shi, editors, CCS 2022, pages 563–577. ACM, 2022. CGGI16. Ilaria Chillotti, Nicolas Gama, Mariya Georgieva, and Malika Izabachène. Faster fully homomorphic encryption: Bootstrapping in less than 0.1 seconds. In Jung Hee Cheon and Tsuyoshi Takagi, editors, Advances in Cryptology - ASIACRYPT 2016 - 22nd International Conference on the Theory and Application of Cryptology and Information Security, Hanoi, Vietnam, December 4-8, 2016, Proceedings, Part I, volume 10031 of Lecture Notes in Computer Science, pages 3–33, 2016. CGGI17. Ilaria Chillotti, Nicolas Gama, Mariya Georgieva, and Malika Izabachène. Improving TFHE: faster packed homomorphic operations and efficient circuit bootstrapping. IACR Cryptology ePrint Archive, 2017:430, 2017. CGGI20. Ilaria Chillotti, Nicolas Gama, Mariya Georgieva, and Malika Izabachène. TFHE: fast fully homomorphic encryption over the torus. J. Cryptol., 33(1):34–91, 2020. CHK + 21. Jihoon Cho, Jincheol Ha, Seongkwang Kim, ByeongHak Lee, Joohee Lee, Jooyoung Lee, Dukjae Moon, and Hyojin Yoon. Transciphering framework for approximate homomorphic encryption. In Mehdi Tibouchi and Huaxiong Wang, editors, ASIACRYPT 2021, Part III, volume 13092 of LNCS, pages 640–669. Springer, 2021. CHMS22. Orel Cosseron, Clément Hoffmann, Pierrick Méaux, and François-Xavier Standaert. Towards caseoptimized hybrid homomorphic encryption - featuring the Elisabeth stream cipher. In Shweta Agrawal and Dongdai Lin, editors, ASIACRYPT 2022, Part III, volume 13793 of LNCS, pages 32–67. Springer, 2022. CL11. Y. Chen and P. Lu. Two classes of symmetric boolean functions with optimum algebraic immunity: Construction and analysis. IEEE Transactions on Information Theory, 57(4):2522–2538, April 2011. CM03. Nicolas T. Courtois and Willi Meier. Algebraic attacks on stream ciphers with linear feedback. In Eli Biham, editor, Advances in Cryptology - EUROCRYPT 2003, International Conference on the Theory and Applications of Cryptographic Techniques, Warsaw, Poland, May 4-8, 2003, Proceedings, volume 2656 of Lecture Notes in Computer Science, pages 345–359. Springer, 2003. CM21. Claude Carlet and Pierrick Méaux. A complete study of two classes of boolean functions: direct sums of monomials and threshold functions. IEEE Transactions on Information Theory, pages 1–1, 2021. Cou03. Nicolas T. Courtois. Fast algebraic attacks on stream ciphers with linear feedback. In Dan Boneh, editor, Advances in Cryptology - CRYPTO 2003, 23rd Annual International Cryptology Conference, Santa Barbara, California, USA, August 17-21, 2003, Proceedings, volume 2729 of Lecture Notes in Computer Science, pages 176–194. Springer, 2003. CP08. Christophe De Cannière and Bart Preneel. Trivium. LNCS, New Stream Cipher Designs - The eSTREAM Finalists, page 244–266, 2008. CR16. Anne Canteaut and Yann Rotella. Attacks against filter generators exploiting monomial mappings. In Thomas Peyrin, editor, Fast Software Encryption, pages 78–98, Berlin, Heidelberg, 2016. Springer Berlin Heidelberg. CS91. Vladimir V. Chepyzhov and Ben J. M. Smeets. On A fast correlation attack on certain stream ciphers. In Donald W. Davies, editor, Advances in Cryptology - EUROCRYPT ’91, Workshop on the Theory and Application of of Cryptographic Techniques, Brighton, UK, April 8-11, 1991, Proceedings, volume 547 of Lecture Notes in Computer Science, pages 176–185. Springer, 1991. CS24. Claude Carlet and Palash Sarkar. Constructions of efficiently implementable boolean functions possessing high nonlinearity and good resistance to algebraic attacks. IACR Cryptol. ePrint Arch., page 1305, 2024. CT00. Anne Canteaut and Michaël Trabbia. Improved fast correlation attacks using parity-check equations of weight 4 and 5. In Bart Preneel, editor, Advances in Cryptology - EUROCRYPT 2000, International Conference on the Theory and Application of Cryptographic Techniques, Bruges, Belgium, May 14-18, 2000, Proceeding, volume 1807 of Lecture Notes in Computer Science, pages 573–588. Springer, 2000. CV05. Anne Canteaut and Marion Videau. Symmetric boolean functions. IEEE Trans. Information Theory, pages 2791–2811, 2005. DEG + 18. Christoph Dobraunig, Maria Eichlseder, Lorenzo Grassi, Virginie Lallemand, Gregor Leander, Eik List, Florian Mendel, and Christian Rechberger. Rasta: A cipher with low anddepth and few ands per bit. In Hovav Shacham and Alexandra Boldyreva, editors, CRYPTO 2018, Part I, volume 10991 of LNCS, pages 662–692. Springer, 2018. DGH + 23. Christoph Dobraunig, Lorenzo Grassi, Lukas Helminger, Christian Rechberger, Markus Schofnegger, and Roman Walch. Pasta: A case for hybrid homomorphic encryption. IACR Trans. Cryptogr. Hardw. Embed. Syst., 2023(3):30–73, 2023. DKR + 22. Christoph Dobraunig, Daniel Kales, Christian Rechberger, Markus Schofnegger, and Greg Zaverucha. Shorter signatures based on tailor-made minimalist symmetric-key crypto. In Heng Yin, Angelos Stavrou, Cas Cremers, and Elaine Shi, editors, CCS 2022, pages 843–857. ACM, 2022. Fau99. Jean-Charles Faugère. A new efficient algorithm for computing groebner bases. Journal of Pure and Applied Algebra, 139:61–88, june 1999. Fau02. Jean-Charles Faugère. A new efficient algorithm for computing Grobner bases without reduction to zero. In Workshop on application of Groebner Bases 2002, Catania, Spain, 2002. GBA24. Antonio Guimarães, Edson Borin, and Diego F. Aranha. MOSFHET: Optimized Software for FHE over the Torus. Journal of Cryptographic Engineering, July 2024. GHR + 23. Lorenzo Grassi, Yonglin Hao, Christian Rechberger, Markus Schofnegger, Roman Walch, and Qingju Wang. Horst meets fluid-spn: Griffin for zero-knowledge applications. In Helena Handschuh and Anna Lysyanskaya, editors, CRYPTO 2023, Part III, volume 14083 of LNCS, pages 573–606. Springer, 2023. GKR + 21. Lorenzo Grassi, Dmitry Khovratovich, Christian Rechberger, Arnab Roy, and Markus Schofnegger. Poseidon: A new hash function for zero-knowledge proof systems. In Michael Bailey and Rachel Greenstadt, editors, USENIX Security 2021, pages 519–535. USENIX Association, 2021. GLR + 20. Lorenzo Grassi, Reinhard Lüftenegger, Christian Rechberger, Dragos Rotaru, and Markus Schofnegger. On a generalization of substitution-permutation networks: The HADES design strategy. In Anne Canteaut and Yuval Ishai, editors, EUROCRYPT 2020, Part II, volume 12106 of LNCS, pages 674–704. Springer, 2020. GM22. Agnese Gini and Pierrick Méaux. On the weightwise nonlinearity of weightwise perfectly balanced functions. Discret. Appl. Math., 322:320–341, 2022. GMM + 24. Lorenzo Grassi, Loı̈c Masure, Pierrick Méaux, Thorben Moos, and François-Xavier Standaert. Generalized feistel ciphers for efficient prime field masking. In Marc Joye and Gregor Leander, editors, EUROCRYPT 2024, Part III, volume 14653 of LNCS, pages 188–220. Springer, 2024. Gol82. Solomon Golomb. Shift register sequences, volume 1. Laguna Hills, Calif., Aegean Park Press, 1982. GØSW23. Lorenzo Grassi, Morten Øygarden, Markus Schofnegger, and Roman Walch. From farfalle to megafono via ciminion: The PRF hydra for MPC applications. In Carmit Hazay and Martijn Stam, editors, EUROCRYPT 2023, Part IV, volume 14007 of LNCS, pages 255–286. Springer, 2023. GRHH11. Guang Gong, Sondre Rønjom, Tor Helleseth, and Honggang Hu. Fast discrete fourier spectra attacks on stream ciphers. IEEE Transactions on Information Theory, 57(8):5555–5565, 2011. GSW13. Craig Gentry, Amit Sahai, and Brent Waters. Homomorphic encryption from learning with errors: Conceptually-simpler, asymptotically-faster, attribute-based. In Ran Canetti and Juan A. Garay, editors, Advances in Cryptology - CRYPTO 2013 - 33rd Annual Cryptology Conference, Santa Barbara, CA, USA, August 18-22, 2013. Proceedings, Part I, volume 8042 of Lecture Notes in Computer Science, pages 75–92. Springer, 2013. HKL + 22. Jincheol Ha, Seongkwang Kim, ByeongHak Lee, Jooyoung Lee, and Mincheol Son. Rubato: Noisy ciphers for approximate homomorphic encryption. In Orr Dunkelman and Stefan Dziembowski, editors, EUROCRYPT 2022, Part I, volume 13275 of LNCS, pages 581–610. Springer, 2022. HMR20. Clément Hoffmann, Pierrick Méaux, and Thomas Ricosset. Transciphering, using filip and TFHE for an efficient delegation of computation. In Karthikeyan Bhargavan, Elisabeth Oswald, and Manoj Prabhakaran, editors, Progress in Cryptology - INDOCRYPT 2020 - 21st International Conference on Cryptology in India, Bangalore, India, December 13-16, 2020, Proceedings, volume 12578 of Lecture Notes in Computer Science, pages 39–61. Springer, 2020. HMS23. Clément Hoffmann, Pierrick Méaux, and François-Xavier Standaert. The patching landscape of elisabeth- 4 and the mixed filter permutator paradigm. In Anupam Chattopadhyay, Shivam Bhasin, Stjepan Picek, and Chester Rebeiro, editors, INDOCRYPT 2023, Part I, volume 14459 of LNCS, pages 134–156. Springer, 2023. HR04. Philip Hawkes and Gregory G. Rose. Rewriting variables: The complexity of fast algebraic attacks on stream ciphers. In Matthew K. Franklin, editor, Advances in Cryptology - CRYPTO 2004, 24th Annual International CryptologyConference, Santa Barbara, California, USA, August 15-19, 2004, Proceedings, volume 3152 of Lecture Notes in Computer Science, pages 390–406. Springer, 2004. HS05. Jin Hong and Palash Sarkar. New applications of time memory data tradeoffs. In Bimal Roy, editor, Advances in Cryptology - ASIACRYPT 2005, pages 353–372, Berlin, Heidelberg, 2005. Springer Berlin Heidelberg. KHS + 23. Seongkwang Kim, Jincheol Ha, Mincheol Son, ByeongHak Lee, Dukjae Moon, Joohee Lee, Sangyup Lee, Jihoon Kwon, Jihoon Cho, Hyojin Yoon, and Jooyoung Lee. AIM: symmetric primitive for shorter signatures with stronger security. In Weizhi Meng, Christian Damsgaard Jensen, Cas Cremers, and Engin Kirda, editors, CCS 2023, pages 401–415. ACM, 2023. KLD + 23. Andrey Kim, Yongwoo Lee, Maxim Deryabin, Jieun Eom, and Rakyong Choi. LFHE: Fully Homomorphic Encryption with Bootstrapping Key Size Less than a Megabyte. (2023/767), 2023. Publication info: Preprint. LPR10. Vadim Lyubashevsky, Chris Peikert, and Oded Regev. On ideal lattices and learning with errors over rings. In Henri Gilbert, editor, Advances in Cryptology - EUROCRYPT 2010, 29th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Monaco / French Riviera, May 30 - June 3, 2010. Proceedings, volume 6110 of Lecture Notes in Computer Science, pages 1–23. Springer, 2010. MCJS19. Pierrick Méaux, Claude Carlet, Anthony Journault, and François-Xavier Standaert. Improved filter permutators for efficient FHE: better instances and implementations. In Feng Hao, Sushmita Ruj, and Sourav Sen Gupta, editors, Progress in Cryptology - INDOCRYPT, volume 11898 of LNCS, pages 68–91. Springer, 2019. Méa19. Pierrick Méaux. On the fast algebraic immunity of majority functions. In Peter Schwabe and Nicolas Thériault, editors, Progress in Cryptology – LATINCRYPT 2019, pages 86–105, Cham, 2019. Springer International Publishing. Méa21. Pierrick Méaux. On the fast algebraic immunity of threshold functions. Cryptogr. Commun., 13(5):741– 762, 2021. Méa25. Pierrick Méaux. From at least n/3 to at most 3 sqrt n correcting the algebraic immunity of the hidden weight bit function - algebraic immunity upper bounds on weightwise degree-d functions and their implications. In Daniel Escudero and Ivan Damgård, editors, Progress in Cryptology - LATINCRYPT 2025 - 9th International Conference on Cryptology and Information Security in Latin America, Medellı́n, Colombia, October 1-3, 2025, Proceedings, volume 16129 of Lecture Notes in Computer Science, pages 345–369. Springer, 2025. MJSC16. Pierrick Méaux, Anthony Journault, François-Xavier Standaert, and Claude Carlet. Towards stream ciphers for efficient FHE with low-noise ciphertexts. In Marc Fischlin and Jean-Sébastien Coron, editors, Advances in Cryptology - EUROCRYPT 2016 - 35th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Vienna, Austria, May 8-12, 2016, Proceedings, Part I, volume 9665 of Lecture Notes in Computer Science, pages 311–343. Springer, 2016. MMMS23. Loı̈c Masure, Pierrick Méaux, Thorben Moos, and François-Xavier Standaert. Effective and efficient masking with low noise using small-mersenne-prime ciphers. In Carmit Hazay and Martijn Stam, editors, EUROCRYPT 2023, Part IV, volume 14007 of LNCS, pages 596–627. Springer, 2023. MO24. Pierrick Méaux and Yassine Ozaim. On the cryptographic properties of weightwise affine and weightwise quadratic functions. Discret. Appl. Math., 355:13–29, 2024. MPC04. Willi Meier, Enes Pasalic, and Claude Carlet. Algebraic attacks and decomposition of boolean functions. In Christian Cachin and Jan L. Camenisch, editors, Advances in Cryptology - EUROCRYPT 2004, pages 474–491, Berlin, Heidelberg, 2004. Springer Berlin Heidelberg. MPP24. Pierrick Méaux, Jeongeun Park, and Hilder V. L. Pereira. Towards practical transciphering for FHE with setup independent of the plaintext space. IACR Commun. Cryptol., 1(1):20, 2024. MS88. Willi Meier and Othmar Staffelbach. Fast correlation attacks on stream ciphers (extended abstract). In Christoph G. Günther, editor, Advances in Cryptology - EUROCRYPT ’88, Workshop on the Theory and Application of of Cryptographic Techniques, Davos, Switzerland, May 25-27, 1988, Proceedings, volume 330 of Lecture Notes in Computer Science, pages 301–314. Springer, 1988. MST24. Pierrick Méaux, Tim Seuré, and Deng Tang. The revisited hidden weight bit function. IACR Cryptol. ePrint Arch., page 2022, 2024. To appear at SAC 2025. NLV11. Michael Naehrig, Kristin Lauter, and Vinod Vaikuntanathan. Can homomorphic encryption be practical? In Proceedings of the 3rd ACM Workshop on Cloud Computing Security Workshop, CCSW ’11, page 113–124, New York, NY, USA, 2011. Association for Computing Machinery. NWH + 25. Chao Niu, Benqiang Wei, Zhicong Huang, Zhaomin Yang, Cheng Hong, Meiqin Wang, and Tao Wei. SoK: FHE-Friendly Symmetric Ciphers and Transciphering. IACR Transactions on Cryptographic Hardware and Embedded Systems, 2025(3):583–613, June 2025. QFLW09. Longjiang Qu, Keqin Feng, Feng Liu, and Lei Wang. Constructing symmetric boolean functions with maximum algebraic immunity. IEEE Trans. Information Theory, pages 2406–2412, 2009. Reg05. Oded Regev. On lattices, learning with errors, random linear codes, and cryptography. In Harold N. Gabow and Ronald Fagin, editors, Proceedings of the 37th Annual ACM Symposium on Theory of Computing, Baltimore, MD, USA, May 22-24, 2005, pages 84–93. ACM, 2005. RH07. Sondre Røjom and Tor Helleseth. A new attack on the filter generator. IEEE Transactions on Information Theory, 53(5):1752–1758, 2007. Røn17. Sondre Rønjom. Improving algebraic attacks on stream ciphers based on linear feedback shift register over F 2 k . Des. Codes Cryptography, 82(1–2):27–41, jan 2017. Sie84. Thomas Siegenthaler. Correlation-immunity of nonlinear combining functions for cryptographic applications. IEEE, IT-30(5):776–780, 1984. Sie85. Thomas Siegenthaler. Decrypting a Class of Stream Ciphers Using Ciphertext Only. IEEE Trans. Computers, 34(1):81–85, 1985. SM07. Palash Sarkar and Subhamoy Maitra. Balancedness and correlation immunity of symmetric boolean functions. Discrete Mathematics, pages 2351 – 2358, 2007. WCST14. Qichun Wang, Claude Carlet, Pantelimon Stanica, and Chik How Tan. Cryptographic properties of the hidden weighted bit function. Discret. Appl. Math., 174:1–10, 2014. A Details on the Nostalgia instance A.1 taps The selected bit indices from the LFSR state used as inputs to the filtering function (i.e. , the taps) are as follows: taps = (0, 2, 5, 9, 10, 15, 17, 20, 24, 25, 28, 32, 36, 40, 41, 51, 58, 62, 66, 77, 79, 83, 99, 100, 104, 124, 129, 131, 137, 160, 177, 178, 193, 194, 197, 200, 201, 216, 218, 228, 230, 238, 240, 250, 281, 298, 307, 316, 324, 328, 335, 342, 347, 350, 361, 375, 377, 378, 379, 381, 387, 390, 397, 430, 440, 456, 457, 469, 476, 484, 501, 531, 535, 536, 541, 557, 565, 566, 568, 569, 575, 581, 603, 608, 609, 624, 638, 639, 647, 651, 661, 681, 696, 697, 699, 700, 701, 702, 710, 712, 726, 752, 759, 769, 780, 781, 791, 792, 808, 813, 814, 827, 857, 866, 874, 893, 899, 932, 956, 961, 963, 964, 975, 976, 997, 1000, 1014, 1021) A.2 Example of the filtering function with a small n. We provide the algebraic normal form of f in 6 variables (we recall that the filter function in Nostalgia is in 128 variables, making it impossible to write its ANF). Let n = 6 we have:     b n c X X  ϕ k,6 (x) ·  x k + f (x 1 , x 2 , x 3 , x 4 , x 5 , x 6 ) = x k−i x k+2i−1   k=1 i=1 = ϕ 1,6 (x)(x 1 + x 6 x 2 + x 5 x 4 ) + ϕ 2,6 (x)(x 2 + x 1 x 3 + x 6 x 5 ) + ϕ 3,6 (x)(x 3 + x 2 x 4 + x 1 x 6 ) + ϕ 4,6 (x)(x 4 + x 3 x 5 + x 2 x 1 ) + ϕ 5,6 (x)(x 5 + x 4 x 6 + x 3 x 2 ) + ϕ 6,6 (x)(x 6 + x 5 x 1 + x 4 x 3 ) = x 1 x 2 x 3 x 4 x 5 + x 1 x 2 x 3 x 4 x 6 + x 1 x 2 x 3 x 6 + x 1 x 2 x 3 + x 1 x 2 x 4 x 5 x 6 + x 1 x 2 x 5 + x 1 x 3 x 4 x 5 x 6 + x 1 x 3 x 4 x 5 + x 1 x 3 x 4 + x 1 x 3 x 5 x 6 + x 1 x 3 x 5 + x 1 x 4 x 5 x 6 + x 1 x 4 x 5 + x 1 x 4 + x 1 x 5 x 6 + x 1 x 5 + x 1 x 6 + x 1 + x 2 x 3 x 4 x 6 + x 2 x 3 x 5 + x 2 x 3 x 6 + x 2 x 3 + x 2 x 4 x 5 x 6 + x 2 x 4 x 5 + x 2 x 4 x 6 + x 2 x 4 + x 2 x 5 x 6 + x 2 x 5 + x 2 x 6 + x 3 x 4 x 5 + x 3 x 4 x 6 + x 4 x 5 x 6 + x 5 x 6 . Alternative designs B We explore two possible modifications to the design of Nostalgia: the inclusion of an Initialization Vector (IV) and the addition of a whitening step. B.1 Initialization step Since hybrid homomorphic encryption does not require the use of IVs, no initialization process is specified for Nostalgia. However, if needed, an initialization step should be designed in such a way that the whole internal state depends non linearly on the whole initialization value and the key. Let us suppose that the key is then reduced to κ bits and the IV is α-bit long with α and κ in {128, N }. The state is initialized with the key in position 0 to κ − 1. The initialization step is then composed of iterations of the cipher where the retroaction bit b i at iteration i is not computed classically but proceeds as follows: 1. For 1 ≤ i ≤ α, b i = o i−1 ⊕ IV i ; 2. For α + 1 ≤ i ≤ 2N + α, b i = o i−1 ; where o i is the output of the cipher at the i th iteration. This initialization ensures that all internal bits of the state depends both of the key and the IV at the beginning of the stream generation. The high algebraic immunity of the WWQ function and the distribution of the taps ensures that no cycles can be found and that the output of this initialization phase behave like random. B.2 Whitening step The linear nature of the LFSR can be altered by XORing a random vector with the input of f at each clock cycle. This process, known as whitening, randomizes the input of f . It requires either n bits of randomness per output bit or the use of a pseudorandom generator for efficiency. The addition of a whitening step in a stream cipher has already been implemented in FiLIP [MCJS19], as it incurs a negligible cost in the context of HHE. The main drawback of this alternative design is that it complicates the analysis of the filtered LFSR, whose simplicity is a key advantage.