1
$\begingroup$

The recommended hash length for post-quantum security seems to be either 384-bits or 512-bits. 512-bits gives 256-bit collision resistance, and 256-bit security is obviously ideal for post-quantum security.

A 256-bit authentication tag offers 128-bit collision resistance, but it's not clear whether that's sufficient for post-quantum security due to use of the MAC key (typically the same key size as the tag length - e.g. 256-bit for a 256-bit tag).

I've never found the security level of MACs to be explained well. Does the key mean a shorter tag length is safe? Or is the tag length still crucial for achieving a high security level?

Improve this question
$\endgroup$
2
  • 2
    $\begingroup$ "A 256-bit authentication tag offers 128-bit collision resistance"... this is not true, as the attacker doesn't know the key it can only try to create a valid message by changing either the authentication tag, the message or both. However, there is only a $1/2^{256}$ chance per message that it gets accepted (not counting replay attacks, and assuming that there is no key reuse). Besides that, many systems will break down communication after the first bad tag is encountered, and you cannot perform a collision search offline without the key. $\endgroup$
    – Maarten Bodewes ♦
    Feb 18, 2021 at 15:01
  • 1
    $\begingroup$ "and 256-bit security is obviously ideal for post-quantum security" no, 128 bit security is enough for any system as $2^{128}$ operations would simply cost too much time / power to ever be performed. However, with quantum computers, you need to perform different calculations to calculate the "bit strength" (which is just the $\log_2$ of the number of operations). A direct comparison with "classical" security immediately breaks down. $\endgroup$
    – Maarten Bodewes ♦
    Feb 18, 2021 at 15:07

1 Answer 1

Reset to default
1
$\begingroup$

Preimage resistance, via Grover search, is as far as I know $2^{n/2}$ while collision resistance is supposedly $2^{n/3}$ via Brassard et al [see linked paper for reference].

The paper below argues that the actual complexity of quantum collision search is higher. They give the collision search complexity as $O(2^{2n/5})$ and the multitarget preimage search complexity as $O(2^{3n/7}).$

https://eprint.iacr.org/2017/847

enter image description here

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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