International Association
for Cryptologic Research

We focus on the problem of constructing fully homomorphic encryption (FHE) schemes that achieve some meaningful notion of adaptive chosen-ciphertext security beyond $\ccai$. Towards this, we propose a new notion, called security against \textit{verified chosen-ciphertext attack} ($\nvcca$). The idea behind it is to ascertain the integrity of the ciphertext by imposing a strong control on the evaluation algorithm. Essentially, we require that a ciphertext obtained by the use of homomorphic evaluation must be "linked" to the original input ciphertexts. We precisely formalize the $\nvcca$ notion in two equivalent formulations; the first is in the indistinguishability paradigm, the second follows the non-malleability simulation-based approach, and is a generalization of the targeted malleability introduced by Boneh et al in 2012. We strengthen the credibility of our definitions by exploring relations to existing security notions for homomorphic schemes, namely $\ccai$, $\rcca$, $\funccpa$, $\ccva$, and $\hcca$. We prove that $\nvcca$ security is the strongest notion known so far, that can be achieved by an FHE scheme; in particular, $\nvcca$ is strictly stronger than $\ccai$. Finally, we provide a generic transformation, that takes \textit{any} $\cpa$-secure FHE scheme and makes it $\nvcca$-secure. Our transformation first turns an FHE scheme into a $\ccaii$-secure scheme where a part of the ciphertext retains the homomorphic properties and then extends it with a succinct non-interactive argument of knowledge to control the evaluation algorithm. In fact we obtain \emph{four} variations for the $\nvcca$-secure FHE construction, as we give two public-key variations and two symmetric-key ones. As a direct implication, we get the \emph{first} $\ccai$-secure FHE schemes that is based on \emph{bootstrapping} techniques.

WebAuthn, forming part of FIDO2, is a W3C standard for strong authentication, which employs digital signatures to authenticate web users whilst preserving their privacy. Owned by users, WebAuthn authenticators generate attested and unlinkable public-key credentials for each web service to authenticate users. Since the loss of authenticators prevents users from accessing web services, usable recovery solutions preserving the original WebAuthn design choices and security objectives are urgently needed. We examine Yubico's recent proposal for recovering from the loss of a WebAuthn authenticator by using a secondary backup authenticator. We analyse the cryptographic core of their proposal by modelling a new primitive, called Asynchronous Remote Key Generation (ARKG), which allows some primary authenticator to generate unlinkable public keys for which the backup authenticator may later recover corresponding private keys. Both processes occur asynchronously without the need for authenticators to export or share secrets, adhering to WebAuthn's attestation requirements. We prove that Yubico's proposal achieves our ARKG security properties under the discrete logarithm and PRF-ODH assumptions in the random oracle model. To prove that recovered private keys can be used securely by other cryptographic schemes, such as digital signatures or encryption schemes, we model compositional security of ARKG using composable games by Brzuska et al. (ACM CCS 2011), extended to the case of arbitrary public-key protocols. As well as being more general, our results show that private keys generated by ARKG may be used securely to produce unforgeable signatures for challenge-response protocols, as used in WebAuthn. We conclude our analysis by discussing concrete instantiations behind Yubico's ARKG protocol, its integration with the WebAuthn standard, performance, and usability aspects.