Improving Algorithmic Efficiency using Cryptography: Trapdoored Matrices and Applications
Abstract
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.
Fields of Study & Subjects
Chaos-based Image/Signal Encryption
Cryptographic Implementations and Security
Cryptography and Data Security
Publication details
- Journal / source
- Society for Industrial and Applied Mathematics eBooks
- Publisher
- Society for Industrial and Applied Mathematics
- Pages
- 2554–2574
- Publication date
- 1 January 2026
- Language
- EN