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.

Metadata
Available format(s)
PDF
Publication info
A minor revision of an IACR publication in Tcc 2021
Keywords
hardware trojansphysical attacks
Contact author(s)
stefan dziembowski @ gmail com
malgorzata bladoszewska @ gmail com
krzpie @ gmail com
tomaszlizurej @ outlook com
suvradip chakraborty @ ist ac at
michelle yeo @ ist ac at
History
2021-10-24: revised
2021-09-20: received
See all versions
Short URL
https://ia.cr/2021/1224
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2021/1224,
      author = {Suvradip Chakraborty and Stefan Dziembowski and Malgorzata Galazka and Tomasz Lizurej and Krzysztof Pietrzak and Michelle Yeo},
      title = {Trojan-Resilience without Cryptography},
      howpublished = {Cryptology ePrint Archive, Paper 2021/1224},
      year = {2021},
      note = {\url{https://eprint.iacr.org/2021/1224}},
      url = {https://eprint.iacr.org/2021/1224}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.