Hardness Self-Amplification in Linear Algebra and Fine-Grained CryptographyResearch Paper
Fine-grained cryptography asks for primitives secure only against adversaries of moderate polynomial running time. One natural candidate is the map : evaluating it takes field operations, while the best known way to invert it solves a linear system in operations, where is the matrix multiplication exponent (Alm…