With continued advances in computing, the amount of digital data continues to grow at an astounding rate. This has strained enterprise infrastructures and triggered development of service oriented architectures. In recent years, storage has also begun its transformation into a class of service. By outsourcing storage to an external storage service provider (SSP), enterprises not only cut management cost but also obtain on-demand infrastructure with superior disaster recovery and content dissemination capabilities. Wide deployment of this new outsourced storage environment requires solutions to many challenging problems. The foremost is the development of usable security and access control mechanisms that provide desirable levels of data confidentiality without placing an inordinate amount of trust into the SSP. This absence of a trusted reference monitor is a fundamental departure from traditional mechanisms and new solutions are required. The second important challenge is the autonomic management of SSP's infrastructure, uniquely characterized by a highly dynamic workload with large data capacity requirements. This dissertation research proposes models and techniques to address these two challenges. First, we introduce a novel access control system called xACCESS that uses cryptographic access control primitives (CAPs) to "embed" access control into stored data. This eliminates any dependency on the SSP for enforcement of security policies. We also analyze the privacy characteristics of its data sharing mechanisms and propose enhancements for more secure and convenient data sharing. We also develop a secure multiuser search approach that permits hosting of secured search indices at untrusted SSPs. We introduce a novel access control barrel (ACB) primitive that embeds access control into indices to prevent unauthorized information extraction during search. Our contribution to the autonomic SSP storage management has two important highlights. First, we have developed an impact analysis engine that efficiently analyzes the impact of a client-initiated change (workload surge, storage growth) on the SSP storage area network with minimal administrator involvement. Second, we have designed a new algorithm to quickly perform reallocation of resources in order to efficiently integrate the client change.