Be very careful. Don't ignore the fact that an attacker can brute force the SSNs from your database without knowing the encryption key.
If your attacker can use your system to encrypt an SSN, (perhaps by signing up a user, changing the value of SSN, and watching for the changed encrypted SSN field in the database) he can learn encrypted SSNs simply by trial and error. Imagine him setting the SSN to 000-00-0000. Your system encrypts it, and he compares the encrypted value to all the other encrypted SSNs in your database. If his test value matches one of the other values, he has learned that person's SSN. He then changes his SSN to 000-00-0001, and tries again.
Given 999,999,999 tries, he will be able to build up a "rainbow table" that contains every possible SSN. But he certainly doesn't need to do that much work to make a profit.
Most attackers are opportunistic. They don't need every SSN in your database to commit identity fraud, they only need to guess one SSN to start stealing. (The more SSNs they steal, the richer they can get, so of course they want as many as they can.) So maybe they only have time to run their attack for a little while, and they will still be satisfied with guessing a few.
The more people in the database, the more likely the attacker will be successful quicker.
Additionally, it's much easier than random guessing. Many people are unaware that until just a few years ago, SSNs were issued by geographic region.
Consider an attacker from Utah that wants to commit identity fraud using a Utah address. His attack will guess only numbers in the range from 528-00-0000 through 529-99-9999. That only takes 2 million guesses, not 1 billion, and is likely to have a high rate of success on your customers that have Utah listed as the state on their address.
The search space for SSNs is so small it is easily searchable by an attacker with modest resources. You need to take extra steps to protect the data and the systems from this kind of attack.