Tiny Bytes: RSA
tldr RSA works by exploiting the fact we can’t easily factor 2 large prime numbers and group theory to make a trapdoor permutation, aka a function that turns x into y but y can’t easily be turned into x without a secret. However, implementing RSA gets tricky because there’s lots of subtle attacks.MathRSA takes advantage of the group Z^*_{n} (multiplicative group of integers modulo n). This is the non-negative integers less than n that have an inverse modulo n. 1 x 1 mod n = 1. 0 x int = 0 so ...
Tiny Bytes: Chilling
Hi, Just chilling tonight. Aiming to finish up chapter tomorrow. Night, Lucas
Tiny Bytes: Quickie
Hi, Did much more writing on RSA. Will finish soon. Bye, Lucas
Tiny Bytes: RSA
tldr RSA works by exploiting the fact we can’t easily factor 2 large prime numbers and group theory to make a trapdoor permutation, aka a function that turns x into y but y can’t easily be turned into x without a secret. However, implementing RSA gets tricky because there’s lots of subtle attacks.MathRSA takes advantage of the group Z^*_{n} (multiplicative group of integers modulo n). This is the non-negative integers less than n that have an inverse modulo n. 1 x 1 mod n = 1. 0 x int = 0 so ...
Tiny Bytes: Chilling
Hi, Just chilling tonight. Aiming to finish up chapter tomorrow. Night, Lucas
Tiny Bytes: Quickie
Hi, Did much more writing on RSA. Will finish soon. Bye, Lucas
Subscribe to ldnovak
Subscribe to ldnovak
Share Dialog
Share Dialog
<100 subscribers
<100 subscribers
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.
Quick 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/
Grover’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/ciphertexts
Implement 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.pdf
Because 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
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.
Quick 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/
Grover’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/ciphertexts
Implement 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.pdf
Because 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
No activity yet