Bonsai Trees or How to Delegate a Lattice Basis David Cash Dennis Hofheinzy Eike Kiltzz Chris Peikertx June 14 2011 of Homeland Security under Contract Number HSHQDC 07 C 00006 and the Alfred P Sloan Foundation Any opinions findings Our first application of bonsai trees is an efficient stateless signature scheme that is