Are there trapdoor functions breakable by moderate polynomial degree complexity algorithm?

Question

Trapdoor function is a function $f$ that is easy to compute in one direction, yet difficult to compute in the opposite direction (finding its inverse) $f^{-1}$ without special information, called the "trapdoor".

Cryptographers use trapdoor functions and they frown upon subexponential complexity of breaking the trapdoor.

Recently we were working on a search problem which used $k$ nested loops from $1$ to $n$ and we realized the time complexity is $n^k$, which becomes very infeasible even for moderate values of $n,k$.

Let $n$ be the size of the input.

Q1 Is there trapdoor function which require time $n^k$ for some $k>1$?

Q2 Is there trapdoor function which require time $n^k$ when $k$ is moderately large, say $k>5$?

Q3 Is there trapdoor function based on matrix inversion?

The folklore complexity of matrix inversion is $O(n^3)$, but we believe the exact bit complexity is about $O(n^5)$.

Answer 1

Q1 goes right back to the dawn of public-key cryptography, with Merkle's Secure communications over insecure channels (see also Merkle's historical note on this). Merkle showed that running this cryptosystem costs $O(n)$, but adversaries cannot break the system in $o(n^2)$ operations. More recently, Baraz and Mahmoody have given an $O(n^2)$ attack, which is therefore asymptotically optimal.

These notions, including Q2, have been revisited in recent years as "fine-grained cryptography". Fine-grained one-way functions require a fixed polynomial gap between the running time of the cryptosystem for an honest user and the running time of an adversary, as opposed to the superpolynomial gap that is more traditional in conventional public-key crypto. Degwekar, Vaikuntanathan, and Vasudevan's CRYPTO 2016 article might be a good starting-point.