Efficient undeniable signature schemes based on ideal arithmetic in quadratic orders (Q1431610)

Undeniable signature schemes are characterized by the property that the signature cannot be checked without the help of the signer; that is the signer can choose which verifiers may check the authenticity of the message. Well-known undeniable signature schemes presented in the literature will induce operations both for the signer and the verifier which take cubic running time. For a real world implementation, when the operations have to be performed by a chip card or a web server with high access rates, this is inefficient. In this paper, the authors present new undeniable signature schemes which are constructed using imaginary quadratic fields. All operations on the signer's side involving the secret key are of quadratic complexity. There are operations of cubic complexity, but they can be left for the software running on the PC to which the chip card is connected. The authors claim that the comparisons with the RSA-based undeniable signature scheme shows a major advantage in practice.