We look at issues that arise when data being encrypted and keys used to encrypt the data are related. We look at the incidence of such relations in disk encryption and password-based encryption, and design practical solutions to address the issue. We explore problems in outsourced storage where keys and messages are related by design, and develop a new framework, message-locked encryption, to provide practical and theoretically interesting solutions. We look at a new framework for studying hash functions, called Universal Computational Extractors towards proving security for some of our constructions from cleaner assumptions