Certain fundamental tasks that are provably impossible under standard cryptographic assumptions---ones that are secure against \emph{arbitrary polynomial-time} attackers---turn out to be possible under time-based assumptions---ones that \emph{can be broken} in some polynomial, parallel time $T$ but cannot be broken in parallel time $T' < T$.Most notably, this is the case for the task of generating trusted randomness among a group of parties over the internet, which has received immense renewed interest for its applications in the distributed settings of decentralized blockchains. The goal of this thesis is to build a \emph{stronger theoretical foundation} for the use of time-based assumptions in cryptography. First, we give new protocols for generating trusted randomness and running sealed-bid auctions using time-lock puzzles---a timed analog of standard cryptographic commitments. To do so, we provide the first formal treatment of non-malleability for time-lock puzzles, which has been extensively studied for plain commitments. We show that fully concurrent non-malleability is impossible to achieve in the timed setting, so we introduce a weaker notion, which we call \emph{functional} non-malleability, that is both achievable and suffices for our applications. Next, we introduce the notion of a \emph{continuous verifiable delay function} (CVDF): a function $g$ such that, for every $t$, the $t$-wise iteration $g^{(t)}$ of $g$ is a (plain) verifiable delay function. This means that $g^{(t)}$ (on a random input) cannot be computed in parallel time less than $t$ times the time to compute $g$, and the output of $g^{(t)}$ can be efficiently verified (in time essentially independent of $t$). We show that CVDFs imply public randomness beacons and hard-on-average instances for the complexity class PPAD (for which finding Nash equilibria is a complete problem). We construct CVDFs from the time-based repeated squaring assumption, and the soundness of the Fiat-Shamir heuristic for constant round proofs. Finally, we study tradeoffs in the complexity of proofs for the repeated squaring relation, which are one of the main tools used in practical time-based cryptographic applications.We consider non-interactive proofs for the relation $y\stackrel{?}{=}x^{2^T} \mod N$ for an RSA modulus $N$, where the verifier has generic access to the input group elements $x,y$ and at most $k$ group elements sent by the prover. We show that any such (statistically sound) non-interactive proof of repeating squaring either (A) has verification time $\Omega(T/(k+1))$ for a proof with $k \ge 0$ group elements, or (B) leaks the factorization of $N$.