Conditional Encryption with Applications to Secure Personalized Password Typo Correction

We introduce the notion of a conditional encryption scheme as an extension of public key encryption. In addition to the standard public key algorithms (KeyGen, Enc, Dec) for key generation, encryption and decryption, a conditional encryption scheme for a binary predicate P adds a new conditional encryption algorithm CEnc. The conditional encryption algorithm c = CEnc pk (c1, m2, m3) takes as input the public encryption key pk, a ciphertext c1 = Enc pk (m1) for an unknown message m1, a control message m2 and a payload message m3 and outputs a conditional ciphertext c. Intuitively, if P (m1, m2) = 1 then the conditional ciphertext c should decrypt to the payload message m3. On the other hand if P (m1, m2) = 0 then the ciphertext should not leak any information about the control message m2 or the payload message m3 even if the attacker already has the secret decryption key sk. We formalize the notion of conditional encryption secrecy and provide concretely efficient constructions for a set of predicates relevant to password typo correction. Our practical constructions utilize the Paillier partially homomorphic encryption scheme as well as Shamir Secret Sharing. We prove that our constructions are secure and demonstrate how to use conditional encryption to improve the security of personalized password typo correction systems such as TypTop. We implement a C++ library for our practically efficient conditional encryption schemes and evaluate the performance empirically. We also update the implementation of TypTop to utilize conditional encryption for enhanced security guarantees and evaluate the performance of the updated implementation. Full Version: This document provides the full version of the article published at CCS 2024 under the same title -see https://doi.org/10.1145/3658644.3690374 . 1 For the Hamming Distance predicate (e.g., predicate requires time proportional to ( n d ) where n is the length of the messages m 1 and m 2 and d is the Hamming Distance that we tolerate. This can be slow when both d and n are large. However, in our target password applications the desired distance parameter d for our Hamming Distance predicate (resp. edit-distance predicate) is relatively small (e.g., d = 2) as is the parameter n (e.g., n ≤ 32). Finding efficient constructions for the Hamming Distance (or Edit-Distance) predicate when n and d are both large is left as an open challenge for future research. 2 https://github.com/mhassanameri/CondEncCCS24Artifact 3 https://zenodo.org/records/13744111 4 Over 99.9% of leaked RockYou passwords were less than 30 characters. 3 TypTop system does not increase authentication delays although it does increase the storage requirements for the authentication server by a factor of ≈ 246. Fortunately, per user storage will not be a limiting factor in most settings. See Section 4 and Table 2 for more details. Related work At a high level the notion of conditional encryption might seem similar to other advanced public key primitives such as identity based encryption [BF01,