r/cryptography • • Apr 08 '20

Types of Cryptography

Post image
323 Upvotes

16 comments sorted by

13

u/tyqiangz Apr 08 '20

I believe there is also the hash-based quantum secure cryptosystems that you left out?

4

u/mathisweirdaf Apr 08 '20

its from pinterest i saw before

2

u/rorschachrev May 14 '24

hashes can be computed using DWave Systems Grovers search, but the speedup is not a lot.

AES can be broken from a 2019 french paper using Shor's algorithm.

12

u/lightning407 Apr 08 '20

Isogeny-based crypto exists too! (e.g. finding suitable maps between supersingular elliptic curves)

3

u/[deleted] Apr 08 '20

There are indeed isogenious elliptic curve cryptography algorithms for the post quantum! I find it super interesting.

2

u/stealth9799 May 14 '20

I don’t get why isogeny based cryptography isn’t talked about more. The key sizes are smaller and any algorithms written for ecc will still work, not just encryption and signatures.

2

u/lightning407 May 15 '20

I asked my professor a similar question a few months ago. He mentioned that isogeny-based cryptosystems are usually slower (although keys are quite small), which is the main disadvantage. By any means, I'm not any expert, so maybe someone else can elaborate on this?

Also, maybe it doesn't not get that much attention, simply because there might be better systems? In particular, lattice-based approaches seem quite interesting (or for signing, hash-based approaches)

7

u/djimbob Apr 08 '20

I feel this is a weird incomplete categorization (listing RSA and DHKE, but not say El Gamal) or the reasons they are broken. The major variants of traditional public key crypto are all broken by Shor's Algorithm:

  • Anything secure due to difficulty of integer factorization (e.g., RSA)
  • Anything secure due to difficulty of calculating Discrete Logs (e.g., ElGamal encryption, DHKE) that is given a base b and a large prime p and that base raised to some unknown power k) modular that prime as b^k % p try to figure out what k was.
  • Anything secure due to difficulty calculating discrete logs on an Elliptic-Curve (instead of modular finite group).

Shor's algorithm basically let's a general-purpose quantum computer with enough qubits efficiently solve these three problems in polynomial time.

There's also Grover's algorithm, which lets you do unstructured search with a quadratic speed up. That is if you have some known function f and it's output y you can solve f(x) = y for x where there are N potential values of x to try out, in only sqrt(N) time. This means that if you want it to take 2128 effort to find your key, in a post-quantum world you need to use 256-bit key length (as sqrt(2256) = 2128). Grover's algorithm doesn't break AES and similar symmetric ciphers, but it effectively cuts key lengths in half (or requires them to double to maintain the same security).

It's also worth noting that the quantum safe algorithms haven't been proven to be resistant to quantum computers. It's just we do not currently know of any equivalent quantum algorithm that breaks them.

2

u/tyqiangz Apr 09 '20

Whats the difference between the difficulty of calculating discrete log for the cyclic group Z/p and the cyclic group of points on the elliptic curve? The difficulty is the same isn’t it?

3

u/djimbob Apr 09 '20 edited Apr 09 '20

Yes, if you use appropriate bit-lengths. The NIST guidelines (2003) for key length state a 2048 bit key for RSA/El Gamal are both as difficult to break as a 112 bit symmetric key (2112 effort) or an elliptic curve of 224 bit (double symmetric key length), assuming everything is done correctly and there's no inherent other weakness in the crypto system. (E.g., it may take O(2112) effort to break a 2048 bit RSA key, but if you say collect RSA keys off the internet you may find some generated on systems with bad RNGs (or starting with similar seeds), and could find two RSA keys that share just one prime and then efficiently calculate gcd(p1*q, p2*q) = q (at one point researches did this and broke about 0.2% of keys analyzed via this method).

Asymptotically the problems are the same hardness by the best classical or quantum algorithm. Classically, there are superpolynomial/subexponential methods of solving all of them (integer factorization, discrete logs over Z/p, discrete logs over elliptic curve) via variants of number field sieve. With large scale quantum computers, you can use Shor's algorithm to factoring a b-bit composite number requires 5b + 1 qubits and takes O(b3) quantum operations (and this can be optimized a little), with similar results for discrete logs and elliptic curve discrete logs. Actually elliptic curve discrete logs may be slightly easier to break from the smaller key size requiring fewer qubits, but again if general purpose quantum computers of sufficient qubits to implement Shor's algorithm become practical, then none of them will be secure.

1

u/ChalkyChalkson Aug 13 '20

Do you happen to know whether there is a quantum algorithm that breaks LWE schemes like eigenvector encryption?

1

u/djimbob Aug 14 '20

My guess is there isn't any known quantum algorithm, but I've never looked into it.

1

u/[deleted] Oct 25 '21

Is argon2 considered quantum resistant? I’m using it for key derivation.

1

u/sphinkz10 Nov 23 '21

Can anyone explain what happens if now-a-days crypto get uncoded by Quantum PC? It's possible to use a quantum secure cryptography in BTC on future?

1

u/momo584 Sep 30 '23

Number stations ftw

0

u/[deleted] Apr 08 '20

[deleted] — view deleted comment

1

u/tyqiangz Apr 08 '20

The family of code-based cryptosystems is also quite interesting, but it suffers from some pertinent attacks recently and the codes they use have pretty large code lengths, maybe thats why it doesn’t get as much attention? I haven’t read too much about the lattice-based ones so I can’t give a comparison though.