Auditable asymmetric password authenticated public key establishment

Non-repudiation of user messages is a desirable feature in a number of online applications, but it requires digital signatures and certified cryptographic keys. Unfortunately, the adoption of cryptographic keys often results in poor usability, as users must either carry around their private keys (e.g., in a smart-card) or store them in all of their devices. A user-friendly alternative, adopted by several companies and national administrations, is based on so-called “cloud-based PKI certificates”. In a nutshell, each user has a certified key-pair stored at a server in the cloud; users authenticate to the server—via passwords or one-time codes—and ask it to sign messages on their behalf. However, moving the key-pair from user-private storage to the cloud impairs non-repudiation. In fact, users can always deny having signed a message, by claiming that the signature was produced by the allegedly malicious server without their consent. In this paper we present Auditable Asymmetric Password Authenticated Public Key Establishment (A2PAKE" role="presentation" style="box-sizing: inherit; display: inline; line-height: normal; word-spacing: normal; overflow-wrap: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0px; min-height: 0px; border: 0px; padding: 0px; margin: 0px; position: relative;">A2PAKE
$\mathsf{A}{}^{\mathsf{2}}\mathsf{P}\mathsf{A}\mathsf{K}\mathsf{E}$

), a cloud-based solution to allow users to manage their signing key-pairs that (i) has the same usability of cloud-based PKI certificates, and (ii) guarantees non-repudiation of signatures. We do so by introducing a new ideal functionality in the Universal Composability framework named FA2PAKE" role="presentation" style="box-sizing: inherit; display: inline; line-height: normal; word-spacing: normal; overflow-wrap: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0px; min-height: 0px; border: 0px; padding: 0px; margin: 0px; position: relative;">FA2PAKE
${\mathcal{F}}_{\mathsf{A}{}^{\mathsf{2}}\mathsf{P}\mathsf{A}\mathsf{K}\mathsf{E}}$

. The functionality is password-based and allows to generate asymmetric key-pairs, where the public key is output to all the parties, but the secret key is the private output of a single one (e.g., the user). Further, the functionality is auditable: given a public key output by the functionality, a server can prove to a third party (i.e., a judge) that the corresponding secret key is held by a specific user. Thus, if a user signs messages with the secret key obtained via A2PAKE" role="presentation" style="box-sizing: inherit; display: inline; line-height: normal; word-spacing: normal; overflow-wrap: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0px; min-height: 0px; border: 0px; padding: 0px; margin: 0px; position: relative;">A2PAKE
$\mathsf{A}{}^{\mathsf{2}}\mathsf{P}\mathsf{A}\mathsf{K}\mathsf{E}$

, then signatures are non-repudiable. We provide an efficient instantiation based on distributed oblivious pseudo-random functions for signature schemes based on DLOG. We also develop a prototype implementation of our instantiation and use it to evaluate its performance in realistic settings.