Towards Stream Ciphers for Efficient FHE with Low-Noise Ciphertexts

Abstract

Symmetric ciphers purposed for Fully Homomorphic Encryption (FHE) have recently been proposed for two main reasons. First, minimizing the implementation (time and memory) overheads that are inherent to current FHE schemes. Second, improving the homomorphic capacity, i.e. the amount of operations that one can perform on homomorphic ciphertexts before bootstrapping, which amounts to limit their level of noise. Existing solutions for this purpose suggest a gap between block ciphers and stream ciphers. The first ones typically allow a constant but small homomorphic capacity, due to the iteration of rounds eventually leading to complex Boolean functions (hence large noise). The second ones typically allow a larger homomorphic capacity for the first ciphertext blocks, that decreases with the number of ciphertext blocks (due to the increasing Boolean complexity of the stream ciphers’ output). In this paper, we aim to combine the best of these two worlds, and propose a new stream cipher construction that allows constant and small(er) noise. Its main idea is to apply a Boolean (filter) function to a public bit permutation of a constant key register, so that the Boolean complexity of the stream cipher outputs is constant. We also propose an instantiation of the filter function designed to exploit recent (3rd-generation) FHE schemes, where the error growth is quasi-additive when adequately multiplying ciphertexts with the same amount of noise. In order to stimulate further investigation, we then specify a few instances of this stream cipher, for which we provide a preliminary security analysis. We finally highlight the good properties of our stream cipher regarding the other goal of minimizing the time and memory complexity of calculus delegation (for 2nd-generation FHE schemes). We conclude the paper with open problems related to the large design space opened by these new constructions.

These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.

1 Introduction

Purpose: Calculus Delegation. Recent years have witnessed massive changes in communication technologies, that can be summarized as a combination of two trends: (1) the proliferation of small embedded devices with limited storage and computing facilities, and (2) the apparition of cloud services with extensive storage and computing facilities. In this context, the outsourcing of data and the delegation of data processing gains more and more interest. Yet, such new opportunities also raise new security and privacy concerns. Namely, users typically want to prevent the server from learning about their data and processing. For this purpose, Gentry’s breakthrough Fully Homomorphic Encryption (FHE) scheme [30] brought a perfect conceptual answer. Namely, it allows applying processing on ciphertexts in a homomorphic way so that after decryption, plaintexts have undergone the same operations as ciphertexts, but the server has not learned anything about these plaintexts.¹

Application Scenario. Cloud services can be exploited in a plethora of applications, some of them surveyed in [51]. In general, they are always characterized by the aforementioned asymmetry between the communication parties. For illustration, we start by providing a simple example where data outsourcing and data processing delegation require security and privacy. Let us say that a patient, Alice, has undergone a surgery and is coming back home. The hospital gave her a monitoring watch (with limited storage) to measure her metabolic data on a regular basis. And this metabolic data should be made available to the doctor Bob, to follow the evolution of the post-surgery treatment. Quite naturally, Bob has numerous patients and no advanced computing facilities to store and process the data of all his patients. So this is a typical case where sending the data to a cloud service would be very convenient. That is, Alice’s data could be sent to and stored on the cloud, and associated to both her and the doctor Bob. And the cloud would provide Bob with processed information in a number of situations such as when the metabolic data of Alice is abnormal (in which case an error message should be sent to Bob), or during an appointment between Alice and Bob, so that Bob can follow the evolution of Alice’s data (possibly after some processing). Bob could in fact even be interested by accessing some other patient’s data, in order to compare the effect of different medications. And of course, we would like to avoid the cloud to know anything about the (private) data it is manipulating.

Typical Framework. More technically, the previous exemplary application can be integrated in a quite general cloud service application framework, that can be seen as a combination of 5 steps, combining a symmetric encryption scheme and an asymmetric homomorphic encryption scheme, as summarised in Fig. 1 and described next:

• 1. Initialization. Alice runs the key generation algorithms $H.\mathsf {KeyGen}$ and $S.\mathsf {KeyGen}$ of the two schemes, and sends her homomorphic public key $\textsf {pk}^H$ and the homomorphic ciphertext of her symmetric key $\mathbf {C}^H( \textsf {sk}^S_i)$.

• 2. Storage. Alice encrypts her data $m_i$ with the symmetric encryption scheme, and sends $\mathbf {C}^S(m_i)$ to Claude.

• 3. Evaluation. Claude homomorphically evaluates, with the $H.\mathsf {Eval}$ algorithm, the decryption $\mathbf {C}^H(m_i)$ of the symmetric scheme on Alice’s data $\mathbf {C}^S(m_i)$.

• 4. Computation. Claude homomorphically executes the treatment f on Alice’s encrypted data.

• 5. Result. Claude sends a compressed encrypted result of the data treatment $\mathbf {c}^H(f(m_i))$, obtained with the $H.\mathsf {Comp}$ algorithm, and Alice decrypts it.

Note that if we assume the existence of a trusted third party active only during the initialization step, Alice can avoid Step 1, which needs a significant computational and memory storage effort. Note also that this framework is versatile: computation can be done in parallel (in a batch setting) or can be turned into a secret key FHE.

Fig. 1.

Homomorphic Encryption - Symmetric Encryption framework. H and S respectively refer to homomorphic and symmetric encryption schemes, for algorithms (e.g. $H.\mathsf {KeyGen}$) or scheme components (e.g. $\textsf {sk}^S$).

FHE Bottlenecks. The main limitation for the deployment of cloud services based on such FHE frameworks relates to its important overheads, that can be related to two main concerns: computational and memory costs (especially on the client side) and limited homomorphic capacity (i.e. noise increase). More precisely:

• The computational and memory costs for the client depend overwhelmingly on the homomorphic encryption and decryption algorithms during the steps 1 and 5. The memory cost is mostly influenced by the homomorphic ciphertexts and public key sizes. Solving these two problems consists in building size-efficient FHE schemes with low computational cost [35, 38]. On the server side, this computational cost further depends on the symmetric encryption scheme and function to evaluate.

• The homomorphic capacity relates to the fact that FHE constructions are built on noise-based cryptography, where the unbounded amount of homomorphic operations is guaranteed by an expensive bootstrapping technique. The homomorphic capacity corresponds to the amount of operations doable before the noise grows too much forcing to use bootstrapping. Therefore, and in order to reduce the time and computational cost of the framework, it is important to manage the error growth during the homomorphic operations (i.e. steps 3 and 4). Furthermore, since the 4th step is the most important one from the application point-of-view (since this is where the useful operations are performed by the cloud), there is strong incentive to minimize the cost of the homomorphic decryption in the 3rd step.

Previous Works. In order to mitigate these bottlenecks, several works tried to reduce more and more the homomorphic cost of evaluating a symmetric decryption algorithm. First attempts in this direction, which were also used as benchmark for FHE implementations, used the AES for this purpose [15, 31]. Various alternative schemes were also considered, all with error and sizes depending on the multiplicative depth of the symmetric encryption scheme, such as BGV [9] and FV [26]. Additional optimizations exploited batching and bitslicing, leading to the best results of performing 120 AES decryptions in 4 minutes [31].

Since the multiplicative depth of the AES decryption evaluation was a restrictive bound in these works, other symmetric encryption schemes were then considered. The most representative attempts in this direction are the family of block ciphers LowMC [1] and the stream cipher Kreyvium [11]. These constructions led to reduced and more suitable multiplicative depths. Yet, and intuitively, these attempts were still limited by complementary drawbacks. First for LowMC, the remaining multiplicative depth remains large enough to significantly reduce the homomorphic capacity (i.e. increase the noise). Such a drawback seems to be inherent in block cipher structures where the iteration of rounds eventually leads to Boolean functions with large algebraic degree, which inevitably imply a constant per block but high noise after homomorphic evaluation. For example, ciphers dedicated to efficient masking against side-channel attacks [33, 34, 52], which share the goal of minimizing the multiplicative complexity, suffer from similar issues and it seems hard to break the barrier of one multiplication per round (and therefore of 12 to 16 multiplications for 128-bit ciphers). Second for Kreyvium, the error actually grows with the number of evaluated ciphertexts, which implies that at some point, the output ciphertexts are too noisy, and cannot be decrypted (which requires either to bootstrap or to re-initialize the stream cipher).

Our Contribution. In view of this state-of-the-art, a natural direction would be to try combining the best of these two previous works. That is, to design a cipher inheriting from the constant noise property offered by block ciphers, and the lower noise levels of stream ciphers (due to the lower algebraic degree of their outputs), leading to the following contributions.

First, we introduce a new stream cipher construction, next denoted as a filter permutator (by analogy with filter generators). Its main design principle is to filter a constant key register with a variable (public) bit permutation. More precisely, at each cycle, the key register is (bit) permuted with a pseudorandomly generated permutation, and we apply a non-linear filtering function to the output of this permuted key register. The main advantage of this construction is to always apply the non-linear filtering directly on the key bits, which allows maintaining the noise level of our outputs constant. Conceptually, this type of construction seems appealing for any FHE scheme.

Second, and going deeper in the specification of a concrete scheme, we discuss the optimization of the components in a filter permutator, with a focus on the filtering function (which determines the output noise after homomorphic evaluation). For this purpose, we first notice that existing FHE schemes can be split in (roughly) two main categories. On one hand the so-called 2nd-generation FHE (such as [9, 15]) where the metric for the noise growth is essentially the multiplicative depth of the circuit to homomorphically evaluate. On the other hand, the so-called 3rd-generation FHE (such as [2, 32]) where the error growth is asymmetric, and in particular quasi-additive when considering a multiplicative chain. From these observations, we formalize a comb structure which can be represented as a (possibly long) multiplicative chain, in order to take the best advantage of 3rd-generation FHE schemes. We then design a filtering function based on this comb structure (combined with other technical ingredients in order to prevent various classes of possible attacks against stream ciphers) and specify a family of filter permutators (called FLIP).

Third, and in order to stimulate further investigations, we instantiate a few version of FLIP designs, for 80-bit and 128-bit security. We then provide a preliminary evaluation of their security against some of the prevailing cryptanalysis from the open literature – such as (fast) algebraic attacks, (fast) correlation attacks, BKW-like attacks [6], guess and determine attacks, etc. – based on state-of-the-art tools. We also analyze the noise brought by their filtering functions in the context of 3rd-generation FHE. In this respect, our main result is that we can limit the noise after the homomorphic evaluation of a decryption to a level of the same order of magnitude as for a single homomorphic multiplication - hence essentially making the impact of the symmetric encryption scheme as small as possible.

We finally observe that our FLIP designs have a very reduced multiplicative depth, which makes them suitable for 2nd-generation FHE schemes as well, and provide preliminary results of prototype implementations using HElib that confirm their good behavior compared to state-of-the-art block and stream ciphers designed for efficient FHE.

Overall, filter permutators in general and FLIP instances in particular open a large design space of new symmetric constructions to investigate. Hence, we conclude the paper with a list of open problems regarding these algorithms, their best cryptanalysis, the Boolean functions used in their filter and their efficient implementation in concrete applications.

2 Background

2.1 Boolean Functions

In this section, we recall the cryptographic properties of Boolean functions that we will need in the rest of the paper (mostly taken from [12]).

Definition 1

(Boolean Function). A Boolean function f with n variables is a function from $\mathbb {F}_2^n$ to $\mathbb {F}_2$. The set of all Boolean functions in n variables is denoted by $\mathcal {B}_n$.

Definition 2

(Walsh Transform). Let $f\in \mathcal {B}_n$ a Boolean function. Its Walsh Transform $\mathsf {W}_{\mathsf {f}}$ at $a \in \mathbb {F}_2^n$ is defined as:

$$\begin{aligned} \mathsf {W}_{\mathsf {f}}(a) = \sum _{x \in \mathbb {F}_2^n} (-1)^{f(x) + \langle a,x \rangle }{,} \end{aligned}$$

where $\langle a,x \rangle$ denotes the inner product in $\mathbb {F}_2^n$.

Definition 3

(Balancedness). A Boolean function $f\in \mathcal {B}_n$ is said to be balanced if its outputs are uniformly distributed over $\{ 0 , 1 \}$.

Definition 4

(Non-linearity). The non-linearity $\mathsf {NL}$ of a Boolean function $f\in \mathcal {B}_n$, where n is a positive integer, is the minimum Hamming distance between f and all the affine functions g:

$$\begin{aligned} \mathsf {NL}(f) = \min _g \{ d_H(f,g) \}{,} \end{aligned}$$

with $d_H(f,g) = \#\{ x \in \mathbb {F}_2^n \;|\; f(x) \ne g(x) \}$ the Hamming distance between f and g. The non-linearity of a Boolean function can also be defined by its Walsh Transform:

$$\begin{aligned} \mathsf {NL}(f) = 2^{n-1} - \frac{1}{2} \;\max _{a\in \mathbb {F}_2^n} |\mathsf {W}_{\mathsf {f}}(a)|{.} \end{aligned}$$

Definition 5

(Resiliency). A Boolean function $f\in \mathcal {B}_n$ is said m-resilient if any of its restrictions obtained by fixing at most m of its coordinates is balanced. We will denote by $\mathsf {res}(f)$ the resiliency m of f and set $\mathsf {res}(f)=-1$ if f is unbalanced.

Definition 6

(Algebraic Immunity). The algebraic immunity of a Boolean function $f\in \mathcal {B}_n$, denoted as $\mathsf {AI}(f)$, is defined as:

$$\begin{aligned} \mathsf {AI}(f) = \min _{g \ne 0}\{ \mathsf {deg}(g) \; | \; fg = 0 \; or \; (f\oplus 1)g = 0 \}{,} \end{aligned}$$

where $\mathsf {deg}(g)$ is the degree of g. The function g is called an annihilator of f (or ($f\oplus 1$)).

Definition 7

(Fast Algebraic Immunity). The fast algebraic immunity of a Boolean function $f\in \mathcal {B}_n$, denoted as $\mathsf {FAI}(f)$, is defined as:

$$\begin{aligned} \mathsf {FAI}(f) = \min \{ 2\mathsf {AI}(f), \min _{1 \le \mathsf {deg}(g) < \mathsf {AI}(f) } ( \max [ \mathsf {deg}(g) + \mathsf {deg}(fg), 3\mathsf {deg}(g) ] )\}. \end{aligned}$$

Summarizing, the good balancedness, non-linearity and resiliency properties have to be ensured to widthstand correlation attacks [56] and fast correlation attacks [48]. The high algebraic immunity and fast algebraic immunity have to be ensured to widthstand algebraic attacks [13].

2.2 (Ring) Learning with Errors

In this section, we recall useful notations and definitions needed about the decisional LWE problem and its ring variation. For an integer modulus q, we denote by $\mathbb {Z}_q$ the quotient ring of integers modulo q. We denote vectors with bold letters $\mathbf {e}$ and matrices with bold capital letters $\mathbf {A}$. The notation $s \leftarrow _{\$}S$ (resp. $s \leftarrow _{\$}\chi$) denotes that s is picked uniformly at random from a finite set S (resp. from a distribution $\chi$).

The decisional Learning With Error problem (dLWE) was introduced by Regev [53].

Definition 8

(dLWE). For an integer $q = q(n) \ge 2$, an adversary $\mathcal {A}$ and an error distribution $\chi =\chi (n)$ over $\mathbb {Z}_q$, we define the following advantage function:

$$\mathsf {Adv}^{\mathsf {dLWE}_{n,m,q,\chi }}_{\mathcal {A}} := | \Pr [\mathcal {A}( \mathbf {A}, \mathbf {z}_0 ) = 1 ] - \Pr [\mathcal {A}( \mathbf {A}, \mathbf {z}_1 ) = 1] | {,}$$

where

$$\begin{aligned} \mathbf {A}\leftarrow _{\$}\mathbb {Z}_q^{n \times m}, \mathbf {s}\leftarrow _{\$}\mathbb {Z}_q^n, \mathbf {e}\leftarrow _{\$}\chi ^m, \mathbf {z}_0 := \mathbf {s}^{\!\scriptscriptstyle {\top }}\mathbf {A}+ \mathbf {e}^{\!\scriptscriptstyle {\top }}\quad and \quad \mathbf {z}_1 \leftarrow _{\$}\mathbb {Z}_q^m {.} \end{aligned}$$

The $\mathsf {dLWE}_{n,m,q,\chi }$ assumption asserts that for all $\mathsf {PPT}$ adversaries $\mathcal {A}$, the advantage $\mathsf {Adv}^{\mathsf {dLWE}_{n,m,q,\chi }}_{\mathcal {A}}$ is a negligible function in n.

The ring variant was introduced by Lyubashevsky, Peikert and Regev in [46].

Definition 9

(d $R$ -LWE). For a polynomial ring $R =\mathbb {Z}[X]/f(X)$ with f of degree n, an integer $q \ge 2$, an adversary $\mathcal {A}$ and an error distribution $\chi$ over $R _q= R /q R$, $R ^\vee$ being $R$ dual fractional ideal, we define the following advantage function:

$$\begin{aligned} \mathsf {Adv}^{\mathsf {d} R \mathsf {LWE}_{ R ,q,\chi }}_{\mathcal {A}} := | \Pr [\mathcal {A}( a,z_0 ) = 1 ] - \Pr [\mathcal {A}( a, z_1 ) = 1] | {,} \end{aligned}$$

where

$$a \leftarrow _{\$} R _q,\; s \leftarrow _{\$} R _q^{\vee }, \; e \leftarrow _{\$}\chi , \; z_0 := a \cdot s + e \quad and \quad z_1 \leftarrow _{\$} R {.} $$

With f(X) a cyclotomic polynomial, the $\mathsf {d} R \mathsf {LWE}_{ R ,q,\chi }$ assumption asserts that for all $\mathsf {PPT}$ adversaries $\mathcal {A}$, the advantage $\mathsf {Adv}^{\mathsf {d} R \mathsf {LWE}_{ R ,q,\chi }}_{\mathcal {A}}$ is a negligible function in n.

For our constructions, we need to take the distribution $\chi$ as a subgaussian random variable which we define hereafter. More details about the subgaussian distribution and the lemmas’ proof can be found in [2, 58].

Definition 10

(Subgaussian Random Variables). Let X be a random variable. We say X is subgaussian with parameter $\sigma$ if there exists $\sigma$ such that:

$$\begin{aligned} \forall t \in \mathbb {R},\mathbb {E}[e^{tX}]\le e^{\sigma ^2 t^2/2} {,} \end{aligned}$$

where $\mathbb {E}[e^{tX}]$ is the moment generating function of X.

Lemma 1

(Subgaussian Random Variables Properties). Let X, $X'$ be independent subgaussian random variables of parameter $\sigma$ and $\sigma '$ respectively. Assuming $\mathbb {E}(X)=\mathbb {E}(X')=0$ we have the following properties:

• Tails: $\forall t \ge 0$ we have $Pr[|X|\ge t] \le 2 e^{-\pi t^2 / \sigma ^2}$.

• Homogeneity: $\forall c \in \mathbb {R}$, cX is subgaussian with parameter $|c|\sigma$.

• Pythagorean additivity: $X+X'$ is subgaussian with parameter $\sqrt{\sigma ^2+\sigma '^2}$.

We extend the notion of subgaussianity to vectors and polynomials. Since the coefficients of a polynomial are seen as a vector, we call subgaussian vector of parameter $\sigma$ a vector where each coefficient follows an independent subgaussian distribution with parameter $\sigma$.

Lemma 2

(Subgaussian Vector Norm, Adapted from [2], Lemma 2.1). Let $\mathbf {x}\in \mathbb {R}^n$ be a random vector where each coordinate follows an independent subgaussian distribution of parameter $\sigma$. Then for some universal constant $C>0$ we have $Pr\left[ ||\mathbf {x}||_2>C\sigma \sqrt{n}\right] \le 2^{-\varOmega (n)}$ and therefore $||\mathbf {x}||_2=\mathcal {O}(\sigma \sqrt{n})$.

2.3 Fully Homomorphic Encryption

In this section we recall the definition of (Fully) Homomorphic Encryption and present the Homomorphic Encryption schemes we will use, both based on GSW [32].

Definition 11

(Homomorphic Encryption Scheme). Let $\mathcal {M}$ be the plaintext space, $\mathcal {C}$ the ciphertext space and $\lambda$ the security parameter. A homomorphic encryption scheme consists of four algorithms:

• $H.\mathsf {KeyGen}(1^\lambda )$. Output $\textsf {pk}^H$ and $\textsf {sk}^H$ the public and secret keys of the scheme.

• $H.\mathsf {Enc}(m, \textsf {pk}^H)$. From the plaintext $m\in \mathcal {M}$ and the public key, output a ciphertext $c\in \mathcal {C}$.

• $H.\mathsf {Dec}(c, \textsf {sk}^H)$. From the ciphertext $c\in \mathcal {C}$ and the secret key, output $m'\in \mathcal {M}$.

• $H.\mathsf {Eval}(f,c_1,\cdots ,c_k, \textsf {pk}^H)$. With $c_i=H.\mathsf {Enc}(m_i, \textsf {pk}^H)$ for $1\le i \le k$, output a ciphertext $c_f \in \mathcal {C}$ such that $H.\mathsf {Dec}(c_f)=f(m_1,\cdots ,m_k)$.

A homomorphic encryption scheme is called a Fully Homomorphic Encryption (FHE) scheme when f can be any function and $|\mathcal {C}|$ is finite. A simpler primitive to consider is the SomeWhat Homomorphic Encryption (SWHE) scheme, where f is restricted to be any univariate polynomial of finite degree.

Since the breakthrough work of Gentry [30], the only known way to obtain FHE consists in adding a bootstrapping technique to a SWHE. As bootstrapping computational cost is still expensive in comparison to the other FHE algorithms, in the following part of the article we will only consider SWHE for our applications.

GSW Homomorphic Encryption Scheme. In 2013, Gentry, Sahai and Waters [32] introduced a Homomorphic Encryption scheme based on LWE using a new technique stemming from the approximate eigenvector problem. This new technique led to a new family of FHE, called 3rd-generation FHE, consisting in Homomorphic Encryption schemes such that the multiplicative error growth is quasi-additive. Hereafter, we present two schemes belonging to this generation, the first one with security based on $\mathsf {dLWE}$ and the second one based on $\mathsf {d} R \mathsf {LWE}$. We first set some useful notations considering the different schemes.

For a matrix $\mathbf {E}$ we refer to the i-th row as $\mathbf {e}_i^{\!\scriptscriptstyle {\top }}$ and to the j-th column as $\mathbf {e}_j$. The $\log q$ notation refers to the logarithm in base 2 of q. The notation $[a]_q$ is for $a\mod q$ and $\lfloor [a]_q \rceil _2 \in \{0,1\}$ is a function in $a \in \mathbb {Z}_q$ giving 1 if $\lfloor \frac{q}{4} \rfloor \le a \le \lfloor \frac{3q}{4} \rfloor \mod q$ and 0 otherwise. We denote by [n] the set of integers $\{1,\cdots , n\}$. We finally use |x| and $||x||_2$ for the standard norms 1 and 2 on vectors $x\in \mathbb {R}^n$.

Batched GSW. This scheme is a batched version of GSW presented in [36], enabling to pack independently r plaintexts in one ciphertext. From the security parameter $\lambda$ and the considered applications, we can derive the parameters $n,q,r,\chi$ of the scheme described below.

$H.\mathsf {KeyGen}(n,q,r,\chi )$. On inputs the lattice dimension n, the modulus q, the number of bits by ciphertext r and the error distribution $\chi$ do:

• Set $\ell =\lceil \log q \rceil$, $m=\mathcal {O}(n\ell )$, $N=(r+n) \ell$, $\mathcal {M}=\{0,1\}^r$ and $\mathcal {C}=\mathbb {Z}_q^{(r+n)\times N}$.

• Pick $\mathbf {A}\leftarrow _{\$}\mathbb {Z}_q^{n\times m}$, $\mathbf {S}' \leftarrow _{\$}\chi ^{r\times n}$ and $\mathbf {E}\leftarrow _{\$}\chi ^{r\times m}$.

• Set $\mathbf {S}=[\mathbf {I}|-\mathbf {S}'] \in \mathbb {Z}_q^{r\times (r+n)}$ and $\mathbf {B}=\begin{bmatrix} \mathbf {S}' \mathbf {A}+ \mathbf {E}\\ \hline \mathbf {A}\end{bmatrix}_q \in \mathbb {Z}_q^{(r+n)\times m}$.

• For all $\mathbf {m}\in \{0,1\}^r$:

  • Pick $\mathbf {R}_\mathbf {m}\leftarrow _{\$}\{0,1\}^{m\times N}$.

  • Set $\mathbf {P}_\mathbf {m}= \begin{bmatrix}\mathbf {B}\mathbf {R}_\mathbf {m}+\begin{pmatrix}m_1 \cdot \mathbf {s}_1^{\!\scriptscriptstyle {\top }}\\ \hline \vdots \\ \hline m_r \cdot \mathbf {s}_r^{\!\scriptscriptstyle {\top }}\\ \hline \mathbf {0} \end{pmatrix} \mathbf {G}\end{bmatrix}_q \in \mathbb {Z}_q^{(r+n)\times N}$.

  with $\mathbf {s}_i^{\!\scriptscriptstyle {\top }}$ the i-th row of $\mathbf {S}$ and $\mathbf {G}=(2^0,\cdots ,2^{\ell -1})^{\!\scriptscriptstyle {\top }}\otimes \mathbf {I}\in \mathbb {Z}_q^{(r+n)\times N}$.

• Output $\textsf {pk}^H:= (\{\mathbf {P}_\mathbf {m}\} ,\mathbf {B}) \text { and } \textsf {sk}^H:= \mathbf {S}$.

$H.\mathsf {Enc}( \textsf {pk}^H,\mathbf {m})$. On input $\textsf {pk}^H$, and $\mathbf {m}\in \{0,1\}^r$, do:

• Pick $\mathbf {R}\leftarrow _{\$}\{0,1\}^{m\times N}$, and output $\mathbf {C}= [\mathbf {B}\mathbf {R}+\mathbf {P}_\mathbf {m}]_q \in \mathbb {Z}_q^{(r+n)\times N}.$

$H.\mathsf {Dec}(\mathbf {C}, \textsf {sk}^H)$. On input the secret key $\textsf {sk}^H$, and a ciphertext $\mathbf {C}$, do:

• For all $i \in [r]$ : $m_i' = \lfloor [ \langle \mathbf {s}_i^{\!\scriptscriptstyle {\top }},\mathbf {c}_{i\ell } \rangle ]_q \rceil _2$ where $\mathbf {c}_{il}$ is the column $i\ell$ of $\mathbf {C}$.

• Output $m_1',\cdots ,m_r'\in \{0,1\}^r$.

Note that $\mathbf {S}\mathbf {C}= \mathbf {S}\mathbf {B}\mathbf {R}+ \mathbf {S}\mathbf {P}_\mathbf {m}= \mathbf {E}\mathbf {R}+\mathbf {E}\mathbf {R}_\mathbf {m}+ \begin{pmatrix}m_1 \cdot \mathbf {s}_1^{\!\scriptscriptstyle {\top }}\\ \hline \vdots \\ \hline m_r \cdot \mathbf {s}_r^{\!\scriptscriptstyle {\top }}\end{pmatrix} \mathbf {G}= \mathbf {E}'+ \begin{pmatrix}m_1 \cdot \mathbf {s}_1^{\!\scriptscriptstyle {\top }}\\ \hline \vdots \\ \hline m_r \cdot \mathbf {s}_r^{\!\scriptscriptstyle {\top }}\end{pmatrix} \mathbf {G}$.

The $H.\mathsf {Eval}$ algorithm finally consists in iterating, following a circuit f, the homomorphic operations $H.\mathsf {Add}$ and $H.\mathsf {Mul}$:

• $H.\mathsf {Add}(\mathbf {C}_1,\mathbf {C}_2): \mathbf {C}_+ = \mathbf {C}_1 + \mathbf {C}_2$.

• $H.\mathsf {Mul}(\mathbf {C}_1,\mathbf {C}_2): \mathbf {C}_\times = \mathbf {C}_1 \times \mathbf {G}^{-1} \mathbf {C}_2$ with $\mathbf {G}^{-1}$ a function such that $\forall \mathbf {C}\in \mathbb {Z}_q^{(r+n) \times N}, \mathbf {G}\mathbf {G}^{-1}(\mathbf {C})=\mathbf {C}$ and the values of $\mathbf {G}^{-1}(\mathbf {C})$ follow a subgaussian distribution with parameter $\mathcal {O}(1)$ (see [49] for the existence and proof of $\mathbf {G}^{-1}$).

The correctness and security of this scheme are proven in the extended version of this paper.

Remark 1

For practical use, we only need to store $r+1$ matrices $\mathbf {P}_m$, namely the $r+1$ ones with $\mathbf {m}$ of hamming weight equal to 0 or 1 are sufficient to generate correct encryption of all $\mathbf {m}\in \{0,1\}^r$ with at most r additions of the corresponding $\mathbf {P}_m$ matrices.

Ring-GSW. This scheme is a ring version of GSW presented in [38], transposing the approximate eigenvector problem into the ring setting. From $\lambda$ the security parameter and the considered applications, we can derive the parameters n, q and $\mathcal {M}$ of the scheme described below.

$H.\mathsf {KeyGen}(n,q,\chi ,\mathcal {M})$. On inputs the lattice dimension n, which is set to a power of 2, the modulus q, the error distribution $\chi$ and the plaintext space $\mathcal {M}$ do:

• Set $R =\mathbb {Z}[X]/(X^n+1)$, $R _q = R /q R$, $\ell =\lceil \log q \rceil$, $N=2 \ell$ and $\mathcal {C}= R _q^{2\times N}.$

• Set $R _{0,1}=\{P\in R _q, p_i \in \{0,1\},0 \le i < n\}.$

• Pick $a \leftarrow _{\$} R _q$, $s' \leftarrow _{\$}\chi$ and $e \leftarrow _{\$}\chi .$

• Set $\mathbf {s}=[1|-s']^{\!\scriptscriptstyle {\top }}\in R _q^{1\times 2}$ and $\mathbf {b}= \begin{pmatrix} s' a + e \\ \hline a\end{pmatrix}\in R _q^{2\times 1}.$

• Output $\textsf {pk}^H:= \mathbf {b}\text { and } \textsf {sk}^H:= \mathbf {s}.$

$H.\mathsf {Enc}( \textsf {pk}^H,m)$. On input $\textsf {pk}^H$, and $m \in \mathcal {M}$, do:

• Pick $\mathbf {E}\leftarrow _{\$}\chi ^{2\times N}.$

• Pick $\mathbf {r}\leftarrow _{\$} R _{0,1}^N$, and output $\mathbf {C}= [\mathbf {b}\mathbf {r}^{\!\scriptscriptstyle {\top }}+m\mathbf {G}+\mathbf {E}]_q \in R _q^{2\times N}.$

$H.\mathsf {Dec}(\mathbf {C}, \textsf {sk}^H)$. On input the secret key $\textsf {sk}^H$, and a ciphertext $\mathbf {C}$, do:

• Compute $m' = \lfloor [ <\mathbf {s},\mathbf {c}_{l}> ]_q \rceil _2$.

• Output $m' \in R _q$.

The $H.\mathsf {Eval}$ algorithm finally consists in iterating $H.\mathsf {Add}$ and $H.\mathsf {Mul}$:

• $H.\mathsf {Add}(\mathbf {C}_1,\mathbf {C}_2): \mathbf {C}_+ = \mathbf {C}_1 + \mathbf {C}_2$.

• $H.\mathsf {Mul}(\mathbf {C}_1,\mathbf {C}_2): \mathbf {C}_\times = \mathbf {C}_1 \times \mathbf {G}^{-1} \mathbf {C}_2$.

The correctness and security of this scheme are proven in the extended version of this paper.

Remark 2

The plaintext space $\mathcal {M}$ has a major influence on the considered application in terms of quantity of information contained in a single ciphertext and error growth. For our application we choose $\mathcal {M}$ as the set of polynomials with all coefficients of degree greater than 0 being zero, and the constant coefficient being bounded.

3 New Stream Cipher Constructions

In this section, we introduce our new stream cipher construction. We first describe the general filter permutator structure. Next we list a number of Boolean building blocks together with their necessary cryptographic properties. Third, we specify a family of filter permutators (denoted as $\textsf {FLIP}$) and analyze its security based on state-of-the art cryptanalysis and design tools. Finally, we propose a couple of parameters to fully instantiate a few examples of $\textsf {FLIP}$ designs.

3.1 Filter Permutators

The general structure of filter permutators is depicted in Fig. 2. It is composed of three parts: a register where the key is stored, a (bit) permutation generator parametrised by a Pseudo Random Number Generator (PRNG) [7, 37] (which is initialized with a public IV), and a filtering function which generates a keystream. The filter permutator can be compared to a filter generator, in which the LFSR is replaced by a permuted key register. In other words, the register is no longer updated by means of the LFSR, but with pseudorandom bit permutations. More precisely, at each cycle (i.e. each time the filtering function outputs a bit), a pseudo-random permutation is applied to the register and the permuted key register is filtered. Eventually, the encryption (resp. decryption) with a filter permutator simply consists in XORing the bits output by the filtering function with those of the plaintext (resp. ciphertext).

Fig. 2.

Filter permutator construction.

3.2 Boolean Building Blocks for the Filter Permutator

We will first exploit direct sums of Boolean functions defined as follows:

Definition 12

(Direct Sum). Let $f_1(x_0,\cdots ,x_{n_1-1})$ and $f_2(x_{n_1},\cdots ,$ $x_{n_1+n_2-1})$ be two Boolean functions in respectively $n_1$ and $n_2$ variables. The direct sum of $f_1$ and $f_2$ is defined as $f=f_1 \oplus f_2$, which is a Boolean function in $n_1+n_2$ variables such that:

$$\begin{aligned} f(x_0,\cdots ,x_{n_1+n_2-1}) = f_1(x_0,\cdots ,x_{n_1-1}) \oplus f_2(x_{n_1},\cdots ,x_{n_1+n_2-1}). \end{aligned}$$

They inherit from the following set of properties, proven in the extended version of this paper.

Lemma 3

(Direct Sum Properties). Let f be the direct sum of $f_1$ and $f_2$ with $n_1$ and $n_2$ variables respectively. Then f has the following cryptographic properties:

• 1. Non Linearity: $\mathsf {NL}(f)=2^{n_2} \mathsf {NL}(f_1)+ 2 ^{n_1} \mathsf {NL}(f_2) - 2 \mathsf {NL}(f_1) \mathsf {NL}(f_2)$.

• 2. Resiliency: $\mathsf {res}(f) = \mathsf {res}(f_1)+\mathsf {res}(f_2)+1$.

• 3. Algebraic Immunity: $\mathsf {AI}(f_1)+\mathsf {AI}(f_2) \ge \mathsf {AI}(f) \ge \max (\mathsf {AI}(f_1),\mathsf {AI}(f_2))$.

• 4. Fast Algebraic Immunity: $\mathsf {FAI}(f) \ge \max (\mathsf {FAI}(f_1),\mathsf {FAI}(f_2))$.

Our direct sums will then be based on three parts: a linear function, a quadratic function and triangular functions, defined as follows.

Definition 13

(Linear Functions). Let $n>0$ be a positive integer, the $L_n$ linear function is a n-variable Boolean function defined as:

$$\begin{aligned} L_n(x_0,\cdots ,x_{n-1}) =\sum _{i=0}^{n-1}x_i. \end{aligned}$$

Definition 14

(Quadratic Functions). Let $n>0$ be a positive integer, the $Q_n$ linear function is a 2n-variable Boolean function defined as:

$$\begin{aligned} Q_n(x_0,\cdots ,x_{2n-1}) =\sum _{i=0}^{n-1}x_{2i}x_{2i+1}. \end{aligned}$$

Definition 15

(Triangular Functions). Let $k>0$ be a positive integer. The k-th triangular function $T_k$ is a $\frac{k(k+1)}{2}$-variable Boolean function defined as:

$$\begin{aligned} T_k(x_0,\cdots ,x_{\frac{k(k+1)}{2} - 1})= \varSigma _{i=1}^{k} \varPi _{j=0}^{i-1} x_{ j + \varSigma _{\ell =0}^{i-1} \ell } . \end{aligned}$$

For example, the 4th triangular function $T_4$ is:

$$\begin{aligned} T_4=x_0 \oplus x_1x_2 \oplus x_3x_4x_5 \oplus x_6x_7x_8x_9. \end{aligned}$$

These three types of functions allow us to guarantee the following properties.

Lemma 4

(Linear Functions Properties). Let $L_n$ be a linear function in n variables, then $L_n$ has the following cryptographic properties:

• 1. Non Linearity: $\mathsf {NL}(L_n)=0$.

• 2. Resiliency: $\mathsf {res}(L_n) =n-1$.

• 3. Algebraic Immunity: $\mathsf {AI}(L_n)=1$.

• 4. Fast Algebraic Immunity: $\mathsf {FAI}(L_n)=2$.

Lemma 5

(Quadratic Functions Properties). Let $Q_n$ be a linear function in 2n variables, then $Q_n$ has the following cryptographic properties:

• 1. Non Linearity: $\mathsf {NL}(Q_n)=2^{2n-1}-2^{n-1}$.

• 2. Resiliency: $\mathsf {res}(Q_n) =-1$.

• 3. Algebraic Immunity: $\mathsf {AI}(Q_1)=1$ and $\forall n>1 ,\mathsf {AI}(Q_n)=2$.

• 4. Fast Algebraic Immunity: $\mathsf {FAI}(Q_1)=2$ and $\forall n>1,~\mathsf {FAI}(Q_n)=4$.

Lemma 6

(Triangular Functions Properties). Let k a positive integer and let $T_k$ the k-th triangular function. Then the following properties hold:

• 1. Non Linearity follows the recursive formula defined as:

                 (i) $\mathsf {NL}(T_1=0)$,

                 (ii) $\mathsf {NL}(T_{k+1})=(2^{k+1} -2) \mathsf {NL}(T_k) + 2^{k(k+1)/2}$.

• 2. Resiliency: $\mathsf {res}(T_k) =0$.

• 3. Algebraic Immunity: $\mathsf {AI}(T_k) = k$.

• 4. Fast Algebraic Immunity: $\mathsf {FAI}(T_k) =k+1$.

The proof of Lemma 6 can be found in the extended version of this paper.

3.3 The FLIP Family of Stream Ciphers

Based on the previous definitions, we specify the FLIP family of stream ciphers as a filter permutator using a forward secure PRNG [5] based on the AES-128 (e.g. as instantiated in the context of leakage-resilient cryptography [57]), the Knuth shuffle (see below) as bit permutation generator and such that the filter F is the N-variable Boolean function defined by the direct sum of three Boolean functions $f_1$, $f_2$ and $f_3$ of respectively $n_1$, $n_2$ and $n_3$ variables, such that:

• $f_1(x_0, \cdots , x_{n_1-1}) = L_{n_1}$ ,

• $f_2(x_{n_1}, \cdots , x_{n_1+n_2-1}) = Q_{n_2/2}$,

• $f_3(x_{n_1+n_2}, \cdots , x_{n_1+n_2+n_3-1})$ is the direct sum of nb triangular functions $T_k$, i.e. such that each $T_{k}$ acts on different and independent variables, that we denote as ${}^{nb}\varDelta ^{k}$.

That is, we have $F: \mathbb {F}_2^{n_1+n_2+n_3} \rightarrow \mathbb {F}_2$ the Boolean function such that:

$$\begin{aligned} F(x_0, \cdots , x_{n_1+n_2+n_3-1}) = L_{n_1} \oplus Q_{n_2/2} \oplus \bigoplus _{i=1}^{nb} T_{k}. \end{aligned}$$

In the following section, we provide a preliminary security analysis of the FLIP filter permutators against a couple of standard attacks against stream ciphers, based on state-of-the-art tools. For this purpose, we will assume that no additional weaknesses arise from its PRNG and bit permutation generator. In this respect, we note that our forward secure PRNG does not allow malleability, so it should be hard to obtain a collision in the chosen IV model better than with birthday probability. This should prevent collisions on the generated permutations. Besides, the Knuth shuffle [41] (or Fisher-Yates shuffle) is an algorithm allowing to generate a random permutation on a finite set. This algorithm has the interesting property of giving the same probability to all permutations if used with a random number generator. As a result, we expect that any deviation between a bit permutation based on a Knuth shuffle fed with the PRNG will be hard to exploit by an adversary. Our motivation for this assumption is twofold. First, it allows us to focus on whether the filter permutator construction is theoretically sound. Second, if such a choice was leading to an exploitable weakness, it remains possible to build a pseudorandom permutation based on standard cryptographic constructions [45].

Remark 3

Since the permutation generation part of FLIP has only birthday security (with respect to the size of the PRNG), it implies that it is only secure up to $2^{64}$ PRNG outputs when implemented with the AES-128. Generating more keystream using larger block ciphers should be feasible. However, in view of the novelty of the FLIP instances, our claims are only made for this limited (birthday) data complexity so far, which should not be limiting for the intended FHE applications. We leave the investigation of their security against attacks using larger data complexities as a scope for further research. Besides, we note that using a PRNG based on a tweakable block cipher [44] (where a part of the larger IV would be used as tweak) could be an interesting track to reduce the impact of a collision on the PRNG output in the known IV model, which we also leave as an open research direction.

3.4 Security Analysis

Since the filter permutator shares similarities with a filter generator, it is natural to start our investigations with the typical attacks considered against such types of stream ciphers. For this purpose, we next study the applicability of algebraic attacks and correlation attacks, together with more specialized cryptanalyses that have been considered against stream ciphers. Note that the attacks considered in the rest of this section frequently require to solve systems of equations and to implement a Gaussian reduction. Our complexity estimations will consider Strassen’s algorithm for this purpose and assume $\omega = \log 7$ to be the exponent in a Gaussian reduction. Admittedly, approaches based on Gröbner bases [27] or taking advantage of the sparsity of the matrices [59] could lead to even faster algorithms. We ignore them for simplicity in these preliminary investigations. Note also that we only claim security in the single-key setting.

Algebraic Attacks were first introduced by Courtois and Meier in [18] and applied to the stream cipher Toyocrypt. Their main idea is to build an over-defined system of equations with the initial state of the LFSR as unknown, and to solve this system with Gaussian elimination. More precisely, by using a nonzero function g such that both g and $h=gF$ have low algebraic degree, an adversary is able to obtain T equations with monomials of degree at most AI(f). It is easily shown that g can be taken equal to the annihilator of F or of $F \oplus 1$, i.e. such that $gF=0$ or $g(F\oplus 1) = 0$. After a linearisation step, the adversary obtains a system of T equations in $D=\sum _{i=0}^{\mathsf {AI}(F)}\left( {\begin{array}{c}N\\ i\end{array}}\right)$ variables. Therefore, the time complexity of the algebraic attack is $\mathcal {O}(D^{\omega })$, that is, $\mathcal {O}(N^{\omega AI(f)})$.

Fast Algebraic Attacks are a variation of the previous algebraic attacks introduced by Courtois at Crypto 2003 [17]. Considering the relation $gF=h$, their goal is to find and use functions g of low algebraic degree e, possibly smaller than AI(f), and h of low but possibly larger degree d, and to lower the degree of the resulting equations by an off-line elimination of the monomials of degrees larger than e (several equations being needed to obtain each one with degree at most e). Following [4], this attack can be decomposed into four steps:

• 1. The search of the polynomials g and h generating a system of $D+E$ equations in $D+E$ unknowns, where $D=\sum _{i=0}^{d}\left( {\begin{array}{c}N\\ i\end{array}}\right)$ and $E=\sum _{i=0}^{e}\left( {\begin{array}{c}N\\ i\end{array}}\right)$. This step has a time complexity in $\mathcal {O}(\sum _{i=0}^{d}\left( {\begin{array}{c}n\\ i\end{array}}\right) +\sum _{i=0}^{e}\left( {\begin{array}{c}n\\ i\end{array}}\right) )^\omega$.

• 2. The search of linear relations which allow the suppression of the monomials of degree more than e. This step has a time complexity in $\mathcal {O}(D\log ^2(D))$.

• 3. The elimination of monomials of degree larger than e using the Berlekamp-Massey algorithm. This step has a time complexity in $\mathcal {O}(ED\log (D))$.

• 4. The resolution of the system. This step has a time complexity in $\mathcal {O}(E^{\omega })$.

Given the $\mathsf {FAI}$ of F, the time complexity of this attack is in $\mathcal {O}(N^{\mathsf {FAI}})$, or more precisely $O(D\log ^2 D + E^2D+E^{\omega })$ (ignoring Step 1 which is trivial for our choice of F).

Correlation Attacks. In their basic versions, correlation attacks try to distinguish the output sequence of a stream cipher from a random one, by exploiting the bias $\delta$ of the filtering function. We can easily rule out such attacks by considering a (much) simplified version of filter permutator where the bit permutations $P_i$’s would be made on two independent permutations $P_i^1$ and $P_i^{2,3}$ (respectively acting on the $n_1+1$ bits of the linear part and the $n_2+n_3-1$ bits of the non-linear part of F). Suppose for simplicity that $P_i^1$ is kept constant t times, then the output distribution of F has a bias $\delta$ and it can be distinguished for the right choice of the $n_1+1=\mathsf {res}+1$ bits of the linear part. In this case, a correlation attack would have a data complexity of $\mathcal {O}(\delta ^{-2})$ and a time complexity of $\mathcal {O}(2^{\mathsf {res}(F)+1}\delta ^{-2})$, with $\delta = \frac{1}{2} - \left( \frac{\mathsf {NL}(F)}{2^N}\right)$. For simplicity, we will consider this conservative estimation in our following selection of security parameters. Yet, we note that since the permutation $P_i$ of a filter permutator is acting on all the N bits of the filter F, the probability that the linear part of F is kept invariant by the permutations t times is in fact considerably smaller than what is predicted by the resilience.

BKW-like Attack. The BKW algorithm was introduced in [6] as a solution to solve the LPN problem using smart combinations of well chosen vectors and their associated bias. Intuitively, our stream cipher construction simplified as just explained (with two independent permutations $P_i^1$ and $P_i^{2,3}$ rather than a single one $P_i$) also shares similarities with this problem. Indeed, we could see the linear part as the parity of an LPN problem and the non-linear one (with a small bias) as a (large) noise. Adapting the BKW algorithm to our setting amounts to XOR some linear parts of F in order to obtain vectors of low Hamming weight, and then to consider a distinguishing attack with the associated bias. Denoting h the target Hamming weight, x the log of the number of XORs and $\delta$ the bias, the resulting attack (which can be viewed as an extension of the previous correlation attack) has data complexity $\mathcal {O}(2^h \delta ^{-2(x+1)})$ (more details are given in the extended version of this paper).

Higher-Order Correlation Attacks were introduced by Courtois [16] and exploit the so-called XL algorithm. They look for good correlations between F and an approximation g of degree $d>1$, in order to solve a linearised system based on the values of this approximation. The value $\varepsilon$ is defined such that g is equal to F with probability greater than $1-\varepsilon$. Such attacks have a (conservative) time complexity estimate:

$$\begin{aligned} \mathcal {O}\left( \left( {\begin{array}{c}N\\ D\end{array}}\right) ^{\omega } (1-\varepsilon )^{-m}\right) , \mathrm {~where~} D \ge d \mathrm {~and~} m \ge \frac{\left( {\begin{array}{c}N\\ D\end{array}}\right) }{\left( {\begin{array}{c}N\\ D-d\end{array}}\right) }. \end{aligned}$$

Guess and Determine Attacks. Note that this section has been motivated by a private communication from Sébastien Duval, Virginie Lallemand and Yann Rotella, of which the details will be available in an upcoming ePrint report [25]. Guess and determine attacks are generic attacks which consist in guessing $\ell$ bits of the key in order to cancel some monomials. In our context, it allows an adversary to focus on a filtering function restricted to a subset of variables. This weaker function can then be cryptanalyzed, e.g. analyzed with the four aforementioned attacks, i.e. the algebraic attack, the fast algebraic attack, the correlation/BKW-like attacks and the higher-order correlation attack. The complexity of a guess and determine attack against a function F of N variables is $\min _{\ell }\{{2^\ell C(F[\ell ])}\}$ where $F[\ell ]$ is a function of $N[\ell ]$ variables obtained by fixing $\ell$ variables of F, C(F) is the complexity of the best of the four attacks considered on the filtering function F and the minimum is taken over all $\ell$’s. The case $\ell =0$ corresponds to attacking the scheme without guess and determine. We next bound the minimal complexity over these four attacks considering the weakest functions obtained by guessing. To do so, we introduce some notations and criteria allowing us to specify the cryptographic properties of Boolean functions obtained by guessing $\ell$ variables of Boolean functions being direct sums of monomials. As the impact of guessing is most relevant for fast algebraic attacks and CA/BKW-like attacks, we defer the other part of the analysis and extra lemmas to the extended version of this paper.

Definition 16

(Direct Sum Vector). For a boolean function F of N variables obtained as a direct sum of monomials we associate its direct sum vector : $\mathbf {m}_F$ of length $k=\deg (F)$: $[m_1,m_2,\cdots ,m_k]$ such that $m_i$ is the number of monomials of degree i of F and $N=\sum _{i=1}^k i m_i$. We define two quantities related to this vector:

• $\mathbf {m}_F^*$ is the number of nonzero values of $\mathbf {m}_F$.

• $\delta _{\mathbf {m}_F}= \frac{1}{2}-\frac{\mathsf {NL}(F)}{2^{N}}$.

These notations will be useful to quantify the impact of guessing some bits on the cryptographic properties of a Boolean function obtained by direct sums. $\mathbf {m}_F$, $\mathbf {m}_F^*$ and $\delta _{\mathbf {m}_F}$ are easily computable from the description of F, the latter can be computed recursively using Lemma 3.

Lemma 7

(Guessing and Direct Sum Vector). For all guessing of $0 \le \ell \le N$ variables of a Boolean function F in N variables obtained by direct sums associated with $\mathbf {m}_F$, we obtain a function $F[\ell ]$ in $N[\ell ]$ variables associated with $\mathbf {m}_{F[\ell ]}$ such that:

• 1. $\sum _{i=1}^{\deg (F[\ell ])} m_i[\ell ] \ge (\sum _{i=1}^{\deg (F)} m_i )-\ell$.

• 2. $\mathbf {m}_{F[\ell ]}^*\ge \mathbf {m}_F^*-\lfloor \frac{\ell }{\min _{1\le i \le \deg (F)} m_i} \rfloor$.

• 3. $\delta _{\mathbf {m}_{F[\ell ]}}\le \delta _{\mathbf {m}_F}2^\ell$.

Hereafter we describe the bounds we have used in order to assess the security of our instances.

Lemma 8

(Guess And Determine & Fast Algebraic Attacks). Let F be a boolean function in N variables and $C_{GDFAA}(F)$ be the minimum complexity of the Guess And Determine with Fast Algebraic Attacks on F, then:

$$\begin{aligned} C_{GDFAA}(F) \ge \min _{0\le \ell \le N} \scriptstyle {\left[ 2^\ell \left( {\begin{array}{c}\min {N[\ell ]}\\ \mathbf {m}_{F[\ell ]}^*\end{array}}\right) \log ^2 \left( {\begin{array}{c}\min {N[\ell ]}\\ \mathbf {m}_{F[\ell ]}^*\end{array}}\right) +\left( \min {N[\ell ]} \right) ^2 \left( {\begin{array}{c}\min {N[\ell ]}\\ \mathbf {m}_{F[\ell ]}^*\end{array}}\right) +\left( \min {N[\ell ]} \right) ^\omega \right] }, \end{aligned}$$

where $\mathbf {m}_{F[\ell ]}^*= \mathbf {m}_F^*-\lfloor \frac{\ell }{\min _{ i\in [\deg (F)]} m_i} \rfloor$.

Lemma 9

(Guess and Determine & CA/BKW-like Attacks). Let F be a boolean function in N variables and $C_{GDCA/BKW}(F)$ be the minimum complexity of the Guess And Determine with Correlation/BKW Attacks on F, then:

$$\begin{aligned} C_{GDCA/BKW}(F) \ge \min _{0\le \ell \le N} \{ 2^{-\ell } \delta _{\mathbf {m}_F}^{-2} \}. \end{aligned}$$

Other Attacks. Besides the previous attacks that will be taken into account quantitatively when selecting our concrete instances of FLIP designs, we also investigated the following other cryptanalyses. First, fast correlation attacks were introduced by Meier and Staffelbach at Eurocrypt 1988 [48]. A recent survey can be found in [47]. The attack is divided into two phases. The first one aims at looking for relations between the output bits $a_i$ of the LFSR to generate a system of parity-check equations. The second one uses a fast decoding algorithm (e.g. the belief propagation algorithm) in order to decode the words of the code $z_i = F(a_i)$ satisfying the previous relations, where the channel has an error probability $p=\frac{\mathsf {NL}(F)}{2^N}$. The working principles of this attack are quite similar to the ones of the previously mentioned correlation attacks and BKW-like attacks. So we assume that the previous (conservative) complexity estimates rule out this variation as well. Besides, note that intuitively, the belief propagation algorithm is best suited to the decoding of low-density parities, which is what our construction (and the LPN problem) typically avoids.

Second, weak keys (i.e. keys of low or high hamming weights) can produce a keystream sufficiently biased to determine this hamming weight, and then to recover the key among the small amount of possible ones. The complexity of such attacks can be computed from the resiliency of F. However, since our N parameter will typically be significantly larger than the bit-security of our filter permutator instances, we suggest to restrict the key space to keys of Hamming weight to rule out this concern. For this purpose, master keys can simply be generated by applying a first (secret) random permutation to any stream with Hamming weight .

Third, augmented function attacks are attacks focusing on multiple outputs of the function rather than one. The goal is to find coefficients $j_1, \cdots , j_r$ such that a relation between the key and the outputs $s_{i+j_1},\cdots ,s_{ i+j_r}$ can be exploited. This relation can be a correlation (as explained in [3]) or simply algebraic [28]. In both cases, a prerequisite is that the relation holds on a sufficient number of i. As each bit output by FLIP depends on a different permutation, we believe that there is no exploitable relation between different outputs.

Eventually, cube attacks were introduced by Dinur and Shamir at Eurocrypt 2009 [20] as a variant of algebraic attacks taking advantage of the public parameters of a cryptographic protocol (plaintext in block ciphers, IV in stream cipher) in order to generate a system of equations of low degree. However in filter permutator constructions, the only such public parameter is the seed of the PRNG allowing to generate the pseudo-random bit permutations $P_i$. Since controlling this seed hardly allows any control of the F function’s inputs, such attacks do not seem applicable. A similar observation holds for conditional differential cryptanalysis [39] and for integral/zero-sum distinguishers [8, 40].

3.5 Cautionary Note and Design Tweaks

As already mentioned, all the previous analyzes are based on standard cryptanalysis and design tools. In particular, the security of our FLIP designs is based on properties of Boolean functions that are generally computed assuming a uniform input distribution. Yet, for filter permutators this condition is not strictly respected since the Hamming weight of the key register is fixed (we decided to set it to N / 2 in order to avoid weak keys, but even without this condition, it would be fixed to an unknown value). This means the input distribution of our linear, quadratic and triangle functions is not uniform. We verified experimentally that the output of FLIP is sufficiently balanced despite this non-uniformity. More precisely, we could not detect biases larger than $2^{\frac{q}{2}}$ when generating $2^q$ bits of keystream (based on small-scale experiments with $q=32$). But we did not study the impact of this non-uniformity for other attacks, which we leave as an important research scope, both from the cryptanalysis and the Boolean functions points-of-view.

Note that in case the filter permutator of Sect. 3.1 turns out to have weaknesses specifically due to the imbalanced F function’s inputs, there are tweaks that could be used to mitigate their impact. The simplest one is to apply a public whitening to the input bits of the non-linear parts of F (using additional public PRNG outputs), which has no impact on the homomorphic capacity. The adversary could then bias the F function’s inputs based on his knowledge of the whitening bits, but to a lower extent than with our fixed Hamming weight keys. Alternatively, one could add a (more or less complex) linear layer before the non-linear part of F, which would then make the filter permutator conceptually more similar to filter generators, and (at least for certain layers) only imply moderate cost from the FHE point-of-view.

3.6 80- & 128-bit Security Instances

We selected a few instances aiming at 80- and 128-bit security based on the previous bounds, leading to the attack complexities listed in Table 1, where $\textsf {FLIP}(n_1,n_2,{}^{nb}\varDelta ^{k})$ denotes the instantiation of $\textsf {FLIP}$ with linear part of $n_1$ bits, quadratic part of $n_2$ bits and nb triangular functions of degree k. These instances are naturally contrasted. On the one hand, the bounds taken are conservative with respect to the attacks considered: if these attacks were the best ones, more aggressive instances could be proposed (e.g. in order to reduce the key size). On the other hand, filter permutators are based on non-standard design principles, and our security analysis is only preliminary, which naturally suggests the need of security margins. Overall, we believe the proposed instances are a reasonable trade-off between efficiency and security based on our current understanding of filter permutators, and therefore are a good target for further investigations.

Table 1. Attack complexities in function of $n_1$, $n_2$ and ${}^{nb}\varDelta ^{k}$. AA stands for algebraic attacks, FAA stands for fast algebraic attacks, CA/BKW stands for correlation or BKW-like attacks, HOC stands for higher-order correlation attacks and $\ell$ stands for the number of bits guessed leading to the best complexity for guess and determine attacks. For the CA/BKW column, we reported the minimum complexity between the correlation and BKW-like attack. Eventually, $\lambda$ stands for the security parameter of F and is simply taken as the minimum between AA, FAA,CA/BKW and HOC.

3.7 Indirect Sums

Before analyzing the FHE properties of filter permutators, we finally suggest FLIP designs based on indirect sums as another interesting topic for evaluation, since they lead to quite different challenges. Namely, the main motivation to use direct sums in the previous sections was the possibility to assess their cryptographic properties based on existing tools. By contrast, filter permutator designs based on indirect sums seem harder to analyze (both for designers and cryptanalysts). This is mainly because in this case, not only the inputs of the Boolean functions vary, but also the Boolean functions themselves. For illustration, we can specify “multi-FLIP” designs, next denoted as b-FLIP designs, such that we compute b instances of $\textsf {FLIP}$ in parallel, each with the same filtering function but with different permutations, and then to XOR the b computed bits in order to produce a keystream bit. We conjecture that such b-FLIP designs could lead to secure stream ciphers with smaller states, and suggest 10-$\textsf {FLIP}(10,20,{}^{1}\varDelta ^{20})$ and 15-$\textsf {FLIP}(15,30,{}^{1}\varDelta ^{30})$ as exemplary instances for 80- and 128-bit security.

4 Application to FHE

4.1 80- & 128-bit Security Parameters

For the security parameters choices, we follow the analysis of Lindner and Peikert [43] for the hardness of LWE and RLWE, considering distinguishing and decoding attacks using BKZ [14, 55]. We assume that the distribution $\chi$ in the considered LWE instances is the discrete Gaussian distribution with mean 0 and standard deviation $\sigma$. First we compute the best root Hermite factor $\delta$ of a basis (see  [29]) computable with complexity $2^\lambda$ from the conservative lower bound of [43]:

$$\begin{aligned} \log (\delta )=1.8/ (110+\lambda ). \end{aligned}$$

(1)

The distinguishing attack described in [43, 50, 54] is successful with advantage $\varepsilon$ by finding vectors of length $\alpha \frac{q}{\sigma }$ with $\alpha =\sqrt{\ln (1/\varepsilon )/\pi }$. The length of the shortest vector that can be computed is $2^{2\sqrt{n\log q \log \delta } }$, leading to the inequality:

$$\begin{aligned} \alpha \frac{q}{\sigma }< 2^{2\sqrt{n\log q \log \delta } }. \end{aligned}$$

(2)

Given $\sigma \ge 2\sqrt{n}$ from Regev’s reduction [53], we can choose parameters for n and q matching Eq. (2) for the considered security parameter $\lambda$. The parameters we select for our application are summarized in Table 2.

Table 2. (R)LWE parameters used in our applications.

4.2 Noise Analysis

Considering our framework of Fig. 1, Claude has at its disposal the homomorphic encryption of the symmetric key $\mathbf {C}^H( \textsf {sk}^S_i)$, the homomorphic public key $\textsf {pk}^H$ and the symmetric encrypted messages $\mathbf {C}^S(m_i)$. He has to perform the homomorphic evaluation of the symmetric decryption circuit, i.e. to perform homomorphic operations on the ciphertexts $\mathbf {C}^H( \textsf {sk}^S_i)$ in order to get $\mathbf {C}^H(m_i)$, the homomorphic encryption of $m_i$. In this section, we study the error growth in these ciphertexts after the application of the homomorphic operations. As we are considering SWHE, we need to control the magnitude of the error and keep it below a critical level to ensure the correctness of a final ciphertext. This noise management is crucial for the applications, it is directly linked with the quantity of computation that the server can do for the client. We now study the error growth stemming from the homomorphic evaluation of $\textsf {FLIP}$. In this case, all the ciphertexts used by the server in the computation step will have a same starting error. The knowledge of this starting error (defined by some parameter) and its growth for additions and multiplications (in a chosen order) is enough to determine the amount of computation that can be performed correctly by the server.

In the remainder of this section we proceed in three steps. First we recall the error growth implied by the $H.\mathsf {Add}$ and $H.\mathsf {Mul}$ operations: for GSW-like HE it has already been done in [2, 10, 24, 32, 36]. As our homomorphic encryption schemes are slightly differently written to fit our applications (batched version to perform in parallel the same computations, generic notations for various frameworks), we give these error growth with our notations for completeness and consistency of the paper. Then we analyse the error for a sub-case of homomorphic product, namely $H.\mathsf {Comb}$, which gives a practical tool to study the error growth in $\textsf {FLIP}$. As the asymmetric property of GSW multiplication and plaintext norm have been pointed out relatively to the error growth, we consider important to focus on both when analysing this error metric. Considering $H.\mathsf {Comb}$ types of operations is therefore suited to be consistent with this metric and is very important for practical purpose (in term of real life applications). Finally we analyse the error in a ciphertext output by $\textsf {FLIP}$ and study some optimizations to reduce the noise growth further.

Error Growth in H. ${{\mathbf {\mathsf{{Add}}}}}$ and H. ${{\mathbf {\mathsf{{Mul}}}}}$ . We first need to evaluate the error growth of the basic homomorphic operations, the addition and the multiplication of ciphertexts. We use the analysis of [2] based on subgaussian distributions to study the error growth in these homomorphic operations. From a coefficient or a vector following a subgaussian distribution of parameter $\sigma$, we can bound its norm with overwhelming probability and then study the evolution of this parameter while performing the homomorphic operations. Hence we can bound the final error to ensure correctness.

For simplicity we use two notations arising from the error growth depending on the arithmetic of the underlying ring of the two schemes, $\gamma$ the expansion factor (see [9]) and $Norm(m_j)$ such that:

• Batched GSW: $\gamma =1$ and $Norm(m_j)=|m_j|$ (arithmetic in $\mathbb {Z}$).

• Ring GSW: $\gamma =n$ and $Norm(m_j)=||m_j||_2$ (arithmetic in $R$).

Lemma 10

( $H.\mathsf {Add}$ Error Growth). Suppose $\mathbf {C}_i$ for $1 \le i \le k$ are ciphertexts of a GSW based Homomorphic Encryption scheme with error components $\mathbf {e}_i$ of coefficients following a distribution of parameter $\sigma _i$. Let $\mathbf {C}_f=H.\mathsf {Add}(\mathbf {C}_i$, for $1 \le i \le k)$ and $\mathbf {e}_f$ the related error with subgaussian parameter $\sigma '$ such that:

$$\begin{aligned} \sigma '=\sqrt{\sum _{i=1}^{k}\sigma _i^2} \quad or \quad \sigma '=\sigma \sqrt{k} \; \, if\, \; \sigma _i=\sigma , \forall i \in [k]. \end{aligned}$$

Lemma 11

( $H.\mathsf {Mul}$ Error Growth). Suppose $\mathbf {C}_i$ for $1 \le i \le k$ are ciphertexts of a GSW based Homomorphic Encryption scheme with error components $\mathbf {e}_i$, of coefficients following a subgaussian distribution of parameter $\sigma _i$, and plaintext $m_i$. $\mathbf {C}_f$ is the result of a multiplicative homomorphic chain such that:

$$\begin{aligned} \mathbf {C}_f=H.\mathsf {Mul}(\mathbf {C}_1,H.\mathsf {Mul}( \mathbf {C}_2,H.\mathsf {Mul}(\cdots ,H.\mathsf {Mul}(\mathbf {C}_k,\mathbf {G})))), \end{aligned}$$

and $\mathbf {e}_f$ the corresponding error with subgaussian parameter $\sigma '$ such that:

$$\begin{aligned} \sigma '=\mathcal {O}\left( \sqrt{N\gamma } \sqrt{ \sigma _1^2+ \sum _{i=2}^{k}\left( \sigma _i \varPi _{j=1}^{i-1} Norm(m_j)\right) ^2 } \right) . \end{aligned}$$

Lemmas  10 and  11 are proven in the extended version of this paper.

Error Growth in H. ${{\mathbf {\mathsf{{Comb}}}}}$ . For the sake of clarity, we formalize hereafter the comb homomorphic product $H.\mathsf {Comb}$ and the quantity $\sigma _{comb}$ which stands for the subgaussian parameter. We study the error growth of $H.\mathsf {Comb}$ as we will use it as a tool for the error growth analysis of $\textsf {FLIP}$.

Definition 17

(Homomorphic Comb $H.\mathsf {Comb}$ ). Let $\mathbf {C}_1,\cdots ,\mathbf {C}_k$ be k ciphertexts of a GSW based Homomorphic Encryption scheme with error coefficients from independent distributions with same subgaussian parameter $\sigma$. We define $H.\mathsf {Comb}(y,\sigma ,c,k) = H.\mathsf {Mul}(\mathbf {C}_1,\cdots ,\mathbf {C}_k,\mathbf {G})$ where:

• $y=\sqrt{N\gamma }$ is a constant depending on the ring,

• $c=\max _{1\le i\le k}(Norm(m_i))$ is a constant which depends on the plaintexts,

and $\mathbf {C}_{comb}=H.\mathsf {Comb}(y,\sigma ,c,k)$ as error components following a subgaussian distribution of parameter $\mathcal {O}(\sigma _{comb})$.

Lemma 12

( $\sigma _{comb}$ Quantity). Let $\mathbf {C}_1,\cdots ,\mathbf {C}_k$ be k ciphertexts of a GSW based Homomorphic Encryption scheme with same error parameter $\sigma$ and $\mathbf {C}_{comb}=H.\mathsf {Comb}(y,\sigma ,c,k)$. Then we have:

$$\begin{aligned} \sigma _{comb}(y,\sigma ,c,k)=y\sigma c_k, \quad where\, c_k = \sqrt{\sum _{i=0}^{k-1} c^{2i}}. \end{aligned}$$

Proof

Thanks to Lemma 11 we obtain:

$\sigma _{comb}=\sqrt{N\gamma } \sqrt{ \sigma ^2+ \sum _{i=2}^{k}(\sigma \varPi _{j=1}^{i-1} Norm(m_j))^2 },$

$\sigma _{comb}=y \sqrt{ \sigma ^2+ \sum _{i=2}^{k}(\sigma c^{i-1})^2 },$

$\sigma _{comb}=y\sigma \sqrt{ \sum _{i=1}^{k}( c^{i-1})^2 },$

$\sigma _{comb}=y\sigma c_k.$ $\square$

The compatibility of this comb structure with the asymmetric multiplicative error growth property of GSW enables us to easily quantify the error in our construction, with a better accuracy than computing the multiplicative depth. In order to minimize the quantity $\sigma _{comb}$, we choose the plaintext space such that $c=1$ for freshly generated ciphertexts. The resulting $\sigma _{comb}(y,\sigma ,1,k)$ quantity is therefore $y\sigma \sqrt{k}$, growing less than linearly in the number of ciphertexts. Fixing the constant c to be 1 is usual with FHE. As we mostly consider Boolean circuits, it is usual to use plaintexts in $\{-1,0,1\}$ to encrypt bits, leading to $c=1$ and therefore $c_k=\sqrt{k}$.

Error Growth in ${{\mathbf {\mathsf{{FLIP}}}}}$. In the previous paragraphs, we have evaluated the error growth in the basic homomorphic operations $H.\mathsf {Add}$, $H.\mathsf {Mul}$ and $H.\mathsf {Comb}$. We will use them as building blocks in order to evaluate the error growth in the homomorphic evaluation of $\textsf {FLIP}$. Coming back to the framework of Fig. 1, the error in the ciphertexts $\mathbf {C}^H(m_i)$ is of major importance as it will determine the possible number of homomorphic computations f that Claude is able to perform.

The main feature of the filter permutator model, considering FHE settings, is that it allows to handle ciphertexts having the same error level, whatever the number of output bits. Consequently all ciphertexts obtained by $\textsf {FLIP}$ evaluation will have the same constant and small amount of noise and will be considered as fresh start for more computation.

Evaluating homomorphically the $\textsf {FLIP}$ decryption (resp. encryption) algorithm consists in applying three steps of homomorphic operations on the ciphertexts $\mathbf {C}^H( \textsf {sk}^S_i)$ in our application framework, each one encoding one bit of the key register. For each ciphertext bit, these steps are: a (bit) permutation, the application of the filtering function F and a XOR with the ciphertext (resp. plaintext). The (bit) permutation consists only in a public rearrangement of the key ciphertexts, leading to a noise-free operation. The last XOR is done with a freshly encrypted bit. Hence the error growth depends mostly on the homomorphic evaluation of F.

As $H.\mathsf {Dec}$ outputs quantities modulus 2, we can evaluate the XORs of F by $H.\mathsf {Add}$ and the ANDs by $H.\mathsf {Mul}$. We then determine the subgaussian parameter of the error of a ciphertext from the homomorphic evaluation of F. For a given encrypted key, this parameter will be the same for every homomorphic evaluation of $\textsf {FLIP}$ and is computed from $\sigma _{comb}$.

Lemma 13

(Error Growth Evaluating $\varvec{F}$ ). Let F be the $\textsf {FLIP}$ filtering function in N variables defined in Sect. 3.3. Assume that $\mathbf {C}_i$ for $0\le i\le N-1$ are ciphertexts of a GSW HE scheme with same subgaussian parameter $\sigma$ and $c=1$. We define $\mathbf {C}_F=H.\mathsf {Eval}(F,\mathbf {C}_i)$ the output of the homomorphic evaluation of the ciphertexts $\mathbf {C}_i$’s along the circuit F. Then the error parameter $\sigma '$ is:

$$\begin{aligned} \sigma '=\mathcal {O}\left( \sigma \sqrt{ n_1 + y^2 (n_2+n_3)}\right) \approx \mathcal {O}\left( \sigma y \sqrt{N}\right) . \end{aligned}$$

Proof

We first evaluate the noise brought by F for each of its components $L_{n_1}$, $Q_{n_2}$, ${}^{nb}\varDelta ^{k}$, defining the respective ciphertexts $\mathbf {C}_{L_{n_1}},\mathbf {C}_{Q_{n_2}},\mathbf {C}_{T_{k}}$(the last one standing for one triangle only) and the subgaussian parameter of the respective error distributions (of the components of the error vectors) $\sigma _{L_{n_1}},\sigma _{Q_{n_2}},\sigma _{T_{k}}$:

• $L_{n_1}$: $\mathbf {C}_{L_{n_1}}=H.\mathsf {Eval}(L_{n_1},\mathbf {C}_0,\cdots ,\mathbf {C}_{n_1-1})= H.\mathsf {Add}(\mathbf {C}_0,\cdots ,\mathbf {C}_{n_1-1})$ then $\sigma _{L_{n_1}}=\sigma \sqrt{n_1}$.

• $Q_{n_2}$: $\mathbf {C}_{Q_{n_2}}= H.\mathsf {Add}(H.\mathsf {Mul}(\mathbf {C}_{n_1+2j},\mathbf {C}_{n_1+2j+1},\mathbf {G}) )$ for $0\le j \le n_2$. $H.\mathsf {Mul}(\mathbf {C}_{n_1+2j},\mathbf {C}_{n_1+2j+1},\mathbf {G})=H.\mathsf {Comb}(y,\sigma ,1,2)$ has subgaussian parameter $\mathcal {O}(\sigma _{comb}(y,\sigma ,1,2))=\mathcal {O}(y\sigma \sqrt{2})$ for $0\le j \le n_2$. Then $\sigma _{Q_{n_2}}=\mathcal {O}(y\sigma \sqrt{2}\sqrt{\frac{n_2}{2}}) = \mathcal {O}(y\sigma \sqrt{n_2})$.

• $T_{k}$: $\mathbf {C}_{T_{k}}=H.\mathsf {Add}(H.\mathsf {Mul}( \mathbf {C}_{n_1+n_2+j+(i-1)(i-2)/2} ; 1 \le j \le i );1\le i \le k)$. $\mathbf {C}_{T_{k}}=H.\mathsf {Add}(H.\mathsf {Comb}(y,\sigma ,1,i), 1\le i \le k)$. then $\sigma _{T_{k}}=\mathcal {O}(\sqrt{\sum _{i=1}^{k}(y\sigma \sqrt{i})^2})=\mathcal {O}( y\sigma \sqrt{\frac{k(k+1)}{2}})$. As ${}^{nb}\varDelta ^{k}$ is obtained by adding nb independent triangles, we get: $\mathbf {C}_{{}^{nb}\varDelta ^{k}}=H.\mathsf {Add}(\mathbf {C}_{T_{k},i}, 1\le i \le nb)$, and $\sigma _{{}^{nb}\varDelta ^{k}}=\mathcal {O}(y\sigma \sqrt{nb}\sqrt{\frac{k(k+1)}{2}})=\mathcal {O}(y\sigma \sqrt{n_3})$.

By Pythagorean additivity the subgaussian parameter of $\mathbf {C}_F$ is finally:

$$\begin{aligned} {} \sigma '=\mathcal {O}(\sqrt{(\sigma \sqrt{n_1})^2+( y\sigma \sqrt{n_2} )^2+( y\sigma \sqrt{n_3} )^2})=\mathcal {O}(\sigma \sqrt{ n_1 + y^2 (n_2+n_3)}).\quad \square \end{aligned}$$

Optimizations. The particular error growth in GSW Homomorphic Encryption enables to use more optimizations to reduce the error norm and perform more operations without increasing the parameter’s size. The error growth in $H.\mathsf {Comb}$ depends on the quantity $c_k$ derived from bounds on norms of the plaintexts; these quantities can be reduced using negative numbers. A typical example is in the LWE-based scheme to use $m\in \{-1,0,1\}$ rather than $\{0,1\}$; the $c_k$ quantity is the same and in average the sums in $\mathbb {Z}$ are smaller. Then the norm $|\sum m_i |$ is smaller which is important when multiplying. Conserving this norm as low as possible gives better bounds and $c_k$ coefficients, leading to smaller noise when performing distinct levels of operations. An equivalent way of minimizing the error growth is to still use $\mathcal {M}=\{0,1\}$ but with $H.\mathsf {Add}(\mathbf {C}_1,\mathbf {C}_2)=\mathbf {C}_1 \pm \mathbf {C}_2$. This homomorphic addition is still correct because:

$$\begin{aligned} \mathbf {S}-\mathbf {C}_2= -\mathbf {E}_2' - \begin{pmatrix}m_{2,1} \cdot \mathbf {s}_1^{\!\scriptscriptstyle {\top }}\\ \hline \vdots \\ \hline m_{2,r} \cdot \mathbf {s}_r^{\!\scriptscriptstyle {\top }}\end{pmatrix} \mathbf {G}= \mathbf {E}_2'' + \begin{pmatrix}-m_{2,1} \cdot \mathbf {s}_1^{\!\scriptscriptstyle {\top }}\\ \hline \vdots \\ \hline -m_{2,r} \cdot \mathbf {s}_r^{\!\scriptscriptstyle {\top }}\end{pmatrix}, \end{aligned}$$

where the coefficients in $\mathbf {E}_2''$ rows follow distribution of same subgaussian parameter as the one in $\mathbf {E}_2'$ by homogeneity and $-m=m \mod 2$.

4.3 Concrete Results

Contrary to other works published in the context of symmetric encryption schemes for efficient FHE [1, 11, 31], our primary focus is not on the performances (see SHIELD [38] for efficient implementation of Ring-GSW) but rather on the error growth. As pointed out in [11], in most of these previous works, after the decryption process the noise inside the ciphertexts was too high to perform any other operation on them, whereas it is the main motivation for a practical use of FHE.

In this section, we consequently provide experimental results about this error growth in the ciphertexts after different operations evaluated on the Ring GSW scheme. As the link between subgaussian parameter, ciphertext error and homomorphic computation is not direct, we make some choices for representing these results focusing on giving intuition on how the error behaves.

The choice of the Ring GSW setting rather than Batched GSW is for convenience. It allows to deal with smaller matrices and faster evaluations, providing the same confirmation on the heuristic error growth. We give the parameters n and $\ell$ defining the polynomial ring and fix $\sigma =2\lceil \sqrt{n}\rceil$ for the error distribution.

An efficient way of measuring the error growth within the ciphertexts is to compute the difference by applying the rounding $\lfloor \cdot \rceil _2$ in $H.\mathsf {Dec}$ between various ciphertexts with known plaintext. This difference (for each polynomial coefficient or vector component) corresponds to the amount of noise contained in this ciphertext. The correctness requires this quantity to be inferior to $2^{\ell -2}$. Then, considering its logarithm in base 2, it enables to have an intuitive and practical measure of the ciphertext noise: this quantity grows with the homomorphic operations until this log equals $\ell -2$. Concretely, in our experiments we encrypt polynomials being $m=0$ or $m=1$, compute on the constant coefficient the quantity $e= |(\langle \mathbf {s},\mathbf {c}_\ell \rangle -m2^{\ell -1})\mod q|$, and give its logarithm. We give another quantity in order to provide intuition about the homomorphic computation possibilities over the ciphertexts, by simply computing a percentage of the actual level of noise relatively to the maximal level $\ell -2$.

Remark 4

The quantity exhibited by our measures is roughly the subgaussian parameter of the distribution of the error contained in the ciphertexts. Considering the simpler case of a real Gaussian distribution $\mathcal {N}(0,\sigma ^2)$, the difference that we compute then follows a half normal distribution with mean $\sigma \frac{\sqrt{2}}{\sqrt{\pi }}$.

We based our prototype implementation on the NTL library combined with GMP and the discrete gaussian sampler of BLISS [23]. We report in Table 3 experimental results on the error growth for different RLWE and $\textsf {FLIP}$ parameters, based on an average over a hundred of samples.

Table 3. Experimental error growth of Ring-GSW. Fresh, $H.\mathsf {Add}$, $H.\mathsf {Mul}$ and $H.\mathsf {Eval}(\textsf {FLIP})$ respectively stands for the noise e measure after a fresh homomorphic encryption, the homomorphic addition of two fresh ciphertexts, the homomorphic multiplication of two fresh ciphertexts and the homomorphic evaluation of $\textsf {FLIP}$ on fresh ciphertexts. The first value is the $\log$ of the error e inside the corresponding ciphertexts and the percentage represents the proportion of the noise with respect to the capacity of decryption (i.e. $\ell -2$).

The results confirm the quasi-additive error growth when considering the specific metric of GSW given by the asymptotic bounds. The main conclusion of these results is that the error inside the ciphertexts after a homomorphic evaluation of $\textsf {FLIP}$ is of the same order of magnitude as the one after a multiplication. The only difference between these noise increases is a term provided by the root of the symmetric key register size, that is linear in $\lambda$. Therefore, with the $\textsf {FLIP}$ construction the error growth is roughly the basic multiplicative error growth of two ciphertexts. Hence, we conclude that filter permutators as $\textsf {FLIP}$ release the bottleneck of evaluating symmetric decryption, and lead the further improvement of the calculus delegation framework to depend overwhelmingly on improvements of the homomorphic operations.

Table 4. Multiplicative depth of different symmetric ciphers.

Table 5. Timings of the homomorphic evaluation of several instances of the Boolean function of FLIP using HElib on an Intel Core i7-3770. The other results are taken from [11]. L and Number of Slots are HElib parameters which stand respectively for the level of noise and the number of bits packed in one ciphertext. (Nb * Number of Slots) corresponds to the number of decrypted bits.

4.4 Performances for 2nd-Generation Schemes

Despite our new constructions are primarily designed for 3rd-generation FHE, a look at Table 4 suggests that also from the multiplicative depth point of view, $\textsf {FLIP}$ instances bring good results compared to their natural competitors such as LowMC [1] and Trivium/Kreyvium [11]. In Trivium/Kreyvium, the multiplicative depth of the decryption circuit is at most 13, while the LowMC family has a record multiplicative depth of 11 which is still larger than our FLIP instances. For completeness, we finally investigated the performances of some instances of $\textsf {FLIP}$ for 2nd-generation FHE schemes using HElib, as reported in Table 5, where the latency is the amount of time (in seconds) needed to homomorphically decrypt (Nb * Number of Slots) bits, and the throughput is calculated as (Nb * Number of Slots * 60)/latency. As in [11], we have considered two noise levels: a first one that does not allow any other operations on the ciphertexts, and a second one where we allow operations of multiplicative depth up to 7. Note that the (max) parenthesis in the Nb column recalls that for Trivium/Kreyvium, the homomorphic capacity decreases with the number of keystream bits generated, which therefore bounds the number of such bits before re-keying. We observe that for 80-bit security, our instances outperform the ones based on Trivium. As for 128-bit security, the gap between our instances and Kreyvium is limited (despite the larger state of FLIP), and LowMC has better throughput in this context. Note also that our results correspond to the evaluation of the F function of FLIP (we verified that the time needed to generate the permutations only marginally affects the overall performances of homomorphic FLIP evaluations). We finally mention that these results should certainly not be viewed as strict comparisons, since obtained on different computers and for relatively new ciphers for which we have limited understanding of the security margins (especially for LowMC [19, 21] and FLIP). So they should mainly be seen as an indication that besides their excellent features from the FHE capacity point-of-view, filter permutators inherently have good properties for efficient 2nd-generation FHE implementations as well.

5 Conclusions and Open Problems

In the context of our Homomorphic Encryption - Symmetric Encryption framework, where most of the computations are delegated to a server, we have designed a symmetric encryption scheme which fits the FHE settings, with as main goal to get the homomorphic evaluation of the symmetric decryption circuit as cheap as possible, with respect to the error growth. In particular the error growth obtained by our construction, only one level of multiplication considering the metric of third generation FHE, achieves the lowest bound we can get with a secure symmetric encryption scheme. The use of zero-noise operations as permutations enables us to combine the advantages of block ciphers and stream ciphers evaluation, namely constant noise on the one hand and starting low noise on the other hand. As a result, the homomorphic evaluation of filter permutators can be made insignificant relatively to a complete FHE framework.

The general construction of our encryption scheme – i.e. the filter permutator – and its FLIP instances are admittedly provocative. As a result, we believe an important contribution of this paper is to open a wide design space of symmetric constructions to investigate, ranging from the very efficient solutions we suggest to more classical stream ciphers such as filter generators. Such a design space leads to various interesting directions for further research. Overall, the main question raised by filter permutators is whether it is possible to build a secure symmetric encryption scheme with aggressively reduced algebraic degree. Such a question naturally relates to several more concrete problems. First, and probably most importantly, additional cryptanalysis is needed in view of the non-standard design principles exploited in filter permutators. It typically includes algebraic attack taking advantage of the sparsity of their systems of equations, attacks exploiting the imbalances at the input of the filter, and the possibility to exploit chosen IVs to improve those attacks. Second, our analyses also raise interesting problems in the field of Boolean functions, e.g. the analysis of such functions with non-uniform input distributions and the investigation of the best fixed degree approximations of a Boolean function (which is needed in our study of higher-order correlation attacks). More directly related to the FLIP instances, it would also be interesting to refine our security analyses, with a stronger focus on the attacks data complexity, and to evaluate whether instances with smaller key register could be sufficiently secure. In case of new cryptanalysis results, the design tweaks we suggest in the paper are yet another interesting research path. Eventually, and from the FHE application point-of-view, optimizing the implementations of filter permutators, e.g. by taking advantage of parallel computing clusters that we did not exploit so far, would be useful in order to evaluate their applicability to real-world scenarii.