This paper introduces a new lattice-based cryptographic structure called a bonsai tree, which resolves several important open problems in lattice-based cryptography. The bonsai tree is used to construct an efficient, stateless 'hash-and-sign' signature scheme in the standard model (without random oracles) and the first hierarchical identity-based encryption (HIBE) scheme that does not rely on bilinear pairings. The abstract properties of bonsai trees have no known realization in conventional number-theoretic cryptography. The bonsai tree is a hierarchy of trapdoor functions with certain properties. The arborist (e.g., the signer in a signature scheme or a simulator in a security proof) can control certain branches of the tree by knowing a trapdoor for the associated function. Control automatically extends down the hierarchy, meaning that knowing a trapdoor for a parent function implies knowing a trapdoor for any of its children. In the lattice-based instantiation, the functions in the tree are indexed by a hierarchy of public lattices chosen at random from a certain 'hard' family. The lattices may be specified by a variety of means, such as a public key, interaction via a protocol, or a random oracle. Their key property is that they naturally form a hierarchy, where every lattice in the tree (excepting the root) is a higher-dimensional superlattice of its parent. Undirected growth in the bonsai tree is technically straightforward and emerges naturally from the underlying hard average-case lattice problems (SIS and LWE). This growth is useful for letting a simulator embed a challenge problem into one or more branches of the tree. Controlled growth is achieved by having the arborist know a short basis for the associated lattice. The hierarchy of lattices is specially designed so that any short basis of a parent lattice can be easily extended to a short basis of any higher-dimensional child lattice, with no loss in quality. This means that control of a branch implicitly comes with control over all its offshoots. The paper presents two main applications of bonsai trees: a hash-and-sign signature scheme without random oracles and a hierarchical identity-based encryption scheme. The signature scheme is secure in the standard model under conventional lattice assumptions and has a 'hash-and-sign' flavor that does not use the key-refresh/authentication-tree paradigm of many prior constructions. The HIBE scheme is the first HIBE that does not rely on bilinear pairings and is anonymous across all levels of the hierarchy. The paper also discusses variations of bonsai trees and their applications, as well as related techniques and works. The main cryptographic security parameter is n, and all algorithms are implicitly given the security parameter n in unary. The paper concludes with a discussion of the complexity and open problems in the area.This paper introduces a new lattice-based cryptographic structure called a bonsai tree, which resolves several important open problems in lattice-based cryptography. The bonsai tree is used to construct an efficient, stateless 'hash-and-sign' signature scheme in the standard model (without random oracles) and the first hierarchical identity-based encryption (HIBE) scheme that does not rely on bilinear pairings. The abstract properties of bonsai trees have no known realization in conventional number-theoretic cryptography. The bonsai tree is a hierarchy of trapdoor functions with certain properties. The arborist (e.g., the signer in a signature scheme or a simulator in a security proof) can control certain branches of the tree by knowing a trapdoor for the associated function. Control automatically extends down the hierarchy, meaning that knowing a trapdoor for a parent function implies knowing a trapdoor for any of its children. In the lattice-based instantiation, the functions in the tree are indexed by a hierarchy of public lattices chosen at random from a certain 'hard' family. The lattices may be specified by a variety of means, such as a public key, interaction via a protocol, or a random oracle. Their key property is that they naturally form a hierarchy, where every lattice in the tree (excepting the root) is a higher-dimensional superlattice of its parent. Undirected growth in the bonsai tree is technically straightforward and emerges naturally from the underlying hard average-case lattice problems (SIS and LWE). This growth is useful for letting a simulator embed a challenge problem into one or more branches of the tree. Controlled growth is achieved by having the arborist know a short basis for the associated lattice. The hierarchy of lattices is specially designed so that any short basis of a parent lattice can be easily extended to a short basis of any higher-dimensional child lattice, with no loss in quality. This means that control of a branch implicitly comes with control over all its offshoots. The paper presents two main applications of bonsai trees: a hash-and-sign signature scheme without random oracles and a hierarchical identity-based encryption scheme. The signature scheme is secure in the standard model under conventional lattice assumptions and has a 'hash-and-sign' flavor that does not use the key-refresh/authentication-tree paradigm of many prior constructions. The HIBE scheme is the first HIBE that does not rely on bilinear pairings and is anonymous across all levels of the hierarchy. The paper also discusses variations of bonsai trees and their applications, as well as related techniques and works. The main cryptographic security parameter is n, and all algorithms are implicitly given the security parameter n in unary. The paper concludes with a discussion of the complexity and open problems in the area.