Improved Magic Ink Signatures Using Hints

We introduce two improvements to the recently proposed so called magic ink DSS signatures. A first improvement is that we reduce the overhead for tracing without noticeably increasing any other cost. The tracing cost is linear in the number of generated signatures in the original proposal; our improved version reduces this to a logarithmic cost in the common case. A second improvement is that we introduce a method for determining whether forged currency is in circulation, without affecting the privacy of honest users. Our improvements rely on our introducing a so called hint value. This is an encryption of the signature transcript received, submitted by the signature receiver. Part of the p…