Our CCS 2024 paper introduces the formal notion of conditional encryption and provides the first concrete constructions of this primitive. First, we give a formal definition of conditional encryption and establish a general feasibility result by showing how to realize conditional encryption for arbitrary predicates using circuit-private fully homomorphic encryption (FHE). While this result demonstrates the expressive power of the primitive, generic FHE-based solutions are often too expensive for practical deployment. To address this challenge, we develop efficient constructions tailored to predicates relevant for password authentication systems. In particular, we design practical conditional encryption schemes for predicates including Hamming distance at most two, edit distance at most one, and CAPSLOCK flip errors. These constructions rely on a combination of Paillier partially homomorphic encryption and Shamir secret sharing to efficiently evaluate predicates on encrypted data while preserving strong confidentiality guarantees. We also present a construction for the OR of these predicates, which corresponds exactly to the password-typo predicate used by the TypTop system for personalized password typo correction. Finally, we implement our conditional encryption constructions and integrate them into a modified implementation of TypTop to improve its security guarantees. Our source code has been released publicly, and the artifact associated with the CCS 2024 paper was independently reviewed and received all three artifact evaluation badges: Artifact Available, Artifacts Evaluated, and Results Reproduced.
Conditional Encryption
Principal Investigator: Jeremiah Blocki
Public-key encryption is a foundational tool for protecting sensitive information in modern computing systems. In a standard public-key encryption scheme, a sender encrypts a message using a recipient’s public key, and only the holder of the corresponding secret key can recover the plaintext. While this paradigm provides strong confidentiality guarantees, many emerging applications require more nuanced forms of cryptographic control. In particular, there are scenarios in which decryption should succeed only when a specific relationship holds between encrypted data and additional input supplied at runtime. Traditional encryption mechanisms do not directly support this kind of conditional behavior.
This project investigates conditional encryption, a new cryptographic primitive that extends the capabilities of standard public-key encryption. In addition to the usual algorithms for key generation, encryption, and decryption, a conditional encryption scheme introduces a new algorithm that produces a ciphertext whose meaning depends on a predicate evaluated on encrypted data. Informally, conditional encryption allows a party to generate a ciphertext that decrypts to a meaningful payload only if a specific condition holds; otherwise, the ciphertext reveals nothing about the payload or the condition.
More concretely, suppose that a ciphertext encrypts a secret message m1. A conditional encryption algorithm can take this ciphertext together with a control message m2 and a payload message m3. The output is a new ciphertext that behaves as follows: if a predicate P(m1,m2) evaluates to true, then decrypting the new ciphertext reveals m3. If the predicate evaluates to false, the ciphertext leaks no information about either m2, even to an adversary who possesses the secret decryption key.
This property distinguishes conditional encryption from conventional cryptographic mechanisms. Normally, once a party obtains the secret key, they can decrypt any ciphertext and recover the underlying plaintext. Conditional encryption introduces a new layer of protection: even a party with the decryption key learns nothing unless the specified condition holds. This capability is particularly useful in situations where a server must evaluate conditions involving sensitive data without directly learning that data.
Constructing such a primitive presents a fundamental technical challenge. In particular, the conditional encryption algorithm does not know the plaintext m1m_1; it only has access to a ciphertext that encrypts m1m_1. Therefore, the algorithm cannot directly evaluate the predicate P(m1,m2)P(m_1,m_2) to determine whether the condition holds. Instead, it must produce a new ciphertext whose behavior depends on the value of this predicate while operating only on encrypted data. Achieving this goal requires carefully designed cryptographic techniques that allow limited computation on encrypted values while preserving strong confidentiality guarantees. Designing constructions that achieve this functionality efficiently and securely is a central challenge addressed by this project.
A motivating application for this work is secure personalized password typo correction. Many authentication systems attempt to improve usability by allowing users to log in even when they make small mistakes while typing their passwords. For example, a system might accept passwords that differ from the correct password by one edit operation or a small Hamming distance. Systems such as TypTop implement this idea by maintaining encrypted records of plausible password variants. However, existing approaches may inadvertently allow the server to learn information about incorrect password attempts, creating potential privacy risks.
Conditional encryption provides a principled way to address this challenge. Using this technique, the system can create encrypted entries that only decrypt to useful values if a submitted password attempt is a plausible typo of the user’s true password. If the attempt is unrelated to the correct password, the resulting ciphertext reveals nothing about the attempted password or any stored data. As a result, the authentication server learns only what is necessary to support typo correction, while protecting users’ privacy against unnecessary information leakage.
Initial Results.
Personnel
Students: Mohammad Hassan Ameri
Representative Publications
Conditional Encryption with Applications to Secure Personalized
Password Typo Correction. Ameri, H. and Blocki, J. CCS 2024.
Keywords: Conditional Encryption, Fuzzy Password Authenticated Key Exchange, Password Typos, passwords, Zero-Interaction Device Pairing