Paper 2022/1598

Efficiently Testable Circuits

Mirza Ahad Baig, ISTA
Suvradip Chakraborty, ETH Zurich
Stefan Dziembowski, University of Warsaw and IDEAS NCBR
Małgorzata Gałązka, University of Warsaw
Tomasz Lizurej, University of Warsaw and IDEAS NCBR
Krzysztof Pietrzak, ISTA

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 $(\widehat{C}, \widehat{T})$ for which we can detect arbitrary tampering with all wires in $\widehat{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 $(\widehat{C}, \widehat{T})$ where $\widehat{C}$ is of size $\approx 12n$ and depth $d+\log(n)+L\cdot n^{1/L}$. The test set $\widehat{T}$ is of size $4\cdot 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.

Note: This is a full version of a paper "Efficiently Testable Circuits" which got accepted to ITCS 2023.

Available format(s)
Publication info
Published elsewhere. ITCS 2023
circuit compilers circuit integrity circuit testing
Contact author(s)
mirzabaig cmi @ gmail com
suvradip1111 @ gmail com
stefan dziembowski @ crypto edu pl
malgorzata bladoszewska @ gmail com
tomasz lizurej @ crypto edu pl
pietrzak @ ist ac at
2022-11-21: approved
2022-11-16: received
See all versions
Short URL
Creative Commons Attribution


      author = {Mirza Ahad Baig and Suvradip Chakraborty and Stefan Dziembowski and Małgorzata Gałązka and Tomasz Lizurej and Krzysztof Pietrzak},
      title = {Efficiently Testable Circuits},
      howpublished = {Cryptology ePrint Archive, Paper 2022/1598},
      year = {2022},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.