Conjectured hard problems are central to modern cryptography and thus to the security of the networked infrastructure on which modern society is built.We investigate the precise hardness of several such problems. In Chapter 1, we study preprocessing attacks aimed at the on-line inversion of arbitrary cryptographic functions. Thirty years ago, Fiat and Naor showed [FN91] that any function f: [N] ->[N] could be inverted in time essentially T using a preprocessed data structure of size S, so long as T S^3 >= O~(N^3). We present the first improvement to this result, showing how to improve the tradeoff curve in the important case S < T.Specifically, we show an algorithm that works for any S and T satisfying T S^2 max(S, T) >= O~(N^3). with the caveat that the on-line inversion procedure still requires S bits of temporary memory. We additionally give the first non-trivial non-adaptive algorithm for function inversion, show that it is optimal among a restricted class of non-adaptive algorithms, and present several equivalence results relating different versions of the function-inversion problem. In the remainder, we turn our attention to \emph{lattice problems}. Conjectured hard lattice problems form the basis for three of the four post-quantum secure cryptographic protocols selected by NIST in 2022 [NIS22a], and two of the three finalized in 2024 [NIS24]. Lattice problems are also the only widely accepted and reasonably practical foundation on which several advanced cryptographic functionalities, most notably fully homomorphic encryption (FHE), can be based. The best known attacks on conjectured hard lattice problems, first, run in nearly exponential time in the lattice dimension n, and second, make essential use of a family of techniques referred to as basis reduction algorithms. Regarding the first point, it is widely assumed by practitioners that such exponential-time attacks are best possible [APS15, ACD+18]. But from a theoretical perspective, the implications of this strengthened hardness assumption were largely unexplored. In Chapter 2, we study these implications. In particular, we show how to modify various important lattice algorithms, protocols, and reductions to make use of small-exponential running time. And, we show that both private- and public-key lattice-based cryptography exists assuming that lattice problems are hard to approximate to within smaller polynomial factors than previously known, when "hard" is meant relative to adversaries running in small-exponential time in addition to those running in polynomial time. Finally, in Chapter 3, we show an algorithmic framework for solving the same approximate lattice problems solved by basis reduction algorithms. More specifically, our framework solves the y-approximate Hermite shortest vector problem (y-HSVP), a central problem for attacks on lattice-based cryptography, with the same asymptotic running time (as a function of y) as basis reduction algorithms. The description and analysis of our framework are quite simple---considerably simpler, we feel, than the description and analysis of comparable basis reduction algorithms such as BKZ reduction. Our framework is also flexible, which we demonstrate by using it to improve on the best known algorithms for the Dense Sublattice Problem (a generalization of HSVP to sublattices of rank k >= 1) in the regime where k is large relative to the runtime budget.