Ambiguous One-Move nominative signature without Random Oracles

Nominative Signature is a useful tool in situations where a signature has to be created jointly by two parties, a nominator (signer) and a nominee (user), while only the user can verify and prove to a third party about the validity of the signature. In this paper, we study the existing security models of nominative signature and show that though the existing models have captured the essential security requirements of nominative signature in a strong sense, especially on the unforgeability against malicious signers/users and invisibility, they are yet to capture a requirement regarding the privacy of the signer and the user, and this requirement has been one of the original ones since the notion of nominative signature was first introduced. In particular, we show that it is possible to build a highly efficient nominative signature scheme which can be proven secure in the existing security models, while in practice it is obvious to find out from the component(s) of a nominative signature on whether a particular signer or user has involved in the signature generation, which may not be desirable in some actual applications. We therefore propose an enhanced security property, named “Ambiguity”, and also propose a new one-move nominative scheme for fulfilling this new security requirement without random oracles, and among the various types of nominative signature, one-move is the most efficient type. Furthermore, this new scheme is at least 33% more efficient during signature generation and 17% shorter in signature size when compared with the existing one-move signature schemes without random oracles even that the existing ones in the literature may not satisfy this new Ambiguity requirement.