Given two square matrices A and B, can we tell if there is an invertible square matrix X such that XAX−1 = B? Yes, quickly! Such an X exists if and only if A and B are similar and there are efficiently computable invariants (such as the Frobenius normal form) that precisely characterize similarity. Phrased differently, we can tell if there is a basis change (conjugation, in this context) that takes one matrix (or the corresponding bilinear form) to the other. But one small step in dimension, jumping from two (square matrices) to three (three dimensional tensors given by a cube of numbers), is a giant leap in computational complexity. Most linear algebraic problems concerning three dimensional tensors (or equivalently, trilinear forms) are (NP- or VNP- or #P-)hard. Two post-quantum signature schemes, ALTEQ and MEDS, are built on the hardness of finding a basis change that takes one of two given trilinear forms (over finite fields) to the other. Also, many other multivariate cryptographic hardness assumptions reduce to such problems.

In this talk, we present new classical and quantum algorithms for solving the trilinear isomorphism problem underlying ALTEQ and MEDS.We improve on the run time exponent by a constant factor, thereby necessitating increasing the key/signature sizes of MEDS to meet the security demands. Key ingredients in our algorithms are new distinguishing invariants under the respective actions.

The talk will be catered to a quantum algorithms audience, without assuming familiarity with cryptography. It will partly be based on the following joint work with Youming Qiao and Gang Tang, but we will take some speculative tangents in hopes of more significantly faster quantum algorithms.