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

Conditional · against fixed-construction reductions · assuming LWE with polynomial modulus-to-noise ratio · AP16

Statement

For every constant $k$ there is an IND-CPA-secure public-key encryption scheme that is not $k$-circular secure, under $n$-dimensional LWE for $\mathrm{poly}(n)$ approximation factors, and for every $k=\mathrm{poly}(\lambda )$ one under degree-$n$ ring-LWE for approximation factors at most $\exp (n^{\epsilon })$; each scheme is also $k^{\prime }$-circular insecure for $2\le k^{\prime }\le k$ — AP16. Hence, under LWE with polynomial modulus-to-noise ratio, the identity map is no reduction from IND-CPA security to circular security for key cycles.

Notes

• From iO, counterexamples exist for every cycle length (KRW15’s barrier) — KRW15.