Improving Algorithmic Efficiency Using Cryptography

Cryptographic primitives have been used for various non-cryptographic objectives, such as eliminating or reducing randomness and interaction. We show how to use cryptography to improve the time complexity of solving computational problems. Specifically, we show that under standard cryptographic assumptions, we can design algorithms that are asymptotically faster than existing ones while maintaining correctness.

We introduce and construct "Trapdoor Matrix Distributions", using which, we present the first uniform reduction from worst-case to approximate and average-case matrix multiplication with optimal parameters (improving on HS2025, albeit under computational assumptions), the first WC to average-case reductions for matrix inversion and other linear operations, fast general-purpose dimension reductions, as well as a speedup of inference time in classification models.

Based on joint work with Vinod Vaikuntanathan.