In some implementations, tokens that are representative of sensitive data may be used in place of the sensitive data to maintain the security of the sensitive data. For example, data may be separated into sensitive data and nonsensitive data, and at least the sensitive data is securely delivered to a data storage service. The data storage service generates a token that is representative of the sensitive data and stores the sensitive data as secure data. The data storage service may deliver the token to an entity that also receives the nonsensitive data, and the entity may use the token in place of the sensitive data. In some implementations, different tokens are generated each time the same piece of sensitive data is submitted for storage as secure data. Further, in some implementations, access policies define authorizations regarding which entities are able to resolve a token to access the actual sensitive data.