As an aside SSNs really need a massive overhaul. In theory they're meant to only be used for government stuff, but their use is now so broad (finance, insurance, medical, et al) that their leakage is all too common and the potential cost of a leak too damaging.
With a little bit of investment the SSA could continue to generate SSNs (for historical reasons and government department usage) and generate a new SSID which is just a longer unique number which companies are legally prohibited from storing, however when they receive it they forward it to the SSA via an API and it returns a static unique customer number (UCN) which they can then in fact store.
This has the following advantages:
- The SSA can update your SSID a lot. Every few years, every new card, or when requested. Unlike SSNs which cannot be changed.
- Updating your SSID won't break existing accounts or similar, as companies won't store the old one anyway (only the resulting UCN). Unlike SSNs which break stuff if changed.
- Leaked UCNs are not as useful because you cannot enter them into a web-site or put them on a financial form directly (it would be a different length/format to SSIDs or SSNs on purpose). Unlike SSNs which can be directly reused.
- The system doesn't depend on complex cryptography. It is just a simple perhaps JSON request over HTTPS.
You could deploy this system over ten years at minimal cost. The system is relatively simply, and behind the scenes it can tie UCNs to SSNs in the SSA's database system. A single customer would have three things (in this system): Current SSID, static SSN, static UCN.