Title: Unique Witness Maps and Deterministic Leakage and Tamper Resilient Signatures

Abstract: We introduce a new primitive, which we call a Unique Witness Map (UWM). A UWM deterministically maps all possible witnesses for an NP statement to a single representative (computationally sound) witness. We construct a UWM from indistinguishability obfuscation (iO). As an application of UWM, we construct the first leakage and tamper-resilient (LTR) signatures with a deterministic signer, thereby solving a decade old open problem posed by Katz and Vaikunthanathan (Asiacrypt 2009), by Boyle, Segev and Wichs (Eurocrypt 2011), as well as by Faonio and Venturi (Asiacrypt 2016). Our construction achieves the optimal leakage rate of 1 - o(1).

Along the way, we provide two results of independent interest. Firstly, we construct punctured digital signatures (PDS) from one-way functions (OWF). Our construction vastly improves upon the previous construction of PDS scheme by Bellare et al. (Eurocrypt 2016), who relied on sub-exponentially secure iO and sub-exponentially secure OWF. Secondly, we introduce and construct new notions of cumulatively lossy trapdoor functions (C-LTDFs) and cumulatively all-lossy-but-one trapdoor functions (C-ALBO-TDF), where arbitrarily many different lossy functions (or lossy branches) taken together are jointly lossy.

Speaker: Suvradip Chakraborty is a PhD Student at Indian Institute of Technology Madras (IITM), India. He is currently a visiting researcher in the Cryptography and Security Research Group at CS https://www.cse.iitm.ac.in/profile.php?arg=Njg0