3 Search Results for "Hajiabadi, Mohammad"


Document
Fully Local Succinct Distributed Arguments

Authors: Eden Aldema Tshuva and Rotem Oshman

Published in: LIPIcs, Volume 319, 38th International Symposium on Distributed Computing (DISC 2024)


Abstract
Distributed certification is a proof system for detecting illegal network states or improper execution of distributed algorithms. A certification scheme consists of a proving algorithm, which assigns a certificate to each node, and a verification algorithm where nodes use these certificates to decide whether to accept or reject. The system must ensure that all nodes accept if and only if the network is in a legal state, adhering to the principles of completeness and soundness. The main goal is to design a scheme where the verification process is local and the certificates are succinct, while using as efficient as possible proving algorithm. In cryptographic proof systems, the soundness requirement is often relaxed to computational soundness, where soundness is guaranteed only against computationally bounded adversaries. Computationally sound proof systems are called arguments. Recently, Aldema Tshuva, Boyle, Cohen, Moran, and Oshman (TCC 2023) showed that succinct distributed arguments can be used to enable any polynomially bounded distributed algorithm to certify its execution with polylogarithmic-length certificates. However, their approach required a global communication phase, adding O(D) communication rounds in networks of diameter D, which limits its applicability to local algorithms. In this work, we give the first construction of a fully local succinct distributed argument system, where the prover and the verifier are both local. We show that a distributed algorithm that runs in R rounds, has polynomial local computation, and messages of B bits each can be compiled into a self-certifying algorithm that runs in R + polylog(n) rounds and sends messages of size B + polylog(n), with certificates of length polylog(n). This construction has several applications, including self-certification for local algorithms, ongoing certification of long-lived algorithms, and efficient local mending of the certificates when the network changes.

Cite as

Eden Aldema Tshuva and Rotem Oshman. Fully Local Succinct Distributed Arguments. In 38th International Symposium on Distributed Computing (DISC 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 319, pp. 1:1-1:24, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)


Copy BibTex To Clipboard

@InProceedings{aldematshuva_et_al:LIPIcs.DISC.2024.1,
  author =	{Aldema Tshuva, Eden and Oshman, Rotem},
  title =	{{Fully Local Succinct Distributed Arguments}},
  booktitle =	{38th International Symposium on Distributed Computing (DISC 2024)},
  pages =	{1:1--1:24},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-352-2},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{319},
  editor =	{Alistarh, Dan},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.DISC.2024.1},
  URN =		{urn:nbn:de:0030-drops-212662},
  doi =		{10.4230/LIPIcs.DISC.2024.1},
  annote =	{Keywords: distributed certification, proof labeling schemes, SNARG}
}
Document
Randomness Recoverable Secret Sharing Schemes

Authors: Mohammad Hajiabadi, Shahram Khazaei, and Behzad Vahdani

Published in: LIPIcs, Volume 267, 4th Conference on Information-Theoretic Cryptography (ITC 2023)


Abstract
It is well-known that randomness is essential for secure cryptography. The randomness used in cryptographic primitives is not necessarily recoverable even by the party who can, e.g., decrypt or recover the underlying secret/message. Several cryptographic primitives that support randomness recovery have turned out useful in various applications. In this paper, we study randomness recoverable secret sharing schemes (RR-SSS), in both information-theoretic and computational settings and provide two results. First, we show that while every access structure admits a perfect RR-SSS, there are very simple access structures (e.g., in monotone AC⁰) that do not admit efficient perfect (or even statistical) RR-SSS. Second, we show that the existence of efficient computational RR-SSS for certain access structures in monotone AC⁰ implies the existence of one-way functions. This stands in sharp contrast to (non-RR) SSS schemes for which no such results are known. RR-SSS plays a key role in making advanced attributed-based encryption schemes randomness recoverable, which in turn have applications in the context of designated-verifier non-interactive zero knowledge.

Cite as

Mohammad Hajiabadi, Shahram Khazaei, and Behzad Vahdani. Randomness Recoverable Secret Sharing Schemes. In 4th Conference on Information-Theoretic Cryptography (ITC 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 267, pp. 12:1-12:25, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)


Copy BibTex To Clipboard

@InProceedings{hajiabadi_et_al:LIPIcs.ITC.2023.12,
  author =	{Hajiabadi, Mohammad and Khazaei, Shahram and Vahdani, Behzad},
  title =	{{Randomness Recoverable Secret Sharing Schemes}},
  booktitle =	{4th Conference on Information-Theoretic Cryptography (ITC 2023)},
  pages =	{12:1--12:25},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-271-6},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{267},
  editor =	{Chung, Kai-Min},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITC.2023.12},
  URN =		{urn:nbn:de:0030-drops-183404},
  doi =		{10.4230/LIPIcs.ITC.2023.12},
  annote =	{Keywords: Secret sharing, Randomness recovery}
}
Document
Algebraic Restriction Codes and Their Applications

Authors: Divesh Aggarwal, Nico Döttling, Jesko Dujmovic, Mohammad Hajiabadi, Giulio Malavolta, and Maciej Obremski

Published in: LIPIcs, Volume 215, 13th Innovations in Theoretical Computer Science Conference (ITCS 2022)


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.

Cite as

Divesh Aggarwal, Nico Döttling, Jesko Dujmovic, Mohammad Hajiabadi, Giulio Malavolta, and Maciej Obremski. Algebraic Restriction Codes and Their Applications. In 13th Innovations in Theoretical Computer Science Conference (ITCS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 215, pp. 2:1-2:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)


Copy BibTex To Clipboard

@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/entities/document/10.4230/LIPIcs.ITCS.2022.2},
  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}
}
  • Refine by Author
  • 2 Hajiabadi, Mohammad
  • 1 Aggarwal, Divesh
  • 1 Aldema Tshuva, Eden
  • 1 Dujmovic, Jesko
  • 1 Döttling, Nico
  • Show More...

  • Refine by Classification
  • 2 Security and privacy → Information-theoretic techniques
  • 1 Security and privacy → Mathematical foundations of cryptography
  • 1 Security and privacy → Public key (asymmetric) techniques
  • 1 Theory of computation → Cryptographic protocols

  • Refine by Keyword
  • 1 Algebraic Restriction Codes
  • 1 DDH
  • 1 Diffie-Hellman
  • 1 OT
  • 1 Oblivious Transfer
  • Show More...

  • Refine by Type
  • 3 document

  • Refine by Publication Year
  • 1 2022
  • 1 2023
  • 1 2024

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