Trying to find a way to secure a client certificate from stealing

I am developing an application that connects to a "Web Service" that I have written in PHP. The client app has 5 games which you can play and your score is then sent to the Web Service. I want to prevent someone from connecting to my Web Service and writing big scores he hasn't achieved. The connection is simple - I use encryption to secure the connection and exchange data, but the problem is that I want only my application to be able to connect with the Web Service I wrote. So, when I connect to the service, I check my Web Service to see if its public key is matching the one I have stored (to prevent man-in-the-middle attacks). But how do I check if the application that is connecting to the server is my application? I thought about using a certificate which I can send to the server, but anyone can download a decompiler (for example JustDecompile from Telerik, I am using .NET C# to make the client app) and see and steal the certificate. He can even alter my public key validation, but that won't be my application anymore. So the problem is - how to prevent someone who have downloaded my app from decompiling it and then stealing my certificate? How to protect my certificate? Or, if it is not possible, how to validate that my app is connection to the Web Service, and not some other?