1 Search Results for "Lin, Huijia (Rachel)"

Document

Invited Talk

DOI: 10.4230/LIPIcs.FSTTCS.2021.4

Indistinguishability Obfuscation from Well-Founded Assumptions (Invited Talk)

Authors: Huijia (Rachel) Lin

Published in: LIPIcs, Volume 213, 41st IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2021)

Abstract

Indistinguishability obfuscation, introduced by Barak et al. [Crypto 2001], aims to compile programs into unintelligible ones while preserving functionality. It is a fascinating and powerful object that has been shown to enable a host of new cryptographic goals and beyond. However, constructions of indistinguishability obfuscation have remained elusive, with all other proposals relying on heuristics or newly conjectured hardness assumptions. In this work, we show how to construct indistinguishability obfuscation from the subexponential hardness of three well-founded assumptions. We prove the following. Theorem (Informal) Assume sub-exponential hardness for the following: - the Learning Parity with Noise (LPN) assumption over general prime fields 𝔽_p with polynomially many LPN samples and error rate 1/k^δ, where k is the dimension of the LPN secret, and δ > 0 is any constant; - the existence of a Boolean Pseudo-Random Generator (PRG) in NC⁰ with stretch n^(1+τ), where n is the length of the PRG seed, and τ > 0 is any constant; - the Decision Linear (DLIN) assumption on symmetric bilinear groups of prime order. Then, (subexponentially secure) indistinguishability obfuscation for all polynomial-size circuits exist. As a corollary, all cryptographic goals that can be achieved using indistinguishability obfuscation can now be achieved assuming the above three assumptions. This includes fully homomorphic encryption, functional encryption, multiparty non-interactive key-exchange, succinct garbled random access machine, and many others. This is joint work with Aayush Jain (UCLA and NTT Research) and Amit Sahai (UCLA).

Cite as

Huijia (Rachel) Lin. Indistinguishability Obfuscation from Well-Founded Assumptions (Invited Talk). In 41st IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 213, p. 4:1, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{lin:LIPIcs.FSTTCS.2021.4,
  author =	{Lin, Huijia (Rachel)},
  title =	{{Indistinguishability Obfuscation from Well-Founded Assumptions}},
  booktitle =	{41st IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2021)},
  pages =	{4:1--4:1},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-215-0},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{213},
  editor =	{Boja\'{n}czyk, Miko{\l}aj and Chekuri, Chandra},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2021.4},
  URN =		{urn:nbn:de:0030-drops-155154},
  doi =		{10.4230/LIPIcs.FSTTCS.2021.4},
  annote =	{Keywords: Cryptography, indistinguishability obfuscation}
}

Refine by Author
1 Lin, Huijia (Rachel)

Refine by Classification
1 Theory of computation → Cryptographic primitives

Refine by Keyword
1 Cryptography
1 indistinguishability obfuscation

Refine by Type
1 document

Refine by Publication Year
1 2021

1 Search Results for "Lin, Huijia (Rachel)"

Indistinguishability Obfuscation from Well-Founded Assumptions (Invited Talk)

Abstract

Cite as

Thanks for your feedback!

Could not send message