Q1 goes right back to the dawn of public-key cryptography, with Merkle's [Secure communications over insecure channels](https://www.merkle.com/1974/PuzzlesAsPublished.pdf) (see also Merkle's [historical note](https://www.merkle.com/1974/) on this).  Running this cryptosystem costs $O(n)$, but adversaries require $o(n^2)$.

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](https://eprint.iacr.org/2016/580.pdf) might be a good starting-point.