Cryptology ePrint Archive: Report 2018/564

Impossibility on Tamper-Resilient Cryptography with Uniqueness Properties

Yuyu Wang and Takahiro Matsuda and 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 public parameters and public/secret key pairs are potentially tampered with.

Category / Keywords: black-box separation, simulatable attack, tamper-resilience, uniqueness

Date: received 31 May 2018, last revised 4 Jun 2018

Contact author: wang y ar at m titech ac jp, t-matsuda@aist go jp, hanaoka-goichiro@aist go jp, keisuke@is titech ac jp

Available format(s): PDF | BibTeX Citation

Version: 20180604:232353 (All versions of this report)

Short URL: ia.cr/2018/564


[ Cryptology ePrint archive ]