Cryptography – Key management – Having particular key generator
Patent
1997-09-25
2000-08-29
Swann, Tod R.
Cryptography
Key management
Having particular key generator
380 28, 380 45, 380259, 380285, H04L 900
Patent
active
061119520
DESCRIPTION:
BRIEF SUMMARY
BACKGROUND OF THE INVENTION
Field of the Invention
The invention relates to an asymmetric cryptographic communication process for processing messages and protecting communications between interlocutors. It can be used to encrypt messages in an asymmetric way, or to sign them in an equally asymmetric way. It can also be used in asymmetric authentication.
SUMMARY OF THE INVENTION
This process uses two novel families of algorithms that are called "Dragon" and "Chains". These two families can also be combined.
What makes these new algorithms particularly advantageous is that some of them are: encryption functions; example).
These "Dragon" and "Chains" algorithms can be seen as a subtle and effective "fix" of an algorithm invented in 1988 by MATSUMOTO and IMAI (Tsutomu Matsumoto and Hideki Imai, "Public quadratic polynomial-tuples for efficient signature-verification and message-encryption", Advances In Cryptology, Eurocrypt '88 (Christoph G. Gunther, ed.), Lecture Notes in Computer Science, Vol. 330, Springer-Verlag, 1988, pp. 419-453). This algorithm was cracked in 1995 by Jacques PATARIN (the attack was published at the CRYPTO '95 congress, Springer-Verlag, pp. 248-261).
For this reason, the invention relates to an asymmetric cryptographic communication process which establishes a correspondence between a first value (x) represented by n elements (x.sub.1, . . . , x.sub.n) of a ring (A) and a second value (y) represented by m elements (y.sub.1, . . . , y.sub.m) of this ring, n and m being integers greater than or equal to 2, characterized in that: (P.sub.i) of A.sup.n+m+k .fwdarw.A, with a low total degree, such that there are equations of the type (P.sub.i (x.sub.1,. . . , x.sub.n ; y.sub.1, . . . , y.sub.m ; z.sub.1, . . . , z.sub.k)=0 where (z.sub.1, . . . z.sub.k) are possible intermediate variables and k is an integer; T.sub.i (y.sub.1, . . . , y.sub.m)=S.sub.i (x.sub.1, . . . , x.sub.n), where the S.sub.i s would be polynomials with a total degree of 2 and the T.sub.i s would be polynomials with a total degree of 1.
The invention also relates to an associated portable object, specifically a portable object which does not store the multivariable public polynomials (P.sub.i).
The concept of a "value x" to be transformed according to the process of the invention designates, as appropriate, either a message (for example when the process is used in encryption) or more generally a magnitude from which a verification is intended to be executed (for example when the process is used in signature verification or authentication).
The concept of "low degree" mentioned below must be understood to designate a degree less than or equal to 6, preferably less than or equal to 4, but at the same time greater than or equal to 2.
BRIEF DESCRIPTION OF THE DRAWINGS
Other details and advantages of the invention will become apparent from the following description of certain preferred but non-limiting embodiments with reference to the appended drawings, in which:
FIG. 1 is a diagram illustrating the concatenation of the transformations used to process a message, according to a first variant of the process of the invention, used in encryption; and
FIG. 2 illustrates an exemplary encryption/decryption system using the cryptographic communication process according to the invention.
DETAILED DESCRIPTION OF THE PREFERRED EMBODIMENTS
The name "Dragons" has been given to a first family of algorithms based on the invention. The basic concept that distinguishes the two families of algorithms "Dragon" and "Matsumoto-Imai" will now be presented. Then, in the subsequent paragraphs, certain particularly advantageous examples of "Dragons" will be shown. Finally, another family of algorithms based on the invention, which are called "Chains", will be described.
The public form exists in the form of n multivariable polynomials in a finite field K, giving an image value y constituted by a plurality of elementary image values y.sub.1, . . . , y.sub.n as a function of a value x constituted by a plurality of elementary values x.sub.1,
REFERENCES:
patent: 5263085 (1993-11-01), Shamir
patent: 5375170 (1994-12-01), Shamir
patent: 5740250 (1998-04-01), Moh
patent: 5790675 (1998-08-01), Patarin
Advances In Cryptology--Eurocrypt '88. Workshop On The Theory And Application Of Cryptographic Techniques. Proceedings, Davos, Switzerland, May 25-27, 1988, ISBN 3-540-50251-3. 1988, Berlin, West Germany, Springer-Verlag, West Germany, pp. 419-453, XP000568374 Matsumoto T Et Al: "Public quadratic polynomial-tuples for efficient signature-verification and message-encryption" cited in the application, see p. 419, line 1-p. 423, line 12.
Advances In Cryptology--Crypto '95. 15th Annual International Cryptology Conference. Proceedings, Proceedings of Crypto '95: 15th Annual Crypto Conference Santa Barbara, CA, USA, Aug. 27-31, 1995, ISBN 3-540-60221-6 1995, Berlin, Germany, Springer-Verlag, Germany, pp. 248-261, XPOOO605562, Patarin J: "Cryptanalysis Of The Matsumoto And Imai Public Key Scheme Of Eurocrypt '88" cited in the application, see p. 248, line 1-p. 250, last line.
Bull CP8
Callahan Paul E.
Kondracki Edward J.
Swann Tod R.
LandOfFree
Asymmetrical cryptographic communication method and portable obj does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Asymmetrical cryptographic communication method and portable obj, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Asymmetrical cryptographic communication method and portable obj will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-1256821