Cryptology ePrint Archive: Report 2021/1224

Trojan-Resilience without Cryptography

Suvradip Chakraborty and Stefan Dziembowski and Malgorzata Galazka and Tomasz Lizurej and 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.

Category / Keywords: hardware trojans, physical attacks

Original Publication (with minor differences): IACR-TCC-2021

Date: received 17 Sep 2021, last revised 24 Oct 2021

Contact author: stefan dziembowski at gmail com, malgorzata bladoszewska at gmail com, krzpie at gmail com, tomaszlizurej at outlook com, suvradip chakraborty at ist ac at, michelle yeo at ist ac at

Available format(s): PDF | BibTeX Citation

Note: Added back the full proofs and appendix.

Version: 20211024:140126 (All versions of this report)

Short URL: ia.cr/2021/1224


[ Cryptology ePrint archive ]