In this paper, we broaden the applicability of peer-to-peer storage infrastructures to weakly-connected clients. We present a client-side technique that exploits the commonality between consecutive versions of a file to reduce the bandwidth required to store and retrieve files in a peer-to-peer storage infrastructure. We then present a novel data structure that allows us to use this technique in an environment where peers cannot be trusted to perform operations over unencrypted data.We have implemented the technique in the OceanStore prototype. Additionally, with simulations, we have demonstrated that the technique can reduce client-perceived latency of write and read operations by up to 80% compared to techniques used in current systems.