3 Search Results for "Chakraborty, Suvradip"

Document
DOI: 10.4230/LIPIcs.ITC.2025.7
Linear-Time Secure Merge in O(loglog n) Rounds

Authors: Mark Blunk, Paul Bunn, Samuel Dittmer, Steve Lu, and Rafail Ostrovsky

Published in: LIPIcs, Volume 343, 6th Conference on Information-Theoretic Cryptography (ITC 2025)

Abstract
The problem of Secure Merge consists of combining two sorted lists (which are either held separately by two parties, or secret-shared among two or more parties), and outputting a single merged (sorted) list, secret-shared among all parties. Just as insecure algorithms for comparison-based sorting are slower than merging (i.e., for lists of size n, Θ(n log n) versus Θ(n)), we explore whether an analogous separation exists for secure protocols; namely, if there exist techniques for performing secure merge that are more performant than simply invoking secure sort. We answer this question affirmatively by constructing a secure merge protocol with optimal Θ(n) communication and computation, and Θ(log log n) rounds of communication. Our results are based solely on black-box use of basic secure primitives, such as secure comparison and secure shuffle. Since two-party secure primitives require computational assumptions, while three-party do not, our protocols achieve these bounds against semi-honest adversaries via a computationally secure two-party (resp. an information-theoretically secure three-party) secure merge protocol. Secure sort is a fundamental building block used in many MPC protocols, e.g., various private set intersection protocols and oblivious RAM protocols. More efficient secure sort can lead to concrete improvements in the overall run-time. Since secure sort can often be replaced by secure merge - as inputs (from different participating players) can be presorted - an efficient secure merge protocol has wide applicability. There are also a range of applications in the field of secure databases, including secure database joins, as well as updatable database storage and search, whereby secure merge can be used to insert new entries into an existing (sorted) database. In building our secure merge protocol, we develop several subprotocols that may be of independent interest. For example, we develop a protocol for secure asymmetric merge (when one list is much larger than the other).
Cite as

Mark Blunk, Paul Bunn, Samuel Dittmer, Steve Lu, and Rafail Ostrovsky. Linear-Time Secure Merge in O(loglog n) Rounds. In 6th Conference on Information-Theoretic Cryptography (ITC 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 343, pp. 7:1-7:23, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{blunk_et_al:LIPIcs.ITC.2025.7,
  author =	{Blunk, Mark and Bunn, Paul and Dittmer, Samuel and Lu, Steve and Ostrovsky, Rafail},
  title =	{{Linear-Time Secure Merge in O(loglog n) Rounds}},
  booktitle =	{6th Conference on Information-Theoretic Cryptography (ITC 2025)},
  pages =	{7:1--7:23},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-385-0},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{343},
  editor =	{Gilboa, Niv},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITC.2025.7},
  URN =		{urn:nbn:de:0030-drops-243573},
  doi =		{10.4230/LIPIcs.ITC.2025.7},
  annote =	{Keywords: Secure Merge, Secure Sort, Secure Databases, Private Set Intersection}
}
Document
DOI: 10.4230/LIPIcs.ITCS.2025.90
Polynomial Size, Short-Circuit Resilient Circuits for NC

Authors: Yael Tauman Kalai and Raghuvansh R. Saxena

Published in: LIPIcs, Volume 325, 16th Innovations in Theoretical Computer Science Conference (ITCS 2025)

Abstract
We show how to convert any circuit of poly-logarithmic depth and polynomial size into a functionally equivalent circuit of polynomial size (and polynomial depth) that is resilient to adversarial short-circuit errors. Specifically, the resulting circuit computes the same function even if up to ε d gates on every root-to-leaf path are short-circuited, i.e., their output is replaced with the value of one of its inputs, where d is the depth of the circuit and ε > 0 is a fixed constant. Previously, such a result was known for formulas (Kalai-Lewko-Rao, FOCS 2012). It was also known how to convert general circuits to error resilient ones whose size is quasi-polynomial in the size of the original circuit (Efremenko et al. STOC 2022). The reason both these works do not extend to our setting is that there may be many paths from the root to a given gate, and the resilient circuits needs to "remember" a lot of information about these paths, which causes it to be large. Our main idea is to reduce the amount of this information at the cost of increasing the depth of the resilient circuit.
Cite as

Yael Tauman Kalai and Raghuvansh R. Saxena. Polynomial Size, Short-Circuit Resilient Circuits for NC. In 16th Innovations in Theoretical Computer Science Conference (ITCS 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 325, pp. 90:1-90:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{taumankalai_et_al:LIPIcs.ITCS.2025.90,
  author =	{Tauman Kalai, Yael and Saxena, Raghuvansh R.},
  title =	{{Polynomial Size, Short-Circuit Resilient Circuits for NC}},
  booktitle =	{16th Innovations in Theoretical Computer Science Conference (ITCS 2025)},
  pages =	{90:1--90:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-361-4},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{325},
  editor =	{Meka, Raghu},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2025.90},
  URN =		{urn:nbn:de:0030-drops-227181},
  doi =		{10.4230/LIPIcs.ITCS.2025.90},
  annote =	{Keywords: Error-resilient computation, short-circuit errors}
}
Document
DOI: 10.4230/LIPIcs.ITCS.2023.10
Efficiently Testable Circuits

Authors: Mirza Ahad Baig, Suvradip Chakraborty, Stefan Dziembowski, Małgorzata Gałązka, Tomasz Lizurej, and Krzysztof Pietrzak

Published in: LIPIcs, Volume 251, 14th Innovations in Theoretical Computer Science Conference (ITCS 2023)

Abstract
In this work, we put forward the notion of "efficiently testable circuits" and provide circuit compilers that transform any circuit into an efficiently testable one. Informally, a circuit is testable if one can detect tampering with the circuit by evaluating it on a small number of inputs from some test set. Our technical contribution is a compiler that transforms any circuit C into a testable circuit (Ĉ,𝕋̂) for which we can detect arbitrary tampering with all wires in Ĉ. The notion of a testable circuit is weaker or incomparable to existing notions of tamper-resilience, which aim to detect or even correct for errors introduced by tampering during every query, but our new notion is interesting in several settings, and we achieve security against much more general tampering classes - like tampering with all wires - with very modest overhead. Concretely, starting from a circuit C of size n and depth d, for any L (think of L as a small constant, say L = 4), we get a testable (Ĉ,𝕋̂) where Ĉ is of size ≈ 12n and depth d+log(n)+L⋅ n^{1/L}. The test set 𝕋̂ is of size 4⋅ 2^L. The number of extra input and output wires (i.e., pins) we need to add for the testing is 3+L and 2^L, respectively.
Cite as

Mirza Ahad Baig, Suvradip Chakraborty, Stefan Dziembowski, Małgorzata Gałązka, Tomasz Lizurej, and Krzysztof Pietrzak. Efficiently Testable Circuits. In 14th Innovations in Theoretical Computer Science Conference (ITCS 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 251, pp. 10:1-10:23, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{baig_et_al:LIPIcs.ITCS.2023.10,
  author =	{Baig, Mirza Ahad and Chakraborty, Suvradip and Dziembowski, Stefan and Ga{\l}\k{a}zka, Ma{\l}gorzata and Lizurej, Tomasz and Pietrzak, Krzysztof},
  title =	{{Efficiently Testable Circuits}},
  booktitle =	{14th Innovations in Theoretical Computer Science Conference (ITCS 2023)},
  pages =	{10:1--10:23},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-263-1},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{251},
  editor =	{Tauman Kalai, Yael},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2023.10},
  URN =		{urn:nbn:de:0030-drops-175130},
  doi =		{10.4230/LIPIcs.ITCS.2023.10},
  annote =	{Keywords: circuit compilers, circuit integrity, circuit testing}
}
  • Refine by Type
  • 3 Document/PDF
  • 2 Document/HTML

  • Refine by Publication Year
  • 2 2025
  • 1 2023

  • Refine by Author
  • 1 Baig, Mirza Ahad
  • 1 Blunk, Mark
  • 1 Bunn, Paul
  • 1 Chakraborty, Suvradip
  • 1 Dittmer, Samuel
  • Show More...

  • Refine by Series/Journal
  • 3 LIPIcs

  • Refine by Classification
  • 1 Security and privacy → Cryptography
  • 1 Security and privacy → Database and storage security
  • 1 Security and privacy → Tamper-proof and tamper-resistant designs
  • 1 Theory of computation → Circuit complexity
  • 1 Theory of computation → Communication complexity

  • Refine by Keyword
  • 1 Error-resilient computation
  • 1 Private Set Intersection
  • 1 Secure Databases
  • 1 Secure Merge
  • 1 Secure Sort
  • Show More...

Any Issues?
X

Feedback on the Current Page

CAPTCHA

Thanks for your feedback!

Feedback submitted to Dagstuhl Publishing

Could not send message

Please try again later or send an E-mail
© 2023-2025 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact