Efficiently Testable Circuits
| Autor: | Baig, Mirza Ahad, Chakraborty, Suvradip, Dziembowski, Stefan, Gałązka, Małgorzata, Lizurej, Tomasz, Pietrzak, Krzysztof |
|---|---|
| Přispěvatelé: | Tauman Kalai, Yael |
| Jazyk: | angličtina |
| Rok vydání: | 2023 |
| Předmět: | |
| Zdroj: | Leibniz International Proceedings in Informatics (LIPIcs), 251 14th Innovations in Theoretical Computer Science Conference (ITCS 2023) |
| ISSN: | 1868-8969 |
| DOI: | 10.4230/lipics.itcs.2023.10 |
| Popis: | 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, b Tb) for which we can detect arbitrary tampering with all wires in Cb. 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, b Tb) where Cb is of size ≈ 12n and depth d+log(n)+L·n1/L. The test set Tb is of size 4 · 2L. The number of extra input and output wires (i.e., pins) we need to add for the testing is 3 + L and 2L, respectively. Leibniz International Proceedings in Informatics (LIPIcs), 251 ISSN:1868-8969 14th Innovations in Theoretical Computer Science Conference (ITCS 2023) ISBN:978-3-95977-263-1 |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|