ちょっと公開鍵の暗号化の仕組みの理解が曖昧なので間違っているかもしれませんが
結局Android側に復号鍵があるのでその鍵と復号ロジックを解析されたら終わりという事ですよね？
それならAndroid側で何度も暗号化を繰り返すという方法の方が実装も簡単で
強度もそんなに変らないのかなと思ったのですがどうなんでしょうか？

・以前の案
ローカル：A(秘密鍵)に対応するB(公開鍵)をサーバに送信
サーバー：Bでタネxを暗号化しローカルに送信
ローカル：Aでxを復号化してf(x)=yを生成
「y + (重要データ)z」= P のような形にする
サーバー：X(秘密鍵)に対応するY(公開鍵)をローカルに送信
ローカル：PをYで暗号化しサーバに送信
サーバー：PをXで復号化しデータの正当性チェック

・今回の案
ローカル：「f(x)+重要データ」を何度もそれぞれ異なる暗号鍵と暗号アルゴリズムで暗号化してサーバに送信
サーバー：ローカルでやった手順を遡って復号化し正当性チェック