7
$\begingroup$

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?

$\endgroup$
2
3
$\begingroup$

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?".

$\endgroup$
1
  • $\begingroup$ I think this is a pretty good attempt $\endgroup$
    – user34945
    Oct 10 '15 at 5:28
1
$\begingroup$

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.

$\endgroup$
6
  • 3
    $\begingroup$ I dont understand.. I wanted to avoid DH and you are giving a special case of it $\endgroup$
    – user34945
    Oct 9 '15 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.
    Oct 10 '15 at 0:59
  • 1
    $\begingroup$ @Arul, my comment was not directed at you -- it was directed at Fleeep. $\endgroup$
    – D.W.
    Oct 10 '15 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$
    – Fleeep
    Oct 11 '15 at 9:17
  • 1
    $\begingroup$ As stated in the answer, its is Diffie-Hellman LIKE, not Diffie-Hellman. $\endgroup$
    – Fleeep
    Oct 11 '15 at 9:20

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy