Hi Rodd,
> When adding a new personnel record, a search was done to ensure the person did not already exist in the system (possibly under a nickname, etc.)
You can achieve the same if you store a hash value of the SSN in the table. Hash values are irreversible which makes it impossible to get a SSN from a hash. However, the same SSN will always generate the same hash allowing you to search for the hash value to find existing entries.
> Is a single key used to encrypt all ssns with AES-256 sufficient or should each ssn be encrypted using a key generated with a unique seed value?
AES is a block cipher which doesn't necessarily require a different key for every record. The question is how much security you would gain by using different keys. Most likely, you are not really using different keys, but somehow generate keys out of the existing one, for example by adding data from the record, the ID, or something similar. So, if you embed the key in the application and someone got it out of the app, it's not unlikely that this person also found out how you generate these individual keys.
Different keys do increase security. However, the question really comes down to: How hard is it to get hold of the key?
--
Christof