Secure hash-and-sign signatures

Details Secure hash-and-sign signatures Secure hash-and-sign signatures

1999-03-23

2003-06-10

Darrow, Justin T. (Department: 2132)

Electrical computers and digital processing systems: support

Multiple computer communication using cryptography

Particular communication authentication technique

C713S170000, C713S181000, C380S030000, C708S605000, C708S606000

Reexamination Certificate

active

06578144

ABSTRACT:

FIELD OF THE INVENTION
The present invention is directed to the field of secure communications. It is more particularly related to secure digital signature schemes.
BACKGROUND OF THE INVENTION
With today's exponential growth in the volume of electronic communications, there is a need for cryptographic tools that offer high security as well as high efficiency. Communication networks todays must support exchange of sensitive information (e.g., medical files), remote access of data, electronic commerce, and a variety of other tasks. At the very least, the network is expected to ensure integrity and authenticity of data, and often also confidentiality.
When a message is transmitted from one party to another, the receiving party may desire to determine whether the message has been altered in transit. Furthermore, the receiving party may which to be certain of the origin of the message. Traditionally, written data has been authenticated by appending the hand-written signature of the appropriate individual to the data. In the realm of electronic communication, methods for authenticating data proceed in a similar fashion, except that the hand-written signature is replaced with a digital signature. The digital signature is computed by the signer based on the message being signed.
The digital signature should have the properties that anyone can verify that a signature is the valid signature of the signer for the associated message, and that only the signer is able to generate the signature. Hence, digital signature methods may also be used to prove to a third party that the message was signed by the actual signer, thus providing non repudiation.
A typical system wherein a sender is using a digital signature scheme to authenticate messages that it sends to a receiver is depicted in FIG.
1
. In this figure, a dashed line separates the operations of a sender
100
on the left from the operation of a receiver
110
on the right. In a preliminary operation, the sender
100
uses a key generation process
101
to generate a public key
102
and a secret key
103
. The public key
102
is made available to the receiver
110
before any message is sent using some mechanism. Mechanisms to supply the public key to the receiver
110
are well known in the art, and are not discussed in this patent. The secret key
103
is kept secret by the sender
100
.
To authenticate a message
104
, the sender
100
uses a signing process
105
, giving it as input the message
104
and the secret key
103
. The output of the signing process
105
is a signature
106
on the message
104
. The sender
100
uses conventional communication equipment to transmit both the message
104
and the signature
106
to the receiver
110
. The receiver
110
uses a verification process
107
, giving it as input the public key
102
, the message
104
and the signature
106
. The output of the verification process
107
signifies that the signature is valid
108
, or that an invalid signature has been detected.
Several digital signature methods are known in the art. The most popular method today for computing digital signatures in the RSA scheme. The strongest notion of security of digital signatures is called existential unforgeability under an adaptive chosen message attack. It requires that forging a signature of an arbitrary message without knowing the secret key is not feasible, even if an attacker receives several signatures on messages of its choice. Construction of efficient signature schemes for which it is possible to prove existential unforgeability under an adaptive chosen message attack is a long standing challenge. Prior to the present invention, the only schemes for which such proofs are known were based on “signature trees”, and were not very efficient. Another drawback of these prior schemes is their stateful nature, i.e. the signer has to store some information from previously signed messages.
Another line of research concentrates on hash-and-sign schemes, wherein the message to be signed is hashed using a cryptographic hash function. The result is signed using a standard signature scheme such as RSA. The current standard for RSA signatures is based on the hash-and-sign approach. Although hash-and-sign schemes are very efficient, they only enjoy a heuristic level of security. The only known security proofs for hash-and-sign schemes are carried out in a model wherein the hash function is assumed to be an “ideal” one. Specifically, in these proofs the hash function is replaced by a random oracle.
SUMMARY OF THE INVENTION
It is thus an object of the present invention to provide a digital signature scheme that can be proven secure without using the random-oracle heuristic. Instead, the security proof is based on well-defined and constructable properties that are required from the hash function in use.
Another object of the invention is to provide a signature scheme which is efficient. Specifically, it should follow the hash-and-sign paradigm, by which a message is first hashed using a cryptographic hash function, and then signed using a few simple algebraic operations.
Yet another object of the invention is to provide a signature scheme in which the signer does not need to keep any state (other than the secret key) for the purpose of generating signatures.
These and other objects are provided in a digital signature scheme wherein the signature of a message relative to a public key is computed by means of a secret key. Other objects and a better understanding of the invention may be realized by referring to the Detailed Description.


REFERENCES:
patent: 5796833 (1998-08-01), Chen et al.
patent: 0 772 165 (1997-05-01), None
“Digital Signature and Public Key Cryptosystem in a Prime Order Subgroup of Z*n”, C. Boyd, Info. Sec. Res. Ctr., School of Data Communications, Queensland University of Technology, Brisbane Q4001, Australia. Proc. ICICS'97, 1997.
“On the Security of some Variants of the RSA Signature Scheme”, M. Michels, M. Stadler and H-M. Sun, Dept. of Information Management, Chao Yang University of Technology, Wufend, Taichung County, Taiwan 413.

Affiliated with

Also associated with

Rating

Secure hash-and-sign signatures does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Secure hash-and-sign signatures, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Secure hash-and-sign signatures will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-3156986