Circular security

An encryption scheme is circular secure if it stays secure when the adversary also sees encryptions of its secret keys arranged in a cycle: a key encrypted under its own public key, or each key encrypted under the next one’s.

Assumption

Let $\mathsf{PKE}=(\mathsf{KeyGen},\mathsf{Enc},\mathsf{Dec})$ be a public-key encryption scheme with secret keys in $\{0,1{\}}^{\ell }$. For $k\ge 1$ and key pairs $({\mathsf{pk}}_j,{\mathsf{sk}}_j)\leftarrow \mathsf{KeyGen}(1^{\lambda })$, $j\in [k]$, the $k$-cycle is $(\mathsf{Enc}({\mathsf{pk}}_j,{\mathsf{sk}}_{j+1}){)}_{j\in [k]}$ with ${\mathsf{sk}}_{k+1}:={\mathsf{sk}}_1$. The scheme, whose message space must contain $\{0,1{\}}^{\ell }$, is $k$-circular secure if it is IND-CPA-secure and the $k$-cycle is indistinguishable from encryptions of $0^{\ell }$ to an adversary holding the public keys — standard.

\begin{algorithm}
\algname{Game}
\caption{$\Game^{k\text{-circ}}_{\PKE,\calA}(\secpar)$}
\begin{algorithmic}
\State $(\pk_j, \sk_j) \gets \KeyGen(1^\secpar)$ for $j \in [k]$; $\sk_{k+1} \gets \sk_1$; $b \getsr \bits$
\State $c_j \gets \Enc(\pk_j, \sk_{j+1})$ for $j \in [k]$ if $b = 0$
\State $c_j \gets \Enc(\pk_j, 0^\ell)$ for $j \in [k]$ if $b = 1$
\State $b' \gets \calA(1^\secpar, \pk_1, \ldots, \pk_k, c_1, \ldots, c_k)$
\Return $[b' = b]$
\end{algorithmic}
\end{algorithm}

A PKE scheme $\mathsf{PKE}$ is $k$-circular secure if it is IND-CPA-secure and for all efficient $\mathcal{A}$,

$${\mathbf{Adv}}_{\mathsf{PKE},\mathcal{A}}^{k\text{-circ}}(\lambda ):=\left|2\mathrm{Pr}\left[{\mathbf{G}}_{\mathsf{PKE},\mathcal{A}}^{k\text{-circ}}(\lambda )=1\right]-1\right|$$

is negligible.

Known Results

• For $k=1$ and full-key encryption, IND-CPA security does not give circular security for a trivial reason: an IND-CPA-secure scheme can be modified to output its message in the clear when that message is a secret key for the public key, which a correct scheme lets the encryptor test by encrypting and decrypting random messages; in the CPA game no efficient adversary submits a secret key, so the modified scheme stays IND-CPA-secure — folklore. The separations below concern the harder cases of bit encryption and of longer cycles.
• Counterexample schemes, IND-CPA-secure but not circular secure, exist for each key-cycle length from iO (KRW15) and, for each length, from LWE with polynomial modulus-to-noise ratio for constant lengths and from ring-LWE for polynomial lengths (AP16), with separations for arbitrary cycle lengths from LWE also in KW16; for public-key bit encryption under an extension of SXDH to multilinear groups (Rot13); and for symmetric-key bit encryption from LWE (GKW17a).
• For symmetric-key encryption, under one-way functions alone, $n$-weak circular (CPA) security is not implied by CCA security, for any $n$; for public-key encryption, under a number-theoretic assumption, $2$-weak circular security is not implied by CCA security — CGH12.
• All known constructions of fully homomorphic encryption from LWE require the encryption scheme to be circular secure — MV24; bootstrapping publishes encryptions of the scheme’s own secret-key bits (circular-secure bootstrappable SHE) — Gen09.

Variations

Key cycles of every length

A PKE scheme is circular secure for key cycles if it is $k$-circular secure for every polynomial $k=k(\lambda )\ge 2$. Cycles of length $1$ are left out because of the trivial separation above.

Circular security of bit encryption

An IND-CPA-secure public-key encryption scheme whose message space contains $\{0,1\}$ is circular secure for bit encryption if the encryptions $(\mathsf{Enc}(\mathsf{pk},\mathsf{sk}[i]){)}_{i\in [\ell ]}$ of the bits of its own secret key are indistinguishable from $(\mathsf{Enc}(\mathsf{pk},0){)}_{i\in [\ell ]}$ to an adversary holding $\mathsf{pk}$. Three seemingly distinct notions of circular security for public-key bit encryption are equivalent — Rot13. It implies the property that bootstrapping asks of a scheme’s own key, IND-CPA security given encryptions of its key bits (circular-secure bootstrappable SHE), by a hybrid that first replaces the key-bit encryptions by encryptions of $0$ — standard.

Symmetric-key bit encryption

A CPA-secure symmetric-key bit-encryption scheme with key $k\in \{0,1{\}}^{\ell }$ is circular secure if $(\mathsf{Enc}(k,k[i]){)}_{i\in [\ell ]}$ is indistinguishable from $(\mathsf{Enc}(k,0){)}_{i\in [\ell ]}$ to an adversary with access to an encryption oracle under $k$.

Attacks

TODO: attacks on the circular security of specific schemes.

Participates in

Barriers

• No fixed-construction reduction from CPA security to circular security of symmetric-key bit encryption (via Symmetric-key bit encryption)
• No fixed-construction reduction from IND-CPA security to circular security of bit encryption (via Circular security of bit encryption)
• No fixed-construction reduction from IND-CPA security to circular security for key cycles (LWE) (via Key cycles of every length)
• No fixed-construction reduction from IND-CPA security to circular security for key cycles (iO) (via Key cycles of every length)