4 ms·

This means that symmetric cryptography is safe from quantum computing. Before, folks were saying we had to double the key length.

api 4y ago
People have been saying that 256 bits is enough because even with Grover's algorithm the largest possible impact is to halve the key size. 128-bit brute force is still prohibitive in reasonable time frames. AES-256 and Salsa/ChaCha should be fine even post-QC. Symmetric crypto and hashes have never really been considered at risk except for very small sizes.
fwlr 4y ago
There might be other algorithms that can take advantage of quantum computing to break symmetric cryptography (although the paper does argue we should expect it is unlikely these algorithms exist). My understanding is there’s a fair bit of quantum computation research that uses Grover’s algorithm as a building block, and this paper pulls that foundational stone out from under them.
olliej 4y ago
The actual meaningful quantum attacks on modern cryptography all target the asymmetric key exchange algorithms, and make them practically attachable (assuming the standard “big enough” and “with low enough noise” constraints). Grover’s algorithm is essentially just a square root improvement on the search complexity for finding the symmetric key. That means the search complexity remains exponential and the encryption is still secure - we might want to increase the key size[1], but that is all that is needed. The attacks on asymmetric ciphers mean increasing the key size isn’t a meaningful solution. [1] currently under classical attack aes128 is “secure”, and assuming no algorithmic weakness being discovered will remain so for a while. However most modern protocols have increased to 256 but keys already as a pre-emotive defense against increasing classical computing capacity. Grover’s algorithm logically reduces the strength of a 256 bit key to 128 bits, but doing so requires quantum computers which so far seem to have some fundamental performance limits that leads me to not being overly concerned. I’d be more concerned about a quantum attack on aes128 as complexity on the order of 2^64 becomes much more plausibly broken.
Vecr 4y ago
I'd still use AES256 or ChaCha20 (as part of a secure AEAD construction if at all possible) for any new crypto system designs, or a new profile of an existing system. See "Understanding brute force" by Daniel J. Bernstein. Get someone who knows what they are doing to look at the basic design before you start.
upofadown 4y ago
Double is probably way too much anyways. Grover's does not parallelize very well. So you would have to do each and every one of those 2^64 operations serially on your quantum computer to get the full benefit of Grover's when cracking a 128 bit key. It is entirely possible that there is more than enough margin in 128 bit keys to prevent a successful Grover's based attack.

api 4y ago

People have been saying that 256 bits is enough because even with Grover's algorithm the largest possible impact is to halve the key size. 128-bit brute force is still prohibitive in reasonable time frames. AES-256 and Salsa/ChaCha should be fine even post-QC. Symmetric crypto and hashes have never really been considered at risk except for very small sizes.

fwlr 4y ago

There might be other algorithms that can take advantage of quantum computing to break symmetric cryptography (although the paper does argue we should expect it is unlikely these algorithms exist). My understanding is there’s a fair bit of quantum computation research that uses Grover’s algorithm as a building block, and this paper pulls that foundational stone out from under them.

olliej 4y ago

The actual meaningful quantum attacks on modern cryptography all target the asymmetric key exchange algorithms, and make them practically attachable (assuming the standard “big enough” and “with low enough noise” constraints). Grover’s algorithm is essentially just a square root improvement on the search complexity for finding the symmetric key. That means the search complexity remains exponential and the encryption is still secure - we might want to increase the key size[1], but that is all that is needed. The attacks on asymmetric ciphers mean increasing the key size isn’t a meaningful solution. [1] currently under classical attack aes128 is “secure”, and assuming no algorithmic weakness being discovered will remain so for a while. However most modern protocols have increased to 256 but keys already as a pre-emotive defense against increasing classical computing capacity. Grover’s algorithm logically reduces the strength of a 256 bit key to 128 bits, but doing so requires quantum computers which so far seem to have some fundamental performance limits that leads me to not being overly concerned. I’d be more concerned about a quantum attack on aes128 as complexity on the order of 2^64 becomes much more plausibly broken.

Vecr 4y ago

I'd still use AES256 or ChaCha20 (as part of a secure AEAD construction if at all possible) for any new crypto system designs, or a new profile of an existing system. See "Understanding brute force" by Daniel J. Bernstein. Get someone who knows what they are doing to look at the basic design before you start.

upofadown 4y ago

Double is probably way too much anyways. Grover's does not parallelize very well. So you would have to do each and every one of those 2^64 operations serially on your quantum computer to get the full benefit of Grover's when cracking a 128 bit key. It is entirely possible that there is more than enough margin in 128 bit keys to prevent a successful Grover's based attack.