In this talk, I will present the notion of “Efficiently TestableCircuits” introduced in [ITCS23].  Informally, a circuit is testable if one can detect tampering with the circuit by evaluating it on a small number ofinputs from some test set. Our technical contribution is a compiler that transforms any circuit C into a testable circuit ( C’, T) for which we can detect tampering (from a class of allowed tampering) with all wires in C’ using only inputs from test set T. This is a deterministic test with a small 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’, T) where C’ is of size ≈ 12n and depth d + log(n) + L · n^(1/L). The test set T 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.

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 they have fan-out greater than one. In a follow-up work from [TCC23], we construct an ETC compiler without this conductivity restriction.  This compiler computes inner products with random vectors. We slightly relax the security notion and only require that tampering is detected with high probability.  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 2^(2^λ).

Based on joint works with Suvradip Chakraborty, Stefan Dziembowski, Malgorzata Galazka, Tomasz Lizurej, and Krzysztof Pietrzak.