We're developing a REST API to be consumed by a couple of mobile applications. It's important that we're able to trust the identities of these mobile applications. In our current design, each API call is authenticated with an "API Key" parameter and secured with HTTPS.
My concern is that the API Key is embedded within each copy of the mobile app, which means there's no way we can keep it secret. It will be on thousands of phones, and theoretically any hacker with a binary editor or HTTP Traffic analyzer could extract the API key and then 'pose as' one of the applications, sending us requests that we'd have no choice but to trust. Client certificates would appear to have the same risk.
Is there an architecture that solves this problem?