I have intentionally NEVER done this all semester, but I had ten more minutes of riveting information to share about lattice-based cryptography, so I made a bonus 10-minute video. (I’ve allowed myself this luxury because I really don’t want to delay coding theory.) Watch it here. The lecture notes include this material.

A Ring-LWE ciphertext chain! You may want to review the course video on canvas and I’ve made careful overleaf notes. Here’s what you’ll need:

Our general setup with be the prime p = 100003 and n=8. We will use l=10. This will allow us enough room for each coefficient to hold one letter from the text-to-integer-to-text tools. Because there are 8 coefficients, you can store 8 letters.

Answer the question “what’s the best part of crypto?” in 8 letters or less, and store it as an element of the ring $R_p$ using one letter per coefficient (coefficient of $x^7$ is the first letter, coefficient of $x^6$ is the second letter, etc.). This will be your message.

At the Ring-LWE Tools page you’ll see how to initialize the polynomial ring, and you’ll have two functions that generate short and random elements. In our case, “short” means coefficients from {-1,0,1}.

First, generate your own private/public key pair and post the public key (g,B) on the discord #ciphertexts channel. Keep your secret key for later (e.g. in a text file). Important note: discord normally interprets asterisks and stuff in special ways; to make it easier on everyone, surround your polynomials with backticks ` when pasting into discord, and it will post it verbatim. This will make cutting-and-pasting to/from Sage easier.

Now, encrypt your message to the most recent unused public key on the #ciphertexts channel. Post your message (K,C) on the #ciphertexts channel and mention the appropriate person.

Wait until someone sends you a message. When this happens, decrypt it using your secret key, and announce their favourite part of crypto on #ciphertexts, mentioning them so they can confirm.

Post your record of the events/computations to the canvas dropbox.

All the in-class assessments are complete. For each one, there is/was an opportunity to make up one Part B problem to improve your grade. For each there was a grade cutoff for doing the retake written (in-person only for grades below 7 on module 2, below 6 on module 3, below 5 on module 4 and all on module 5). You will find written retake problems for all of these on canvas (the final assessment will be written-retakes-only in the interests of time). If you missed out on one of these opportunities, please contact me and we can re-open an opportunity for you. Please look through your records and your canvas grades and let me know if I’ve made any errors.

The final day of class there will be an in-class presentation (to which I will be joining virtually).

That leaves us four lecture days for lattices & coding (sadly not enough). For this reason the final exam will be a larger proportion of comprehensive review than expected.

I apologize for not getting through material at the rate predicted. The grading adjustments have now been made on the website in red under “Grading” in the top bar.

Please go through your daily post activities and make sure I have a current version of your daily post self-evaluation sheet (and that you do too!).

By hand, find a reduced basis and a shortest nonzero vector in the lattice generated by (58,19) and (168,55). (We covered this in Monday’s class; also see section 17.2 in text, and the example in class is written up in the overleaf notes.)

You have a test! I’ll be happy to have office hours, which I will announce on discord if we set some times, but that will include the hour 9-10 am before the test for last-minute stuff (room 308). Thursday I can be found on discord/zoom.

Please play with the Shor’s Algorithm Demo and do a couple continued-fraction expansions by hand to match with the Sage output there, to make sure you know how.

I have posted some quantum-review questions on the “Goals” page (with solutions).

Demonstrate the classical part of Shor’s algorithm using Sage, as follows:

Choose N = 33463.

Let a be your favourite random integer between 1 and N-1.

Define R = IntegerModRing(N) and alpha = R(a). The Sage command alpha.multiplicative_order() will play the role of the quantum computer; it outputs the multiplicative order of alpha.

Use the result to factor N, in the manner of Shor’s algorithm, as described in class. If it doesn’t work, try another random a (as you would in Shor’s algorithm).

This exercise gets you closer to computing a discrete logarithm on a quantum computer. Suppose $h = g^a$ for some unknown $a$. Consider the function $f: \mathbb{Z}/(p-1)\mathbb{Z} \times \mathbb{Z}/(p-1)\mathbb{Z} \rightarrow \mathbb{Z}/p\mathbb{Z}$ given by $(x,y) \mapsto h^{-x} g^y \pmod p$.

For what values of $(x,y)$ do you have $f(x,y)=1$?

For what values of $(x,y)$ do you have $f(x,y) = g$?

Show that the function $f$ is constant on any line $L_K$ given by $y= ax + K$ for any constant $K$.

Show that $f$ is `periodic’ in the sense that it repeats when we add any $(z,az)$ to the input values. In other words, $f(x,y) = f(x+z,y+az)$.

Suppose you somehow discover that $f(x_1,y_1) = f(x_2,y_2)$ for different input pairs. Explain how you can compute $a$ from this.

I know the course has been covering lots lately. On Monday we will pull it all together and factor with a quantum computer. Please take your weekend daily post time and do what is most useful for you. Some ideas (just ideas, don’t feel obligated) are:

Catch up/revisit the last daily post (here are solutions) or earlier ones.

Revisit course notes and videos to solidify what we’ve got.

Read your textbook’s chapter on quantum, which is much more big-picture and fewer details.

There is a Module 5 Test on Friday, November 18th, 2022. As usual, I’ll try to update the “Goals” page with topics/review.

See the last daily post for retakes on last module test.

Compare your last daily post to the solutions here.

Read the Overleaf Notes section on “Quantum Fourier Transform” (currently 6.10 toward the end). This addresses notational handling of the QFT. (1 page) Please read actively, which means testing yourself as you go (for example, cover up the display we just derived and re-derive it).

If you want to do a written retake for the earlier modules (2 and 3) they are due on canvas — I’ve moved the due date back to Wednesday in case you lost track of this (I didn’t remind people a lot).

Module 4 retakes: if you wish to retake a grade of 0, 1, 2, 3, or 4, we will do it in person; otherwise we’ll have a written retake. Email or discord me to set up an in-person retake. The written retakes will open on canvas soon and you’ll have a few weeks.

Compare your answers to the last daily exercise to these solutions.

Watch this excellent 3Blue1Brown/MinutePhysics video (17:34) which closely relates to class. In particular, it revisits polarized photons and some of what we’ve done for class already, but then moves on to Bell States and Bell’s Theorem, which I wish we had time to do, but we are going to focus on quantum computation next. If anyone is curious, I have an old video doing the underlying math of this that I can put up on canvas.

If you’re curious, here’s an article about a Bell test at NIST here in Boulder and how they are using it to make random numbers.

Please look over your exams and the solutions and let me know if there are any grading questions etc. There’ll be a re-do opportunity as before (more info soon).

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.