In my previous note on Lattice based cryptography,
Simple lattice cryptography 2D
the 'secret' transmission
[(116,348), (104,312), (101,303), (32,96), (113,339), (117,351), (105,315),
(99,297), (107,321), (32,96), (98,294), (114,342), (111,333),
(119,357), (110,330), (32,96), (102,306), (111,333), (120,360),
(32,96), (106,318), (117,351), (109,327), (112,336), (101,303), (100,300)]
to the sender was easy to break
even without the public key
Anyone who knows the ascii codes for the alphabet would recognize the ascii
codes in the first element of each pair and notice that the second pair was just
three times the first pair. Not very secure!
This note encodes the same message "the quick brown fox
jumped over the lazy dog"
using 'linerly independent' basis vectors in 3D.
They are: B1 = [4,7,2], B2 = [1,3,5], and B3 = [6,2,9]. These generate a lattice that looks
like:
THE ENCODING (WITHOUT ERROR TERMS)
Since we are in 3D space, let's group the character values (in ascii),
into triplets so that each group becomes a vector of coefficients to
the basis vectors like this:
ci = x*B1 + y*B2 + z*B3 which defines lattice points for the message.
Each point is a unique combination of three hard-to-guess
basis vectors. If someone did not have the three basis vectors
it would be very hard to reverse this and find the ascii characters
within the encoding - and there is no noise term
required in real applications added into
each triplet.
Here's what the encoded points look like in 3D space.
Can anyone (or any computer program) figure out that this represents the
plaintext "the quick brown fox jumped over the lazy dog"?
This is why Lattice encryption
is so secure!
DECODING THE MESSAGE
To understand how a receiver might determine that
the point [146, 69, 181] corresponds to the plaintext
"the", there are a few things to understand about the decoding process
using lattice-based cryptography.
Lattice Decoding:.
The receiver receives the encoded point [146, 69, 181].
The receiver knows the basis vectors B1, B2, and B3.
The receiver then solves the system of three equations (details omiited) in three
unknowns (x,y,z) x*B1 + y*B2 + z*B3 = [149,69,181] to find the coefficients (x,y,z) that were used to encode the point.
After solving the equations
the receiver multiplies the coefficients by the basis matrix,
to retrieve the original point which is [x = 116,y =104,z = 101].
Mapping Back to Plaintext:
The receiver then must map the recovered point [116, 104, 101] back to plaintext.
The receiver knows using ASCII mapping that 116 corresponds to "t", 104 corresponds to "h", and 101 corresponds to "e".
Therefore, the receiver can reconstruct the plaintext "the".
In short:
A pre-agreed upon mapping between letters and numbers exists
between the sender and the receiver.
The sender encodes the message using the lattice basis vectors.
The receiver decodes the message using the inverse of the lattice basis vectors.
The receiver uses everything pre-agreed
(ascii map and basis vectors) to turn the numbers back into letters.
CONCLUDING REMARKS
Real-world lattice-based cryptography is significantly more complex,
involving modular arithmetic, error correction codes,
and carefully chosen basis vectors to ensure security.
I have kept the mathematics in this note to a high-school level.
I hope you remember that stuff so you can follow all the details. 😂