Impossibility on Tamper-Resilient Cryptography with Uniqueness Properties

Yuyu Wang; Takahiro Matsuda; Goichiro Hanaoka; Keisuke Tanaka

Paper 2018/564

Impossibility on Tamper-Resilient Cryptography with Uniqueness Properties

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

Abstract

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.

Metadata

Available format(s): PDF
Publication info: Published by the IACR in PKC 2021
Keywords: black-box separation simulatable attack tamper-resilience uniqueness
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
History: 2021-04-24: revised; 2018-06-04: received; See all versions
Short URL: https://ia.cr/2018/564
License: CC BY

BibTeX

@misc{cryptoeprint:2018/564,
      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},
      url = {https://eprint.iacr.org/2018/564}
}