As Ken pointed out, this is the same problem as DRM systems. They use various methods for storing keys where users cannot (easily) find them. You would combine a digital signature scheme with an overly complex key storage scheme. Divide it into several parts scattered around the user system - some parts in the registry, some in files in the file system, some encoded in the modification dates and file names of various innocent files. Also, making the DRM subsystem of your code intentionally unclear and difficult to debug.
Another alternative would be to periodically send the signature data to some remote system (if you can depend on having an Internet connection).