CryptoDB
Indistinguishability Obfuscation from Bilinear Maps and LPN Variants
| Authors: |
|
|---|---|
| Download: | |
| Presentation: | Slides |
| Conference: | TCC 2024 |
| Abstract: | We construct an indistinguishability obfuscation (IO) scheme from the sub-exponential hardness of the decisional linear problem on bilinear maps together with two variants of the learning parity with noise (LPN) problem, namely large-field LPN and (binary-field) sparse LPN. This removes the need to assume the existence of polynomial-stretch PRGs in $\mathsf{NC}^0$ from the state-of-the-art construction of IO (Jain, Lin, and Sahai, EUROCRYPT 2022). As an intermediate step in our construction, we abstract away a notion of structured-seed polynomial-stretch PRGs in $\mathsf{NC}^0$ which is implied by both sparse LPN and the existence of polynomial-stretch PRGs in $\mathsf{NC}^0$. As immediate applications, from the sub-exponential hardness of the decisional linear assumption on bilinear groups, large-field LPN, and sparse LPN, we get alternative constructions of (a) FHE without lattices or circular security assumptions (Canetti, Lin, Tessaro, and Vaikuntanathan, TCC 2015), and (b) perfect zero-knowledge adaptively-sound Succinct Non-interactive Arguments (SNARGs) for NP (Waters and Wu, STOC 2024). |
BibTeX
@inproceedings{tcc-2024-34798,
title={Indistinguishability Obfuscation from Bilinear Maps and LPN Variants},
publisher={Springer-Verlag},
author={Seyoon Ragavan and Neekon Vafa and Vinod Vaikuntanathan},
year=2024
}