[BUW24] Evasive LWE Assumptions: Definitions, Classes, and Counterexamples

Authors: Chris Brzuska, Akin Ünal, Ivy K. Y. Woo | Venue: ASIACRYPT 2024 | Source

Abstract

We give a systematic treatment of evasive LWE assumptions, organizing them into public-coin and private-coin variants and studying their relative strengths. We provide simple counterexamples refuting three private-coin evasive LWE variants that had been used in prior cryptographic constructions, demonstrating that these variants do not hold in general. We also identify qualitative separations between public-coin and private-coin hardness, and propose restricted classes of evasive LWE assumptions for which we have greater confidence. Our counterexamples show that care is required when instantiating evasive LWE, particularly in the private-coin regime.