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). 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 might be a good starting-point.

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.