Page 115 - Kaleidoscope Academic Conference Proceedings 2024

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 –