# Tiny Bytes: Symmetric Keys

**Published by:** [ldnovak](https://paragraph.com/@ldnovak/)
**Published on:** 2022-07-18
**URL:** https://paragraph.com/@ldnovak/tiny-bytes-symmetric-keys

## Content

Hey, Thought I was going to do a quick quantum section and a quick world building. Turning into just quantum computing about why symmetric keys are safe.Quantum ComputingGrover’s AlgorithmQuick tldr: Can search an unstructured list of N elements for a specific element in root(N) time. This is the theoretical optimal solution. (tried to quickly understand in 10 minutes but couldn’t quite get it. here’s my best guess of how it workds) Grover’s algorithm does this by “guessing” the best element BUT altering the odds such that it will always be right. Consider an array of N elements and we are looking for the index of an element with value s. We have a vector where the amplitude of index n_i/(n_j for j=1-N) is to probability that index i is element s. We can apply an operation to that vector that will increase the amplitude of element s and decrease the amplitude of all other elements. This amplification/”rotation” of the vector takes ~root(N) steps in order to guarantee our guess for element s will be correct (or root(N/M) if there are M elements that are s) I’ve also seen this rotation called “making a call to the Grover Oracle.” This oracle takes a guess an gives 1 if the guess is correct and 0 else (i.e., 1 if s 0 else). https://qiskit.org/textbook/ch-algorithms/grover.html https://quantum-computing.ibm.com/composer/docs/iqx/guide/grovers-algorithm It’s worth noting that Grover’s algorithm doesn’t parallelize well. I don’t quite understand why. According to Bas Westerbaan an operation (specifically speeding up brute force AES) that takes O(n^64) can be parallelized to O(n^49). https://arxiv.org/abs/quant-ph/9711070 https://blog.cloudflare.com/nist-post-quantum-surprise/How does Grover’s algorithm affect encryptionGrover’s algorithm enables a way to brute force AES. How? Note sure but here’s my understanding:Get a known plaintext/ciphertext pair encrypted with an unknown secret key (e.g., I trick Alice to encrypt known message for me)Note may need many combinations of plaintext/ciphertextsImplement a quantum AES circuit that implements Grover’s oracle (i.e., f(key) → Enc(plaintext, key) = ciphertext for all plaintext and ciphertext combinations)With this you can apply Grover’s algorithm (lots of discussion on the fastest way to do this) https://crypto.stackexchange.com/questions/63068/attacking-aes-128-with-grovers-algorithm https://eprint.iacr.org/2019/1146.pdfSymmetric Key SafeBecause lots of symmetric keys rely on AES they are safe (with enough bytes) from quantum computers. I’m still not sure on the fundamental reason why this is. Seems like no one has found an algorithm that can break it. We do know the limits placed on Grover’s and the parallelization limits of it. From my current understanding AES / symmetric encryption is safe from quantum computers because it doesn’t rely on math that is known to be exponentially sped up from quantum computers. What makes some math safe and others not? I’m not sure besides it doesn’t rely on factoring large numbers. We also know that brute forcing solutions is at most an O(root(n)) speed up with limitations parallelization. This is a little of an unsatisfying answer. I hope more research + understanding creates better answers to this question (specifically the why). If someone came along tomorrow and said there’s something new that breaks it, I don’t know enough to be shocked. That being said lots of smart people say it’s safe so it’s fine. It’s annoying how it’s logic that doesn’t scale too well. A corollary to Grover’s is that any algorithm where we can make an oracle that gives 0/1 to an answer can have a quantum root(n) speed up. Not sure if this is true. Also, even asymptotic speed ups aren’t always speed ups because constants still matter. That’s all folks, Lucas

## Publication Information

- [ldnovak](https://paragraph.com/@ldnovak/): Publication homepage
- [All Posts](https://paragraph.com/@ldnovak/): More posts from this publication
- [RSS Feed](https://api.paragraph.com/blogs/rss/@ldnovak): Subscribe to updates