License: Creative Commons Attribution 4.0 International license (CC BY 4.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.ITCS.2022.2
URN: urn:nbn:de:0030-drops-155987
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2022/15598/
Go to the corresponding LIPIcs Volume Portal

Aggarwal, Divesh ; Döttling, Nico ; Dujmovic, Jesko ; Hajiabadi, Mohammad ; Malavolta, Giulio ; Obremski, Maciej

Algebraic Restriction Codes and Their Applications

pdf-format:
LIPIcs-ITCS-2022-2.pdf (0.7 MB)

Abstract

Consider the following problem: You have a device that is supposed to compute a linear combination of its inputs, which are taken from some finite field. However, the device may be faulty and compute arbitrary functions of its inputs. Is it possible to encode the inputs in such a way that only linear functions can be evaluated over the encodings? I.e., learning an arbitrary function of the encodings will not reveal more information about the inputs than a linear combination.
In this work, we introduce the notion of algebraic restriction codes (AR codes), which constrain adversaries who might compute any function to computing a linear function. Our main result is an information-theoretic construction AR codes that restrict any class of function with a bounded number of output bits to linear functions. Our construction relies on a seed which is not provided to the adversary.
While interesting and natural on its own, we show an application of this notion in cryptography. In particular, we show that AR codes lead to the first construction of rate-1 oblivious transfer with statistical sender security from the Decisional Diffie-Hellman assumption, and the first-ever construction that makes black-box use of cryptography. Previously, such protocols were known only from the LWE assumption, using non-black-box cryptographic techniques. We expect our new notion of AR codes to find further applications, e.g., in the context of non-malleability, in the future.

BibTeX - Entry

@InProceedings{aggarwal_et_al:LIPIcs.ITCS.2022.2,
  author =	{Aggarwal, Divesh and D\"{o}ttling, Nico and Dujmovic, Jesko and Hajiabadi, Mohammad and Malavolta, Giulio and Obremski, Maciej},
  title =	{{Algebraic Restriction Codes and Their Applications}},
  booktitle =	{13th Innovations in Theoretical Computer Science Conference (ITCS 2022)},
  pages =	{2:1--2:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-217-4},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{215},
  editor =	{Braverman, Mark},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/opus/volltexte/2022/15598},
  URN =		{urn:nbn:de:0030-drops-155987},
  doi =		{10.4230/LIPIcs.ITCS.2022.2},
  annote =	{Keywords: Algebraic Restriction Codes, Oblivious Transfer, Rate 1, Statistically Sender Private, OT, Diffie-Hellman, DDH}
}

Keywords: Algebraic Restriction Codes, Oblivious Transfer, Rate 1, Statistically Sender Private, OT, Diffie-Hellman, DDH
Collection: 13th Innovations in Theoretical Computer Science Conference (ITCS 2022)
Issue Date: 2022
Date of publication: 25.01.2022

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI