Learning with Errors is easy with quantum samples
Alex B. Grilo Iordanis Kerenidis Timo Zijlstra


  
  
	
  ^1 IRIF, CNRS, Université Paris Diderot, Paris, France
  ^2 Lab-STICC, Université Bretagne Sud

  
    Learning with Errors is one of the fundamental problems in computational
    learning theory and has in the last years become the cornerstone of
    post-quantum cryptography. In this work, we study the quantum sample
    complexity of Learning with Errors and show that there exists an efficient
    quantum learning algorithm (with polynomial sample and time complexity) for the Learning with Errors problem where
    the error distribution is the one used in cryptography. While our quantum
    learning algorithm does not break the LWE-based encryption schemes proposed
    in the cryptography literature, it does have some interesting implications
    for cryptography: first, when building an LWE-based scheme, one needs to be
    careful about the access to the public-key generation algorithm that is given
    to the adversary; second, our algorithm shows a possible way for attacking
    LWE-based encryption by using classical samples to approximate the
    quantum sample state, since then using our quantum learning algorithm would
    solve LWE. Finally, we extend our results and show quantum learning algorithms for three related problems: Learning Parity with Noise, Learning with Rounding and Short Integer Solution.
  

  
    ^2
    
======



  [plain]
  

§ INTRODUCTION

  The large amount of data arising in the real world, for example through
  scientific observations, large-scale experiments, internet traffic, social
  media, etc, makes it necessary to be able to predict some general properties
  or behaviors of the data from a limited number of samples of the data. In this
  context, Computational Learning Theory provides rigorous models for learning
  and studies  the necessary and sufficient resources, for example, the number
  of samples or the running time of the learning algorithm. In his seminal work,
  Valiant <cit.> introduced the model of PAC
  learning, and since then this model has been extensively studied and has given rise to numerous extensions.

In another revolutionary direction, Quantum Computing takes advantage of the quantum nature of small-scale systems as a computational resource. In this
  field, the main question is to understand what problems can be solved more efficiently in a quantum computer than in
  classical computers. In the intersection of the two fields, we have Quantum Learning Theory, where we ask if quantum learning algorithms can be more efficient than classical ones. 

One of course needs to be careful about defining quantum learning and more precisely, what kind of access to the data a quantum learning algorithm has. On one hand, we can just provide classical samples to the quantum learning algorithm that can then use the quantum power in processing these classical data. In the more general scenario, we allow the quantum learning algorithm to receive quantum samples of the data, for a natural notion of a quantum sample as a superposition that corresponds to the classical sample distribution. 

More precisely, in classical learning, the learning algorithm is provided with samples of (x, f(x)),
  where x is drawn from some unknown distribution D and f is the function we wish to learn. The goal of the learner
  in this case is to output a function g such that with high probability (with
  respect to the samples received), f and g are close, i.e., f(x) 
  g(x) is small when x is drawn from the same distribution D.  

The extension of this model to the quantum setting is that the samples now are
  given in the form of a quantum state ∑_x√(D(x))|x⟩|f(x)⟩.
  Note that one thing the quantum learner can do with this state is simply
  measure it in the computational basis and get a classical sample from the distribution D. Hence, a
  quantum sample is at least as powerful as a classical sample. The main
  question is whether the quantum learner can make better use of these quantum samples and provide an advantage in the number of samples and/or running time compared to a classical learner. 


In this work we focus on one of the fundamental problems in learning theory, the Learning with Errors (LWE).
  In LWE,  one is given samples of the form
  
    (a, a· s + e q)

  where s ∈^n is fixed, a ∈^n is drawn uniformly at random and
  e ∈ is an 'error' term drawn from some distribution χ. The goal is to
  output s, while minimizing the number of samples used and the computation
  time.

First, LWE is the natural generalisation of the well-studied Learning Parity with Noise problem (LPN), which is the case of q=2. Moreover, a lot
  of attention was drawn to this problem when Regev <cit.> reduced
  some (expected to be) hard problems involving lattices to LWE. With this
  reduction, LWE has become the cornerstone of current post-quantum
  cryptographic schemes. 
  Several cryptographic primitives proposals such as Fully Homomorphic
  Encryption <cit.>, Oblivious Transfer <cit.>, Identity based
  encryption <cit.>,
  and others schemes are based in the hardness of LWE (for a more complete list
  see Ref. <cit.> and Ref. <cit.>).

  Classically, Blum et al. <cit.> proposed the first sub-exponential algorithm for
  this problem, where both sample and time complexities are  2^O(n/logn).
  Then, Arora and Ge <cit.> improved the time complexity for LWE with a learning
  algorithm that runs in 2^Õ(n^2) time, for some <
  1/2, and it uses at least Ω(q^2logq) 
  samples
  For LPN, 
  Lyubashevsky <cit.> has proposed an algorithm with sample complexity n^1+  at the
  cost of increasing computation time to O(2^n/loglogn).



§ THE QUANTUM LEARNING MODEL

  
  In this work, we use the model of learning under the uniform distribution where the learner receives 
  samples according to the uniform distribution and outputs the exact function
  with  high probability.
  In the quantum setting, the learning algorithm is given quantum samples, namely a
  uniform superposition of the inputs and function values, 
  
    ∑_x ∈ X1/√(|X|)|x⟩|f(x)⟩.

  
In this work, we are interested in noisy samples, that can be modeled by setting
f(x) = g(x) + e(x,r), where  g and e are deterministic functions, x ∈ X and r ∈ R is the randomness necessary to generate the noise. For defining the quantum sample, we start with the superposition
  
    1/√(|R|)∑_r ∈ R|r⟩(1/√(|X|)∑_x ∈ X|x⟩|g(x) + e(x,r)⟩),

  and then the register corresponding to the randomness is traced out. It means that with probability 1/|R| the quantum sample is  
  
    1/√(|X|)|x⟩|g(x) + e(x,r)⟩,

  for each possible value r ∈ R.

We consider the noise model defined in Bshouty and Jackson <cit.>, where
 independent noise is added for each element in the superposition, in other words, r = (r_1,...,r_|X|) and e(x,r) = e'(r_x). This model is a natural generalisation for quantum samples with noise since it can be
  seen as a superposition of the classical samples. 
 
 In contrast, Cross et al. <cit.> proposed a noise function that is independent of x. 
Although our noise model might require exponentially more resources to implement quantum samples, we show that this does not make the problem intractable. Also, this
  is the kind of state we would get after solving the index erasure problem.


  

§ OUR CONTRIBUTIONS

  In this work we study quantum algorithms for solving LWE with quantum samples. Let us be more explicit on the definition of a quantum sample for the LWE problem. We assume that the quantum learning algorithm receives samples in the form

  
    1/√(q^n)∑_a ∈^n|a⟩|a · s
        + e_a q⟩ ,

    where e_a are iid random variables from some distribution
    χ over . 

As expected, the performance of the learning algorithm, both in the classical and quantum case, is
  sensitive to the noise model adopted, i.e. to the distribution χ. When LWE is used in cryptographic schemes, the distribution χ has support on a small interval around 0, either uniform or a discrete gaussian. We prove that for such distributions, there exists an efficient quantum learner for LWE.



Main Result[informal]
For error distributions χ used in cryptographic schemes, and for any
η>0, there exists a quantum learning algorithm that solves LWE with probability 1-η using O(n log1/η) samples and running time poly(n,log1/η).



Another interesting feature of our quantum learner is that it is conceptually a
very simple algorithm based on one of the basic quantum operations, the Quantum
Fourier Transform. Such algorithms have even started to be implemented, of
course for very small input sizes and for the binary case <cit.>. Nevertheless, as far as quantum algorithms are concerned, our learner is quite feasible from an implementation point of view.

  The approach to solve the problem is a generalisation of
  Bernstein-Vazirani algorithm <cit.>: we start with a quantum sample,
  apply a Quantum Fourier Transform over  on each qudit, and then, we measure in the computational
  basis. Our analysis shows that, when the last qudit is not 0, which happens with high probability, the value of the remaining registers gives s with constant probability. We can then repeat this process so that our algorithm outputs s with high probability.

  We also use the same technique in quantum learning algorithms for three related problems.
  First, we generalise the result proposed by Cross et al. <cit.> and
  Ristè et al. <cit.> for
  the LPN problem. The main difference with their work is that we start with a
  quantum sample, i.e. a state where the noise is independent for each element
  in the superposition. Second, we show how to solve the Learning with Rounding
  problem, which can be seen as a derandomized version of LWE. Finally, we also
  propose a quantum learning algorithm for another relevant problem in
  cryptography, the Short Integer Solution problem.

  

 §.§ Related work

  We now review some results on quantum algorithms for learning problems. For a
  more extended introduction, see the survey by Arunachalam and de Wolf <cit.>.

  The first approach on trying to solve learning problems with quantum samples
  was proposed by  Bshouty and Jackson <cit.>, where they prove that DNFs can be learned
  efficiently, even when the samples are noisy.  No such efficient learners are
  known classically.
 
  Despite not presenting it as a learning problem, Bernstein and Vazirani <cit.>
  show how to learn parity using a single quantum sample, while classically we
  need a linear number of samples.

  Some years later, Servedio and Gortler <cit.> showed that classical
  and quantum sample/query complexity of learning problems are polynomially
  related, but they showed that for time complexity there exist exponential
  separations between classical and quantum learning (assuming standard
  computational hardness assumptions).

  Then, Ambainis et al. <cit.>, Atici and Servedio <cit.>,
  and Hunziker et al. <cit.> provided general upper
  bounds on the query complexity for learning problems that depend on the size
  of the concept class being learned.

  On specific problems, Atici and Servedio <cit.> and Belovs
  <cit.> provided quantum algorithms for learning juntas and Cross et
  al. <cit.> proposed and implemented quantum algorithms for
  LPN in a different noise model.
  
  Recently, Arunachalam and de Wolf <cit.> proved optimal bounds
  for the quantum sample complexity of the Quantum PAC model.


 

 §.§ Relation to LWE-based cryptography

 
 As we have mentioned, LWE is used in cryptography for many different tasks. Let us briefly describe how one can build an encryption scheme based on LWE <cit.>. 
 The key generation algorithm produces a secret key s ∈, while the public key
  consists of a sequence of classical LWE samples (a_1, a_1 · s + e_1
  q), ..., (a_m,
  a_m · s + e_m  q ), where the error comes from a distribution with support in a small interval around 0. For the encryption of a bit b, the party picks a
  subset S of [m] uniformly at random and outputs 
  
    (∑_i ∈ S a_i  q , b⌈q/2⌉ +  ∑_i ∈ S a_i · s +
      e_i  q).

  For the decryption, knowing s allows one to find b. The security analysis of the encryption scheme postulates that if an adversary can break the encryption efficiently then he is also able to solve the LWE problem efficiently. 

The algorithm we present here does not break the above LWE-based
encryption scheme. Nevertheless, it has interesting implications for cryptography.

First, our algorithm shows a possible way for attacking LWE-based encryption: use classical samples to approximate the quantum sample state, and then use our algorithm to solve LWE. One potential way for this would be to start with m classical samples and create the following superposition
  
    ∑_S ⊆ [m]|S⟩|∑_i ∈ S a_i  q⟩|∑_i ∈ S a_i · s +
      e_i  q⟩.

  This operation is in fact efficient. Then, in order to approximate the quantum sample state, one would need to 'forget' the first register that contains the index information about which subset of the m classical samples we took. In the most general case, such an operation of forgetting the index of the states in a quantum superposition, known as index-erasure
  (see Aharonov and Ta-Shma <cit.> and Ambainis et al. <cit.>), is exponentially hard,
  and a number of problems, such as Graph Non-isomorphism, would have an
  efficient quantum algorithm, if we could do it efficiently. Nevertheless, one
  may try to use the extra structure of the LWE problem to find sub-exponential algorithms for this case.
  
A second concern that our algorithm raises is that  when building an LWE-based scheme, one needs to be careful on the access to the public-key generation algorithm that is given to the adversary. It is well-known that for example, even in the classical case, if the adversary can ask classical queries to the LWE oracle, then he can easily break the scheme: by asking the same query many times one can basically average out the noise and find the secret s. However, if we just assume that the public key is given as a box that an agent has passive access to it, in the sense that he can request a random sample and receive one, then the encryption scheme is secure classically as long as LWE is difficult. However, imagine that the random sample from LWE is provided
  by a device that creates a superposition 
    1/√(q^n)∑_a ∈^n|a⟩|a · s
    + e_a q⟩ and then measures it. 
Then a quantum adversary that has access to this quantum state can break the scheme. Again, our claim is, by no means, that our algorithm breaks the proposed LWE-based encryption schemes, but more that LWE-based schemes which are secure classically (assuming the hardness of LWE) may stop being secure against quantum adversaries if the access to the public key generation algorithm becomes also quantum. 

  A similar situation has also appeared in the symmetric key cryptography with the so called 
  superposition attacks <cit.>.
  There, the attacker has the ability to query the encryption oracle in
  superposition, and in this way, she can in fact break many schemes that are assumed to be secure classically. 
While in the case of symmetric cryptography, the attacker must have quantum access to the encryption oracle in order to break the system, our results show that in the case of LWE-based public-key encryption, the attacker must have quantum access to the public key generation algorithm.  




§ ALGORITHM FOR LWE

In this section we present the extension of the Bernstein-Vazirani algorithm for
higher order fields and analyse its behaviour with LWE samples.

We show now the Field Bernstein-Vazirani algorithm <cit.> and its main component is the  Quantum Fourier Transform over ,
  QFT|j⟩ = 1/√(q^n)∑_k = 0^q^n - 1ω^jk|k⟩.

[1ex]0.450.5pt

Field Bernstein-Vazirani algorithm

Input: |ψ⟩∈ (^2)^⊗ n+1

Output: s̃∈^n ∪{⊥}

Apply QFT^⊗ n+1  on |ψ⟩.

Measure in the computational basis

Let |j⟩|j^*⟩ be the output

If   j^*  0, return -(j^*)^-1j q

      Else, return ⊥

[1ex]0.450.5pt

For warming-up, we show the behaviour of Field Bernstein-Vazirani for learning
linear functions without noise in <Ref> and then in
<Ref> we analyse it for LWE samples. 

  

 §.§ Quantum algorithm for learning a linear function without error
 
If the input |ψ⟩ is a noiseless quantum sample of a linear function, 
namely
  
    |ψ⟩ = 1/√(q^n)∑_a ∈^n|a⟩|a · s q⟩,

Then the Field-Bernstein Vazirani outputs the correct value with probability
q-1/q: after applying the QFT on each qudit of <ref>,  we get
  the state
  
    1/q^n+1/2∑_a,j ∈^n∑_j^*∈ω^a · (j + j^*s)|j⟩|j^*⟩.

  It is not hard to see that the probability that for all i ∈ [n], we have
  j = -j^*s q and j^*  0 is
    
    1/q^n+∑_j^* ∈^*∑_a ∈^nω^0|-j^*s q⟩^2
        
        
        
             =q-1/q.


  Therefore, if j^*  0, we can retrieve s by outputting
  -(j^*)^-1 j_i (all operations mod q). 
 
 

 §.§ Analysis of the algorithm for noisy samples

 

In this section we show that the Field Bernstein-Vazirani algorithm works even
if the input is noisy.  Instead of the superposition of all elements in ^n,
we prove our result here for a more general case
where the quantum sample has the form

    |ψ⟩ = 1/√(v)∑_a ∈ V|a⟩|a· s + e_a (mod   q)⟩,
 
where v ∈ [q^n] is a fixed value, V be a random subset of ^n of size
v and e_a is a random noise. In this case, for every quantum sample, a new subset V of size v is picked independently at random. 


 
Fix v ∈ [q^n].  Let V ⊆^n be a random subset of ^n such that |V| = v, and let 
    
    |ψ⟩ = 1/√(v)∑_a ∈ V|a⟩|a· s + e_a (mod   q)⟩,
 
    where the e_a are random variables with absolute value at most k.
The Field Bernstein-Vazirani(|ψ⟩) outputs s with probability
v/20kq^n.

  
     If we apply QFT on the state |ψ⟩, we have
  
    1/√(q^n+1v)∑_a ∈
        V∑_j∈^n, j^* ∈ω^e_a j^* + a · (j + j^*s)|j⟩|j^*⟩.


From the last equation, we have that the probability that j =
    -j^*s q and j^*  0 is:
     
    1/q^n+1v∑_a ∈
        V∑_j^* ∈^*ω^e_a j^*|-j^*s q⟩|j^*⟩^2  
       =
          1/q^n+1v∑_j^* ∈^*( ∑_a ∈ Vℜ(ω^e_a j^*)
     
           )^2
          + ( ∑_a ∈ V
           ℑ(ω^e_a j^*)
           )^2
          
       ≥1/q^n+1v(
           ∑_a ∈ Vℜ(ω^e_a j^*)
           
           )^2 
       ≥
    
    
           γ vcos(2πγ)^2/kq^n.

    where γ∈ (0, 1/4) ℜ(z) and ℑ(z) are
    the real and imaginary part of z, respectively. For the first inequality, 
    we have removed some positive
    quantities, and the last inequality follows from the fact that
    ℜ(ω^e_a j^*) ≤cos(2πγ)
for j^* ≤ and 
e_a≤. The result follows by maximizing the quantity over all
    γ∈ (0, 1/4).

We now propose an algorithm that tests a candidate solution.

 

[1ex]0.450.5pt

Test Candidate

Input: s̃∈^n, M ∈^+

Output: Accept/reject

Repeat M times.

	Pick sample  |ψ⟩ =  1/√(v)∑_a ∈ V|a⟩|a · s + e_a  q⟩.	

  Measure the sample in the computational basis
  
  Let (a', a'· s + e_a') be the output

   If |a'· s + e_a' - a'·s̃| > k, reject

Accept

[1ex]0.450.5pt

 
For s̃ = s, Test Candidate(s̃, M) accepts with probability 1,  while for 
    s̃ s, Test Candidate(s̃, M) accepts 
    with probability probability at most (2k+1/q)^M. 


  Since
   |a'· s + e_a' - a'· s| = |e_a'| ≤ k by the noise
   distribution, it follows that the
   test passes with probability 1 when s̃ = s.

For a value a' picked uniformly random from  ^n, it follows that a' · (s - s̃) + e_a' q
  is uniformly distributed over _q
if s̃≠ s. Therefore, the probability that 
  it lies in the interval [-k, k] is 2k+1/q. Since the
  probability is independent for every iteration, the probability that
  s̃ is accepted on M iterations is 
  (2k+1/q)^M.


In <Ref>, we show how to use the previous algorithms to achieve
the following theorem.

 
   
    For dimension n, let q be a prime in the interval [2^n^γ,
    2· 2^n^γ).  Let 
    
    |ψ⟩ = 1/√(q^n)∑_a ∈^n|a⟩|a · s + e_a⟩,
 
    where the e_a are random variables drawn from a noise
    distribution with noise magnitude at most 
    k = poly(n). There is an algorithm that outputs s with probability 1 - η with sample complexity O(klog1/η) and running time poly(n, log1/η).
 

We show then how to extend the result to related problems in
<Ref>.



§ OPEN PROBLEMS




 §.§ Generalizing from linear functions

Learning linear functions can be seen as finding a hidden subgroup H = a | a
· s = 0 of _q^n. Efficient algorithms for general Abelian Hidden Subgroup Problem are known <cit.><cit.>, and we leave as an open question if these algorithms are also tolerant to noise.



 §.§ LWE over rings
 
Due to technical reasons regarding the representation of polynomials in Ring-LWE
instances (see  <Ref> for more details), our LWE algorithm cannot be used to solve Ring-LWE with quantum samples and we leave this question as an open problem.



§ ACKNOWLEDGMENTS


AG and IK thank Ronald de Wolf for helpful discussions. AG thanks also Lucas
Boczkowski, Brieuc Guinard, François Le Gall and Alexandre Nolin for helpful
discussions. Supported by ERC QCC and  French Programme d’Investissement
d’Avenir RISQ P141580.



[references]


[plain]
  
  

§ NOTATION

  For n ∈ℕ, we define  [n] := {1, ..., n}.
  For a complex number x = a + ib, a,b ∈, we define its norm |x| by
  √(a^2 + b^2), its real part ℜ(x) = a and its imaginary part
  ℑ(x) = b. We denote ω as the q-th root of unity, where q
  will be clear by the context.
  For a field  and element a ∈, we denote |a| as the unique value
  b ∈[-(q-1)/2, q-1/2] such that b ≡ a q. 

  We remind now the notation for quantum information and computation. For
  readers not familiar with these concepts we refer Ref. <cit.>.  Let {e_i} be the standard basis for the
  q-dimensional Hilbert space ℂ^q. We denote here |i⟩ = e_i
  and a q-dimensional qudit is a unit vector in this space, i.e.
  |ψ⟩ = ∑_i ∈α_i|i⟩, for α_i ∈ℂ and
  ∑_i ∈α_i^2 = 1. We call the state a qubit when q =
  2. A k-qudit quantum state is
  a unit vector in the complex Hilbert space ^q^k and we shorthand
  the basis states for this space |i_1⟩⊗...⊗|i_k⟩ with
  |i_1⟩...|i_k⟩.

 


§ AN EFFICIENT QUANTUM LEARNING ALGORITHM FOR LWE

  
 In this section we show how to use <Ref> in order to solve solve LWE
 with quantum samples using noise distributions proposed in
  Brakerski and Vaikuntanathan <cit.>, proving
  <Ref>. There, the field order q is sub-exponential in the
dimension n, generally in [2^n^γ,2· 2^n^γ) for some constant γ∈ (0,1), while the noise
distribution χ produces samples with magnitude at most polynomial in n
(for instance linear).


[1ex]0.450.5pt

LWE Algorithm(L, M)

Input: L, M ∈^+

Output: s̃∈^n ∪{⊥}

Repeat L times:

Pick a quantum sample |ψ⟩ 

 Run the Field Bernstein-Vazirani(|ψ⟩) to get output s̃

 Run Test Candidate(s̃, M)

If s̃ passes the test, return s̃

Return ⊥.

[1ex]0.450.5pt



LWE Algorithm(L, M) outputs s with probability

    1 - (1-v/20kq^n)^L - (3k/q)^M L.



LWE Algorithm(L, M) does not output s if either  Test Candidate(s̃, log1/η)  accepts some s̃ s before an iteration where Field Bernstein-Vazirani outputs  s, or LWE Algorithm outputs ⊥. We can upper bound the probability of this event by the probability  that at least one of L independent calls to Test Candidate(s̃, log1/η) accepts some s̃ s or that L independent calls to Field Bernstein-Vazirani do not output s. 

From <Ref> and using the union bound, the probability that at least one of L independent calls to Test Candidate(s̃, log1/η) accepts  some s̃ s  is at most
  
    (2k+1/q)^M L ≤(3k/q)^M L.


From <Ref>, the probability that s is not the output of L independent calls to Field Bernstein-Vazirani is at most
  
    (1-v/20kq^n)^L.



  
By union bound, LWE Algorithm(L, M) does not output s with probability at most
  
    (1-v/20kq^n)^L + (3k/q)^M L.



<Ref> follows directly from <Ref> and picking v = q^n,  L = 20k ln1/η and M = 1.



§ QUANTUM LEARNING COMPLEXITY OF RELATED PROBLEMS


In this section we present learning algorithms for problems that are related to LWE.





 §.§ Learning parity with noise

We show here our result for Learning Parity with Noise (LPN) problem,
which is the LWE problem for q=2. 

Here, the parity bit is flipped independently for
each element in the superposition with probability η. This
is the same noise model proposed by Bshouty and Jackson <cit.>. Note
that Cross et al. <cit.> studied LPN with different noise models. In
the first, all parities in the superposition are flipped at the same time with
probability η. In the second one, each qubit passed through a depolarising
channel. Our algorithm and analysis also works for both of the noise models proposed by
Cross et al. <cit.>.

The algorithm is the same as in the previous section, where now the QFT is over
 (also called the Hadamard Transform H). 


    
    Let 
    1/√(2^n)∑_a ∈{0,1}^n|a⟩|a · s  + e_a 2⟩
    be a quantum sample where e_a are iid random variables with value 0 with
    probability 1-η and 1 with probability η.

    For every constant 0 < δ < 1, applying a Hadamard transform on all qubits and measuring them in the computational
     basis, provides an outcome |j⟩|j^*⟩, where j ∈{0,1}^n and j^* ∈{0,1} such that 
     with probability exponentially close to 1, j = s≥1/2 (1-δ)^2(1-2η)^2.

  
  If we apply Hadamards on each qubit of the sample state, we have
  
    1/2^n+1/2∑_a ∈{0,1}^n∑_j∈{0,1}^n+1 
        (-1)^e_aj^* + a ·(j + j^*s)|j⟩|j^*⟩


   We now calculate the probability 
    that j^* = 1 and the first qubits are in the state |s⟩: 

    
    1/2^n+∑_a ∈{0,1}^n 
          (-1)^e_a  + a · (s + s)|s⟩^2
          
       = 1/2^2n+1(∑_a ∈{0,1}^n  (-1)^e_a)^2


  From the distribution of each e_a, we have that 
    (-1)^e_a is 1 w.p. 1-η and -1 w.p. η, independently. Therefore (-1)^e_a = 1-2η
  and using Hoeffding's bound  we have that
    
    ∑_a ∈{0,1}^n (-1)^e_a≤ (1-δ)(1-2η)2^n
       <e^δ^2 (1-2η)^2 2^2n/4


  Therefore, with probability exponentially close to 1, the probability that
  j = s is at least
  
    1/2^2n+1 ((1-δ)(1-2η)2^n)^2 = 
        1/2(1-δ)^2(1-2η)^2.



We can test a candidate solution s̃ in the lines of <Ref> and then repeat
the process a linear number of times, and in this case the algorithm can find
the right s with probability exponentially close to 1.




 §.§ LWE over rings



The Ring-LWE problem<cit.>, a variant of LWE over the ring of polynomials, has been proposed in order to improve the performance of cryptographic constructions using LWE, at the cost of needing
stronger assumptions for proving its hardness.

The Ring-LWE problem uses the structure of the ring ℛ_q = ℛqℛ for a prime q, ℛ = ℤ[x]f(x) and a cyclotomic polynomial f(x). 
As in LWE, a Ring-LWE sample is the pair (a, as + e q) for random s,a
∈ℛ_q and e is picked according to some error distribution χ.

Unfortunately, our algorithm cannot be used to solve Ring-LWE with the noise model proposed by Bshouty et al. <cit.>, due to technical issues on representing the polynomials.
In order to use the quantum learning algorithm for LWE, we need to find an isomorphism ϕ from ℛ_q to ℤ_q^n, where n = φ(m) is the number of invertible elements modulo m.
With this isomorphism, we can consider a sample (a, as+e) ∈ℛ_q^2 as two vectors in ℤ_q^n, and a superposition of quantum states representing these vectors can be written as:

    |ψ⟩ = 1/√(q^n)∑_a ∈ℛ_q|ϕ(a)⟩|ϕ(as + e_a)⟩,

and applying the QFT over every register of this state results in 

    QFT^⊗ 2n|ψ⟩
       = 1/√(q^3n)∑_a ∈ℛ_q∑_x,y ∈ℤ_qω^ϕ(a) · x|x⟩⊗ω^ϕ(as + e_a) · y|y⟩
       = 1/√(q^3n)∑_a ∈ℛ_q∑_x,y ∈ℤ_qω^ϕ(a)·(x+yϕ(s)) + y·ϕ(e_a)|x⟩|y⟩,

where the second equality holds because ϕ is a homomorphism.

We consider two ways of representing elements in ℛ_q as integer vectors.
The first one consists of identifying a polynomial in ℛ_q with the vector containing its coefficients. However, this 
coefficient embedding is not a homomorphism to _q^n, and the following identity, used in <ref>, does not hold

    ϕ(a)· x + ϕ(a· s + e_a)y = ϕ(a)(x + yϕ(s)) + y ϕ(e_a).


Therefore, this representation of polynomials cannot be used within our learning algorithm.

The second way of representing a polynomial is through the map 

    ϕ(p(x)) = (p(ω_m), …, p(ω_m^m-1)),

where  ω_m ∈ℤ_q be a primitive m-th root of unity.
This map is particularly interesting since multiplication  ℤ_q^n is done component-wise<cit.>
and therefore it can be used in implementations of Ring-LWE with efficient multiplication<cit.>.
However, in these constructions, the error is sampled from a distribution over
polynomials with small coefficients and when after applying the isomorphism,
ϕ(e_a) can be arbitrarily large in ℤ_q^n which cannot be handled
by our algorithm if the error is independent for each element in the
superposition.

 

Finally, we show now how to do solve Ring-LWE for the error model presented in Cross et al. <cit.>, namely, the noise is the same for all elements in the superposition.

Let ϕ be any isomorphism from ℛ_q to ℤ_q^n. We can map the original quantum sample using ϕ resulting in 

    1/√(q^n)∑_a ∈ℛ_q|ϕ(a)⟩⊗|ϕ(as + e)⟩.

and using the Field Bernstein-Vazirani algorithm on this state we have

    QFT^⊗ 2n|ψ⟩
       = 1/√(q^3n)∑_a ∈ℛ_q∑_x,y ∈ℤ_qω^ϕ(a) · x|x⟩⊗ω^ϕ(as + e) · y|y⟩
       = 1/√(q^3n)∑_y∈_qω^y·ϕ(e)∑_a ∈ℛ_q∑_x ∈ℤ_qω^ϕ(a)·(x+yϕ(s)))|x⟩|y⟩.

By measuring the last register, the error becomes a global phase and we are able to retrieve s as shown in <Ref>.



 §.§ Learning with Rounding

LWE has been used in the construction of several cryptographic primitives.
However, its usage sometimes is limited. For instance, in the implementation of
pseudo-random functions, the output must use little or no randomness, which does
not correspond to the inherent randomness in
LWE's input.

For this purpose, Banerjee, Peikert and Rosen<cit.> proposed a derandomized version of LWE called Learning with Rounding (LWR), which does not compromise hardness. LWR has been used in the construction of pseudo-random functions <cit.> and deterministic public key encryption <cit.>. 


The main idea of LWR consists in replacing a · s + e_a
by the 'rounding' of a· s  with respect to some modulus p≪ q, which can be seen as a “deterministic noise”.
More precisely, the rounding function is defined as follows:

    ⌊·⌉_p : ℤ_q    →ℤ_p,  with⌊ x ⌉_p  = ⌊p/qx ⌉p.

An LWR sample is then given by (a, ⌊ a · s ⌉_p) for some a sampled from the uniform distribution on ^n. 


 Let 
    
    |ψ⟩ = 1/√(q^n)∑_a ∈^n|a⟩|⌊ a · s ⌉_p⟩,
 
    be a quantum LWR sample. Let |ϕ⟩ be the state when we multiply the
    last register of |ψ⟩ with q/p. The Field Bernstein-Vazirani(|ϕ⟩) outputs s with probability
     at least p/12(q-1).


For a fixed a,  we have that

    q/p⌊ a · s ⌉_p  = a· s + (q/p⌊ a · s ⌉_p - a· s)q .

Since -q/2p≤q/p⌊ a · s ⌉_p - a· s ≤q/2pq, 
the result follows by 
<Ref> for  k = q/2p.

	


 §.§ Quantum Samples for SIS problem
	
We present in this section a learning algorithm for another relevant problem in cryptography, the Short Integer Solution problem.  As the name indicates, the Short Integer Solution problem (SIS) consists in finding a short integer solution for a  system of linear equations, and we present now its formal definition.


Given a random matrix A ∈^m × n, a random vector z ∈^m, the SIS_n,m,q,β problem is to find a
  vector x ∈^n such
  that Ax = z q with x < β. 


As in the LWE case, the hardness of SIS is also proved through the reduction of
(expected to be) hard lattice problems <cit.><cit.><cit.><cit.>.
We remark that if we drop either the constraint of
having an integer solution or having a short solution, the problem
can be easily solved using Gaussian Elimination. 

The SIS problem and its variants have been used to prove security of
constructions of signature schemes <cit.><cit.>, and hash
functions <cit.>. In these schemes, samples in the form (A, Av) are
public, where v is a small random vector and A is a random matrix.

Inspired in the LWE case,  we can define a quantum sample for SIS problem as

    |ψ⟩ = 1/√(q^nm)∑_A ∈^m× n|A⟩|Av⟩q,

and we are interested in the sample complexity of finding the (fixed) short solution v. Using Field Bernstein-Vazirani brings the same problem of Gaussian Elimination: there is no guarantee of finding a short solution instead of an arbitrary one.

We notice that tracing out m-1 rows of A and the corresponding positions of Av, we remain with

    1/√(q^n)∑_a ∈^n|a⟩|a· v⟩,

and we show an algorithm that works even for this type of quantum sample.

The algorithm consists by testing all possible values j ∈{-k,...,k} of -v_i. The test on j = -v_i passes with probability 1, while the test rejects with constant probability for j  -v_i. By repeating the test L times, the probability of finding the correct value is amplified.

[1ex]0.450.5pt
 

SIS Algorithm(L)

Input: L ∈^+

Output: ṽ∈^n

For i ∈ [n] do:

For j ∈{-k,...,k} do:

 For l ∈ [L]:

  Pick a quantum sample 1/√(q^n)∑_a ∈^n|a⟩|a· v⟩.

 Add ja_i to the last register

  Apply QFT on the i-th qudit of a and measure it

  Test next value of j if outcome is not |0⟩

 Set ṽ_i = -j and continue with the next value of i.

Output ṽ

[1ex]0.450.5pt


Let v ∈^n whose coefficients are all smaller in absolute value than some bound k. Given the quantum samples in the form

    |ψ⟩ = ∑_a ∈^n|a⟩|a· v⟩,
  
SIS Algorithm(L) outputs v with probability 
1-2km/q^L.


We start by doing the analysis of SIS algorithm for i = 1.
After adding ja_1 to the last register of the quantum sample, we have
  
    1/√(q^n)∑_a ∈^n|a⟩|a· v + a_1j⟩
       = 1/√(q^n)∑_a_1 ∈∑_a∈^n-1|a_1⟩|a⟩|a_1 (v_1+j) + a·v⟩.


If j = -v_1, then the previous state is the product state

    1/√(q)∑_a_1 ∈|a_1⟩⊗1/√(q^n-1)∑_a∈^n-1|a⟩|a·v⟩.

and since QFT∑_a_1 ∈|a_1⟩ = |0⟩, the test passes for all l ∈ [L].

On the other hand,  if j  -v_1, then the state is entangled, and the reduced density matrix of the first register is

    1/q∑_a_1 ∈a_1.

In this case, after applying the QFT on the first register and measuring it, the output is |0⟩ with probability 1/q. Therefore,  we have ṽ_1 = -j if for all L independent samples the  measurement outcome after the QFT is |0⟩, and this happens with probability 1/q^L.
By the union bound, the probability that the test passes for any value j  -v_i is at most 2k/q^L.

Finally, the previous analysis holds for every i ∈ [n]. Since  
 v ṽ iff there exists an i ∈ [n] such that ṽ_i  v_i, we can use union bound again to show that  this happens with probability  at most 2km/q^L.


By picking L = max{1, log2km/η/log q}, the algorithm outputs the correct v with probability at least 1 - η.



[references]

