Techniques are disclosed relating to user authentication using multi-party computation and public key cryptography. In some embodiments, a server may receive, from a client, a request to authenticate a user to a service. The server may access key-pair information that includes, for a server key-pair, a first component of a server private key and, for a client key-pair, a client public key and a first component of a client private key. The server may generate a partial signature value that is based on the first component, but not the entirety, of the server private key. The server may send, to the client, an authentication challenge that includes challenge information and the partial signature value. The server may then determine whether to authenticate the user based on an authentication response from the client.