Page 113 - Kaleidoscope Academic Conference Proceedings 2024

Innovation and Digital Transformation for a Sustainable World

where: n m k q
256 150 25 5 3907
• is a known matrix with rows corresponding to
coefficients . • The parameter is set to 256 to utilize a plaintext
size of 256 bits, ensuring 256 bits of entropy for key
• is a vector of error terms .
encapsulation. A lower reduces noise and affects
• is a vector of known values . security.
The LWE problem is challenging because the error terms
• The parameter is chosen to ensure a negligible
are typically drawn from a random distribution, making it
probability of decryption failure, similar to Kyber, where
difficult to distinguish between the true solution and random 12
a prime number around 2 defines a good security
noise. The LWE’s security relies on the hardness of solving
parameter.
this problem, even when given multiple noisy equations. In
practical lattice-based cryptography, LWE is used to build • The parameter represents the number of LWE samples
secure encryption schemes such as Ring-LWE, which is a chosen to resist BKW and BKZ attacks with LLL
variant of LWE, and many other cryptographic primitives. reduction techniques.
The security of these schemes is based on the assumption
that solving the LWE problem is computationally infeasible, • The parameter balances security and computational
even for powerful adversaries. timing, determining the number of equations selected
Hardness. The LWE problem is difficult for several reasons. from the public key for a single bit with modulo .
First of all, even quantum algorithms don’t seem to be
• The parameter is the number of equations chosen from
able to help because the most effective LWE algorithms
samples in the public key matrix. A subset of rows,
operate in exponential time. Second, since it is a logical
when combined, produces different equations to encrypt
extension of the Learning Parity with Noise (LPN) issue,
a single bit.
it has been well explored and is generally accepted to be
a challenging topic in learning theory. Furthermore, as
3.1 Key Generation
LPN involves the issue of decoding from random linear
binary codes, any advancement in algorithmic techniques At the beginning, several arrays (sk, sk_t, pk, pk_t, a) and
for LPN is likely to result in advances in coding theory. It a prime number (prime) are initialized. These arrays are
is known that LWE is hard because of several assumptions used to store secret keys, public keys, and other parameters
about the worst-case difficulty of typical lattice problems used in the encryption and decryption processes. The
like SIVP (the shortest independent vectors problem) and "generateUniqueRandomNumbers" function is defined to
GapSVP (the decision version of the shortest vector problem) generate a specified number of unique random numbers
[1][4]. More specifically, the conventional assumption that within a given range. This function is used to generate
GapSVP is difficult to estimate within polynomial factors secret keys, public keys, and other random values required
underlies difficulties when the modulus q is exponential. The for encryption by SHAKE-128 in its standard variant and
hardness is based on somewhat less common (but still quite AES-256 in CTR mode in its 90s variant as XOFs to generate
credible) assumptions for polynomial moduli q, which is the pseudorandom output for cryptographic operations. The
more important setting for cryptographic applications. To secret_key_gen and public_key_gen functions are defined to
be more precise, this means that either GapSVP or SIVP are generate secret keys (sk, sk_t) and public keys (pk, pk_t)
difficult to approximate within polynomial factors, even with based on random numbers generated using the XOF.
a quantum hint, or that GapSVP is difficult to estimate even
Algorithm 1 KeyGen(): Key generation
when provided with a short basis [3].
1: , ← {0, 1} 256 and ← {0, 1}
3. ALGORITHM AND SPECIFICATIONS 2: ∼ ( ) := XOF( )
3: ∼ ( ) := XOF( )
The algorithm is based on the LWE encryption scheme which
4: ∼ ( ) := XOF( )
was introduced by Odded Regev. We adopted the approach
5: ∼ D
[10] for the generation of the public matrix A and used the
6: ∼ ×
SVP problem to make the public key and secret key. The main
7: for = 0 to do
difference in creating the lattice dimensions in our algorithm
8: for = 0 to do
and others is that we are using the concept of reduced
9: [ ][ ] := ( [ ] [ ])
dimensions which means we would not take ’k’ dimensions
10: end for
in counter to calculate the resultant lattice equations and
11: end for
that would work as our second secret key. It also increases
12: _ ∼ ( ) := G(( . + ), _ )
the complexity of lattice reduction techniques. Similar to
13: return (( := ( , , p_t) , sk:= (s, s_t))
other post-quantum cryptography (PQC) algorithms in which
parameters play an important role in their security strength. In the provided code, the equation
We have also defined a set of parameters in it. The algorithm
is parameterized by n, m, k, q, . · + = _
– 69 –