Short and efficient convertible undeniable signature schemes without random oracles

A convertible undeniable signature allows a signer to confirm or disavow a non-self-authenticating signature and also convert a valid one to a publicly verifiable signature. During the conversion, existing schemes either require the signer to be stateful, or have their security based on the random oracle assumption, or result in getting a large converter. In this work we propose a new construction, which supports both selective conversion and universal conversion, and is provably secure without random oracles. It has the shortest undeniable signature and the smallest converter. A signature consists of three bilinear group elements and just one group element each in a selective converter and a universal converter. The scheme can be extended further to support new features, such as the delegation of conversion and confirmation/disavowal, threshold conversion and others. We also propose an alternative generic construction of stateless convertible undeniable signature. Unlike the conventional 'sign-then-encrypt' paradigm, a signer in this new generic scheme encrypts a signature using identity-based encryption instead of public key encryption. It also enjoys the advantage of a short selective converter.