---
OA_place: repository
OA_type: green
_id: '18756'
abstract:
- lang: eng
  text: "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:\r\n(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.\r\n\r\n(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.\r\n\r\n(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."
acknowledgement: The authors thank the anonymous reviewers for insightful comments
  which very much improved this work, in particular, sharing with us the counterexamples
  against a prior version of Hiding Evasive LWE, and against public-coin Evasive LWE
  when the sampler inputs B. Chris Brzuska and Ivy K. Y. Woo are supported by Research
  Council of Finland grant 358950. We thank Russell W. F. Lai and Hoeteck Wee for
  helpful discussions.
alternative_title:
- LNCS
article_processing_charge: No
author:
- first_name: Chris
  full_name: Brzuska, Chris
  last_name: Brzuska
- first_name: Akin
  full_name: Ünal, Akin
  id: f6b56fb6-dc63-11ee-9dbf-f6780863a85a
  last_name: Ünal
  orcid: 0000-0002-8929-0221
- first_name: Ivy K.Y.
  full_name: Woo, Ivy K.Y.
  last_name: Woo
citation:
  ama: 'Brzuska C, Ünal A, Woo IKY. Evasive LWE assumptions: Definitions, classes,
    and counterexamples. In: <i>30th International Conference on the Theory and Application
    of Cryptology and Information Security</i>. Vol 15487. Springer Nature; 2024:418-449.
    doi:<a href="https://doi.org/10.1007/978-981-96-0894-2_14">10.1007/978-981-96-0894-2_14</a>'
  apa: 'Brzuska, C., Ünal, A., &#38; Woo, I. K. Y. (2024). Evasive LWE assumptions:
    Definitions, classes, and counterexamples. In <i>30th International Conference
    on the Theory and Application of Cryptology and Information Security</i> (Vol.
    15487, pp. 418–449). Kolkata, India: Springer Nature. <a href="https://doi.org/10.1007/978-981-96-0894-2_14">https://doi.org/10.1007/978-981-96-0894-2_14</a>'
  chicago: 'Brzuska, Chris, Akin Ünal, and Ivy K.Y. Woo. “Evasive LWE Assumptions:
    Definitions, Classes, and Counterexamples.” In <i>30th International Conference
    on the Theory and Application of Cryptology and Information Security</i>, 15487:418–49.
    Springer Nature, 2024. <a href="https://doi.org/10.1007/978-981-96-0894-2_14">https://doi.org/10.1007/978-981-96-0894-2_14</a>.'
  ieee: 'C. Brzuska, A. Ünal, and I. K. Y. Woo, “Evasive LWE assumptions: Definitions,
    classes, and counterexamples,” in <i>30th International Conference on the Theory
    and Application of Cryptology and Information Security</i>, Kolkata, India, 2024,
    vol. 15487, pp. 418–449.'
  ista: 'Brzuska C, Ünal A, Woo IKY. 2024. Evasive LWE assumptions: Definitions, classes,
    and counterexamples. 30th International Conference on the Theory and Application
    of Cryptology and Information Security. ASIACRYPT: Conference on the Theory and
    Application of Cryptology and Information Security, LNCS, vol. 15487, 418–449.'
  mla: 'Brzuska, Chris, et al. “Evasive LWE Assumptions: Definitions, Classes, and Counterexamples.”
    <i>30th International Conference on the Theory and Application of Cryptology and
    Information Security</i>, vol. 15487, Springer Nature, 2024, pp. 418–49, doi:<a
    href="https://doi.org/10.1007/978-981-96-0894-2_14">10.1007/978-981-96-0894-2_14</a>.'
  short: C. Brzuska, A. Ünal, I.K.Y. Woo, in:, 30th International Conference on the
    Theory and Application of Cryptology and Information Security, Springer Nature,
    2024, pp. 418–449.
conference:
  end_date: 2024-12-13
  location: Kolkata, India
  name: 'ASIACRYPT: Conference on the Theory and Application of Cryptology and Information
    Security'
  start_date: 2024-12-09
date_created: 2025-01-05T23:01:56Z
date_published: 2024-12-13T00:00:00Z
date_updated: 2025-09-09T12:00:51Z
day: '13'
department:
- _id: KrPi
doi: 10.1007/978-981-96-0894-2_14
external_id:
  isi:
  - '001443890800014'
intvolume: '     15487'
isi: 1
language:
- iso: eng
main_file_link:
- open_access: '1'
  url: https://eprint.iacr.org/2024/2000
month: '12'
oa: 1
oa_version: Preprint
page: 418-449
publication: 30th International Conference on the Theory and Application of Cryptology
  and Information Security
publication_identifier:
  eissn:
  - 1611-3349
  isbn:
  - '9789819608935'
  issn:
  - 0302-9743
publication_status: published
publisher: Springer Nature
quality_controlled: '1'
scopus_import: '1'
status: public
title: 'Evasive LWE assumptions: Definitions, classes, and counterexamples'
type: conference
user_id: 317138e5-6ab7-11ef-aa6d-ffef3953e345
volume: 15487
year: '2024'
...