Tech Briefs

Developing new algorithms to improve data security.

In order to make computing on encrypted data more practical to use and more secure from attack, it is necessary to discover, develop, and understand the mathematics on which it is based and the mathematics that can be used to attack it.

The security of homomorphic encryption schemes is based on the presumed difficulty of mathematics problems about lattices. Discovering and fully exploring algorithms to solve these mathematical problems allow computing on encrypted data to be performed with confidence, knowing that its cryptographic security is based on sound mathematical foundations.

Hendrik Lenstra and Alice Silverberg discovered and developed algorithms to solve some lattices problems under suitable conditions, and investigated the mathematical foundations of these algorithms. A primary method of attack on homomorphic encryption schemes consists of lattice algorithms performed on ideal lattices, which are lattices with a certain type of algebraic structure. Any structure or symmetry is potentially susceptible to exploitation and attack. The work performed here gives algorithms for lattice problems for lattices that have symmetry. Recommendations are that the mathematical foundations of lattices with symmetry be further developed, in order to quantify the security of lattice-based cryptography, including especially the security of homomorphic encryption schemes.

In encryption schemes, one party encrypts a plaintext message to obtain a ciphertext. The other party decrypts the ciphertext to recover the plaintext. In Fully Homomorphic Encryption (FHE), parties that do not know the plaintext data can perform computations on it by performing computations on the corresponding ciphertexts.

The security of essentially all currently known FHE schemes is based on the presumed difficulty of some lattice problem, such as finding an approximately shortest (non-zero) vector in a high dimensional lattice. The primary known attacks on FHE schemes are variants of the LLL lattice basis reduction algorithm, originally due to Lenstra, Lenstra, and Lovász.

A number of Fully Homomorphic Encryption schemes use ideal lattices rather than arbitrary lattices, including Gentry’s first FHE scheme. Fully Homomorphic Encryption is performed more efficiently with ideal lattices than with general lattices. However, ideal lattices are very special lattices, with much structure (“symmetries”) that has the potential to be exploited, and it might turn out to be the case that lattice attacks are easier for ideal lattices than for generic lattices.

Gentry and Szydlo introduced some powerful new ideas that combined in a clever way lattice basis reduction and number theory. They used these ideas to cryptanalyze NTRU (NTRUEncrypt Public Key Cryptosystem) Signatures. The recent interest in Fully Homomorphic Encryption and in the candidate multilinear maps of Garg-Gentry-Halevi have renewed the interest in the Gentry-Szydlo results.

The algorithm of Gentry and Szydlo can be viewed as a way to find an orthonormal basis (if one exists) for an ideal lattice. Determining whether a lattice has an orthonormal basis is in general a difficult algorithmic problem. The results of this research show that this problem is easier when the lattice has many symmetries. Lenstra and Silverberg construct a provably deterministic polynomial-time algorithm that decides whether a given lattice with sufficiently many symmetries has an orthonormal basis, and finds one if it does. More precisely, they give a deterministic polynomial-time algorithm that, given a finite abelian group G, an element u in G of order 2, and a G-lattice L, decides whether L and Z〈G〉are G-isomorphic, and if they are, exhibits a G-isomorphism. The Gentry-Szydlo algorithm is put into a mathematical framework, and shown as part of a general theory of “lattices with symmetry,” shedding new light on the Gentry-Szydlo algorithm, and demonstrating that the ideas should be applicable to a range of questions in cryptography.

This work was done by Alice Silverberg and Hendrik Lenstra of the University of California, Irvine for the Air Force Research Laboratory. AFRL-0243

This Brief includes a Technical Support Package (TSP).

USING MATHEMATICS TO MAKE COMPUTING ON ENCRYPTED DATA SECURE AND PRACTICAL (reference AFRL-0243) is currently available for download from the TSP library.

Please Login at the top of the page to download.