---
_id: '10407'
abstract:
- lang: eng
  text: 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   F  one has more sophisticated circuits   F⋄  manufactured
    (where   F⋄  specifies a MPC or VC of   F ), and then embeds these   F⋄ ’s into
    a master circuit which must be trusted but is relatively simple compared to   F
    . Those solutions impose a significant overhead as   F⋄  is much more complex
    than   F , also the master circuits are not exactly trivial. In this work, we
    show that in restricted settings, where   F  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.,   F=F⋄ ). 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   F  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.
alternative_title:
- LNCS
article_processing_charge: No
author:
- first_name: Suvradip
  full_name: Chakraborty, Suvradip
  id: B9CD0494-D033-11E9-B219-A439E6697425
  last_name: Chakraborty
- first_name: Stefan
  full_name: Dziembowski, Stefan
  last_name: Dziembowski
- first_name: Małgorzata
  full_name: Gałązka, Małgorzata
  last_name: Gałązka
- first_name: Tomasz
  full_name: Lizurej, Tomasz
  last_name: Lizurej
- first_name: Krzysztof Z
  full_name: Pietrzak, Krzysztof Z
  id: 3E04A7AA-F248-11E8-B48F-1D18A9856A87
  last_name: Pietrzak
  orcid: 0000-0002-9139-1654
- first_name: Michelle X
  full_name: Yeo, Michelle X
  id: 2D82B818-F248-11E8-B48F-1D18A9856A87
  last_name: Yeo
  orcid: 0009-0001-3676-4809
citation:
  ama: 'Chakraborty S, Dziembowski S, Gałązka M, Lizurej T, Pietrzak KZ, Yeo MX. Trojan-resilience
    without cryptography. In: Vol 13043. Springer Nature; 2021:397-428. doi:<a href="https://doi.org/10.1007/978-3-030-90453-1_14">10.1007/978-3-030-90453-1_14</a>'
  apa: 'Chakraborty, S., Dziembowski, S., Gałązka, M., Lizurej, T., Pietrzak, K. Z.,
    &#38; Yeo, M. X. (2021). Trojan-resilience without cryptography (Vol. 13043, pp.
    397–428). Presented at the TCC: Theory of Cryptography Conference, Raleigh, NC,
    United States: Springer Nature. <a href="https://doi.org/10.1007/978-3-030-90453-1_14">https://doi.org/10.1007/978-3-030-90453-1_14</a>'
  chicago: Chakraborty, Suvradip, Stefan Dziembowski, Małgorzata Gałązka, Tomasz Lizurej,
    Krzysztof Z Pietrzak, and Michelle X Yeo. “Trojan-Resilience without Cryptography,”
    13043:397–428. Springer Nature, 2021. <a href="https://doi.org/10.1007/978-3-030-90453-1_14">https://doi.org/10.1007/978-3-030-90453-1_14</a>.
  ieee: 'S. Chakraborty, S. Dziembowski, M. Gałązka, T. Lizurej, K. Z. Pietrzak, and
    M. X. Yeo, “Trojan-resilience without cryptography,” presented at the TCC: Theory
    of Cryptography Conference, Raleigh, NC, United States, 2021, vol. 13043, pp.
    397–428.'
  ista: 'Chakraborty S, Dziembowski S, Gałązka M, Lizurej T, Pietrzak KZ, Yeo MX.
    2021. Trojan-resilience without cryptography. TCC: Theory of Cryptography Conference,
    LNCS, vol. 13043, 397–428.'
  mla: Chakraborty, Suvradip, et al. <i>Trojan-Resilience without Cryptography</i>.
    Vol. 13043, Springer Nature, 2021, pp. 397–428, doi:<a href="https://doi.org/10.1007/978-3-030-90453-1_14">10.1007/978-3-030-90453-1_14</a>.
  short: S. Chakraborty, S. Dziembowski, M. Gałązka, T. Lizurej, K.Z. Pietrzak, M.X.
    Yeo, in:, Springer Nature, 2021, pp. 397–428.
conference:
  end_date: 2021-11-11
  location: Raleigh, NC, United States
  name: 'TCC: Theory of Cryptography Conference'
  start_date: 2021-11-08
date_created: 2021-12-05T23:01:42Z
date_published: 2021-11-04T00:00:00Z
date_updated: 2025-04-14T07:22:05Z
day: '04'
department:
- _id: KrPi
doi: 10.1007/978-3-030-90453-1_14
ec_funded: 1
external_id:
  isi:
  - '000728364000014'
intvolume: '     13043'
isi: 1
language:
- iso: eng
main_file_link:
- open_access: '1'
  url: https://eprint.iacr.org/2021/1224
month: '11'
oa: 1
oa_version: Preprint
page: 397-428
project:
- _id: 258AA5B2-B435-11E9-9278-68D0E5697425
  call_identifier: H2020
  grant_number: '682815'
  name: Teaching Old Crypto New Tricks
publication_identifier:
  eissn:
  - 1611-3349
  isbn:
  - 9-783-0309-0452-4
  issn:
  - 0302-9743
publication_status: published
publisher: Springer Nature
quality_controlled: '1'
scopus_import: '1'
status: public
title: Trojan-resilience without cryptography
type: conference
user_id: 4359f0d1-fa6c-11eb-b949-802e58b17ae8
volume: 13043
year: '2021'
...