Optimising Program Generation for Post-quantum Cryptography

Primary supervisor

Ron Steinfeld

Co-supervisors

Recently, program generation and optimisation techniques have been adapted to performance critical subroutines in cryptography. Codes generated/optimised by these techniques are both secure and their performance is highly competitive compared to hand-optimised code by experts [1].

 

Student cohort

Double Semester

Aim/outline

This project aims to investigate how to adapt the program optimisation techniques [1] to performance critical subroutines in post-quantum cryptography. A primary goal is to optimise the program generation of the Number Theoretic Transform vectorised with the AVX2 instructions [2,3,4]. The Number Theoretic Transform is a variant of the Fast Fourier Transform over a finite field, and is a key subroutine in lattice-based cryptography.

 

URLs/references

[1] Joel Kuepper, Andres Erbsen, Jason Gross, Owen Conoly, Chuyue Sun, Samuel Tian, David Wu, Adam Chlipala, Chitchanok Chuengsatiansup, Daniel Genkin, Markus Wagner, Yuval Yarom: CryptOpt: Verified Compilation with Random Program Search for Cryptographic Primitives. https://arxiv.org/abs/2211.10665

[2] Masahiro Masuda, Yukiyoshi Kameyama: FFT Program Generation for Ring LWE-Based Cryptography. IWSEC 2021: 151-171

[3] Masahiro Masuda, Yukiyoshi Kameyama: Unified Program Generation and Verification: A Case Study on Number-Theoretic Transform. FLOPS 2022: 133-151

[4] Ryo Tokuda, Yukiyoshi Kameyama: Generating Programs for Polynomial Multiplication with Correctness Assurance. PEPM@POPL 2023: 27-40

Required knowledge

Depending on the nature of the specific project topic selected, the student should have one (or more) of:

  • Knowledge/skills in program generation
  • Knowledge/skills in optimisation

Knowledge in cryptography is not required.

If in doubt, please contact the primary supervisor for advice.