The purposes of this geoart series are twofold: to bring cachers to the watershed of the North Fork of the Broad River in Stephens and Franklin Counties and to serve as an introduction to the fascinating field of cryptography.
If you've seen Despicable Me, then you've heard the definition of a vector. "It's a mathematical term, a quantity represented by an arrow, with both direction and magnitude," as the film's villain (codename Vector) describes it.
If we work in two dimensions, then we can describe vectors using an ordered pair of real numbers. For example, the vector (1, 2) is an arrow that points 1 unit to the right and 2 units up.
We can add vectors by adding their components, e.g., (1, 2) + (3, 4) = (1 + 3, 2 + 4) = (4, 6). And we can multiply vectors by a single real number (called a scalar) by multiplying each component by that scalar, e.g., 5 × (1, 2) = (5 × 1, 5 × 2) = (5, 10).
A linear combination of several vectors is some combination of addition and scalar multiplication of those vectors, e.g., 5 × (1, 2) + 6 × (3, 4) = (5, 10) + (18, 24) = (23, 34) is a linear combination of (1,2) and (3,4).
A lattice is the set of all linear combinations of some set of vectors where the scalars are all integers. For example, (23, 34) is in the lattice generated by (1, 2) and (3, 4), but 1/2 × (1, 2) + 1/3 × (3, 4) = (3/2, 7/3) is not since 1/2 and 1/3 are not integers. A set of vectors which generates a lattice is known as a basis (provided it has some other properties we won't go into).
There are several interesting lattice problems that lend themselves well to cryptography. One of these is the closest vector problem, or CVP. The task is to find the closest vector in a lattice to a given vector (which is not in the lattice). If we're provided with a "good" basis for the lattice, i.e., the angles between the vectors are all pretty close to right angles, then we can solve the CVP pretty easily using Babai's algorithm. However, if the basis is "bad" and the angles between the vectors are small, then the CVP becomes much harder.
A cryptosystem developed by Oded Goldreich, Shafi Goldwasser (yes, the same one), and Shai Halevi in the 1997 paper "Public-key cryptosystems from lattice reduction problems" is based on the CVP. Here's how it works.
Alice picks a good basis v1, ..., vn of a lattice in n dimensions and also finds a bad basis w1, ..., wn for the same lattice. She publishes the bad lattice as her public key.
If Bob wants to send a plaintext message m = (x1, ..., xn), then he computes the vector v = x1 × w1 + ... + xn × wn , which lies on the lattice. Then he picks a random vector r and then computes the ciphertext e = v + r.
If r is relatively short, then v will be the closest vector on the lattice to e, and so it can be recovered by solving the CVP. Then the message m can be recovered by solving a system of linear equations.
Alice can do this easily with Babai's algorithm since she has a good basis, but it is much more difficult for Eve since she only has access to the bad basis for the lattice from Alice's public key.
The coordinates to this geocache have been encrypted using the GGH cryptosystem. The degrees are the same as the posted coordinates, but the minutes (ignoring the decimal points) are the entries in a 2-dimensional vector which has been encrypted using Alice's public key:
w1 = (534, 264)
w2 = (696, 337)
The first entry in this vector gives the minutes for the latitude and the second entry the minutes for the longitude.
The ciphertext is e = (24715873, 12115151).
Congratulations to beldredge and groundcrew for FTF!!