[1]Joanna E. Sobczyk

[1]Institut für Kernphysik and PRISMA+ Cluster of Excellence, Johannes
Gutenberg-Universität, Mainz, 55128, Germany

# Electron scattering on 4He from coupled-cluster theory

<EMAIL_ADDRESS>*

###### Abstract

We present a coupled-cluster calculation for the electron-4He scattering in
the region of the quasi-elastic peak. We show the longitudinal and transverse
responses separately, and discuss results within two distinct theoretical
methods: the Lorentz integral transform and spectral functions. The comparison
between them allows to investigate the role of final state interactions, two-
body currents and relativistic effects.

##  1 Introduction

In recent years, there has been a resurgence of interest in lepton-nucleus
scattering, particularly due to long baseline neutrino oscillation programs
[1, 2]. These experiments aim at measuring fundamental neutrino properties,
such as mixing angles and, notably, the CP-violating phase. These are inferred
from the observed oscillation patterns, the accuracy of which hinges upon the
precise reconstruction of neutrino energy in scattering events. This
reconstruction procedure is heavily reliant on theoretical models of lepton-
nucleus interactions. It is widely acknowledged that electron scattering
processes, benefiting from precise datasets, offer an ideal opportunity to
validate theoretical calculations [3]. These two processes are analogous, with
the neutrino-induced reactions being theoretically more sophisticated since
neutrinos break parity and so the process involves both vector and axial
currents. Historically, electromagnetic probes have been recognized as
excellent tools for investigating the structural properties of nuclear
systems. Electron scattering experiments conducted at various energy scales
provide precise data across a wide energy range. This breadth of data is
crucial for neutrino experiments, as their energy range of interest, spanning
from hundreds of MeV to a few GeV, encompasses various physical mechanisms,
from the quasi-elastic (QE) peak to deep inelastic scattering. Already in the
QE peak the typical energies relevant for experiments are high, so that the
relativistic treatment in theoretical calculations becomes crucial.

Future oscillation experiments, DUNE [4] and Hyper-K [5], use detectors built
of medium-mass nuclei (40Ar and 16O respectively), making the many-body
nuclear methods an essential tool to interpret experimental data. Motivated by
this need, we initiated a program which aims at calculating neutrino-nucleus
cross sections from an ab initio coupled-cluster framework [6, 7, 8]. The
ultimate goal of this endeavor are medium-mass nuclei of experimental
interest. However, the method should be first benchmarked in the few-body
sector for electromagnetic reactions for which highly precise few-body
approaches exist. In the following, we present results in the QE regime from
the coupled-cluster calculations for 4He which is an excellent case-study,
being a closed-shell nucleus. We discuss two complementary approaches, the
Lorentz integral transform and spectral functions, which are reliable at low
and high momentum transfers respectively. Spectral functions, assuming certain
approximations, allow for the relativistic calculation required in the large
phase-space probed by neutrino experiments. For moderate momenta, the
comparison of two approaches reveals the role of the used approximations.

##  2 Formalism

Inclusive electron scattering cross section $(e,e^{\prime})$ can be written in
terms of two response functions,

$\frac{d^{2}\sigma}{d\Omega_{e^{\prime}}d\omega}=\sigma_{Mott}\left(\left(\frac{q^{2}}{{\bf
q}^{2}}\right)^{2}R_{L}(\omega,|{\bf
q}|)+\left(\tan^{2}\frac{\theta_{e^{\prime}}}{2}-\frac{1}{2}\frac{q^{2}}{{\bf
q}^{2}}\right)R_{T}(\omega,|{\bf q}|)\right),$ (1)

with the Mott cross section $\sigma_{Mott}$, the energy-momentum transfer
$q=(\omega,{\bf q})$ and the scattering angle $\theta_{e^{\prime}}$ of an
outgoing electron. The nuclear responses $R_{L/T}$ encapsulate the behaviour
of the probed nucleus. At low energies they describe excitations of low-lying
states and resonances. For the momentum transfers ${\bf q}$ of the order of
$\mathcal{O}(100)$ MeV the response is dominated by a single nucleon knock-out
reaction in the so-called QE regime. Within the nonrelativistic picture, the
responses correspond to the excitations of the system by the charge operator
and the transverse part of the electromagnetic current:

$R_{L}(\omega,|{\bf q}|)=\sum_{f}\langle 0|\rho^{\dagger}({\bf
q})|f\rangle\langle f|\rho({\bf q})|0\rangle\delta(E_{0}+\omega-E_{f})\ ,$ (2)

$R_{T}(\omega,|{\bf q}|)=\sum_{f}\langle 0|{\bf j_{T}}^{\dagger}({\bf
q})|f\rangle\langle f|{\bf j_{T}}({\bf q})|0\rangle\delta(E_{0}+\omega-E_{f})\
.$ (3)

The one-body operators $(\rho,{\bf j})$ have a standard form. They act on the
groundstate nucleus $|0\rangle$, exciting it to the final $|f\rangle$ state.
The sum over $f$ is a highly demanding computational problem since it requires
techniques which give access to a continuum set of states. A well-established
approach to solve this problem within ab initio nuclear methods, amounts to
calculating an integral transform of the response instead,

$\tilde{R}(\sigma,|{\bf q}|)=\langle 0|\theta^{\dagger}K\left(\sigma-
E_{0},\mathcal{H}\right)\theta|0\rangle$ (4)

and inverting it afterwards. Here, $\theta$ is an operator of interest (in our
case $\rho$ or ${\bf j}$), $K$ corresponds to a kernel function and
$\mathcal{H}$ is the nuclear Hamiltonian. For the few-body sector, the
Lorentzian and Laplace kernels have been successfully employed [9, 10, 11,
12]. In last years the Lorentz integral transform (LIT) has been used in
conjuncture with the many-body coupled-cluster framework, first to obtain the
dipole response of medium-mass nuclei [13, 14] and more recently also for the
longitudinal and transverse responses [15, 16]. This computational procedure
leads to results in which the final excited states – albeit explicitly not
known – are treated in a consistent way, i.e. not introducing any
approximation to the form of the final wave function. However, this approach
comes with some drawbacks. Firstly, it is burdened with a heavy computational
cost. Secondly, the inversion procedure is an ill-posed problem which requires
some additional techniques or smoothing assumptions about the shape of the
response.

The cross section in the QE regime can be approximated, assuming that a
single-nucleon knock-out process occurs and the final nucleon does not
interact with the residual system. In this picture, called impulse
approximation (IA), the nuclear information is encoded in the spectral
functions (SF) which gives the energy-momentum distribution of removing a
nucleon from the groundstate

$\displaystyle S(E,\mathbf{p})$
$\displaystyle=\sum_{\alpha,\alpha^{\prime}}\int_{\Psi_{A-1}}|\langle
0|a_{\alpha}^{\dagger}|\Psi_{A-1}\rangle\langle\Psi_{A-1}|a_{\alpha^{\prime}}|0\rangle$
$\displaystyle\langle\mathbf{p}|\alpha\rangle^{\dagger}\langle\mathbf{p}|\alpha^{\prime}\rangle\delta(E+E_{f}^{A-1}-E_{0})\,,$
(5)

where $a_{\alpha}$ is a one-particle removal operator with quantum numbers
$\alpha$. The nuclear responses can be then directly related to the SF

$R_{\mathrm{IA}}(\omega,{\bf q})=\int d^{3}{\bf p}dE\ S(E,{\bf p})|\langle{\bf
p}+{\bf q}|\theta|{\bf p}\rangle|^{2}\delta(E+\omega-E_{p+q})\,.$ (6)

The knocked-out nucleon at interaction vertex is treated as a free
nonrelativistic particle, leading to a drastic simplification of the response
calculation, in which the matrix element $|\langle{\bf p}+{\bf q}|\theta({\bf
q})|{\bf p}\rangle|^{2}$ is factorized from the information of the groundstate
nucleus. This factorization allows to extend the formalism to the relativistic
regime: while the spectral function is obtained using nonrelativistic nuclear
techniques, it can be coupled to the vertex of interaction in which both the
kinematics and the electromagnetic current can be treated in the relativistic
theory

$R_{\mathrm{IA}}^{\mathrm{rel}}(\omega,{\bf q})=\int d^{3}{\bf
p}dE\,\frac{m}{E_{p}}\frac{m}{E_{p+q}}S(E,{\bf p})|\langle
p+q|\theta_{\mathrm{rel}}(q)|p\rangle|^{2}\delta(E+\omega-E_{p+q})\,,$ (7)

with the relativistic energy $E_{p+q}=\sqrt{m^{2}+({\bf p}+{\bf q})^{2}}$ and
additional $m/E$ factors which arise from the normalization of Dirac spinors.
One can also include the relativistic effects only in the kinematics leading
to

$R_{\mathrm{IA}}^{\mathrm{semi-rel}}(\omega,{\bf q})=\int d^{3}{\bf
p}dE\,\frac{m}{E_{p}}\frac{m}{E_{p+q}}S(E,{\bf p})|\langle{\bf p}+{\bf
q}|\theta|{\bf p}\rangle|^{2}\delta(E+\omega-E_{p+q})\,.$ (8)

It has to be noted that for the relativistic currents, which depend on the
four-momentum transfer, the procedure is not fully consistent since the
initial nucleon is off-shell (with the energy-momentum distributed according
to the spectral function). On the other hand, the vertex of interaction
assumes both initial and final nucleons to be on-shell. This leads to some
ambiguities and a violation of current conservation [17] (which can be
restored by de Forest procedure [18]).

###  2.1 Coupled-cluster for LIT and SF

Within the coupled-cluster method, the nuclear A-body groundstate wavefunction
is constructed based on an ansatz:

$|0\rangle=e^{T}|\Psi_{0}\rangle$ (9)

with the correlation operator $T=T_{1}+T_{2}+...$ and the Hartree-Fock state
$|\Psi_{0}\rangle$. The $T_{n}$ operator creates n-particle n-hole excitations
in respect to the reference state. The sum of $T=\sum_{i}T_{i}$ is truncated
at some level. The results presented in this work were obtained within singles
and doubles approximation (CCSD), i.e. $T=T_{1}+T_{2}$. The $T$ amplitudes are
obtained by solving a set of coupled equations. The dynamics between
constituent nucleons is modelled by state-of-the-art chiral Hamiltonians. They
are derived from chiral perturbation theory and allow for an order-by-order
expansion with low energy constants fit to experimental data. In our
calculations, we employ NNLO${}_{\text{sat}}$ potential with two- and three-
body forces, which was adjusted to groundstate properties of some medium-mass
nuclei [19]. We perform the calculation of LIT and SF both within the same
many-body method (and approximations within) and employing the same nuclear
dynamics. This allows us to perform a meaningful comparison of both approaches
to understand the role of various approximations.

The calculation of nuclear response functions using LIT is performed within a
nonrelativistic formalism, both in the description of nuclear dynamics, as
well as in electromagnetic currents. The scattering problem is formally
reformulated into a bound-state problem. The Lorentz Integral Transform,
merged with the coupled-cluster method (LIT-CC), is based on the equation-of-
motion technique [20]. The inversion is performed by the least squares method
[10].

The spectral function for 4He within the coupled-cluster formalism was
obtained in Ref. [21]. The calculation was performed using Gaussian Integral
Transform, through an expansion into Chebyshev polynomials. In this sense the
procedure resembles LIT calculation. However, rather than inverting the
integral transform, the final spectral reconstruction is built as a histogram,
allowing for a rigorous estimation of uncertainties [22]. As mentioned in Sec.
2, within IA the spectral function can be directly employed to calculate the
cross section.

We note that for light systems the coupled-cluster method is prone to the
center-of-mass spurious states [23]. This problem was addressed in Ref. [24]
for the LIT and Ref. [21] for the SF, in both cases assuming that the center-
of-mass motion is approximately a Gaussian factorized from the wavefunction.
We found that the spurious states are excited at low energy transfers and can
be removed from the spectrum. For the SF, the effect can be mitigated by a
transformation of the momentum distribution.

##  3 Results

We present results of electron scattering on 4He for two kinematics, ${\bf
q}=300,400$ MeV/c for which the Rosenbluth separation has been performed. In
this regime the LIT-CC results using a chiral Hamiltonian are fully converged.
At the same time, the momentum is high enough to justify the impulse
approximation in the SF approach.

Disentangling the longitudinal and transverse responses allows for a more
thorough analysis, in which the final state interactions, relativistic effects
and the role of two-body currents can be addressed. It is well known that the
two-body contribution to the charge operator appears at a higher chiral order,
making the longitudinal response a good starting point for the analysis. In
fact, in Fig. 1, we show that the LIT-CC results, which consistently treat
final state effects, lead to a very good agreement with the data already at
the level of one-body operator. The difference between the LIT-CC result and
SF (dashed blue line) can be fully prescribed to final state interactions.
This comparison reveals an advantage of LIT-CC in resolving the fine details
of nuclear excitations at low energy transfers. In this region (below the QE
peak), the SF underestimates the strength since the dynamics of the system is
more complicated than a single-nucleon knock-out process. Within the SF
approximation the response is smooth, peaking approximately at
$\omega\approx{\bf q}^{2}/2m$, which corresponds to the kinematics of a
process in which a free nucleon receives the whole momentum transfer $q$ and
the final knocked-out nucleon is assumed to be on-shell. Also, all
interactions with the residual system are neglected. This approximation leads
to an enhancement of the QE peak (around $30\%$ at this kinematical setup) and
a shift towards higher energy transfers by around 15 MeV. This behaviour can
be understood in the mean-field picture: we neglect the potential energy of
the outgoing nucleon which would change its dispersion relations in the
nuclear medium. Although it is not straightforward to assess the magnitude of
relativistic effects within the LIT-CC, one can account for them within the SF
formalism. In Figs. 1, 2 the blue band shows the difference between the
nonrelativistic and relativistic kinematics (see Eqs. (6) and (8)). The dashed
blue line corresponds to the nonrelativistic kinematics. While for ${\bf
q}=300$ MeV/c momentum transfer the effect is small, it becomes visible for
${\bf q}=400$ MeV/c. It affects the high energy tail of the response, above
the QE peak. Since this is a purely kinematical effect, we would expect that
its magnitude is similar for the LIT-CC method.

The transverse response, see Fig. 2, shows a somehow different behaviour. The
LIT-CC results underestimate the experimental data by around $20\%$. This can
be expected, since for the electromagnetic current operator the two-body
currents appear at lower chiral order and were shown to produce an enhancement
in several few-body calculations [25, 12]. At ${\bf q}=300$ MeV/c we also
observe a low-lying structure which originates from the magnetic part of the
transverse current. With respect to the LIT-CC, the SF predicts more strength
and shifts the QE peak towards higher energy transfers. At the same time, it
leads to a reasonable agreement with the experimental strength (although still
shifted by 15 MeV). For ${\bf q}=400$ MeV/c momentum transfer we also show
with the green dotted line in Figs. 1, 2 the results of a fully relativistic
calculation, Eq. (7) (both in kinematics and one-body currents). The
difference is of the order of a few percent in the strength of the response.
Finally, at higher energies, above $200$ MeV, the experimental data reveals
additional mechanisms above the QE peak. Pion production, which is not
accounted for in our method, starts playing an important role and dominates
the transverse response.

It is important to point out that the analysis of nuclear responses give
insights which could be easily missed when considering the inclusive cross
section only. In fact, for the kinematics in which $R_{T}$ dominates (backward
scattering angles), the SF approach could predict a result close to experiment
since the final-state-interactions effects would compensate for the lack of
two-body currents.

The analysis also reveals that the relativistic effects of the LIT-CC should
be already important for ${\bf q}=400$ MeV/c and they would affect mostly the
distribution tail. One could account for them following a procedure of Ref.
[26], i.e. performing calculation in a boosted reference frame in which the
relativistic effects become smaller.

Figure 1: Longitudinal response for two values of momentum transfer ${\bf
q}=300,400$ MeV/c. The uncertainty of LIT-CC method (red band) comes from the
inversion procedure. The blue dashed line corresponds to the nonrelativistic
SF calculation, while the blue band shows the difference from the relativistic
case. The dotted green curve shows the fully relativistic calculation from Eq.
(7). Data taken from Refs. [27, 28, 29].

Figure 2: Similar to Fig. 1 but for the transverse response.

##  4 Conclusions

We conducted a comparison between two approaches for calculating the lepton-
nucleus cross section to investigate the interplay of various effects: final
state interactions, two-body currents, and relativistic effects. Specifically,
we analyzed the longitudinal and transverse responses for electron-4He
scattering, utilizing available Rosenbluth separated data in the intermediate
momentum transfer regime. Both the LIT and SF calculations were derived within
the coupled-cluster theory using a chiral nuclear Hamiltonian. This shared
theoretical framework enabled a meaningful comparison.

The LIT-CC method represents the current state-of-the-art approach for
calculating nuclear responses while consistently considering final state
interactions. However, it is limited to the nonrelativistic regime.
Conversely, the SF formalism, which can extend to the relativistic energies,
does not incorporate final state interactions.

We point out that the lack of two-body currents, crucial for the transverse
response, might lead to a good comparison of the SF method only with one-body
currents. Moreover, the relativistic effects play a non-negligible role
already at ${\bf q}=400$ MeV/c and can lead to a suppression of the
distribution tail, beyond the QE peak.

The conclusions drawn from our analysis of electron scattering processes can
be directly applied for the neutrino induced reactions, thereby making a
direct impact on the theoretical studies for neutrino oscillation experiments.

Acknowledgements This project has received funding from the European Union’s
Horizon 2020 research and innovation programme under the Marie Skłodowska-
Curie grant agreement No. 101026014. This work was supported by the Deutsche
Forschungsgemeinschaft (DFG) through the Cluster of Excellence “Precision
Physics, Fundamental Interactions, and Structure of Matter” (PRISMA+ EXC
2118/1) funded by the DFG within the German Excellence Strategy (Project ID
39083149). Computer time was provided by the supercomputer MogonII at Johannes
Gutenberg-Universität Mainz.

## References

  *   * Alvarez-Ruso et al. [2018] Alvarez-Ruso, L., et al.: NuSTEC White Paper: Status and challenges of neutrino–nucleus scattering. Prog. Part. Nucl. Phys. 100, 1–68 (2018) https://doi.org/10.1016/j.ppnp.2018.01.006 arXiv:1706.03621 [hep-ph]
  * Ruso et al. [2022] Ruso, L.A., et al.: Theoretical tools for neutrino scattering: interplay between lattice QCD, EFTs, nuclear physics, phenomenology, and neutrino event generators (2022) arXiv:2203.09030 [hep-ph]
  * Ankowski et al. [2022] Ankowski, A.M., et al.: Electron Scattering and Neutrino Physics (2022) arXiv:2203.06853 [hep-ex]
  * Acciarri et al. [2015] Acciarri, R., et al.: Long-Baseline Neutrino Facility (LBNF) and Deep Underground Neutrino Experiment (DUNE) (2015) arXiv:1512.06148 [physics.ins-det]
  * Abe et al. [2015] Abe, K., et al.: Physics potential of a long-baseline neutrino oscillation experiment using a J-PARC neutrino beam and Hyper-Kamiokande. PTEP 2015, 053–02 (2015) https://doi.org/10.1093/ptep/ptv061
  * Kümmel et al. [1978] Kümmel, H., Lührmann, K.H., Zabolitzky, J.G.: Many-fermion theory in expS- (or coupled cluster) form. Physics Reports 36(1), 1–63 (1978) https://doi.org/10.1016/0370-1573(78)90081-9
  * Dean and Hjorth-Jensen [2004] Dean, D.J., Hjorth-Jensen, M.: Coupled-cluster approach to nuclear physics. Phys. Rev. C 69, 054320 (2004) https://doi.org/10.1103/PhysRevC.69.054320
  * Hagen et al. [2010] Hagen, G., Papenbrock, T., Dean, D.J., Hjorth-Jensen, M.: Ab initio coupled-cluster approach to nuclear structure with modern nucleon-nucleon interactions. Phys. Rev. C 82, 034330 (2010) https://doi.org/10.1103/PhysRevC.82.034330 arXiv:1005.2627 [nucl-th]
  * Efros et al. [1994] Efros, V.D., Leidemann, W., Orlandini, G.: Response functions from integral transforms with a Lorentz kernel. Phys. Lett. B 338, 130–133 (1994) https://doi.org/10.1016/0370-2693(94)91355-2 arXiv:nucl-th/9409004
  * Efros et al. [2007] Efros, V.D., Leidemann, W., Orlandini, G., Barnea, N.: The lorentz integral transform (lit) method and its applications to perturbation-induced reactions. Journal of Physics G: Nuclear and Particle Physics 34(12), 459 (2007)
  * Carlson et al. [2015] Carlson, J., Gandolfi, S., Pederiva, F., Pieper, S.C., Schiavilla, R., Schmidt, K.E., Wiringa, R.B.: Quantum monte carlo methods for nuclear physics. Rev. Mod. Phys. 87, 1067–1118 (2015) https://doi.org/10.1103/RevModPhys.87.1067
  * Lovato et al. [2016] Lovato, A., Gandolfi, S., Carlson, J., Pieper, S.C., Schiavilla, R.: Electromagnetic response of ${}^{12}\mathrm{C}$: A first-principles calculation. Phys. Rev. Lett. 117, 082501 (2016) https://doi.org/10.1103/PhysRevLett.117.082501
  * Bacca et al. [2013] Bacca, S., Barnea, N., Hagen, G., Orlandini, G., Papenbrock, T.: First principles description of the giant dipole resonancein ${}^{16}\mathbf{O}$. Phys. Rev. Lett. 111, 122502 (2013) https://doi.org/10.1103/PhysRevLett.111.122502
  * Bacca et al. [2014] Bacca, S., Barnea, N., Hagen, G., Miorelli, M., Orlandini, G., Papenbrock, T.: Giant and pigmy dipole resonances in 4He, 16,22O, and 40Ca from chiral nucleon-nucleon interactions. ArXiv e-prints (2014) arXiv:1410.2258 [nucl-th]
  * Sobczyk et al. [2021] Sobczyk, J.E., Acharya, B., Bacca, S., Hagen, G.: Ab initio computation of the longitudinal response function in 40Ca. Phys. Rev. Lett. 127(7), 072501 (2021) https://doi.org/10.1103/PhysRevLett.127.072501 arXiv:2103.06786 [nucl-th]
  * Sobczyk et al. [2024] Sobczyk, J.E., Acharya, B., Bacca, S., Hagen, G.: 40Ca transverse response function from coupled-cluster theory. Phys. Rev. C 109(2), 025502 (2024) https://doi.org/10.1103/PhysRevC.109.025502 arXiv:2310.03109 [nucl-th]
  * Benhar et al. [2008] Benhar, O., day, D., Sick, I.: Inclusive quasi-elastic electron-nucleus scattering. Rev. Mod. Phys. 80, 189–224 (2008) https://doi.org/10.1103/RevModPhys.80.189 arXiv:nucl-ex/0603029
  * De Forest [1983] De Forest, T.: Off-Shell electron Nucleon Cross-Sections. The Impulse Approximation. Nucl. Phys. A 392, 232–248 (1983) https://doi.org/10.1016/0375-9474(83)90124-0
  * Ekström et al. [2015] Ekström, A., Jansen, G.R., Wendt, K.A., Hagen, G., Papenbrock, T., Carlsson, B.D., Forssén, C., Hjorth-Jensen, M., Navrátil, P., Nazarewicz, W.: Accurate nuclear radii and binding energies from a chiral interaction. Phys. Rev. C 91(5), 051301 (2015) https://doi.org/%****␣sn-article.bbl␣Line␣350␣****10.1103/PhysRevC.91.051301 arXiv:1502.04682 [nucl-th]
  * Stanton and Bartlett [1993] Stanton, J.F., Bartlett, R.J.: The equation of motion coupled-cluster method. a systematic biorthogonal approach to molecular excitation energies, transition probabilities, and excited state properties. J. Chem. Phys. 98(9), 7029–7039 (1993) https://doi.org/10.1063/1.464746
  * Sobczyk et al. [2022] Sobczyk, J.E., Bacca, S., Hagen, G., Papenbrock, T.: Spectral function for 4He using the Chebyshev expansion in coupled-cluster theory (2022) arXiv:2205.03592 [nucl-th]
  * Sobczyk and Roggero [2021] Sobczyk, J.E., Roggero, A.: Spectral density reconstruction with Chebyshev polynomials (2021) arXiv:2110.02108 [nucl-th]
  * Hagen et al. [2009] Hagen, G., Papenbrock, T., Dean, D.J.: Solution of the center-of-mass problem in nuclear structure calculations. Phys. Rev. Lett. 103, 062503 (2009) https://doi.org/10.1103/PhysRevLett.103.062503
  * Sobczyk et al. [2020] Sobczyk, J.E., Acharya, B., Bacca, S., Hagen, G.: Coulomb sum rule for 4He and 16O from coupled-cluster theory. Phys. Rev. C 102, 064312 (2020) https://doi.org/10.1103/PhysRevC.102.064312 arXiv:2009.01761 [nucl-th]
  * Lovato et al. [2015] Lovato, A., Gandolfi, S., Carlson, J., Pieper, S.C., Schiavilla, R.: Electromagnetic and neutral-weak response functions of 4He and 12C. Phys. Rev. C 91(6), 062501 (2015) https://doi.org/10.1103/PhysRevC.91.062501 arXiv:1501.01981 [nucl-th]
  * Efros et al. [2005] Efros, V.D., Leidemann, W., Orlandini, G., Tomusiak, E.L.: Improved (e,e’) response functions at intermediate momentum transfers: The He-3 case. Phys. Rev. C 72, 011002 (2005) https://doi.org/10.1103/PhysRevC.72.011002 arXiv:nucl-th/0505028
  * Zghiche et al. [1994] Zghiche, A., et al.: Longitudinal and transverse responses in quasielastic electron scattering from pb-208 and he-4. Nucl. Phys. A572, 513–559 (1994)
  * Carlson et al. [2002] Carlson, J., Jourdan, J., Schiavilla, R., Sick, I.: Longitudinal and transverse quasielastic response functions of light nuclei. Phys. Rev. C 65, 024002 (2002) https://doi.org/10.1103/PhysRevC.65.024002 arXiv:nucl-th/0106047
  * Dytman et al. [1988] Dytman, S.A., Bernstein, A.M., Blomqvist, K.I., Pavel, T.J., Quinn, B.P., Altemus, R., Mccarthy, J.S., Mechtel, G.H., Ueng, T.S., Whitney, R.R.: Inclusive Electron Scattering From 2H, 3He, and 4He. Phys. Rev. C 38, 800–812 (1988) https://doi.org/10.1103/PhysRevC.38.800


# On the Sample Complexity of solving LWE using BKW-Style Algorithms

Qian Guo, Erik Mårtensson and Paul Stankovski Wagner  Department of Electrical
and Information Technology
Lund University, Lund, Sweden
Email: {qian.guo, erik.martensson<EMAIL_ADDRESS>
###### Abstract

The Learning with Errors (LWE) problem receives much attention in
cryptography, mainly due to its fundamental significance in post-quantum
cryptography. Among its solving algorithms, the Blum-Kalai-Wasserman (BKW)
algorithm, originally proposed for solving the Learning Parity with Noise
(LPN) problem, performs well, especially for certain parameter settings with
cryptographic importance. The BKW algorithm consists of two phases, the
reduction phase and the solving phase.

In this work, we study the performance of distinguishers used in the solving
phase. We show that the Fast Fourier Transform (FFT) distinguisher from
Eurocrypt’15 has the same sample complexity as the optimal distinguisher, when
making the same number of hypotheses. We also show that it performs much
better than theory predicts and introduce an improvement of it called the
pruned FFT distinguisher. Finally, we indicate, via extensive experiments,
that the sample dependency due to both LF2 and sample amplification is
limited.

##  I Introduction

Post-quantum cryptography studies replacements of cryptographic primitives
based on the factoring or discrete-log problem, since both can be efficiently
solved by a quantum computer [1]. Lattice-based cryptography is its main area.
In the NIST Post-Quantum Cryptography Standardization [2], 5 out of 7
finalists and 2 out of 8 alternates are lattice-based.

The Learning with Errors (LWE) problem, introduced by Regev [3], is the major
problem in lattice-based cryptography. Its average-case hardness can be based
on the worst-case hardness of some standard lattice problems, which is
extremely interesting in theoretical crypto. The most famous, of its many
cryptographic applications, is the design of Fully Homomorphic Encryption
(FHE) schemes. Its binary counterpart, the Learning Parity with Noise problem
(LPN), also plays an significant role in cryptography (see [4]), especially in
light-weight cryptography for very constrained environments such as RFID tags
and low-power devices.

The algorithms for solving LWE can be divided into lattice-based, algebraic,
and combinatorial methods. The last class of algorithms all inherit from the
famous Blum-Kalai-Wasserman (BKW) algorithm [5, 6], and are the most relevant
to our study. We refer interested readers to [7] for concrete complexity
estimation for solving LWE instances, and to [8, 9] for asymptotic complexity
estimations.

The BKW-type algorithms include two phases, the reduction phase and the
solving phase. The prior consists of a series of operations, called BKW steps,
iteratively reducing the dimension of the problem at the cost of increasing
its noise level. At the end of the reduction phase, the original LWE problem
is transformed to a new problem with a much smaller dimension. The new problem
can be solved efficiently by a procedure called distinguishing in the solving
phase.

One of the main challenges in understanding the precise performance of BKW
variants on solving the LWE problem comes from the lack of extensive
experimental studies, especially on the various distinguishers proposed for
the solving phase. Firstly, we have borrowed many heuristics from BKW variants
on the LPN problem, but only very roughly or not at all verified them for the
LWE problem. Secondly, the tightness of the nice theoretical bound in [10] on
the sample complexity of the FFT distinguisher also needs to be experimentally
checked. Lastly, a performance comparison of the different known
distinguishers is still lacking.

###  I-A Related Work

The BKW algorithm proposed by Blum et al. [5, 6] is the first sub-exponential
algorithm for solving the LPN problem. Its initial distinguisher, an
exhaustive search method in the binary field, recovers one bit of the secret
by employing majority voting. Later, Levieil and Fouque [11] applied the fast
Walsh-Hadamard transform (FWHT) technique to accelerate the distinguishing
process and recovered a number of secret bits in one pass. They also proposed
some heuristic versions and tested these assumptions by experiments. In [12]
Kirchner proposed a secret-noise transform technique to change the secret
distribution to be sparse. This technique is an application of the transform
technique proposed in [13] for solving LWE. Bernstein and Lange [14] further
instantiated an attack on the Ring-LPN problem, a variant of LPN with
algebraic ring structures. In [15, 16], Guo, Johansson, and Löndahl proposed a
new distinguishing method called subspace hypothesis testing. Though this
distinguisher can handle an instance with larger dimension by using covering
codes, its inherent nature is still an FWHT distinguisher. Improvements of the
BKW algorithm were further studied by Zhang et al. [17] and Bogos-Vaudenay
[18]. An elaborate survey with experimental results on the BKW algorithm for
solving LPN can be found in [19].

BKW for solving LWE follows a similar research line. Albrecht et al. initiated
the study in [20]. In PKC 2014 [21], a new reduction technique called lazy
modulus switching was proposed. In both works, the solving phase uses an
exhaustive search approach. In [10] Duc et al. introduced the fast Fourier
transform (FFT) technique in the distinguishing process and bounded the sample
complexity theoretically from the Hoeffding inequality. Note that the actual
performance regarding the bound is not experimentally verified and the
information loss in the FFT distinguisher is unclear. There are new reduction
methods in [22, 23, 24], and in [22], the authors also proposed a new method
with polynomial reconstruction in the solving phase. This method has the same
sample complexity as that of the exhaustive search approach but requires
$(q+1)$ FFT operations rather than only one FFT in [10]. The BKW variants with
memory constraints were recently studied in [25, 26, 27].

###  I-B Contributions

In the paper, we compare the performances of the known distinguishers
empirically. We investigate the performance of the optimal distinguisher and
the FFT distinguisher. We also test the sample dependency when using LF2 or
sample amplification. We have the following contributions.

  1. 1.

We show that the FFT distinguisher and the optimal distinguisher have the same
sample complexity, if we make sure that the distinguishers make the same
number of hypotheses. Thus, except for very sparse secrets, the FFT
distinguisher is always preferable. This also makes the polynomial
reconstruction method of [22] obsolete.

  2. 2.

We indicate that the formula from [10] for the number of samples needed for
distinguishing is off by roughly an order of magnitude.

  3. 3.

We introduce a pruned FFT method. By only testing probable hypotheses, we
improve the performance of the FFT method from [10] with no computational
overhead.

  4. 4.

We indicate that the sample dependency due to using LF2 or sample
amplification is limited.

###  I-C Organization

The rest of the paper is organized as follows. Section II introduces some
necessary background. In Section III we cover the basic BKW algorithm. Section
IV goes over distinguishers used for hypothesis testing when solving LWE using
BKW and introduces the pruned FFT method. Next, in Section V we show why the
FFT distinguisher and the optimal distinguisher perform identically for our
setting, followed by simulation results in Section VI. Section VII concludes
the paper.

##  II Background

Let us introduce some notation. Bold small letters denote vectors. Let
$\left\langle\cdot,\cdot\right\rangle$ denote the scalar products of two
vectors with the same dimension. By $|x|$ we denote the absolute value of $x$
for a real number $x\in\mathbb{R}$. We also denote by $\Re{(y)}$ the real part
and $\left\lVert y\right\rVert$ the absolute value of a complex number
$y\in\mathbb{C}$.

###  II-A LWE

Let us define the LWE problem.

######  Definition 1 (LWE)

Let $n$ be a positive integer, $q$ an odd prime. Let $\bf s$ be a uniformly
random secret vector in $\mathbb{Z}_{q}^{n}$. Assume access to $m$ noisy
scalar products between $\bf s$ and known vectors $\bf a_{i}$, i.e.

$b_{i}=\left\langle{\bf a_{i}},{\bf s}\right\rangle+{e_{i}},$ (1)

for $i=1,\ldots,m$. The error terms ${e_{i}}$ are drawn from a distribution
$\chi$. The (search) LWE problem is to find $\bf s$.

Thus, when solving LWE you have access to a large set of pairs
$(\mathbf{a_{i}},b_{i})$ and want to find the corresponding secret vector
$\mathbf{s}$. Some versions restrict the number of available samples. If we
let $\mathbf{b}=(b_{1},b_{2},\ldots,b_{m})$,
$\mathbf{e}=(e_{1},e_{2},\ldots,e_{m})$ and
$\mathbf{A}=[\mathbf{a}_{1}^{T},\mathbf{a}_{2}^{T}\cdots\mathbf{a}_{m}^{T}]$
we can write the problem on matrix form as

$\mathbf{b}=\mathbf{s}\mathbf{A}+\mathbf{e}.$ (2)

###  II-B Rounded Gaussian Distribution

For the error we use the rounded Gaussian distribution111Also common is to use
the Discrete Gaussian distribution, which is similar.. Let $f(x|0,\sigma^{2})$
denote the PDF of the normal ditribution with mean 0 and standard deviation
$\sigma$, this distribution in turn being denoted as
$\mathcal{N}(0,\sigma^{2})$. The rounded Gaussian distribution samples from
$\mathcal{N}(0,\sigma^{2})$, rounds to the nearest integer and wraps to the
interval $[-(q-1)/2,(q-1)/2]$. In other words, the probability of choosing a
certain error $e$ is equal to

$\sum_{k=-\infty}^{\infty}\int_{e-1/2+k\cdot q}^{e+1/2+k\cdot
q}f(x|0,\sigma^{2})dx,$

for $e\in[-(q-1)/2,(q-1)/2]$. We denote this distribution by
$\bar{\Psi}_{\sigma,q}$. We use the well-known heuristic approximation that
the sum of two independent distributions $X_{1}$ and $X_{2}$, drawn from
$\bar{\Psi}_{\sigma_{1},q}$ and $\bar{\Psi}_{\sigma_{2},q}$, is drawn from
$\bar{\Psi}_{\sqrt{\sigma_{1}^{2}+\sigma_{2}^{2}},q}$. We also use the
notation $\alpha=\sigma/q$. Finally, we let $\mathcal{U}(a,b)$ denote the
discrete uniform distribution taking values from $a$ up to $b$.

##  III BKW

The BKW algorithm was originally invented to solve LPN. It was first used for
LWE in [20]. The BKW algorithm consists of two parts, reduction and hypothesis
testing.

###  III-A Reduction

We divide samples into categories based on $b$ position values in the
$\mathbf{a}$ vectors. Two samples should be in the same category if and only
if the $b$ position values get canceled when adding or subtracting the
$\mathbf{a}$ vectors. Given two samples
$([\pm\mathbf{a_{0}},\mathbf{a_{1}}],b_{1})$ and
$([\pm\mathbf{a_{0}},\mathbf{a_{2}}],b_{2})$ within the same category. By
adding/subtracting the $\mathbf{a}$ vectors we get

$\mathbf{a_{1,2}}=[\underbrace{\begin{matrix}0&0&\cdots&0\end{matrix}}_{b\textnormal{
symbols}}\begin{matrix}&*&*&\cdots&*\end{matrix}].$

The corresponding $b$ value is $b_{1,2}=b_{1}\pm b_{2}$. Now we have a new
sample $(\mathbf{a_{1,2}},b_{1,2})$. The corresponding noise variable is
$e_{1,2}=e_{1}\pm e_{2}$, with variance $2\sigma^{2}$, where $\sigma^{2}$ is
the variance of the originial noise. By calculating a suitable number of new
samples for each category we have reduced the dimensionality of the problem by
$b$, but increased the noise variance to $2\sigma^{2}$. If we repeat the
reduction process $t$ times we end up with a dimensionality of $n-tb$, and a
noise variance of $2^{t}\cdot\sigma^{2}$.

####  III-A1 LF1 and LF2

LF1 and LF2 are two implementation tricks originally proposed for solving LPN
in [11]. Both can naturally be generalized for solving LWE.

In LF1 we choose one representative per category. We form new samples by the
other samples with the representative. This way all samples at the hypothesis
testing stage are independent of each other. However, the sample size shrinks
by $(q^{b}-1)/2$ samples per generation, requiring a large initial sample
size.

In LF2 we allow combining any pair of samples within a category, creating much
more samples. If we form every possible sample, a sample size of
$3(q^{b}-1)/2$ is enough to keep the sample size constant between steps. The
disadvantage of this approach is that the samples are no longer independent,
leading to higher noise levels in the hypothesis stage of BKW. It is generally
assumed that this effect is quite small. This assumption is well tested for
solving the LPN problem [11].

####  III-A2 Sample Amplification

Some versions of LWE limit the number of samples. We can get more samples
using sample amplification. For example, by adding/subtracting triples of
samples we can increase the initial sample size $m$ up to a maximum of
$4\cdot\binom{m}{3}$. This does increase the noise by a factor of $\sqrt{3}$.
It also leads to an increased dependency between samples in the hypothesis
testing phase, similar in principle to LF2.

####  III-A3 Secret-Noise Transformation

There is a transformation of the LWE problem that makes the distribution of
the secret vector follow the distribution of the noise [12, 13].

####  III-A4 Improved Reduction Steps

There are many improvements of the plain BKW steps. Lazy modulus switching
(LMS) was introduced in [21] and further developed in [23]. In [22] coded-BKW
was introduced. Coded-BKW with sieving was introduced in [24] and improved in
[9, 28].

Since only the final noise level, not the type of steps, matters for the
distinguishers, we only use plain steps in this paper.

###  III-B Hypothesis Testing

Assume that we have reduced all but $k$ positions to 0, leaving $k$ positions
for the hypothesis testing phase. After the reduction phase we have samples on
the form

$b=\sum_{i=1}^{k}a_{i}\cdot s_{i}+e\Leftrightarrow b-\sum_{i=1}^{k}a_{i}\cdot
s_{i}=e,$ (3)

where $e$ is (approximately) rounded Gaussian distributed with a standard
deviation of $\sigma_{f}=2^{t/2}\cdot\sigma$ and mean 0. Now the problem is to
distinguish the correct guess $\mathbf{s}=(s_{1},s_{2},\ldots,s_{k})$ from all
the incorrect ones, among all $q^{k}$ guesses222After the secret-noise
transforming most of these hypotheses are almost guaranteed to be incorrect,
simplifying the hypothesis testing a bit.. For each guess $\hat{\mathbf{s}}$
we calculate the corresponding error terms in (3). For the correct guess the
observed values of $e$ are rounded Gaussian distributed, while for the wrong
guess they are uniformly random. How to distinguish the right guess from all
the wrong ones is explained in Section IV.

##  IV Distinguishers

For the hypothesis testing we study the optimal distinguisher, which is an
exhaustive search method; and a faster method based on the fast Fourier
transform.

###  IV-A Optimal Distinguisher

Let $D_{\hat{\mathbf{s}}}$ denote the distribution of the $e$ values for a
given guess of the secret vector $\hat{\mathbf{s}}$. As is shown in [29, Prop.
1] to optimally distinguish the hypothesis
$D_{\hat{\mathbf{s}}}=\mathcal{U}(0,q-1)$ against
$D_{\hat{\mathbf{s}}}=\bar{\Psi}_{\sigma_{f},q}$ we calculate the log-
likelihood ratio

$\sum_{e=0}^{q-1}N(e)\log\frac{\Pr_{\bar{\Psi}_{\sigma_{f},q}}(e)}{\Pr_{\mathcal{U}(0,q-1)}(e)}=\sum_{e=0}^{q-1}N(e)\log\left(q\cdot\Pr\nolimits_{\bar{\Psi}_{\sigma_{f},q}}(e)\right),$
(4)

where $N(e)$ denotes the number of times $e$ occurs for the guess
$\hat{\mathbf{s}}$, $\sigma_{f}$ denotes the standard deviation of the samples
after the reduction phase and $\Pr_{D}(e)$ denotes the probability of drawing
$e$ from the distribution $D$. We choose the value $\hat{\mathbf{s}}$ that
maximizes (4). The time complexity of this distinguisher is

$\mathcal{O}(m\cdot q^{k}),$ (5)

if we try all possible hypotheses. After performing the secret-noise
transformation of Section III-A3 we can limit ourselves to assuming that the
$k$ values in $\mathbf{s}$ have an absolute value of at most $d$, reducing the
complexity to

$\mathcal{O}(m\cdot(2d+1)^{k}).$ (6)

By only testing the likely hypotheses we have a lower risk of choosing an
incorrect one333as long as the correct one is among our hypotheses.. This
trick of limiting the number of hypotheses can of course also be applied to
the FFT method of Section IV-B, which we do in Section IV-D.

###  IV-B Fast Fourier Transform Method

For LWE, the idea of using a transform to speed up the distinguishing was
introduced in [10]. Consider the function

$f(\mathbf{x})=\sum_{j=1}^{m}\mathds{1}_{\mathbf{a}_{j}=\mathbf{x}}\theta_{q}^{b_{j}},$
(7)

where $\mathbf{x}\in\mathbb{Z}_{q}^{k}$,
$\mathds{1}_{\mathbf{a}_{j}=\mathbf{x}}$ is equal to 1 if and only if
$\mathbf{x}=\mathbf{a}_{j}$ and 0 otherwise, and $\theta_{q}$ denotes the
$q$-th root of unity. The idea of the FFT distinguisher is to calculate the
FFT of $f$, that is

$\hat{f}(\boldsymbol{\alpha})=\sum_{\mathbf{x}\in\mathbb{Z}_{q}^{k}}f(\mathbf{x})\theta_{q}^{-\left\langle\mathbf{x},\boldsymbol{\alpha}\right\rangle}=\sum_{j=1}^{m}\theta_{q}^{-(\left\langle\mathbf{a}_{j},\boldsymbol{\alpha}\right\rangle-
b_{j})}.$ (8)

Given enough samples compared to the noise level, the correct guess
$\boldsymbol{\alpha}=\mathbf{s}$ maximizes $\Re(\hat{f}(\boldsymbol{\alpha}))$
in (8).

The time complexity of the FFT distinguisher is

$\mathcal{O}(m+k\cdot q^{k}\cdot\log(q)).$ (9)

In general this complexity is much lower than the one in (5). However, it does
depend on the sparsity of the secret $\mathbf{s}$. For a binary $\mathbf{s}$,
the exhaustive methods are better.

From [10, Thm. 16] we have the following (upper limit) formula for the sample
complexity of the FFT distinguisher

$8\cdot\ln\left(\frac{q^{k}}{\epsilon}\right)\left(\frac{q}{\pi}\sin\left(\frac{\pi}{q}\right)e^{-2\pi^{2}\sigma^{2}/q^{2}}\right)^{-2^{t+1}},$
(10)

where $\epsilon$ is the probability of guessing $\mathbf{s}$ incorrectly.
Notice that the expression is slightly modified to fit our notation and that a
minor error in the formula is corrected444Using our notation $k$ should be
within the logarithm and not as a factor in front of it like in [10]..

###  IV-C Polynomial Reconstruction Method

In [22], a method combining exhaustive search and the FFT was introduced. It
achieves optimal distinguishing information theoretically, while being more
efficient than the optimal distinguisher. However, its complexity is roughly a
factor $q$ higher than the complexity of the FFT distinguisher.

###  IV-D Pruned FFT Distinguisher

Also when using an FFT distinguisher we can limit the number of hypotheses. We
only need a small subset of the output values of the FFT distinguisher in (8),
so we can speed-up the calculations using a pruned FFT. In general, if we only
need $K$ out of all $N$ output values, the time complexity for calculating the
FFT improves from $\mathcal{O}(N\log(N))$ to $\mathcal{O}(N\log(K))$ [30].
Limiting the magnitude when guessing the last $k$ positions of $\mathbf{s}$ to
$d$, this changes the time complexity from (9) to

$\mathcal{O}(m+k\cdot q^{k}\cdot\log(2d+1)).$ (11)

More importantly this method reduces the sample complexity. In the formula for
sample complexity (10), the numerator $q^{k}$ corresponds to the number of
values of $\mathbf{s}$ can take on the last $k$ positions. Re-doing the proofs
of [10, Thm. 16], limiting the magnitude of the guess in each position to $d$,
we get

$8\cdot\ln\left(\frac{(2d+1)^{k}}{\epsilon}\right)\left(\frac{q}{\pi}\sin\left(\frac{\pi}{q}\right)e^{-2\pi^{2}\sigma^{2}/q^{2}}\right)^{-2^{t+1}}.$
(12)

This reduced sample complexity comes at no extra cost.

##  V Equal Performance of Optimal and FFT Distinguishers

When starting to run simulations, we noticed that the FFT distinguisher and
the optimal distinguisher performed identically, in terms of number of samples
to correctly guess the secret. We explain this phenomenon in Appendix A555We
do, of course, not claim that this is true in general for distinguishing
distributions outside of our context of solving LWE using BKW..

There are two immediate effects of this finding.

  * •

The polynomial reconstruction method is obsolete.

  * •

Unless the secret is very sparse, the FFT distinguisher is strictly better
than the optimal distinguisher, since it is computationally cheaper.

Hence we limit our investigation to the FFT distinguisher from Section VI. We
do not make any claims about the equivalance between the sample complexity of
the two distinguishers outside of our context of solving LWE using BKW, when
having large rounded (or Discrete) Gaussian noise 666Although it could be
interesting to investigate..

##  VI Simulations and Results

This section covers the simulations we ran, using the FBBL library [31] from
[32], and the results they yielded. For all figures, each point corresponds to
running plain BKW plus distinguishing at least 30 times. For most points we
ran slightly more iterations. See Appendix B for details on the number of
iterations for all the points. We chose our parameters inspired by the
Darmstadt LWE Challenge [33].

The challenges are a set of (search) LWE instances used to compare LWE solving
methods. Each instance consists of the dimension $n$, the modulus $q\approx
n^{2}$, the relative error size $\alpha$ and $m\approx n^{2}$ equations of the
form (1). Our simulations mostly use parameters inspired by the LWE
challenges. We mostly let $q=1601$ (corresponding to $n=40$) and vary $\alpha$
to get problem instances that require a suitable number of samples for
simulating hypothesis testing. The records for the LWE challenges are set
using lattice sieving [34].

###  VI-A Varying Noise Level

In the upper part of Figure 1 we compare the theoretical sample complexity
from (10) with simulation results from an implementation of the FFT
distinguisher of [10] and our pruned FFT distinguisher. The latter
distinguisher guesses values of absolute value up to $3\sigma$, rounded
upwards. The simulated points are the median values of our simulations and the
theoretical values correspond to setting $\epsilon=0.5$ in (10). We use
$q=1601$, $n=28$, we take $t=13$ steps of plain BKW, reducing 2 positions per
step. Finally we guess the last 2 positions and measure the minimum number of
samples to correctly guess the secret. We vary $\alpha$ between 0.005 and
0.006. We use LF1 to guarantee that the samples are independent.

We notice that there is a gap of roughly a factor 10 between theory and
simulation. More exactly, the gap is a factor [10.8277, 8.6816, 10.1037,
8.6776, 10.5218, 10.1564] for the six points, counting in increasing order of
noise level.

We also see a gap between the FFT distinguisher and pruned FFT distinguisher.
We can estimate the gap by comparing (12) and (10). Counting in increasing
level of noise by theory we expect the pruned version to need [1.8056, 1.8056,
1.7895, 1.7743, 1.7598, 1.7461] times less samples for the 6 data points. The
numbers from the simulation were [2.0244, 1.8610, 1.8433, 2.1905, 2.0665,
2.2060], pretty close to theory.

###  VI-B Varying $q$

In the lower part of Figure 1 we show how the number of samples needed for
distinguishing varies with $q$. For $q$ we use the values [101, 201, 401, 801,
1601, 3201], for $\alpha$ we use the values [0.0896, 0.0448, 0.0224, 0.0112,
0.0056, 0.0028] and the number of steps were [5, 7, 9, 11, 13, 15]. Thereby
the final noise level and the original $\mathbf{s}$ vectors have almost the
same distribution, making the $q$ values the only varying factor. We use LF1
to guarantee that the samples are independent.

Notice that the number of samples needed to guess the secret is roughly an
order of magnitude lower than theory predicts, counting in increasing order of
$q$, the gain is a factor [11.4537, 10.6112, 9.2315, 10.4473, 9.5561, 9.7822]
for the six points.

Also notice that the pruned version is an improvement, that increases with
$q$. This is because the total number of hypotheses divided by the number of
hypotheses we make increases with $q$. By comparing (12) and (10), we expect
the improvement to be a factor [1.1303, 1.2871, 1.4563, 1.6152, 1.7743,
1.9334]. This is pretty close to the factors 1.1435, 1.4551, 1.6215, 1.8507,
2.0121, 2.3045] from simulation.

Figure 1: Theoretical values vs. simulated values.

###  VI-C LF1 vs LF2

We investigate the increased number of samples needed due to dependencies,
when using LF2. For LF2, depending on the number of samples needed for
guessing, we used either the minimum number of samples to produce a new
generation of the same size or a sample size roughly equal to the size needed
for guessing at the end. To test the limit of LF2 we made sure to produce
every possible sample from each category. See the upper part of Figure 2 for
details. The setting is the same as in Section VI-A. We only use the pruned
FFT distinguisher. Notice that the performance is almost exactly the same in
both the LF1 and the LF2 cases, as is generally assumed [11].

###  VI-D Sample Amplification

The lower part of Figure 2 shows the increased number of samples needed, due
to sample amplification. We use $q=1601$ and 1600 initial samples. We form new
samples by combining triples of samples to get a large enough sample size. We
vary the noise level between $\alpha=0.005/\sqrt{3}$ and
$\alpha=0.006/\sqrt{3}$. We take 13 steps of plain BKW, reducing 2 positions
per step. Finally we guess the last 2 positions and measure the minimum number
of samples needed to guess correctly. We use LF1 and we compare the results
against starting with as many samples as we want and noise levels between
$\alpha=0.005$ and $\alpha=0.006$, both tricks to isolate the dependency due
to sample amplification. We only use the pruned FFT distinguisher. The
difference between the points is small, implying that the dependency due to
sample amplification is limited.

Figure 2: Testing the effect of sample dependence.

##  VII Conclusions

We have shown that the FFT distinguisher and the optimal distinguisher have
the same sample complexity for solving LWE using BKW. We have also showed that
it performs roughly an order of magnitude better than the upper limit formula
from [10, Thm. 16]. Our pruned version of the FFT method improves the sample
complexity of the FFT solver, at no cost. Finally, we have indicated that the
sample dependency due to both LF2 and sample amplification is limited.

## References

  * [1] P. W. Shor, “Algorithms for quantum computation: Discrete logarithms and factoring,” in _35th Annual Symposium on Foundations of Computer Science_. Santa Fe, NM, USA: IEEE Computer Society Press, Nov. 20–22, 1994, pp. 124–134.
  * [2] “NIST Post-Quantum Cryptography Standardization,” https://csrc.nist.gov/Projects/Post-Quantum-Cryptography/Post-Quantum-Cryptography-Standardization, accessed: 2019-09-24.
  * [3] O. Regev, “On lattices, learning with errors, random linear codes, and cryptography,” in _37th Annual ACM Symposium on Theory of Computing_ , H. N. Gabow and R. Fagin, Eds. Baltimore, MA, USA: ACM Press, May 22–24, 2005, pp. 84–93.
  * [4] A. Blum, M. L. Furst, M. J. Kearns, and R. J. Lipton, “Cryptographic primitives based on hard learning problems,” in _Advances in Cryptology – CRYPTO’93_ , ser. Lecture Notes in Computer Science, D. R. Stinson, Ed., vol. 773. Santa Barbara, CA, USA: Springer, Heidelberg, Germany, Aug. 22–26, 1994, pp. 278–291.
  * [5] A. Blum, A. Kalai, and H. Wasserman, “Noise-tolerant learning, the parity problem, and the statistical query model,” in _32nd Annual ACM Symposium on Theory of Computing_. Portland, OR, USA: ACM Press, May 21–23, 2000, pp. 435–440.
  * [6] ——, “Noise-tolerant learning, the parity problem, and the statistical query model,” _J. ACM_ , vol. 50, no. 4, pp. 506–519, 2003. [Online]. Available: https://doi.org/10.1145/792538.792543
  * [7] M. R. Albrecht, R. Player, and S. Scott, “On The Concrete Hardness Of Learning With Errors,” _J. Mathematical Cryptology_ , vol. 9, no. 3, pp. 169–203, 2015.
  * [8] G. Herold, E. Kirshanova, and A. May, “On the asymptotic complexity of solving LWE,” _Des. Codes Cryptogr._ , vol. 86, no. 1, pp. 55–83, 2018. [Online]. Available: https://doi.org/10.1007/s10623-016-0326-0
  * [9] Q. Guo, T. Johansson, E. Mårtensson, and P. Stankovski Wagner, “On the asymptotics of solving the LWE problem using coded-bkw with sieving,” _IEEE Trans. Information Theory_ , vol. 65, no. 8, pp. 5243–5259, 2019\. [Online]. Available: https://doi.org/10.1109/TIT.2019.2906233
  * [10] A. Duc, F. Tramèr, and S. Vaudenay, “Better algorithms for LWE and LWR,” in _Advances in Cryptology – EUROCRYPT 2015, Part I_ , ser. Lecture Notes in Computer Science, E. Oswald and M. Fischlin, Eds., vol. 9056\. Sofia, Bulgaria: Springer, Heidelberg, Germany, Apr. 26–30, 2015, pp. 173–202.
  * [11] É. Levieil and P.-A. Fouque, “An improved LPN algorithm,” in _SCN 06: 5th International Conference on Security in Communication Networks_ , ser. Lecture Notes in Computer Science, R. D. Prisco and M. Yung, Eds., vol. 4116\. Maiori, Italy: Springer, Heidelberg, Germany, Sep. 6–8, 2006, pp. 348–359.
  * [12] P. Kirchner, “Improved generalized birthday attack,” Cryptology ePrint Archive, Report 2011/377, 2011, http://eprint.iacr.org/2011/377.
  * [13] B. Applebaum, D. Cash, C. Peikert, and A. Sahai, “Fast cryptographic primitives and circular-secure encryption based on hard learning problems,” in _Advances in Cryptology – CRYPTO 2009_ , ser. Lecture Notes in Computer Science, S. Halevi, Ed., vol. 5677. Santa Barbara, CA, USA: Springer, Heidelberg, Germany, Aug. 16–20, 2009, pp. 595–618.
  * [14] D. J. Bernstein and T. Lange, “Never trust a bunny,” Cryptology ePrint Archive, Report 2012/355, 2012, http://eprint.iacr.org/2012/355.
  * [15] Q. Guo, T. Johansson, and C. Löndahl, “Solving LPN using covering codes,” in _Advances in Cryptology – ASIACRYPT 2014, Part I_ , ser. Lecture Notes in Computer Science, P. Sarkar and T. Iwata, Eds., vol. 8873\. Kaoshiung, Taiwan, R.O.C.: Springer, Heidelberg, Germany, Dec. 7–11, 2014, pp. 1–20.
  * [16] Q. Guo, T. Johansson, and C. Löndahl, “Solving LPN using covering codes,” _J. Cryptology_ , vol. 33, no. 1, pp. 1–33, 2020. [Online]. Available: https://doi.org/10.1007/s00145-019-09338-8
  * [17] B. Zhang, L. Jiao, and M. Wang, “Faster algorithms for solving LPN,” in _Advances in Cryptology – EUROCRYPT 2016, Part I_ , ser. Lecture Notes in Computer Science, M. Fischlin and J.-S. Coron, Eds., vol. 9665. Vienna, Austria: Springer, Heidelberg, Germany, May 8–12, 2016, pp. 168–195.
  * [18] S. Bogos and S. Vaudenay, “Optimization of LPN solving algorithms,” in _Advances in Cryptology – ASIACRYPT 2016, Part I_ , ser. Lecture Notes in Computer Science, J. H. Cheon and T. Takagi, Eds., vol. 10031. Hanoi, Vietnam: Springer, Heidelberg, Germany, Dec. 4–8, 2016, pp. 703–728.
  * [19] S. Bogos, F. Tramèr, and S. Vaudenay, “On solving L P N using B K W and variants - implementation and analysis,” _Cryptography and Communications_ , vol. 8, no. 3, pp. 331–369, 2016. [Online]. Available: https://doi.org/10.1007/s12095-015-0149-2
  * [20] M. R. Albrecht, C. Cid, J.-C. Faugère, R. Fitzpatrick, and L. Perret, “On the complexity of the BKW algorithm on LWE,” _Designs, Codes and Cryptography_ , vol. 74, no. 2, pp. 325–354, 2015.
  * [21] M. R. Albrecht, J.-C. Faugère, R. Fitzpatrick, and L. Perret, “Lazy modulus switching for the BKW algorithm on LWE,” in _PKC 2014: 17th International Conference on Theory and Practice of Public Key Cryptography_ , ser. Lecture Notes in Computer Science, H. Krawczyk, Ed., vol. 8383. Buenos Aires, Argentina: Springer, Heidelberg, Germany, Mar. 26–28, 2014, pp. 429–445.
  * [22] Q. Guo, T. Johansson, and P. Stankovski, “Coded-BKW: Solving LWE using lattice codes,” in _Advances in Cryptology – CRYPTO 2015, Part I_ , ser. Lecture Notes in Computer Science, R. Gennaro and M. J. B. Robshaw, Eds., vol. 9215. Santa Barbara, CA, USA: Springer, Heidelberg, Germany, Aug. 16–20, 2015, pp. 23–42.
  * [23] P. Kirchner and P.-A. Fouque, “An improved BKW algorithm for LWE with applications to cryptography and lattices,” in _Advances in Cryptology – CRYPTO 2015, Part I_ , ser. Lecture Notes in Computer Science, R. Gennaro and M. J. B. Robshaw, Eds., vol. 9215. Santa Barbara, CA, USA: Springer, Heidelberg, Germany, Aug. 16–20, 2015, pp. 43–62.
  * [24] Q. Guo, T. Johansson, E. Mårtensson, and P. Stankovski, “Coded-BKW with sieving,” in _Advances in Cryptology – ASIACRYPT 2017, Part I_ , ser. Lecture Notes in Computer Science, T. Takagi and T. Peyrin, Eds., vol. 10624\. Hong Kong, China: Springer, Heidelberg, Germany, Dec. 3–7, 2017, pp. 323–346.
  * [25] A. Esser, R. Kübler, and A. May, “LPN decoded,” in _Advances in Cryptology – CRYPTO 2017, Part II_ , ser. Lecture Notes in Computer Science, J. Katz and H. Shacham, Eds., vol. 10402. Santa Barbara, CA, USA: Springer, Heidelberg, Germany, Aug. 20–24, 2017, pp. 486–514.
  * [26] A. Esser, F. Heuer, R. Kübler, A. May, and C. Sohler, “Dissection-BKW,” in _Advances in Cryptology – CRYPTO 2018, Part II_ , ser. Lecture Notes in Computer Science, H. Shacham and A. Boldyreva, Eds., vol. 10992\. Santa Barbara, CA, USA: Springer, Heidelberg, Germany, Aug. 19–23, 2018, pp. 638–666.
  * [27] C. Delaplace, A. Esser, and A. May, “Improved low-memory subset sum and LPN algorithms via multiple collisions,” in _17th IMA International Conference on Cryptography and Coding_ , ser. Lecture Notes in Computer Science, M. Albrecht, Ed., vol. 11929. Oxford, UK: Springer, Heidelberg, Germany, Dec. 16–18, 2019, pp. 178–199.
  * [28] E. Mårtensson, “The asymptotic complexity of coded-bkw with sieving using increasing reduction factors,” in _IEEE International Symposium on Information Theory, ISIT 2019, Paris, France, July 7-12, 2019_. IEEE, 2019, pp. 2579–2583. [Online]. Available: https://doi.org/10.1109/ISIT.2019.8849218
  * [29] T. Baignères, P. Junod, and S. Vaudenay, “How far can we go beyond linear cryptanalysis?” in _Advances in Cryptology – ASIACRYPT 2004_ , ser. Lecture Notes in Computer Science, P. J. Lee, Ed., vol. 3329. Jeju Island, Korea: Springer, Heidelberg, Germany, Dec. 5–9, 2004, pp. 432–450.
  * [30] H. V. Sorensen and C. S. Burrus, “Efficient computation of the dft with only a subset of input or output points,” _IEEE Transactions on Signal Processing_ , vol. 41, no. 3, pp. 1184–1200, 1993.
  * [31] A. Budroni, E. Mårtensson, and P. Stankovski Wagner, “FBBL - file-Based BKW for LWE,” https://github.com/FBBL/fbbl, 2020.
  * [32] A. Budroni, Q. Guo, T. Johansson, E. Mårtensson, and P. S. Wagner, “Making the bkw algorithm practical for lwe,” in _Progress in Cryptology – INDOCRYPT 2020_ , K. Bhargavan, E. Oswald, and M. Prabhakaran, Eds. Cham: Springer International Publishing, 2020, pp. 417–439.
  * [33] “TU Darmstadt Learning with Errors Challenge,” https://www.latticechallenge.org/lwe_challenge/challenge.php, accessed: 2020-09-30.
  * [34] M. R. Albrecht, L. Ducas, G. Herold, E. Kirshanova, E. W. Postlethwaite, and M. Stevens, “The general sieve kernel and new records in lattice reduction,” in _Advances in Cryptology – EUROCRYPT 2019, Part II_ , ser. Lecture Notes in Computer Science, Y. Ishai and V. Rijmen, Eds., vol. 11477\. Darmstadt, Germany: Springer, Heidelberg, Germany, May 19–23, 2019, pp. 717–746.

##  Appendix A Explaining the Optimimality of the FFT Distinguisher

Consider a sample on the form (3). By making a guess $\hat{\mathbf{s}}$ we
calculate the corresponding error term $\hat{e}$. The Fourier transform of the
FFT distinguisher in (8) can now be written as

$\sum_{j=1}^{m}\theta_{q}^{\hat{e}_{j}}.$ (13)

The real part (13) is equal to

$\sum_{j=1}^{m}\cos{(2\pi\hat{e}_{j}/q)}.$ (14)

The FFT distinguisher picks the guess that maximizes (14). Now, let us rewrite
(4) for the optimal distinguisher as

$\sum_{j=1}^{m}\log\left(q\cdot\Pr\nolimits_{\bar{\Psi}_{\sigma_{f},q}}(\hat{e}_{j})\right).$
(15)

It turns out that with increasing noise level, the terms in (15) can be
approximated as cosine functions with a period of $q$, as illustrated in
Figure 3. The terms correspond to $q=1601$, starting with rounded Gaussian
noise with $\alpha=0.005$, $\sigma=\alpha\cdot q=8.005$ and taking 12 or 13
steps of plain BKW respectively. Notice that the approximation gets
drastically better with increasing noise level777Also notice that the
approximation is not necessarily the best cosine approximation. It is simple
the approximation that matches the largest and the smallest value of the
curve.. The 13 step picture corresponds to the setting used in most of the
experiments in Section VI. For a large-scale problem, the noise level would of
course be much larger, resulting in an even better cosine approximation.

(a) Taking 12 plain BKW steps

(b) Taking 13 plain BKW steps

Figure 3: Approximating the terms in (15) as cosine functions.

Since both distinguishers pick the $\hat{\mathbf{s}}$ that minimizes a sum of
cosine functions with the same period, they will pick the same
$\hat{\mathbf{s}}$, hence they will perform identically.

##  Appendix B Number of Iterations in the Simulations

The following is a collection of lists of the number of iterations used for
each point to get the estimations of the median values in Figures 1-2. For
each figure and curve we list the number iterations from left to right in, in
other words in increasing level of noise level $\alpha$ or modulus $q$.

### Figure 1 \- Varying $\alpha$

Simulated FFT | 31 | 51 | 52 | 59 | 50 | 52
---|---|---|---|---|---|---
Simulated Pruned FFT | 33 | 41 | 56 | 35 | 30 | 49

### Figure 1 \- Varying $q$

Simulated FFT | 100 | 100 | 95 | 80 | 67 | 82
---|---|---|---|---|---|---
Simulated Pruned FFT | 100 | 100 | 95 | 80 | 67 | 82

### Figure 2 \- LF1 vs. LF2

LF1 | 33 | 41 | 56 | 35 | 30 | 49
---|---|---|---|---|---|---
LF2 | 43 | 46 | 69 | 37 | 69 | 50

### Figure 2 \- Unlimited vs. Sample Amplification

Unlimited Samples | 33 | 41 | 56 | 35 | 30 | 49
---|---|---|---|---|---|---
Sample Amplification | 37 | 59 | 38 | 45 | 47 | 40