Вот тебе решение, которое я считаю “приемлимым”: пишешь на крестах либу, в которой будет размешан твой зашифрованный ключ API (white-box aes тебе в помощь или свой колхоз). Эту же либу используешь для подписи запросов, т.е. ты шлешь в либу данные, а она тебе в ответ подпись. Эту подпись ты цепляешь к запросу. Сервак, естественно, знает по какому алгоритму все вычисляется и проводит ту же операцию с данными, сверяет подписи. И если они идентичны, то данные пришли от приложения (ну вы понимаете…)