Probabilistic signature scheme

Details Probabilistic signature scheme Probabilistic signature scheme

1998-02-09

2001-07-24

Barron, Jr., Gilberto (Department: 2132)

Electrical computers and digital processing systems: support

Multiple computer communication using cryptography

Particular communication authentication technique

C713S178000, C713S180000, C713S181000

Reexamination Certificate

active

06266771

ABSTRACT:

BACKGROUND OF THE INVENTION
1. Technical Field
The present invention relates generally to digital signature schemes and, more particularly, to an RSA-based signing scheme that combines excellent efficiency with attractive security properties.
2. Brief Description of the Related Art
In the RSA public key system, a party has public key (N,e) and secret key (N,d), where N is a k-bit modulus, the product of two (k/2)-bit primes, and e,d&egr;Z
&phgr;(N)
* satisfy ed≡1 mod &phgr;(N). The RSA function f: Z
N
*→Z
N
* is defined by f(x)=x
e
mod N and its inverse f
−1
: Z
N
*→Z
N
* is defined by f
−1
(y)=y
d
mod N (x, y&egr;Z
N
*, where Z
N
* denotes the set of numbers between 1 and N−1 which are relatively prime to N). The function f can be used for encryption and f
−1
for decryption. The generally-made assumption is that f is trapdoor one-way; roughly, if one does not know d (or the prime factors of N), then it is hard to compute x=f
−1
(y) for a y drawn randomly from Z
N
*.
A widely employed paradigm to sign a document M is to first compute some “hash” y=Hash(M) and then set the signature to x=f (y)=y
d
mod N. To verify that x is a signature of M, one computes f(x)=x
e
mod N and checks that this equals Hash(M). This technique is the basis for several existing standards. A necessary requirement on Hash in such a scheme is that it be collision-intractable and produce a k-bit output that encodes a point in Z
N
*. Accordingly, Hash is most often implemented via a cryptographic hash function like h=MD5 (which yields a 128 bit output and is assumed to be collision-intractable) and some padding. A concrete example of such a scheme is described in PKCS #1: RSA Encryption Standard (Version 1.4), June 1991, and PKCS #7, Cryptographic Message Syntax Standard (Version 1.4), June 1991, RSA Data Security, Inc., where the hash is:
Hash
PCKS
(M)=0×0001FFFF . . . FFFF00|h(M).
In the above expression, the “0x” indicates that the following number is written in hexadecimal notation, and “|” denotes concatenation. Such a signature scheme may be called a “hashthen-decrypt” scheme.
The security of a hash-then-decrypt signature depends on how Hash is implemented. But the security of a scheme like Sign
PKCS
(M)=f
−1
(Has
PKCS
(M)) cannot be justified given only that RSA is trapdoor one-way, even under the assumption that hash function h is ideal. This is because the set of points {Hash
PKCS
(M):M&egr;{0,1}*} has size at most 2
128
and hence is a very sparse, and a very structured, subset of Z
N
*. This lack of demonstrable security is disadvantageous. In particular, although there is no known attack on this scheme, it is preferable to have a signature scheme with some proof of security. The same issue arises for other known standards, including ISO/IEC 9796. There, the hash function involves no cryptographic hashing, and the message M is easily recovered from Hash(M).
Thus, the security of the current PKCS standards, as well as that of the ISO standard, cannot be justified based on the assumption that RSA is trapdoor one-way. Other standards, such as described in Privacy Enhancement for Internet Electronic Mail: Part III Algorithms, Modes, and Identifiers, by Balenson, IETF RFC 1423, February, 1993, are similar to the RSA standard, and the same reasoning applies.
Signature schemes whose security can be provably based on the RSA assumption include the schemes described in the following representative publications: Goldwasser, Micali and Rivest, A digital signature scheme secure against adaptive chosen-message attacks, SIAM Journal of Computing, 17(2):281-308, April 1988; Bellare and Micali, How to sign given any trapdoor permutation, JACM Vol. 9, No. 1, 214-233, January, 1992; Naor and Yung, Universal one-way hash functions and their cryptographic applications, Proceedings of the 21st Annual Symposium on Theory of Computing, ACM, 1989; Rompel, One-way Functions are Necessary and Sufficient for Secure Signatures, Proceedings of the 22nd Annual Symposium on Theory of Computing, ACM, 1990; and Dwork and Noar, An efficient existentially unforgeable signature scheme and its applications, Advances in Cryptology—Crypto 94 proceedings, Lecture Notes in Computer Science Vol. 839, Y. Desmedt. ed., Springer-Verlag, 1994. The major advantage of these works is that they can be proven to be sound, under some formalized mathematical assumption. On the other hand, these are not practical schemes; their cost (in computation time and storage) is so high that they are not considered for real world security applications.
There are additional signature schemes that have been proven secure under the assumption that a hash function which they use behaves as though it were a random function. Such schemes can be based on the hardness of factoring, or on other assumptions. Some of these schemes have been derived from identification schemes, as was first described by Fiat and Shamir, How to prove yourself: practical solutions to identification and signature problems, Advances in Cryptology—Crypto 86 Proceedings, Lecture Notes in Computer Science, Vol. 263, A. Odlyzko ed., Springer-Verlag, 1986. The efficiency of those schemes varies. The computational requirements are often lower than a hash-then-decrypt RSA signature, although key sizes are typically larger.
The paradigm of protocol design using hash functions that are regarded (in proofs) as random functions is thus well-developed, as described in Bellare and Rogaway, Random oracles are practical: a paradigm for designing efficient protocols, Proceedings of the First Annual Conference on Computer and Communications Security, ACM, 1993; and Bellare and Rogaway, Optimal Asymmetric Encryption, Advances in Cryptology—Eurocrypt 94 Proceedings, Lecture Notes in Computer Science Vol. 950, A. De Santis ed., Springer-Verlag, 1994.
When a signature scheme is proven secure, the security proof demonstrates how to transform an attack on the signature scheme into an attack on the underlying mathematical primitive. For example, in a scheme based on factoring numbers, the proof would show how to turn a forging algorithm against the signature scheme into a factoring algorithm. The efficiency of this “reduction” quantifies the demonstrated security. A signature scheme is said to have “tight” demonstrated security if it has been proven secure by a highly efficient reduction. Tight demonstrated security is desirable because for such a scheme the security parameter (e.g., length of RSA modulus) which is deemed adequate for the mathematical primitive is necessarily adequate for the signature scheme, too.
None of the prior art has taught a signature scheme with tight demonstrated security based on a simple construction. There remains a need in the art to provide new signature schemes that fall in the hash-then-decrypt paradigm, so that they are easy to implement, yet are simple, efficient, and practical, and, above all, have attractive security properties like tight demonstrated security. The present invention addresses this need.
BRIEF SUMMARY OF THE INVENTION
An object of the present invention is to provide new signature schemes that are as simple and efficient as standardized ones. Assuming the underlying hash function is ideal, the inventive methods are not only provably secure, but provably secure in a strong sense. In one embodiment involving RSA, signing takes one RSA decryption plus some hashing, verification takes one RSA encryption plus some hashing, and the size of the signature is the size of the modulus. The security of the inventive scheme in this embodiment is tightly related to the security of the RSA function.
The inventive teachings are also extended to provide schemes for Rabin signatures with analogous properties; in particular, their security can be tightly related to the hardness of factoring.
It is known to hash a message M onto the full domain Z
N
* of the RSA function before decrypting. The signature of M i

Affiliated with

Also associated with

Rating

Probabilistic 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 Probabilistic signature scheme, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Probabilistic signature scheme will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-2479535