Let us say that I have a Windows Phone application. If I hardcode a private key in the Windows Phone application, can people extract it once the application is released to the public on the Windows Store?
I am asking this because I have found no way of accessing installed certificates from the phone.
With software, reverse engineering works (there is even a dedicated StackExchange site for reverse engineering questions). Extracting secrets from compiled binaries has been done and redone and done again since the days of the first "copy-protected" games for personal computers, back in the 1980s. The bottom-line is that you cannot really hide a secret value in an application.
What you can do is to hide a customer-specific secret in the application. This is similar to giving to each customer his own login+password, except that the human customer does not see it (it is hidden in the application). This won't prevent reverse-engineering, but it may help with mitigating consequences: if a given "application secret" appears to be leaking too much (e.g. hundreds of different clients use it), then you can invalidate that secret on the server, without impacting the rest of your user base. (I assume here that your private key, to be hidden in the application, is used to talk to a server that you control.)
This is somehow equivalent to the Blu-Ray security model: each (physical) player has a player-specific key, and content distributors can blacklist keys which are known to have been leaked through reverse-engineering (the actual blacklisting uses a nifty system called broadcast encryption because it needs to work even without a network; but a Windows phone is a phone, thus presumed network-able).
