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. As a concrete demonstration, we construct a distribution of trapdoored matrices with the following properties: (a) computationally bounded adversaries cannot distinguish a random matrix from one drawn from this distribution, and (b) given a secret key, we can multiply such a n-by-n matrix with any vector in near-linear (in n) time. We provide constructions both over finite fields and the reals. This enables a broad speedup technique: any algorithm relying on a random matrix - such as those using various notions of dimensionality reduction - can replace it with a matrix from our distribution, achieving computational speedups while preserving correctness.
The paper introduces a novel approach to improve the time complexity of solving computational problems by leveraging cryptography. The key idea is to replace random matrices in algorithms with trapdoored matrices, which are computationally indistinguishable from random matrices but allow for efficient multiplication when a secret key is available.
Significance: This work demonstrates a new application of cryptography beyond its traditional security purposes, showing that it can also be used to enhance the efficiency of algorithms. This approach has the potential to significantly speed up a wide range of algorithms that rely on random matrices, such as those used in dimensionality reduction, sketching, and other computational tasks.
Key Innovations:
1. Trapdoored Matrices: The introduction of trapdoored matrices, which are pseudorandom matrices that can be efficiently multiplied with a vector given a secret key.
2. Black-Box Reduction: The use of cryptographic indistinguishability to provide a black-box reduction from the correctness of the original algorithm to that of the modified algorithm using trapdoored matrices. This means that the correctness of the sped-up algorithm is guaranteed without needing problem-specific proofs.
3. Kac’s Random Walks: The introduction and motivation of a hardness assumption based on Kac’s random walks, which is used to construct trapdoored matrices over the reals.
Prior Ingredients Needed:
1. Cryptographic Hardness Assumptions: The constructions rely on standard cryptographic assumptions, such as the Learning Parity with Noise (LPN) problem and the McEliece assumption.
2. Random Matrices in Algorithm Design: The paper builds upon the extensive use of random matrices in modern algorithm design, particularly in areas like dimensionality reduction, sketching, and subspace embeddings.
3. Fast JL Transforms and Error-Correcting Codes: The paper draws inspiration from existing techniques that seek to optimize the computation of random matrices, such as Fast Johnson-Lindenstrauss (JL) Transforms and error-correcting codes with fast encoding.
| Action | Title | Date | Authors |
|---|
| Action | Title | Date | Authors |
|---|