A payment system implemented on a mobile device authenticates transactions made via the mobile device. The mobile device generates a public-private key pair and receives an authenticating input from a user of the device. The public key is sent to a secure payment system, and the authenticating input is used to generate a symmetric key that encrypts the private key. After a transaction is initiated, the mobile device receives an authenticating input from the user. The symmetric key is generated from the authenticating input and the mobile device attempts to decrypt the private key from the encrypted private key using the symmetric key generated by the user's input. The decrypted key is used to sign a transaction authorization message which is sent to the secure payment system, along with payment information, which can verify the signed message via the public key. Additional techniques related to secure payments are also disclosed.