Cryptography often uses two special keys: a public key and a private
key. The private key is secret and stays with the owner,
while the public key can be shared with anyone.
If someone wants to send a secure message,
they use the public key to encrypt it,
and only the owner can decrypt it with their private key.
RSA-based cryptography, which protects online communications
and financial transactions, is in danger as quantum computing advances
toward "Q-Day" —the moment when quantum machines can break it instantly using Shor’s
algorithm.
In response, governments worldwide have mandated lattice-based
cryptographic schemes by 2036 to secure digital infrastructure against
quantum attacks. These new systems, based on the hardness of mathematical "lattice problems",
provide long-term security in a post-quantum world where
traditional encryption is obsolete.
This note has an
overly simplified example of
how lattice-based encryption works (without a critical
part involving adding in error terms to the encoding).
LATTICES GENERATED BY 'BASIS-VECTORS'
Lattices are generated with 'basis vectors' that
determine the points in the lattice. Different basis vectors generate different lattices.
Here's a 2-dimensional
lattice. In this picture v1 and v2
are the 'basis-vectors',
It is important to note that lattices used in secure cryptography are made in hundreds of dimensions (with hundreds of basis-vectors) not just two as shown here to keep thing simple.
SIMPLE NON-SECURE EXAMPLE TO ILLUSTRATE THE BASIC IDEAS
Let's encode, using lattices, the plain text message: "the quick brown fox jumped"
with the basis vectors
B1 = [1,3] and B2 = [1,0], that generated the lattice shown above.
HOW THE MESSAGE IS ENCODED:
Each character’s ASCII value A is represented as the pair:
[ASCII_VALUE,0], then as a linear combination of the basis vectors B1 and B2:
ci = ASCII_VALUE*B1 + 0 * B2 = [ASCII_VALUE, 3*ASCII_VALUE]
Using ASCII values for "the quick fox jumped" we get:
't' → (116, 348), 'h' → (104, 312), 'e' → (101, 303), ' ' → (32, 96), 'q' → (113, 339),
'u' → (117, 351), 'i' → (105, 315), 'c' → (99, 297), 'k' → (107, 321), ' ' → (32, 96),
'b' → (98, 294), 'r' → (114, 342), 'o' → (111, 333), 'w' → (119, 357), 'n' → (110, 330),
' ' → (32, 96), 'f' → (102, 306), 'o' → (111, 333), 'x' → (120, 360), ' ' → (32, 96),
'j' → (106, 318), 'u' → (117, 351), 'm' → (109, 327), 'p' → (112, 336), 'e' → (101, 303),
'd' → (100, 300)
Hence the final Encoded Message sent to the receiver is:
(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)
HOW THE MESSAGE IS DECODED BY THE RECEIVER
Decoding 't' (116, 348) as an example:
Given that the receiver has the the basis vectors as
the public key:
B1 = [1,3], B2 = [1,0] and the
Encoded vector: (116, 348)
We need to solve two simultaneous linear equations for x and y:
x*[1,3] + y*[1,0] = (116, 348)
Expanding from vector form we get the two equations:
1*x + 1*y = 116
3*x = 348
Solving for x:
x = 348/3 = 116
y = 116 - 116 = 0
so we get [116,0] which is the
decoded character: ASCII_VALUE(116) = 't'
and we have successfully decoded
the first character in the plain text "the lazy fox jumped"!
CONCLUDING REMARKS
This example is presented without the use
of error terms, and lattices in
high order (100's) dimensional spaces making it easy to crack the encoding
in this example.
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. 😂