Paper 2021/1224

Trojan-Resilience without Cryptography

Suvradip Chakraborty, Stefan Dziembowski, Malgorzata Galazka, Tomasz Lizurej, Krzysztof Pietrzak, and Michelle Yeo

Abstract

Digital hardware Trojans are integrated circuits whose implementation differ from the specification in an arbitrary and malicious way. For example, the circuit can differ from its specified input/output behavior after some fixed number of queries (known as ``time bombs'') or on some particular input (known as ``cheat codes''). To detect such Trojans, countermeasures using multiparty computation (MPC) or verifiable computation (VC), have been proposed. On a high level, to realize a circuit with specification $\cF$ one has more sophisticated circuits $\cF^\diamond$ manufactured (where $\cF^\diamond$ specifies a MPC or VC of $\cF$), and then embeds these $\cF^\diamond$'s into a \emph{master circuit} which must be trusted but is relatively simple compared to $\cF$. Those solutions have a significant overhead as $\cF^\diamond$ is significantly more complex than $\cF$ and also the master circuits are not exactly trivial either. In this work, we show that in restricted settings, where $\cF$ has no evolving state and is queried on independent inputs, we can achieve a relaxed security notion using very simple constructions. In particular, we do not change the specification of the circuit at all (i.e., $\cF=\cF^\diamond$). Moreover the master circuit basically just queries a subset of its manufactured circuits and checks if they're all the same. The security we achieve guarantees that, if the manufactured circuits are initially tested on up to $T$ inputs, the master circuit will catch Trojans that try to deviate on significantly more than a $1/T$ fraction of the inputs. This bound is optimal for the type of construction considered, and we provably achieve it using a construction where $12$ instantiations of $\cF$ need to be embedded into the master. We also discuss an extremely simple construction with just $2$ instantiations for which we conjecture that it already achieves the optimal bound.

Note: Added back the full proofs and appendix.