No fixed-construction reduction from IND-CPA security to circular security for key cycles (iO)

Conditional · against fixed-construction reductions · assuming Indistinguishability Obfuscation, preimage resistance (one-wayness) · KRW15

Statement

Under iO, for every $n$ there is an encryption scheme that is IND-CPA-secure but not $n$-circular secure — KRW15. Hence the identity map is no reduction from IND-CPA security to circular security for key cycles.

Notes

• Each counterexample depends on $n$. One scheme that fails $l$-circular security for every cycle length $l$ follows from iO and leveled homomorphic encryption — GKW17b — and lockable obfuscation, from LWE, turns circular-security separations previously based on iO into constructions from LWE almost immediately — GKW17c.
• Cycles of every constant length are separated from LWE with polynomial modulus-to-noise ratio (AP16’s barrier) — AP16.