Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

Is there a significantly advantage to these data structures, or is it simply the status-quo and the easiest to use for describing constructions?

share|improve this question

Lattices are used simply because we do not know how to build homomorphic encryption from any other problems, like factoring or discrete logarithm. Their mathematical structure was found to simultaneously enable homomorphic addition and multiplication while other bases for encryption could handle at most one of them. (For the case of ideal lattices/rings, this seems intuitive: If ciphertexts are elements of a ring then you can naturally add and multiply them, although things are not really that simple. It was later found that the ring structure could be removed, and that any lattice would suffice.)

Advantages like quantum resistance etc are only incidental.

share|improve this answer
Hey David, what exactly is an ideal lattice compared to a regular lattice? I've asked on math SE and other places and haven't been able to get an answer. – Alan Wolfe Apr 14 at 2:47

For the second part of question: Intractability of existing lattice based problems have the following advantages over the existing in number theory as the big prime factorization and the discrete logarithm problem:

  • Hard to solve in worse case and not in average.
  • Resilient to quantum attacks yet.
  • Lattice problems seem to be more easily formulated as they can be draw with paper and pencil.
  • In the end it is simple, extremely simple operations of linear algebra with noise

but there are still far away to resemble a practical cryptographic efficient scheme compared with the existing ones.

share|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.