Alkaline: A Simplified Post-Quantum Encryption Algorithm for Classroom Use

Abstract

This paper describes Alkaline, a size-reduced version of Kyber, which has recently been announced as a prototype NIST standard for post-quantum public-key cryptography. While not as simple as RSA, I believe that Alkaline can be used in an undergraduate classroom to effectively teach the techniques and principles behind Kyber and post-quantum cryptography in general. Classroom experiences with individual concepts used in Alkaline support this belief. In addition to cryptography, linear algebra and abstract algebra classes would be good candidates for the use of Alkaline. A few exercises suitable for use in these classes are included.

Keywords:

• Post-quantum
• Kyber
• classroom
• cryptography
• public-key

ACKNOWLEDGMENTS

I would like to thank the guest editors and the anonymous reviewers for many helpful comments. I would also like to thank all of the students over the years who have helped to playtest my simplified cryptographic systems.

DISCLOSURE STATEMENT

No potential conflict of interest was reported by the author(s).

BIOGRAPHICAL SKETCH

Joshua Holden is the Endowed Chair for Innovation in Science, Engineering & Math Education and Professor of Mathematics at the Rose-Hulman Institute of Technology, a private undergraduate math, science, and engineering college in Indiana. His research interests are in computational and algebraic number theory, cryptography, and the application of mathematics in the arts. His teaching interests include the use of technology in teaching and the teaching of mathematics to computer science majors, as well as the use of historically informed pedagogy. His non-mathematical interests used to include fiber arts and music, but those now seem to be mathematical interests. He is the author of a popular-science book on cryptography and its history.

Notes

1 Note that competing Post-Quantum proposals included NewHope and SABER, which has a version called LightSABER.

2 This distinction will become relevant when we consider objects which have been reduced both modulo q and then modulo 2. This would be nonsensical if we considered modulo as a relation rather than an action. At the very least, we will get a different answer depending on the order in which we do the operations, which should not be the case for relations.

3 Note that this is a case where if the $\mathrm{M}\mathrm{O}\mathrm{D}$ operations are done at the wrong point of the computation, for example, if the $\mathrm{M}\mathrm{O}\mathrm{D}2$ reduction is too early, the result will be incorrect.

4 Feel free to now forget what the “M” stands for if you like; we will not be mentioning modules again in this paper.

5 This script was clearly not designed for such small parameters and the result should be taken with a grain of salt, although limited testing suggests the failure is not significantly greater than reported. A version of the script modified to run on small parameters without crashing is available on GitHub [13].

6 To be exact, there is a trade-off between speed and failure rate in these algorithms. LLL runs in time polynomial in the dimension, but has a failure rate exponential in the dimension. BKZ can be tuned to have a polynomial failure rate, but then has an exponential running time. See Hoffstein et al. [9, Sec. 7.13.4] for more details.