Projects per year
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: 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.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.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. 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. 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. 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.
Original language | English |
---|---|
Title of host publication | Advances in Cryptology – ASIACRYPT 2024 - 30th International Conference on the Theory and Application of Cryptology and Information Security, Proceedings |
Editors | Kai-Min Chung, Yu Sasaki |
Publisher | Springer |
Pages | 418-449 |
Number of pages | 32 |
Volume | 4 |
ISBN (Electronic) | 978-981-96-0894-2 |
ISBN (Print) | 978-981-96-0893-5 |
DOIs | |
Publication status | Published - 2025 |
MoE publication type | A4 Conference publication |
Event | International Conference on the Theory and Application of Cryptology and Information Security - Kolkata, India Duration: 9 Dec 2024 → 13 Dec 2024 Conference number: 30 |
Publication series
Name | Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) |
---|---|
Publisher | Springer |
Volume | 15487 LNCS |
ISSN (Print) | 0302-9743 |
ISSN (Electronic) | 1611-3349 |
Conference
Conference | International Conference on the Theory and Application of Cryptology and Information Security |
---|---|
Abbreviated title | ASIACRYPT |
Country/Territory | India |
City | Kolkata |
Period | 09/12/2024 → 13/12/2024 |
Fingerprint
Dive into the research topics of 'Evasive LWE Assumptions: Definitions, Classes, and Counterexamples'. Together they form a unique fingerprint.Projects
- 1 Active
-
Brzuska ICT: Limits of Lattice-based Cryptography: A New Era of Hinted and Structured Assumptions
Brzuska, C. (Principal investigator), Woo, I. K. Y. (Project Member), Karanko, P. (Project Member) & Puniamurthy, K. (Project Member)
01/01/2024 → 31/12/2026
Project: Academy of Finland: Other research funding