Convertible Nominative Signatures from Standard Assumptions without Random Oracles

While standard signatures provide an efficient mechanism for information certification, the lack of privacy protecting measures makes them unsuitable if sensitive or confidential information is being certified. In this paper, we revisit nominative signatures, first introduced by Kim, Park and Won, which provides the functionality and security guarantees required to implement a certification system allowing the user ( and not the authority) to control the verifiability of an obtained certificate. Unlike systems based on related primitives, the use of nominative signatures protects the user against authority information leaks and impersonation attacks based on these. We refine the security model of nominative signatures, and propose a new efficient scheme which is provably secure based on the computational Diffie-Hellman problem and the decisional linear problem. To the best of our knowledge, our scheme is the the only nominative signature scheme which is provably secure in the standard model based on standard assumptions. Furthermore, unlike most previous schemes, the proposed scheme provides signatures which hide both the signer and user identity. Hence, through our nominative signature scheme, we achieve an efficient non-transferable user certification scheme with strong security guarantees.