Efficient hybrid public key signature scheme

Details Efficient hybrid public key signature scheme Efficient hybrid public key signature scheme

1999-05-07

2004-03-02

Jean, Frantz B. (Department: 2131)

Electrical computers and digital processing systems: support

Multiple computer communication using cryptography

Particular communication authentication technique

C713S156000, C713S170000, C713S177000, C713S179000, C380S028000, C380S030000, C380S046000, C380S277000, C705S037000

Reexamination Certificate

active

06701434

ABSTRACT:

FIELD OF THE INVENTION
The present invention is directed to the field of cryptography. It is more specifically related to the field of digital signature technology.
BACKGROUND OF THE INVENTION
A digital signature is a fundamental cryptographic primitive which, in the digital setting, generally serves the same purpose as a handwritten signature in the real world setting. Namely, it binds, in an unforgeable, non-repudiable manner, the identity of the signer to the information being signed.
The mechanisms of applying and using public-key based digital signature technology however, are quite different than those used for handwritten signatures. Firstly the digital signature itself is a mathematical function of the message being signed and a private key known only to the signer. Thus, unlike a handwritten signatures, every digital signature employed by an entity is very different from its other signatures, since the underlying message being signed is likely to be different. Verification of a digital signature, therefore, is also very different from its handwritten counterpart. Instead of examining the similarity between the signature on a message and a sample signature of the signer, the verifier applies a mathematical function on the message, the signature and a publicly known key of the signer. The publicly known key is known to correspond to the signer's privately held key. The system works as long as it is infeasible to compute the private key from the publicly known key, and without the private key it is infeasible to compute the signature on any new message. Therefore, whereas everyone is able to verify the signatures using the public key, only the owner of the private key can compute digital signatures.
The above is a description of how public key signatures work in theory. However, to make such signatures useful in practice, several additional steps, cryptographic primitives and infrastructure are required. We now describe some of these additional steps, primitives and infrastructure since they have a direct bearing on this invention.
From the description of the generation, signing and verification process above, it should be clear that a digital signature only binds the signature to the owner of a private key corresponding to the public key used in the verification process. Since private-public key pairs are just mathematical objects which can be generated by anyone, to serve any useful legal and/or other purpose, there should also be a binding between the public key and the real-world identity of the owner of the corresponding private key. In practice this is done by means of another digital object called a public key certificate. The certificate (or chain of certificates) is essentially a statement binding the real-world identity of a signer with a public key, together with a digital signature (or chain of digital signatures) from a trusted entity vouching for the veracity of the binding statement. The trusted entity is referred to as a certification authority. Since the certification authority's public key is well known, this provides a way for another entity which trusts the certification authority, to verify that indeed the signer with a certain real-life identity is in possession of the private key corresponding to the public key. This other entity can verify the binding between the signer's identity and public key by verifying the certification authority's signature on the binding object.
There is yet another important practical issue relating to the use of digital signatures. In popular public key signature schemes such as the RSA algorithm, the DSA algorithm etc, once the public/private key for a signer is chosen, the core signature algorithm can only be applied to message blocks of a certain fixed size. However, it is impractical for entities to have multiple certified public keys for all possible message block sizes. Also, computing signatures for very large message-block sizes is very time consuming. In practice, core signature schemes are used in conjunction with another cryptographic primitive known as a cryptographic hash function. A cryptographic hash function is a publicly known function that takes in an arbitrary sized message as an argument and produces a fixed sized output. This output is said to be the cryptographic hash of the message. The hash function has a property of being collision resistant. A function is collision resistant if it is infeasible to come up with two different inputs upon which the function produces the same output. Examples of cryptographic hash functions include SHA-
1
and MD
5
which produce 160-bit and 128-bits outputs respectively.
With a collision resistant hash function, a signer can sign any arbitrarily sized message with a single private key by applying the signature algorithm only to the cryptographic hash of the message. Similarly, a verifier can verify a signature on a message by applying the signature verification algorithm on the cryptographic hash of the message. Since it is infeasible for anybody (including the signer, the verifier or any other third party) to compute two different messages which have the same cryptographic hash, with respect to unforgeability and non-repudiation, a signature on the hash behaves like a signature on the actual message.
In many cases, another cryptographic primitive called a Target Collision Resistant (TCR) hash function can be used in the place of collision resistant hash function in the signature compution process for arbitrary messages. TCR hash functions may be referred to as universal one-way hash functions. Target Collision Resistance can be viewed as a weaker requirement than collision resistance, but is nevertheless considered to be good enough for signatures. A target collision resistant function is a publicly known function that takes as input a fixed sized message and a fixed sized key and produces an output of some fixed size. The cryptographic property required of a TCR function T is that given its description, it is infeasible for someone to come up with any message M
1
, such that, when the function T is computed with a randomly chosen key K, it becomes feasible for that someone to compute some other message M
2
, such that the value of T on M
1
and K coincides with the value of T on M
2
and K. The point to note in the definition of a TCR function is that the key K is randomly chosen only after M
1
has been chosen. Indeed, it is quite possible that if K were to be chosen first then it may be quite easy to produce a collision, i.e., two messages M
1
and M
2
such that T on K and M
1
coincides with T on K and M
2
. Thus, the TCR requirements of a function are less burdensome than the requirements of collision resistance from a keyless function which prohibits easy computation for any collision whatsoever. Therefore, candidates for TCR functions are expected to be easier to design than candidates for collision resistant hash functions.
TCR functions are suitable for use in signatures in the following way. In order to sign a message m, which in the most general setting could have been chosen by someone other than the signer, the signer randomly picks a key k, computes the TCR function on m and k and then signs the output resulting from applying the TCR function together with k using any available digital signature scheme. If the available digital signature scheme is unforgeable, then the scheme involving TCR function retains the property that it is not feasible for anyone else to forge signatures based on it. Hence they cannot be repudiated. It should be noted that in the case of TCR based signatures, the signer can come up with two different messages which have the same signature by choosing the messages after choosing the key to the TCR function, whereas in the case of collision-resistant hash functions, even the signer cannot do so.
We now briefly describe another cryptographic primitive known as a commitment scheme. Although, prior to the present invention commitment schemes are unrelated to digital signatures, they are described here, since t

Affiliated with

Also associated with

Rating

Efficient hybrid public key signature scheme does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Efficient hybrid public key signature scheme, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Efficient hybrid public key signature scheme will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-3275568