DROPS

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 (Ĉ,𝕋̂) for which we can detect arbitrary tampering with all wires in Ĉ. 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 (Ĉ,𝕋̂) where Ĉ 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}
}

Document

DOI: 10.4230/LIPIcs.DISC.2019.3

Long-Lived Counters with Polylogarithmic Amortized Step Complexity

Authors: Mirza Ahad Baig, Danny Hendler, Alessia Milani, and Corentin Travers

Published in: LIPIcs, Volume 146, 33rd International Symposium on Distributed Computing (DISC 2019)

Abstract

A shared-memory counter is a well-studied and widely-used concurrent object. It supports two operations: An Inc operation that increases its value by 1 and a Read operation that returns its current value. Jayanti, Tan and Toueg [Jayanti et al., 2000] proved a linear lower bound on the worst-case step complexity of obstruction-free implementations, from read and write operations, of a large class of shared objects that includes counters. The lower bound leaves open the question of finding counter implementations with sub-linear amortized step complexity. In this paper, we address this gap. We present the first wait-free n-process counter, implemented using only read and write operations, whose amortized operation step complexity is O(log^2 n) in all executions. This is the first non-blocking read/write counter algorithm that provides sub-linear amortized step complexity in executions of arbitrary length. Since a logarithmic lower bound on the amortized step complexity of obstruction-free counter implementations exists, our upper bound is optimal up to a logarithmic factor.

Cite as

Mirza Ahad Baig, Danny Hendler, Alessia Milani, and Corentin Travers. Long-Lived Counters with Polylogarithmic Amortized Step Complexity. In 33rd International Symposium on Distributed Computing (DISC 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 146, pp. 3:1-3:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@InProceedings{baig_et_al:LIPIcs.DISC.2019.3,
  author =	{Baig, Mirza Ahad and Hendler, Danny and Milani, Alessia and Travers, Corentin},
  title =	{{Long-Lived Counters with Polylogarithmic Amortized Step Complexity}},
  booktitle =	{33rd International Symposium on Distributed Computing (DISC 2019)},
  pages =	{3:1--3:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-126-9},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{146},
  editor =	{Suomela, Jukka},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.DISC.2019.3},
  URN =		{urn:nbn:de:0030-drops-113108},
  doi =		{10.4230/LIPIcs.DISC.2019.3},
  annote =	{Keywords: Shared Memory, Wait-freedom, Counter, Amortized Complexity, Concurrent Objects}
}

Search Results

Documents authored by Baig, Mirza Ahad

Efficiently Testable Circuits

Abstract

Cite as

Long-Lived Counters with Polylogarithmic Amortized Step Complexity

Abstract

Cite as

Thanks for your feedback!

Could not send message