Methods and apparatus are disclosed for generation of secure and efficient
digital signatures in an information processing system. The system
includes one or more user devices, a signing aid or other intermediary
device, and a verifier. A given user device has associated therewith key
pairs (s, p) and (s', p') corresponding to respective first and second
digital signature protocols. As part of a setup process, an agreement
relating to the public keys p and p' is signed by both the user device
and the intermediary device, and the resulting twice-signed agreement is
stored by both the user device and the intermediary device. A first
digital signature s1 is then generated on a message m or a hash h(m)
thereof in the user device using the secret key s' and is sent to the
verifier. The verifier in turn sends s1 to the intermediary, and the
intermediary checks that s1 is a valid digital signature for the user
device. If s1 is valid, the intermediary device generates a second
digital signature s2 on m or h(m) using the secret key s, and s2 is
returned to the verifier as a signature generated by the user device. The
intermediary may be configured to wait a predetermined delay period
between checking that s1 is a valid signature and generating s2, such
that a user may contact the intermediary device and upon providing an
access code thereto direct the intermediary device not to generate s2.