Page 115 - Kaleidoscope Academic Conference Proceedings 2024
P. 115

Innovation and Digital Transformation for a Sustainable World





           ⟨  ,   ⟩ and the secret    would result in either 0 or      ,  Since we have used redundant dimensions our c matrix
                                                         2
           depending on the encrypted bit. Consequently, the decryption  which is (A.s + e) doesn’t show the exact results for all the
           process remains consistently accurate.  Thus, decryption  dimensions rather it shows the lattice of (n - M) dimensional
           errors only arise if the summation of error terms across all  lattice with error so that the original c matrix is hard to
           secrets exceeds      . Given that we sum at most    normal  retrieve which will affect the lattice reduction technique to
                        4
           error terms, each with a standard deviation     , the standard  guess the correct set of vector and for even with the efficient
                                           √
                                                                                              2
           deviation of the sum remains at most         <      . An  algorithm it would take more than O(   ) to search for each
                                                   log   
           analysis confirms that the likelihood of such a normal variable  possibility. Even if it guessed the dimensions and got some c
                                                                                            ∗
           surpassing      is negligible.                     the condition of success will be Let    be the projection of   
                    4
           Now, let’s delve into the security proof, demonstrating  orthogonally onto the first    −   vectors of the Gram-Schmidt
                                                                    ∗
           the system’s resilience according to the LWE assumption.  basis    .
           Assume vulnerability to chosen plaintext attacks, signifying  BKZ-like algorithms will call an SVP oracle on the last block
           that for a non-negligible portion of secrets   , there exists an  of dimension   .
           efficient method to accurately predict the encrypted bit, given  If    ∗  is the shortest vector in that block, it will be found.
                                                                   −  
                                                                 ∗
           a public key (      ,       )      selected from the LWE distribution  If    is the shortest vector for all projections up to    −   , it
                             =1                                    
           and encryption of a random bit as described earlier, with a  will “travel to the front”.
                                                                                √
                             1     1                                   ∗
           probability of at least  +  . Given our parameter set  Assume ∥    ∥ ≈    ·   .
                             2   poly(  )                                −  
           and algorithm, many attacks appear futile.         Applying the GSA, we expect the shortest vector to be found
           Core-SVP Hardness:   The SVP hardness depends upon  in the last block to have a norm
           how much time to solve for the given parameter set more
                                                                ∗              0       1    0       0        1
           likely the number of equations, modulus size, and the  ∥     −  +1 ∥ =      −   ·    · Vol(  )    =    −2(  −  )  ·    · Vol(  )   
                                                                                                      
                                                                                 
           number of dimensions. Various lattice reduction techniques
                                                                                 0          1
           allow to production of the shortest vector in exponential          =    2  −    · Vol(  )    .
           time complexity. No such known algorithm now even with  Thus, we expect success if
           the help of quantum algorithms can solve a particular LWE
                                                                              √                1
           problem in polynomial time. Blum, Kalai, and Wasserman’s           ·    ≤    0  · Vol(  )    .
                                                                                    2  −  
           work [23] yields a far more intriguing approach that takes
           just 2   (  )  samples and time. The method works by breaking  And for the parameters, we numerically optimized it to
           down the n coordinates into  1        (  ) blocks of size  defend against these types of attacks. Our parameter set
                                      2
           2  /      (  ) each, and then building S recursively by finding  allows security against BKZ attacks. The time complexity
           collisions in these blocks. This is based on a clever idea that  for these attacks is still exponential but it’s one of the
           finds a small set S of equations (let’s say, of size n) among  best-known attacks to uSVP.
           2   (  )  equations, such that  Í        is, let’s say, (1, 0,..., 0).
                                     
           By summing those equations, we get a very noisy estimate  Side-channel attacks: The implementation of our algorithm
           for the first coordinate of s, but a typical computation still  is such that side-channel attacks don’t seem much of a help in
           reveals a bias of around 2    (  )  toward the correct value.  tracing the modulo or any timing leakage. We implemented
           Therefore, by repeating the preceding technique just 2   (  )  it in such a way that there is a tight bound of timing and
           times, we have a good likelihood of recovering the value of  is nearly a constant time. Even if the matrix generation
           s1 and thus all of the s.                          from the seed doesn’t leave any timing leakage, there would
           Blum et al. approach is the most well-known technique for  be a case of leakage in modular reduction but it can be
           solving the LWE problem. The best-known algorithms for  easily modified by implementing the algorithm on the device.
           lattice problems [24], [25], take 2   (  )  time, which is closely
           connected to this.                                 Hybrid attacks:   A hybrid attack that combines
                                                              Meet-in-the-Middle combinatorial search with lattice
           Primal attack:  The primary attack involves creating a  reduction techniques, might compromise several algorithms.
           distinct SVP instance from the LWE problem and applying  The analysis of this approach is very challenging, and new
           BKZ to solve it.  We investigate the minimum block  research indicates that it is frequently less competitive than
           dimension b that BKZ needs to find the unique solution.  previously believed. As mistakes and secrets are not ternary
           Given LWE instance (A, b = As+e) then one make a lattice  and scarce in our design, we see that this attack is particularly
                        +1                                    pertinent in certain situations.
           Λ = { x ∈ Z    (A|      | −   )   =0 mod q } and then it
           will generate a distinct or unique solution v = (s, e, 1)
                         √
           of norm    =         +    where the    shows the standard   5.  PERFORMANCE ANALYSIS
           deviation[25][16][12].
                                                              Indeed, the algorithm produces different encryption text
           Success condition. With our parameter set at first it will be
                                                              vectors for the same input each time it runs due to the use of
           very difficult to make an accurate Λ or the basis matrix
                                                              random variables. This property is crucial for the security of
                               A’       0                   cryptographic systems, as it ensures that even if an attacker
                         ×  
                                              (  +1)×(  +1)
                                         
                                                            observes multiple ciphertexts of the same plaintext, they
                 = 0   −  ×         (  −  )×(  −  )  0 ∈ Z
                                         
                        
                                           
                                                            cannot deduce any information about the original message
                                         
                                                           – 71 –
   110   111   112   113   114   115   116   117   118   119   120