Assume that Discrete logarithms can be solved in linear time over any group (hence factorization is also trivial by a result of Eric Bach), is there any other candidate public key exchange problem that will facilitate computationally secure key exchange?
$\begingroup$
$\endgroup$
2
-
5$\begingroup$ There are candidates in Lattice-based cryptography, for instance using the problem Learning with errors. $\endgroup$– BrunoCommented Oct 9, 2015 at 8:17
-
$\begingroup$ @Bruno. Also, as the Wikipedia article mentions, lattice based cryptography has so far resisted quantum attempts to break it. $\endgroup$– Juan Bermejo VegaCommented Oct 11, 2015 at 13:01
Add a comment
|
2 Answers
$\begingroup$
$\endgroup$
1
The Wikipedia page on "Post-quantum cryptography" provides a list of proposals for PKE resistant to quantum attacks. Quantum algorithms can solve DL in finite abelian groups (as well as a few nonabelian and infinite abelian ones), so they get very close to the spirit of the question you are asking. The learning with errors problem mentioned by one of the commenters is on that list.
I do not know of a general answer to the question of "What is the power of DL in arbitrary (that is, nonabelian) groups?".
-
$\begingroup$ I think this is a pretty good attempt $\endgroup$– user34945Commented Oct 10, 2015 at 5:28
$\begingroup$
$\endgroup$
6
Check Supersingular Isogeny Key Exchnage for some nice work on a Diffie-Hellman like Key Exchange based on isogenies between supersingular elliptic curves. This will compute computationally secure key. The authors mention that even though the key exchange is secure it will most likely be interesting purely for research/ pedagogical reasons.
There also is a cython implementation by De Feo SSIKE git. I would not rely on that for cryptographically secure key exchange but it is a good starting point.
Additionally to the wiki page mentioned Adam Smith you might wonna checkout this website for a good overview of literature: pqcrypto. On that page you will also find a link to this document: Post-Quantum Crypto Introduction. Thats the introduction to a book called ''Post Quantum Cryptography''. On pages 6-10 you will find a technical overview of three ''common'' post-quantum cryptosystems.
-
3$\begingroup$ I dont understand.. I wanted to avoid DH and you are giving a special case of it $\endgroup$– user34945Commented Oct 9, 2015 at 13:53
-
1$\begingroup$ Can you explain why you expect the "supersingular isogeny.." scheme will remain secure even if the discrete log is easy in every group? For instance, the paper doesn't try to make that kind of claim, from what I can see. Can you explain why you think this might be true? $\endgroup$– D.W.Commented Oct 10, 2015 at 0:59
-
1$\begingroup$ @Arul, my comment was not directed at you -- it was directed at Fleeep. $\endgroup$– D.W.Commented Oct 10, 2015 at 17:38
-
1$\begingroup$ The SSIKE is not based on diskrete log but on finding isogenies between curves. The fastest algorithm for calculating such isogenies over a field $F_{p^2}$ is $\sqrt[6]{p}$ for quantum computers and $\sqrt[4]{p}$ for classic computers. The scheme looks like DH though. Take a look at page 5/6 of the paper, theres a sketch of the key exchange. $\endgroup$– FleeepCommented Oct 11, 2015 at 9:17
-
1$\begingroup$ As stated in the answer, its is Diffie-Hellman LIKE, not Diffie-Hellman. $\endgroup$– FleeepCommented Oct 11, 2015 at 9:20