4 ms·

What would you use as an RSA replacement? Beyond that, is there a technique that's still relatively simple like RSA (humor me) but impervious to publicly-known

What would you use as an RSA replacement? Beyond that, is there a technique that's still relatively simple like RSA (humor me) but impervious to publicly-known quantum attack vectors like Shor's algo?

tptacek 13y ago
Here's a good place to start: http://pqcrypto.org/ http://pqcrypto.org/ (This is Daniel J. Bernstein).
betterunix 13y ago
The Learning With Errors problem is promising: https://en.wikipedia.org/wiki/Learning_with_errors https://en.wikipedia.org/wiki/Learning_with_errors When last I checked there was still a lot of debate about choosing secure parameters for LWE-based cryptosystems, so it would be pretty risky to start using that right now.
rdtsc 13y ago
I was going to jump in and say ECC https://en.wikipedia.org/wiki/Elliptic_curve_cryptography https://en.wikipedia.org/wiki/Elliptic_curve_cryptography but, searching I found that it is apparently vulnerable to quantum computing attacks (wikipedia points me to: Nielsen, Michael A.; Chuang, Isaac L. Quantum Computation and Quantum Information. p. 202) and also found this: http://www.mathcs.richmond.edu/~jad/summerwork/ellipticcurvequantum.pdf http://www.mathcs.richmond.edu/~jad/summerwork/ellipticcurve...
- yk 13y ago
  In one of the crypto talks at the 30C3 the speaker mentioned that quantum computers are actually a greater danger to ECC, because of the smaller key sizes. ( I think this sounds plausible, but I am not an expert.)
- scythe 13y ago
  Elliptic curve cryptography is logically equivalent to prime-factorization cryptography in a sense: both are special cases of the hidden subgroup problem. DLP is also a version of the hidden subgroup problem. Any variant of HSP can be broken by a quantum computer using a variant of Shor's algorithm.
  - venomsnake 13y ago
    How broken is the question - NSA cracks 2048 keys we just double the key size and are safe for 3-4 more years, or making it so trivial it doesn't matter how big the key size is.
maaku 13y ago
Lamport signatures.

tptacek 13y ago

Here's a good place to start: http://pqcrypto.org/ http://pqcrypto.org/ (This is Daniel J. Bernstein).

betterunix 13y ago

The Learning With Errors problem is promising: https://en.wikipedia.org/wiki/Learning_with_errors https://en.wikipedia.org/wiki/Learning_with_errors When last I checked there was still a lot of debate about choosing secure parameters for LWE-based cryptosystems, so it would be pretty risky to start using that right now.

rdtsc 13y ago

I was going to jump in and say ECC https://en.wikipedia.org/wiki/Elliptic_curve_cryptography https://en.wikipedia.org/wiki/Elliptic_curve_cryptography but, searching I found that it is apparently vulnerable to quantum computing attacks (wikipedia points me to: Nielsen, Michael A.; Chuang, Isaac L. Quantum Computation and Quantum Information. p. 202) and also found this: http://www.mathcs.richmond.edu/~jad/summerwork/ellipticcurvequantum.pdf http://www.mathcs.richmond.edu/~jad/summerwork/ellipticcurve...

yk 13y ago
In one of the crypto talks at the 30C3 the speaker mentioned that quantum computers are actually a greater danger to ECC, because of the smaller key sizes. ( I think this sounds plausible, but I am not an expert.)
scythe 13y ago
Elliptic curve cryptography is logically equivalent to prime-factorization cryptography in a sense: both are special cases of the hidden subgroup problem. DLP is also a version of the hidden subgroup problem. Any variant of HSP can be broken by a quantum computer using a variant of Shor's algorithm.
- venomsnake 13y ago
  How broken is the question - NSA cracks 2048 keys we just double the key size and are safe for 3-4 more years, or making it so trivial it doesn't matter how big the key size is.

maaku 13y ago

Lamport signatures.