International Association for Cryptologic Research

International Association
for Cryptologic Research


Paper: Trojan-Resilience without Cryptography

Suvradip Chakraborty
Stefan Dziembowski
Malgorzata Galazka
Tomasz Lizurej
Krzysztof Pietrzak
Michelle Yeo
DOI: 10.1007/978-3-030-90453-1_14
Search ePrint
Search Google
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.
Video from TCC 2021
  title={Trojan-Resilience without Cryptography},
  booktitle={Theory of Cryptography;19th International Conference},
  author={Suvradip Chakraborty and Stefan Dziembowski and Malgorzata Galazka and Tomasz Lizurej and Krzysztof Pietrzak and Michelle Yeo},