2
$\begingroup$

Lattice cryptography is a post quantum cryptography that work on two NP-hard problem in below:

  1. Find shortest nonzero vector from origin and

  2. Find minimum distance of a arbitrary point out of lattice from origin.

At the moment lattice cryptography system is broken with key space of dimension 300. On the other hand we use dimension 400 in this cryptosystem. Can we use this cryptosystem in future?

How we can distinguish between this cryptosystem with others?

Improve this question
$\endgroup$
2
  • 1
    $\begingroup$ The second part of your question is vague and probably too broad. Also, did you mean to ask something about performance or why did you choose that tag? $\endgroup$
    – otus
    Jan 5, 2016 at 11:43
  • $\begingroup$ The hardness of lattice cryptography is NOT reducible to an NP-hard problem. Worst-case lattice assumptions are usually similar to the NP-hard version of the problem, except with a larger approximation factor. $\endgroup$
    – pg1989
    Jan 5, 2016 at 19:37

2 Answers 2

Reset to default
2
$\begingroup$

With math and computational advances, for protecting systems we should increase key size. We know that recommended key size for lattice based systems such as the NTRU is approximately $3slog(s)+1000$ bit, which $s$ is a desired security level.Today $s=80$, but with the advances of math, $s$ is increasing. $s=96$ is believed to provide protection until $2020$. So if we use lattice in future we should increase its dimensions.

For more detail about other cryptographic Schemes complexity you can see "Cryptographic Schemes Based on Isogenies" and also "Yearly report on algorithms and key sizes".

Improve this answer
$\endgroup$
3
  • $\begingroup$ Note that the isogeny-based scheme you refer to is broken by now $\endgroup$
    – CurveEnthusiast
    Dec 3, 2016 at 17:24
  • $\begingroup$ @CurveEnthusiast, Can you give me a reference please? $\endgroup$
    – Meysam Ghahramani
    Dec 3, 2016 at 23:35
  • $\begingroup$ Perhaps the introduction of eprint.iacr.org/2011/506.pdf is most useful. Stolbunov's isogeny-based schemes rely on ordinary elliptic curves. This scheme is broken (in a quantum setting). Instead, people are looking at isogeny-based schemes that rely on supersingular elliptic curves (not broken). The reference is the first work proposing to do this. $\endgroup$
    – CurveEnthusiast
    Dec 4, 2016 at 7:05
0
$\begingroup$

Very recently,Lior Eldar and Peter Shor,posted an arXiv preprint claiming a bombshell result: namely, a polynomial-time quantum algorithm to solve LWE.Unfortunately,Oded Regev has discovered a flaw in the algorithm.But, maybe it's a Potential threat to lattice problem.Futher study need.

Improve this answer
$\endgroup$
1

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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