No fixed-construction reduction from IND-CPA security to circular security of bit encryption
Statement
Under an extension of the Symmetric External Diffie–Hellman assumption from bilinear to multilinear groups, there is a public-key bit-encryption scheme that is IND-CPA-secure but not circular secure for bit encryption: given encryptions of the bits of its own secret key, an efficient attack recovers the whole key — Rot13. So, unless that assumption fails, the identity map is no reduction from IND-CPA security to circular security of bit encryption.
Notes
- The folklore conjecture that every semantically secure bit-encryption scheme is circular secure also cannot be proved by a black-box reduction, and both negative results extend to the weaker conjecture for CCA-secure bit encryption — Rot13.
- For symmetric-key bit encryption the separation holds under LWE (No fixed-construction reduction from CPA security to circular security of symmetric-key bit encryption) — GKW17a.
- Bootstrapping a somewhat homomorphic scheme into one for unbounded depth publishes encryptions of its own secret-key bits, so it needs IND-CPA security given those encryptions (circular-secure bootstrappable SHE) — Gen09; circular security for bit encryption implies that property — standard.