Paper 2018/564

Impossibility on Tamper-Resilient Cryptography with Uniqueness Properties

Yuyu Wang, Takahiro Matsuda, Goichiro Hanaoka, and Keisuke Tanaka


In this work, we show negative results on the tamper-resilience of a wide class of cryptographic primitives with uniqueness properties, such as unique signatures, verifiable random functions, signatures with unique keys, injective one-way functions, and encryption schemes with a property we call unique-message property. Concretely, we prove that for these primitives, it is impossible to derive their (even extremely weak) tamper-resilience from any common assumption, via black-box reductions. Our proofs exploit the simulatable attack paradigm proposed by Wichs (ITCS ’13), and the tampering model we treat is the plain model, where there is no trusted setup.

Available format(s)
Publication info
Published by the IACR in PKC 2021
black-box separationsimulatable attacktamper-resilienceuniqueness
Contact author(s)
wang y ar @ m titech ac jp
t-matsuda @ aist go jp
hanaoka-goichiro @ aist go jp
keisuke @ is titech ac jp
2021-04-24: revised
2018-06-04: received
See all versions
Short URL
Creative Commons Attribution


      author = {Yuyu Wang and Takahiro Matsuda and Goichiro Hanaoka and Keisuke Tanaka},
      title = {Impossibility on Tamper-Resilient Cryptography with Uniqueness Properties},
      howpublished = {Cryptology ePrint Archive, Paper 2018/564},
      year = {2018},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.