Establishment of a practical software protection method is a major issue in software distribution. There are several approaches to the issue; however, no practical, secure method for mobile phone applications has been proposed. In this paper, we propose a new software protection scheme combined with a tamper-proof device (TPD) in order to achieve computational security against illegal analysis and copying of the target program. Our scheme achieves a reasonable level of security for encoding the data and variables in a program. The program on a mobile phone deals only with encoded data that is difficult to compromise, and the TPD plays a role of decoding execution results. We implemented the proposed scheme on a 3G mobile phone and a user identification module (UIM). An analysis and copying of the protected program impose exponential computation complexities under our attack model.