A computer-based system (10) and method for dis-identifying personal identifiable information (152, 162) and associated records (172) is disclosed. The system includes a system manager (20) module, an encryption and key management module (30), and a storage module (40). The system manager module (20) stores related sensitive information portions (152) of the personal identifiable information (152, 162), non-sensitive information portions (162) of the personal identifiable information, and associated records (172) in separate databases (100, 110, 120 or 150, 160, 170) in storage module (40) with each database record including one or more hidden links generated by the encryption and key management module (30) that can be used to determine the related records or information in one of the other databases. The hidden links are encrypted so that the relationships between the database records are hidden. The methods provide for storing sensitive and non-sensitive personal identifiable information and associated records as database records, and for storing the hidden links associated with these database records. The present invention also includes methods for retrieving sensitive personal identifiable information for a given associated record and for retrieving the associated record(s) for a given sensitive personal identifiable information.