1
$\begingroup$

I understand that asymmetric encryption is fundamentally deemed useless under Shor's Algorithm, and understand that symmetric encryption is somewhat quantum-resistant as long as the key-length is equal or above 192-bits.

MACs are symmetric cryptographic primitives, however, I have heard that they may be insecure due to the key exchange.

$\endgroup$
0
2
$\begingroup$

MACs don't involve any key exchange. The ability to share the key is assumed, just like with symmetric encryption. I'd tend to recommend a 256 bit key over a 192 bit key, because the effective key length is halved. 96 bits effective security might be breakable eventually, 128 bits effective security basically never will without discovery of flaws in the algorithm or implementation.

I understand that asymmetric encryption is fundamentally deemed useless under Shor's Algorithm,

This is incorrect. RSA and the usual ECC constructions (ECDSA, EdDSA, ECDH) are breakable for all practical key sizes. Other asymmetric constructions not based on integer factorization (RSA) or the discrete log problem(s) (ECC, ElGamal, traditional Diffie-Hellman) can be secure. EG Lattice-based cryptography (including but not limited to learning with errors, ring learning-with-errors, module learning-with-errors, and module learning-with-rounding), code-based cryptography, supersingular isogeny Diffie-Hellman are all asymmetric encryption thought to be resistant to attack by quantum computers. NIST is running a public contest to standardize some of these quantum-resistant asymmetric algorithms. It's currently in its third round.

$\endgroup$
3
  • $\begingroup$ Thanks for your answer. Just to clarify, is the reason MACs are secure from quantum computers due to the key length? $\endgroup$ – CyberCrusader Nov 29 '20 at 1:27
  • 1
    $\begingroup$ @CyberCrusader It's a combination of two things: 1) MACs (normal ones, anyway) are not vulnerable to any (known) high-efficiency quantum attacks (e.g. Schor's algorithm), only to Grover's algorithm (or variants). 2) Doubling the key size is sufficient to defeat Grover's algorithm. $\endgroup$ – Gordon Davisson Nov 29 '20 at 2:00
  • 1
    $\begingroup$ Of course, "the effective key length is halved" and "breakable for all practical key sizes" assume quantum computers usable for cryptanalysis, which do not exist at time of writing, AFAIK, the biggest similar problems solved using actual quantum computers (including adiabatic) all are amenable to solving with pencil and paper: recent example (reports simulated factoring up to 1028171=1009×1019). Earlier example (reports factoring 23357=401×557 using the D-Wave 2000Q). $\endgroup$ – fgrieu Dec 2 '20 at 6:23

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.