In today's digital world, computer security issues have become increasingly important. In particular, researchers have proposed designs for secure processors which utilize hardware-based mem- ory encryption and integrity verification to protect the privacy and integrity of computation even from sophisticated physical attacks. However, currently proposed schemes remain hampered by prob- lems that make them impractical for use in today's computer sys- tems: lack of virtual memory and Inter-Process Communication support as well as excessive storage and performance overheads. In this paper, we propose 1) Address Independent Seed Encryption (AISE), a counter-mode based memory encryption scheme using a novel seed composition, and 2) Bonsai Merkle Trees (BMT), a novel Merkle Tree-based memory integrity verification technique, to elim- inate these system and performance issues associated with prior counter-mode memory encryption and Merkle Tree integrity veri- fication schemes. We present both a qualitative discussion and a quantitative analysis to illustrate the advantages of our techniques over previously proposed approaches in terms of complexity, feasi- bility, performance, and storage. Our results show that AISE+BMT reduces the overhead of prior memory encryption and integrity ver- ification schemes from 12% to 2% on average, while eliminating critical system-level problems.