I’ve posted solutions to the last daily post in the overleaf document, currently Section 6.4. Please look these over!
I’ve posted some example practice problems for entanglement in Section 6.8. Please attempt these and compare to the given answers.
Can you measure the first qubit of the state $\frac{1}{\sqrt{2}} |00 \rangle + \frac{1}{\sqrt{2}}|01 \rangle$ and get $1$?
Consider the quantum state $\frac{1}{2} |00 \rangle + \frac{1}{2} |01 \rangle + \frac{1}{2} |10 \rangle + \frac{1}{2} |11 \rangle$. Is this entangled?
Measure the quantum state $\frac{2}{\sqrt{7}} |00 \rangle + \frac{1}{\sqrt{7}} |01 \rangle + \frac{1}{\sqrt{7}} |10 \rangle + \frac{1}{\sqrt{7}} |11 \rangle$ in the first coordinate. What are the probabilities of the possible results, and the resulting quantum states?
Apply the Pauli Y gate to the state $\frac{1}{\sqrt{5}} |0\rangle + \frac{2}{\sqrt{5}} |1 \rangle$. What is the result?
Check that the Hadamard gate is unitary.
Apply the CNOT gate to the state $\frac{1}{\sqrt{5}}|00\rangle + \frac{2}{\sqrt{5}} |11 \rangle$. What is the result?
Check out the solutions to the test. We will do in-person make-ups as usual. My calendar link is the same (access it from canvas main page). Written make-up info soon!
Consider the qubit state superposition $i|0\rangle + \sqrt{3}|1 \rangle$.
Normalize it so that it is length 1 (i.e. $|a|^2 + |b|^2 = 1$).
Normalize it further so that it also lies on the Bloch sphere (first entry $a$ should be positive real).
Find $\theta$ and $\phi$ giving this state as a point on the Bloch sphere.
Draw it on a Bloch sphere.
Write $|-\rangle$ as a linear combination of $|0\rangle$ and $|1\rangle$.
Write $|i\rangle$ as a linear combination of $|+\rangle$ and $|-\rangle$.
Consider the state $|\psi\rangle = \frac{1}{\sqrt{5}} |0\rangle + \frac{2}{\sqrt{5}}|1\rangle$.
Measure it in the basis $|0\rangle$, $|1\rangle$. What are the possible outcomes and their probabilities?
Measure it in the basis $|+\rangle$, $|-\rangle$. What are the possible outcomes and their probabilities? (To do this, you will first need to write $|\psi\rangle$ as a linear combination of $|+\rangle$ and $|-\rangle$.)
Time permitting, here’s an interesting bonus problem concerning phase estimation.
Quantum Key Distribution! (Section 6.4 in Overleaf)
I think this will get confusing with everyone simultaneously on the #ciphertexts channel, so I want you to do this in pairs in the “QKD pairs” channel category of discord. There you will find plenty of text channels, so fill them up with two people each as you arrive, taking the first empty spot (the first person needing a partner or the first unused channel). Announce your arrival. The first person to arrive in a channel is Alice, the second person to arrive is Bob. Once two people are there, it’s full, so pick the next channel. You’ll do all communication on the channel so I can help you debug if it doesn’t work.
Open up the QKD BB84 Tools. The first box contains some code to initialize; no need to read this, just run it. The second box is a spot where you can either create photons (in our instantiation, they are just mysterious looking integers), or measure existing photons. It just holds an example for now.
Once you know if you are Alice or Bob, follow the protocol for your role.
Choose a sequence of 16 random choices of basis: example V L V V etc. The best way to do this is with a random number generator (like randint() in Sage).
Now choose a sequence of 16 bits: example 011001010101 etc. Again, true or good pseudo-randomness is best.
Use your two sequences to generate photons using the command create_photon in the QKD BB84 Tools page. This will create 16 integers (the photons), which you should obtain and paste into the channel as your “outgoing photon stream”.
Wait until Bob harvests your photon stream and reports that they are done “measuring” the photons.
Then, post to the channel the list of bases you used on your photons.
Bob will also post their list of bases used on the channel.
Then, determine the shared secret key from these two lists. Share it and see if Bob agrees.
Choose a sequence of 16 random choices of basis: example V L V V etc. The best way to do this is with a random number generator (like randint() in Sage). Keep this secret for now.
Alice will create a stream of photons (integers). Harvest (cut-n-paste) Alice’s photon stream, and use the command measure_photon() in the QKD BB84 Tools page to measure them using your list of bases (first basis to measure first photon etc.) Record the measurements and keep them secret.
Report to the channel you have finished measuring.
Then, report to the channel your list of bases.
When Alice also reports her list of bases, derive the shared secret.
Then, post the shared secret you derived to check if it agrees with Alice’s.
To Do: When you’re done, just post to canvas a screenshot or record of your experience; you can screenshot the channel or you can screenshot your spreadsheet or a text file you kept a record in; whatever, just to show you did it.
To Do: Watch the first 32 minutes of This Video. This is my friend, mentor and collaborator, Dr. Kristin Lauter, from Meta AI (formerly from Microsoft Research). She’s giving a fairly generally accessible talk about a lot of different aspects of modern cryptography. She has a lot of perspective on this because she’s in industry — she does the underlying math and the deployment and implementation. She is one of the first people to propose using isogeny graphs in cryptography, for hash functions. You’ll find lots of interesting stuff in here about practicalities and cryptography in the real world, like the future of cryptography after quantum computing. It’s a great overview that should be just perfect for this moment in the course, where we’ve done the classical and pre-quantum crypto and are ready to dive into the newest of the new. Note: like a week or so after this video, SIKE (the isogeny-based proposal) was broken.
Hand in some reactions to the video: What questions did you have? What did you learn? 3-6 sentences is fine.
Please finish up the Web Worksheet on Complex Numbers. Please cover anything that was skipped Monday. You can hand in your notes from doing some of the little quiz questions on the way through.
You can use your daily post time to study for that and submit a few practice problems on canvas. (See the “Tests” tab and past daily posts for practice.)
Thank you for your patience with my travel schedule; I’ll be flying back tomorrow (Tue) morning, and will try to set a Tuesday afternoon office hour, but it depends on my flight not getting delayed, so I’ll post info/confirmation on discord/email.
There is a test coming up Wednesday! See the Tests tab above.
Figure out how many points are in $\mathbb{P}^1_{\mathbb{F}_5}$ and $\mathbb{P}^2_{\mathbb{F}_5}$.
Determine the points at infinity of the equation $Y^2 – X^2 + Z^2 = 0$ in $\mathbb{P}^2_{\mathbb{R}}$. That is, figure out how many elements of $\mathbb{P}^2_{\mathbb{R}}$ satisfy the equation with $Z=0$. (Hint: it is a finite number.)
With remaining time, review for Wednesday’s test. I will post example problems on the Tests tab ASAP.
Note: I’ve added Section 5.3 to the overleaf notes about pseudo-random number generators. We kind of had only a few minutes at the end of two lectures to talk about this, so it was a little chopped up. The notes should add a bit more info and clarify the main ideas.
We are mid-semester, so please make sure your self-eval sheet is up to date and hand in a copy with today’s daily post, so I can see how things are going. Please contact me if you are concerned about your grade. The grade in canvas is only a rough estimate; you can compute for yourself using this info.this info
To Do: An Elliptic Curve El Gamal Ciphertext Chain! Today’s question: best hallowe’en costume? You will encrypt your answer. Here are the steps:
As a group, we will all use the elliptic curve E given by $y^2 = x^3 + x^2 + x + 1$ over the finite field of p = 123456789101234567891027
elements. We will furthermore use the point P = [3,11655832467975276266127,1] on $E$, which has order 61728394550949287614731.
You should create a private and public key pair based on the information given above. Publish your public key on the #ciphertexts channel on discord. Keep your private key in a text document somewhere to use for decrypting later.
You should answer the question (Best halloween costume?) with a word of 6 or fewer letters. Translate this to an integer and add three digits of “padding” “000” at the end.
Turn your message into a point on the elliptic curve as described in class. This might mean updating the padding to “001”, “010” etc. until it works.
You should then obtain the most recent public key on the #public-keys channel, and encrypt your ASCII message (turned into a point on the curve) to that public key. Post your encryption to the #ciphertexts channel, @mentioning the owner of the public key it is encrypted to.
You should then keep an eye on the channel and when someone encrypts a message to your public key (they should @mention you), you should decrypt it and announce what the plaintext was, @mentioning them back.
When someone decrypts your message, you should give them a thumbs up to let them know it’s right (or let them know if it isn’t).
Hand in your notes from this exercise to the canvas dropbox.
Factor the number 184507 using the p-1 factoring method from today’s class. Tell me what you choose for a, and tell me what powers of a you compute, and tell me what gcd you tried, and what factor you found (you may need to keep lengthening the chain and trying again). You could use the Sage command “factorial(n)” if that seems useful. You can use the command “is_prime(n)” to check that you’ve factored it all the way. Do not ever use the command “factor(n)” since that’s cheating (except to check your answer after you’re done).
Use EC Factoring Tools to factor n = 290265623. You might want to increase the size of the loop! Use the result to factor n (that is, take the gcd of the non-invertible residue with n to get a non-trivial factor).
Now do it again with a different choice of curve and point (revisit lecture for some advice on finding random curve + point pairs). Factor n.
Now try modifying one of the middle digits of n, and see how long it takes. Factor n.
Try modifying one of the digits a couple more times and see how long it takes. Factor n.
Report to canvas on how long it took (what multiple of P) on different curves and points, and different n. Explain why you think it was fast sometimes and slow other times.