A Decade of Lattice Cryptography (2016) [pdf]

web.eecs.umich.edu

45 points·Tomte··3 comments

I'm not math fluent enough to know what lattices really are, but it seems, from the wikipedia article, that a (geometric/group theory) lattice is a subgroup of the additive group of real numbers [1] that is isomorphic with the additive group of the "free abelian group" [2].

[1] which is to say, real numbers that one can obtain by adding or subtracting other real numbers.

[2] which is a set that satisfies addition, commution, and inversion to derive any element from some subgroup of the set. Integers are an example, as one can produce any integer as a combination of the number 1.

The way lattice math has intruded into my outgroup awareness is from C Gentry's formulation of a fully homomorphic encryption scheme using lattices. So, if you are interested in a survey of papers delving into the applications of lattices for cryptography, consider looking at this 70 page work. I guess if you want to see some code that results from understanding this stuff, consider looking over Shai Halevi's HELib repo: https://github.com/shaih/HElib

Thank you for taking the time to explain that; I was struggling to understand exactly what a lattice is and isn’t, and your description cemented my understanding.

Isomorphic to a free abelian group means that it behaves like Zⁿ for some n,that is the set of n-uples of integers with operations defined pointwise.

A simple example is Z², this is the set of all pairs of integers (a,b) where addition is defined as (a,b)+(c,d)=(a+c,b+d).

A more interesting example is the set of pairs (a,b√2) where a and b are integers and addition is defined as (a,b√2)+(c,d√2)=(a+c,(b+d)√2).

If you draw those in R² they look like repeating parallelograms (squares actually for the first), hence lattices

Reply on news.ycombinator.com