Computational cryptography › Public-key encryption and key exchange › Post-quantum public-key › Lattices
Trust or structural assumption

Circular security

In plain words

The assumption that it's safe to encrypt a key using that same key.

The idea: FHE ciphertexts get noisier with every operation, and bootstrapping cleans them by running decryption on encrypted data, which needs the secret key published encrypted under itself. Ordinary security proofs say nothing about that case, because the message isn't independent of the key. Nobody has found a way to exploit it for the schemes in use, so it is taken as an extra assumption.

Why it matters: Needed for fully homomorphic encryption to run long computations.

The details

On the map: safe to encrypt your own key

The assumption that it is safe to encrypt a secret key under its own public key[1].

Fully homomorphic encryption needs it[2]: bootstrapping, which refreshes ciphertexts so computation can continue, publishes exactly such an encryption. Standard LWE security doesn't cover this case, so FHE relies on the extra assumption. No attack is known against the schemes in use.

Rests on

If any of these breaks, this breaks too.

If it falls

If this breaks, these break with it.

References

  1. John Black, Phillip Rogaway and Thomas Shrimpton. Encryption-Scheme Security in the Presence of Key-Dependent Messages. Selected Areas in Cryptography, 2003. doi:10.1007/3-540-36492-7_6
  2. Craig Gentry. Fully homomorphic encryption using ideal lattices. Proceedings of the forty-first annual ACM symposium on Theory of computing, 2009. doi:10.1145/1536414.1536440