## Global Sales Contact List

Contact   A B C D E F G H I J K L M N O P Q R S T U V W X Y Z
• 1-781-515-5000
RSA LABORATIORIES
11 Cambridge Center
Cambridge, MA 02142 - USA

# RSA Laboratories

## 2.3.11 What are lattice-based cryptosystems?

Lattice-based cryptosystems are based on NP-complete problems (see Question 2.3.1) involving lattices. A lattice can be viewed as the set of all linear combinations with integral coefficients of a specified set of elements in a vector space. An example of a lattice is the infinite square grid in 2-dimensional space consisting of all points with integral coordinates. This lattice is generated by integral linear combinations of the vectors (0,1) and (1,0).

Lattice-based methods fall into two basic classes, although the solution methods for both are identical. In fact, there are efficient transformations between the two classes. The first class is based on the so-called subset sum problem: Given a set of numbers S = and another number K, find a subset of S whose values sum to K. The knapsack problem of Merkle and Hellman [MH78] is an example of this.

Other lattice-based methods require finding short vectors embedded in a lattice or finding points in the vector space close to vertices of the lattice or close to vectors embedded in the lattice. The method of Ajtai and Dwork [AD97] is an example of this type.

So far lattice-based methods have not proven effective as a foundation for public-key methods. In order for a lattice-based cryptosystem to be secure, the dimension of the underlying problem has to be large. This results in a large key size, rendering encryption and decryption quite slow. Ongoing research aims to improve the efficiency of these cryptosystems.

Top of the page

Notes:
Connect with EMC
Need help immediately? EMC Sales Specialists are standing by to answer your questions real time.
Use Live Chat for fast, direct access to EMC Customer Service Professionals to resolve your support questions.
Explore and compare EMC products in the EMC Store, and get a price quote from EMC or an EMC partner.
We're here to help. Send us your sales inquiry and an EMC Sales Specialist will get back to you within one business day.
Want to talk? Call us to speak with an EMC Sales Specialist live.
Share & Follow