The paper introduces a new cryptographic structure called bonsai trees, which are based on lattice problems and have applications in various cryptographic schemes. Bonsai trees are used to resolve open problems in lattice-based cryptography, such as removing the need for random oracles in stateless 'hash-and-sign' signature schemes and facilitating hierarchical identity-based encryption (HIBE) without bilinear pairings. The authors present two main applications: an efficient, stateless signature scheme secure in the standard model and a collection of HIBE schemes that are the first to not rely on bilinear pairings. The security of these schemes is based on the hardness of lattice problems like the Short Integer Solution (SIS) and Learning with Errors (LWE). The paper also discusses the combinatorial techniques used in the constructions and their relation to other cryptographic primitives.The paper introduces a new cryptographic structure called bonsai trees, which are based on lattice problems and have applications in various cryptographic schemes. Bonsai trees are used to resolve open problems in lattice-based cryptography, such as removing the need for random oracles in stateless 'hash-and-sign' signature schemes and facilitating hierarchical identity-based encryption (HIBE) without bilinear pairings. The authors present two main applications: an efficient, stateless signature scheme secure in the standard model and a collection of HIBE schemes that are the first to not rely on bilinear pairings. The security of these schemes is based on the hardness of lattice problems like the Short Integer Solution (SIS) and Learning with Errors (LWE). The paper also discusses the combinatorial techniques used in the constructions and their relation to other cryptographic primitives.