Mathematics of privacy? I wonder to which extent the current public debate on privacy issues (not only by state sniffing, but e.g. by microtargetting ads too an issue) offers interesting questions in mathematics? 
Can we expect proven and durable software solutions? 
Question stimulated by AdLeaks 
 A: I don't know what you can expect.  You might be interested in work of Cynthia Dwork on the concept of differential privacy.  The idea concerns what information can be revealed by queries to a database in spite of attemts to anonymize or average the data or limit the scope of the queries.  It seems some valid statistical analyses can be done even if the answerer throws in a random but intentional error to help protect privacy.
The article at jeremykun.com mentioned in Samuel Monnier's comment also mentions Dwork.  The other answers should
give you enough encouragement to check out the research.
A: Here is an example of the type you appear to be seeking. The story -- like many good stories -- involves a million dollar prize offered by a billion dollar corporation, sought by armies of computer wizards. There's even a courtroom scene at the climax. 
In 2007, Netflix released a dataset consisting of roughly a hundred million movie ratings (from 1 through 5 stars) given by 500 thousand users. The basic idea was to award prize money to anyone who managed improve upon the existing Netflix algorithm for predicting (based on your past ratings) how much you will like a new movie. A team from AT&T research won the million dollar prize by producing an algorithm which improved the state of the art by 10% or so. Many references for those interested in the full story can be found on wikipedia here.
Of course, in order to preserve their users' privacy, Netflix "anonymized" their dataset. Meaning, they removed all mention of user names and ip addresses, etc before making the data available to the public. Much to their surprise (and their users' annoyance), a team of computer scientists from the University of Texas used publically available non-anonymous data from IMDB and deduced the identities of many Netflix users. I'm not qualified to judge the sophistication of their framework, but from a glance at their paper there certainly seems to be some non-trivial mathematics involved.
Here's an open question: 

what statistical properties of your anonymized data might guarantee (with high probability) that it can not be de-anonymized?

I suspect that such considerations are likely to guide a lot of research in statistics at least in the foreseeable future
A: Proving and verifying statements about private data without releasing that data is a nice candidate question/problem with some known solutions. Let me hereby name interactive proof/argument systems, zero knowledge, commitments, oblivious transfer as well as implementations like U-Prove, DAA, Idemix.
"How to prove a theorem so no one else can claim it", Manuel Blum, International Congress of Mathematicians, 1986.
A: The mathematics of privacy is a HUGE area of research. It started in the statistics community way back when, with issues of disclosure along the lines of what Vidit Nanda mentioned. In the 90s, things exploded in the CS community when a researcher at CMU first showed that using only publicly disclosed information she could retrieve private information about the governor of Massachusetts. 
Perhaps the most mathematically mature take on privacy is the idea of differential privacy: like in crypto, it frames the problem in terms of what's computationally feasible. Specifically, the classic problem of differential privacy is: design a scheme to release data so that a computationally bounded adversary cannot tell the difference between the released data and a release of a db that differs on one element with more than an exponentially small probability. 
A: Another interesting topic is on performing computation on encrypted data. For example, you can have your data encrypted and yet use cloud services on them. There are mathematicians and computer scientists working on this, however the current constructions are not efficient enough for practical purposes yet (AFAIK).
The keyword to search for is Homomorphic encryption.
For example, have a look at Vinod Vaikuntanathan's expository article "Computing Blindfolded: New Developments in Homomorphic Encryption" for FOCS 2011.
