Security Flavors

Overview

When we say a scheme is “CPA-secure” or “CCA1-secure,” we are implicitly referring to a specific flavor of security - most commonly indistinguishability (IND). However, several other flavors exist, each capturing a different aspect of what it means for an encryption scheme to be secure. Understanding these distinctions matters because equivalences that hold between flavors for standard encryption do not always carry over to the homomorphic setting.

Indistinguishability (IND)

Indistinguishability is the most common formulation. The adversary chooses two messages and receives an encryption of one of them, chosen at random. It must guess which one was encrypted. A scheme is IND-secure (under a given attack model) if no efficient adversary has a non-negligible advantage (i.e., its winning probability is not significantly greater than ). This is the flavor used throughout this zoo unless stated otherwise, and the IND prefix is generally omitted.

Semantic Security (SS)

Semantic security, introduced by Goldwasser and Micali, captures the intuition that the ciphertext reveals no partial information about the plaintext. Formally, anything an adversary can compute about the plaintext given the ciphertext, it could also compute without the ciphertext. For standard public-key encryption, semantic security is equivalent to IND-CPA. This equivalence was established by Goldwasser and Micali (1984).

Non-Malleability (NM)

Non-malleability requires that an adversary, given a challenge ciphertext, cannot produce a related ciphertext, one whose plaintext bears a meaningful relation to the challenge plaintext.

In the context of FHE, non-malleability is a critical distinguishing factor. Because FHE schemes are explicitly designed to allow computation on encrypted data, they are inherently malleable. Consequently, no useful FHE scheme can be NM-CPA secure. This makes indistinguishability (IND) the standard goal for homomorphic encryption rather than non-malleability. (For standard, non-homomorphic encryption, non-malleability under CCA2 is equivalent to IND-CCA2, but NM-CPA is strictly stronger than IND-CPA).

Key Recovery (KR)

Key recovery security simply requires that no efficient adversary can recover the secret key. This is strictly weaker than indistinguishability: a scheme can be KR-secure while leaking partial information about plaintexts. KR variants are occasionally relevant when analyzing the practical impact of attacks (e.g., certain CPAD attacks aim at full key recovery rather than just distinguishing).

One-Wayness (OW)

One-wayness requires that given a ciphertext, the adversary cannot recover the entire plaintext. This is stronger than KR but weaker than IND. For deterministic encryption or schemes with small message spaces, OW and IND can differ substantially.

Left-or-Right (LOR) vs Find-Then-Guess (FTG)

These are not separate security flavors, but rather two structurally distinct formulations of the indistinguishability game that characterize how the adversary interacts with the challenge:

Find-Then-Guess (FTG): Also known as the single-challenge formulation. The game has two distinct phases. In the “Find” phase, the adversary receives the public key and outputs a single pair of messages . It then receives a challenge ciphertext encrypting for a random hidden bit . In the “Guess” phase, it outputs its guess for .
Left-or-Right (LOR): Also known as the multi-challenge formulation. The adversary is given access to a challenge oracle initialized with a random hidden bit . The adversary can query this oracle polynomially many times with arbitrary pairs , and each time receives an encryption of .

For CPA and CCA security of standard exact encryption, Bellare, Desai, Jokipii, and Rogaway (1997) showed that FTG and LOR are polynomially equivalent. A standard hybrid argument proves that an adversary making queries to an LOR oracle can be reduced to an FTG adversary with its advantage degraded by a factor of .

However, this equivalence does not hold universally. For IND-CPAD and IND-vCCAD security in the approximate FHE regime, Brzuska et al. (CIC 2025) proved that the LOR (multi-challenge) variants are strictly stronger than the FTG (single-challenge) variants.