A Proxy Authentication Network includes a server that stores credentials for subscribers, along with combinations of devices and locations from which individual subscribers want to be authenticated. Data is stored in storage: the storage can be selected by the subscriber. The data stored in the storage, which can be personally identifiable information, can be stored in an encrypted form. The key used to encrypt such data can be divided between the storage and server. In addition, third parties can store portions of the encrypting key. Subscribers can be authenticated using their credentials from recognized device/location combinations; out-of-band authentication supports authenticating subscribers from other locations. Once authenticated, a party can request that the encrypted data be released. The portions of the key are then assembled at the storage. The storage then decrypts the data, generates a new key, and re-encrypts the data for transmission to the requester.