1 Search Results for "Singh, Ishaan Preet"


Document
Reusable Garbled Deterministic Finite Automata from Learning With Errors

Authors: Shweta Agrawal and Ishaan Preet Singh

Published in: LIPIcs, Volume 80, 44th International Colloquium on Automata, Languages, and Programming (ICALP 2017)


Abstract
We provide a single-key functional encryption scheme for Deterministic Finite Automata (DFA). The secret key of our scheme is associated with a DFA M, and a ciphertext is associated with an input x of arbitrary length. The decryptor learns M(x) and nothing else. The ciphertext and key sizes achieved by our scheme are optimal – the size of the public parameters is independent of the size of the machine or data being encrypted, the secret key size depends only on the machine size and the ciphertext size depends only on the input size. Our scheme achieves full functional encryption in the “private index model”, namely the entire input x is hidden (as against x being public and a single bit b being hidden). Our single key FE scheme can be compiled with symmetric key encryption to yield reusable garbled DFAs for arbitrary size inputs, that achieves machine and input privacy along with reusability under a strong simulation based definition of security. We generalize this to a functional encryption scheme for Turing machines TMFE which has short public parameters that are independent of the size of the machine or the data being encrypted, short function keys, and input-specific decryption time. However, the ciphertext of our construction is large and depends on the worst case running time of the Turing machine (but not its description size). These provide the first FE schemes that support unbounded length inputs, allow succinct public and function keys and rely on LWE. Our construction relies on a new and arguably natural notion of decomposable functional encryption which may be of independent interest.

Cite as

Shweta Agrawal and Ishaan Preet Singh. Reusable Garbled Deterministic Finite Automata from Learning With Errors. In 44th International Colloquium on Automata, Languages, and Programming (ICALP 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 80, pp. 36:1-36:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)


Copy BibTex To Clipboard

@InProceedings{agrawal_et_al:LIPIcs.ICALP.2017.36,
  author =	{Agrawal, Shweta and Singh, Ishaan Preet},
  title =	{{Reusable Garbled Deterministic Finite Automata from Learning With Errors}},
  booktitle =	{44th International Colloquium on Automata, Languages, and Programming (ICALP 2017)},
  pages =	{36:1--36:13},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-041-5},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{80},
  editor =	{Chatzigiannakis, Ioannis and Indyk, Piotr and Kuhn, Fabian and Muscholl, Anca},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2017.36},
  URN =		{urn:nbn:de:0030-drops-75014},
  doi =		{10.4230/LIPIcs.ICALP.2017.36},
  annote =	{Keywords: Functional Encryption, Learning With Errors, Deterministic Finite Automata, Garbled DFA}
}
  • Refine by Author
  • 1 Agrawal, Shweta
  • 1 Singh, Ishaan Preet

  • Refine by Classification

  • Refine by Keyword
  • 1 Deterministic Finite Automata
  • 1 Functional Encryption
  • 1 Garbled DFA
  • 1 Learning With Errors

  • Refine by Type
  • 1 document

  • Refine by Publication Year
  • 1 2017

Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail