Timeline for Mathematical conjectures on which applications depend
Current License: CC BY-SA 3.0
11 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Jan 21, 2018 at 20:00 | comment | added | Sasho Nikolov | @PyRulez an efficient algorithm for factoring gives an (essentially) equally efficient algorithm for breaking RSA and Diffie Hellman key exchange. The only technicality that can salvage these systems is that the efficient algorithm may be efficient only in theory, but in practice be very slow for all inputs of less than astronomical size. | |
| Jan 21, 2018 at 16:13 | comment | added | slebetman | @JosephO'Rourke: The application where factoring difficulty matters is not related to hashing. It is related to mainly two things: 1. secretly passing encryption keys without a listener being able to know what either party is talking about (Diffie-Hellman key exchange) and 2. asymmetric encryption where you can expose one of your encryption keys to the public (the public key) yet nobody can crack the encrypted message without your secret private key | |
| Jan 20, 2018 at 22:51 | comment | added | Gray Taylor | Even if P!=NP, factoring isn't known to be NP-hard, so crypto based on it could still be vulnerable even if we can't tackle NP problems in polynomial time. | |
| Jan 19, 2018 at 13:34 | comment | added | Luchostein | See P!=NP mathoverflow.net/a/291019/102169 | |
| Jan 19, 2018 at 3:44 | comment | added | Christopher King | How likely is it that this would be proven false, but those systems still being secure? | |
| Jan 19, 2018 at 1:05 | comment | added | darij grinberg | Isn't a Merkle tree just as secure as its underlying hash function? | |
| Jan 19, 2018 at 0:39 | comment | added | ThiKu | It‘s Merkle by the way. No politics involved. | |
| Jan 19, 2018 at 0:15 | history | made wiki | Post Made Community Wiki by Todd Trimble | ||
| Jan 19, 2018 at 0:11 | comment | added | Joseph O'Rourke | I'm not an expert, but I think this is not true for Merkel hash-based schemes: "the European Commission has recommended use of Merkle signature scheme for long term security protection against quantum computers." | |
| Jan 18, 2018 at 23:36 | comment | added | Dustan Levenstein | Afaik, all (public key) cryptography algorithms boil down to some number theoretic conjecture. Not necessarily factoring large numbers, but something has to be assumed to be difficult. | |
| Jan 18, 2018 at 22:02 | history | answered | Alexandre Eremenko | CC BY-SA 3.0 |