Paper 2026/2547
$\mathcal{iO}$ from LWE with Structured Preimage
Abstract
Constructing $\mathcal{iO}$ from simple, safe assumptions in the post-quantum regime is an important problem with wide-ranging applications. In this work, we make progress towards this goal. We formulate a new, arguably simple assumption called LWE with Structured Preimage that suffices to build $\mathcal{iO}$. Our assumption is instance-independent, falsifiable and non-interactive. Our assumption posits that a set of LWE (Learning With Errors) samples is indistinguishable from random given a short Gaussian matrix which is carefully chosen to satisfy the required functionality while avoiding problematic leakage. We provide a thorough cryptanalysis of our assumption, using the extensive cryptanalytic effort against the related evasive LWE assumption (Wee, Eurocrypt 2022 and Tsabary, Crypto 2022) to gain confidence. We emphasize that our assumption is superficially similar but fundamentally different from evasive LWE. Thus, we obtain $\mathcal{iO}$ from a simple lattice assumption whose hardness is somewhat better understood as compared to brand new assumptions.
Metadata
- Available format(s)
-
PDF
- Category
- Public-key cryptography
- Publication info
- Published by the IACR in ASIACRYPT 2026
- Keywords
- Indistinguishability ObfuscationLWEOblivious LWE Sampler
- Contact author(s)
-
shweta @ cse iitm ac in
anujamodi97 @ gmail com
anshuy @ cse iitk ac in
yamada-shota @ aist go jp - History
- 2026-10-20: approved
- 2026-10-19: received
- See all versions
- Short URL
- https://ia.cr/2026/2547
- License
-
CC BY
BibTeX
@misc{cryptoeprint:2026/2547,
author = {Shweta Agrawal and Anuja Modi and Anshu Yadav and Shota Yamada},
title = {$\mathcal{{iO}}$ from {LWE} with Structured Preimage},
howpublished = {Cryptology {ePrint} Archive, Paper 2026/2547},
year = {2026},
url = {https://eprint.iacr.org/2026/2547}
}
