International Association for Cryptologic Research

International Association
for Cryptologic Research


Efficiently Testable Circuits without Conductivity

Mirza Ahad Baig , ISTA, Austria
Suvradip Chakraborty , Visa Research
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, Austria
Search ePrint
Search Google
Presentation: Slides
Conference: TCC 2023
Abstract: The notion of “efficiently testable circuits” (ETC) was recently put forward by Baig et al. (ITCS’23). Informally, an ETC compiler takes as input any Boolean circuit C and outputs a circuit/inputs tuple (C′, T) where (completeness) C′ is functionally equivalent to C and (security) if C′ is tampered in some restricted way, then this can be detected as C′ will err on at least one input in the small test set T. The compiler of Baig et al. detects tampering even if the adversary can tamper with all wires in the compiled circuit. Unfortunately, the model requires a strong “conductivity” restriction: the compiled circuit has gates with fan-out up to 3, but wires can only be tampered in one way even if the have fan-out greater than one. In this paper, we solve the main open question from their work and construct an ETC compiler without this conductivity restriction. While Baig et al. use gadgets computing the AND and OR of particular subsets of the wires, our compiler computes inner products with random vectors. We slightly relax their security notion and only require that tampering is detected with high probability over the choice of the randomness. Our compiler increases the size of the circuit by only a small constant factor. For a parameter λ (think λ ≤ 5), the number of additional input and output wires is |C|1/λ, while the number of test queries to detect an error with constant probability is around 22λ.
  title={Efficiently Testable Circuits without Conductivity},
  author={Mirza Ahad Baig and Suvradip Chakraborty and Stefan Dziembowski and Małgorzata Gałązka and Tomasz Lizurej and Krzysztof Pietrzak},