Storing private information

How should a company store private information about its customers, to lessen the danger of accidentally disclosing it, as AT&T has?

Perhaps the company should always store each customer's data encrypted so that only the customer knows the key. A company data breach reveals very little, though one must guard against phishing attacks attempting to lure the customer into revealing the key of the breached data.

Perhaps personal information should be stored only on each customer's personal server. If done correctly, an attacker steals only one identity for breaking one server, and it induces care on the customers' part to guard their information.

These are just seeds of ideas, unpractical as yet. Perhaps with a large mess of crypto and other engineering and financial innovations, they may become workable.