April 18, 2023
Math 302 Cryptography
Spring 2023

T. Ratliff, Wheaton College
ratliff_thomas@wheatoncollege.edu

The GGH example from In Class

If you place the basis for a lattice in the rows a matrix, this will compute the Hadamard ratio of the basis.

Notice there’s a little Mathematica magic of the Apply[ ] function that allows this to work with square matrices of any size

hadamard[V_]:= N[ Surd[Abs[Det[V]]/Apply[Times,Map[Norm,V]], Length[V]]];

Let L be the lattice with basis  V = { {1,1,1}, {-3,1,1}, {-1,-1,3} }, that we’ll use for the private key

The public key is W = { {723,-285,-403}, {-691,273,385}, {-43,17,24} }

Let’s take a look and check the Hadamard ratios

V={{1,1,2},{-3,1,1},{-1,-1,3}};
V//MatrixForm
hadamard[V]

W= {{723,-285,-403},{-691,273,385},{-43,17,24}};
W // MatrixForm
hadamard[W]

Ratios look good. 

Let’s verify that the W matrix is also a basis for L - All integer entries, and det(U)= 1, good to go!

U =W.Inverse[V];
U // MatrixForm
Det[U]

Let’s encrypt m = {4, 1, 5}  using r={-1,0,1}

m={4,1,5};
r={-1,0,1};
v=m.W
e= v + r

Now if we decrypt using Babai’s algorithm

t= e.Inverse[V]

a=Round[t]

v=a.V

v.Inverse[W]

Or, we can combine to fewer steps, too

v = Round[e.Inverse[V]].V
v.Inverse[W]

What would happen if we had tried to solve the CVP using the skewed public basis?

We don’t get the correct plaintext!

v = Round[e.Inverse[W]].W
v.Inverse[W]

Let’s apply the LLL algorithm to W to find a more orthogonal basis

A lattice of dimension 3 isn’t very secure.

Wow, we end up with a basis that is more orthogonal than our private V!

V1 = LatticeReduce[W];
V1 //MatrixForm
hadamard[V1]

Values for In-Class Work #1

V={{1,1,-1},{-3,2,0},{3,5,8}}
W={{-2140,-1744,1329},{-1033,-573,330},{30,17,-10}}
m={3,7,8}
r={-1,1,1}
e={-828256,-634219,467126}

Values for In-Class Work #2

W={{-300,-3690,-1650,-19845,-5295,3990,-390,8445,-9930,-9630,3120,4920,1650,525,45},{-7140,18390,25635,5145,19620,4335,-10305,9480,10095,1080,-3540,19065,1125,-2370,-240},{7830,34890,1755,57975,-7605,23895,-16395,-16875,-8115,-2865,3705,16695,4710,-1410,-165},{-8175,-13080,9105,-39510,-14460,-18765,11550,-5490,-2130,-11175,-2265,-6360,-10095,825,135},{11385,10095,41145,14340,2130,12510,-17460,20685,-8535,-17880,-4005,4575,-6855,390,75},{9840,105,21660,5655,-10665,-5580,-9975,-11205,-7380,-3105,-1830,-17160,2400,-1215,-135},{-1425,6765,23805,-1455,-4245,-7350,-8460,7395,-8415,-10125,-2460,-3240,4635,-1875,-210},{-7245,2115,-21630,-12600,40560,-13920,26700,2100,17625,17160,8535,-5640,10290,-840,-135},{-4770,7800,8880,405,-11115,3345,-9375,-1965,855,-2385,-6270,12450,-1530,-1590,-150},{-1365,3900,-20760,-8880,-3525,7530,10785,-525,-4395,-8220,4155,10005,-7530,2310,270},{18105,-11460,4410,11955,-26595,10185,-9630,-17805,-6735,-2010,-3090,-12870,-9420,1800,225},{45,-750,11895,12705,7575,-5235,-6990,-2625,4875,7155,-555,-5130,7650,-2160,-255},{1005,-1650,60,-3210,-8115,2610,-1605,-630,-2520,-4485,-1605,2085,-4725,660,90},{9750,-3210,-8085,-6510,-14280,6840,4830,-3000,-7770,-1725,-135,-8505,-6015,2715,300},{480,-165,-390,-330,-735,345,225,-150,-390,-105,-15,-405,-315,135,15}}
m={0,1,0,0,0,0,1,0,1,1,0,1,1,0,1}
r={0,-1,-1,-1,1,-1,1,1,0,0,1,0,-1,-1,0}
e1={-414029,1700490,960750,-1305481,681165,258496,576404,-394471,75691,-922500,327721,1509749,-310890,-71686,-5264}