Paper 2024/2000

Evasive LWE Assumptions: Definitions, Classes, and Counterexamples

Abstract

The evasive LWE assumption, proposed by Wee [Eurocrypt'22 Wee] for constructing a lattice-based optimal broadcast encryption, has shown to be a powerful assumption, adopted by subsequent works to construct advanced primitives ranging from ABE variants to obfuscation for null circuits. However, a closer look reveals significant differences among the precise assumption statements involved in different works, leading to the fundamental question of how these assumptions compare to each other. In this work, we initiate a more systematic study on evasive LWE assumptions: (i) Based on the standard LWE assumption, we construct simple counterexamples against three private-coin evasive LWE variants, used in [Crypto'22 Tsabary, Asiacrypt'22 VWW, Crypto'23 ARYY] respectively, showing that these assumptions are unlikely to hold. (ii) Based on existing evasive LWE variants and our counterexamples, we propose and define three classes of plausible evasive LWE assumptions, suitably capturing all existing variants for which we are not aware of non-obfuscation-based counterexamples. (iii) We show that under our assumption formulations, the security proofs of [Asiacrypt'22 VWW] and [Crypto'23 ARYY] can be recovered, and we reason why the security proof of [Crypto'22 Tsabary] is also plausibly repairable using an appropriate evasive LWE assumption.

Note: Main changes compared to the proceedings version: - We strengthen the heuristic obfuscation-based counterexample by [VWW22] against all private-coin evasive LWE variants into a provable counterexample, assuming only indistinguishability obfuscation for null circuits and the hardness of LWE with super-polynomial modulus-to-noise ratio. This can be viewed as concrete evidence of the qualitative difference between public- and private-coin evasive LWEs. See Section 7 for details. - In the proceedings version of this work, we stated all our proposed evasive LWE assumption families with respect to arbitrary distributions of matrix B. Unfortunately, we later noticed that allowing for arbitrarily distributed matrices B leads to simple counterexamples. See Section 8 for details. Thus, for the time being, we advise to use evasive LWE only with uniformly distributed B. Understanding how the choice of the matrix B distribution affects hardness of evasive LWE is an interesting open question. We left our definitions of the proposed evasive LWE assumption families in Section 4 unchanged and only added a note referring to Section 8 which discusses the new counterexamples.