The cryptographic community so far has paid very limited attention to the problem. In this work, we present the basic issues and suggest a possible methodology and the first scheme that may be used to solve much of the problem. Our solution takes the following steps: (1) it develops the notion of a nested trapdoor which our methodology is based on, (2) we implement this notion based on a novel composite “double-decker” exponentiation technique which embeds the RSA problem within it (the technique may be of independent interest), (3) we analyze carefully what can be and what cannot be achieved regarding the open problem by NIST (our analysis is balanced and points out possibilities as well as impossibilities), and (4) we give a secure signature scheme within a public key infrastructure, wherein the published public key can be used for signature verification only (if it is used for encryptions, then the authorities can decrypt the data). The security of our scheme is based on RSA. We then argue how the scheme’s key cannot be abused (statically) based on an additional assumption. We also show that further leakages and subliminal leakages when the scheme is in (dynamic) use are not added substantially beyond what is always possible by a simple adversary; we call this notion competitive leakage. We also demonstrate such simple leaking adversary.

We hope that our initial work will stimulate further thoughts on the non-trivial issue of signature-only signatures.