Cryptography – Particular algorithmic function encoding
Patent
1996-08-09
1998-04-14
Cain, David C.
Cryptography
Particular algorithmic function encoding
380 30, H04K 100
Patent
active
057402507
ABSTRACT:
The present invention relates to a tame automorphism based encryption system or scheme. Let K be a finite field of 2.sup.m elements. Let .o slashed..sub.4,.o slashed..sub.3,.o slashed..sub.2, .o slashed..sub.1 be Let the composition be .pi.=.o slashed..sub.4 .o slashed..sub.3 .o slashed..sub.2 .o slashed..sub.1. The automorphism .pi. and the factorization .pi.=.o slashed..sub.4 .o slashed..sub.3 .o slashed..sub.2 .o slashed..sub.1 are hidden. Let .pi.=(.pi..sub.1 (x.sub.1, . . . ,x.sub.n+r), . . . , .pi..sub.n+r (x.sub.1, . . . , x.sub.n+r)). The field K and the polynomials (f.sub.1, . . . , f.sub.n+r)=(.pi..sub.1 (x.sub.1, . . . ,x.sub.n, 0, . . . ,0), . . . ,.pi..sub.n+r (x.sub.1, . . . ,x.sub.n,0, . . . ,0)) will be announced publicly. Let (x'.sub.1, . . . ,x'.sub.n) be the plaintext. Then the cyphertext will be (y'.sub.1, . . . ,y'.sub.n+r)=(f.sub.1 (x'.sub.1, . . . ,x'.sub.n), . . . , f.sub.n+r (x'.sub.1, . . . ,x'.sub.n)). It is easy to find .o slashed..sub.i.sup.-1 ((y'.sub.1, . . . , y'.sub.n+r)) (see Corollary 2). Therefore, it is easy to recover the plaintext (x'.sub.1, . . . ,x'.sub.n)=.o slashed..sub.1.sup.-1 .o slashed..sub.2.sup.-1 .o slashed..sub.3.sup.-1 .o slashed..sub.4.sup.-1 .pi.((.pi..sub.1, . . . ,x'.sub.n)). However without knowing the automorphism .pi. precisely and the decomposition .pi.=.o slashed..sub.4 .o slashed..sub.3 .o slashed..sub.2 .o slashed..sub.1, it is very hard to find plaintext (x'.sub.1, . . . ,x'.sub.n). The encryption system or scheme may be applied to electronic message transmission, data storage, smart card security, and product verification applications.
REFERENCES:
patent: 4875207 (1989-10-01), Van Twist et al.
patent: 5377207 (1994-12-01), Perlman
International Search Report corresponding to PCT/US96/19708.
Abhyankar, S.S. and Moh, T.T. "Embeddings of the line in the plane. Journal fur die rein und angewandte Mathematik", pp. 148-166, vol. 27 (1975).
Bajaj, C. Garrity, T. Warren, J. On the Application of Multi-Equational Resultants. Purdue University, Department of C.S. Technical Report CSD-TR-826, 1988.
Hopcroft, J.E., Ullman, Jeffrey D. "Formal Languages and Their Relation to Automata, Motivation", pp. 8-9, Addison-Wesley Publishing Co.
Berlekamp, E.R., "Factoring polynomials over fine fields. Bell System Tech. J". pp. 1853-1859, vol. 46, 1967.
Brandstrom, H. "A public-key cryptosystem based upon equations over a finite field. Cryptologia", pp. 347-358, vol. 7, 1983.
Brent, R., and Kung, H. "Fast Algorithms for Manipulating Formal Power Series. Journal of ACM", pp. 581-595, vol. 25, No. 4, 1978.
Cohen, Henri "A Course in Computational Algebraic Number Theory. Springer-Verlag". Berlin, 1993.
Canny, John F. "Complexity of robot Motion Planning" The MIT Press, Cambridge, Massachusetts, 1988.
Dickerson, Mathew "The inverse of an Automorphism in Polynomial Time. J. Symbolic Computation", vol. 13. 209-220, 1992.
Lidl, R. "Finite fields". Addison-Wesley, Reading, Massachusetts, 1983.
Lidl, R. "On Cryptosystems Based on Polynomials and Finite Fields." Advances in Cryptology (Proceedings of Eurocrypt 84), pp. 10-15, 1983.
Moh, T.T. "On the Classification Problem of Embedded Lines in Characteristic p. Algebraic Geometry and Commutative Algebra in honor of M. Nagata", vol. 1, pp. 267-280, Kinokuniya, Kyoto, Japan, 1988. Tokyo, Japan, 1972.
Niederreiter, H. "New Deterministic Factorization Algorithm for Polynomials over Finite Fields." Contemporary Mathematics (Finite Fields) (AMS), vol. 168, 1993.
Rivest, R.L. Shamir, A., and Adleman, L.M."A Method for Obtaining Digital Signatures and Public Key Cryptosystems". Communications of the ACM 21(2), 120-126, Feb. 1978.
Van Der Kulk, W. "On polynomial rings in two variables," Nieuw Archief voor Wiskunde. vol. 3, I(1953).
Bresinsky, H., "On Prime Ideals with Generic Zerio x.sub.i = t.sup.n i", American Mathematical Society, vol. 47, No. 2, Feb., 1975.
LandOfFree
Tame automorphism public key system does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Tame automorphism public key system, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Tame automorphism public key system will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-644226