Cryptography – Particular algorithmic function encoding – Public key
Reexamination Certificate
2000-04-05
2001-10-02
Swann, Tod (Department: 2132)
Cryptography
Particular algorithmic function encoding
Public key
C380S028000, C380S283000
Reexamination Certificate
active
06298137
ABSTRACT:
FIELD OF THE INVENTION
This invention relates to encoding and decoding of information and, more particularly, to a public key cryptosystem for encryption and decryption of digital messages by processor systems.
BACKGROUND OF THE INVENTION
Secure exchange of data between two parties, for example, between two computers, requires encryption. There are two general methods of encryption in use today, private key encryption and public key encryption. In private key encryption, the two parties privately exchange the keys to be used for encoding and decoding. A widely used example of a private key cryptosystem is DES, the Data Encryption Standard. Such systems can be very fast and very secure, but they suffer the disadvantage that the two parties must exchange their keys privately.
A public key cryptosystem is one in which each party can publish their encoding process without compromising the security of the decoding process. The encoding process is popularly called a trap-door function. Public key cryptosystems, although generally slower than private key cryptosystems, are used for transmitting small amounts of data, such as credit card numbers, and also to transmit a private key which is then used for private key encoding.
Heretofore a variety of trap-door functions have been proposed and implemented for public key cryptosystems.
One type of trap-door function which has been used to create public key cryptosystems involves exponentiation in a group; that is, taking an element of a group and repeatedly multiplying the element by itself using the group operation. The group most often chosen is the multiplicative group modulo pq for large prime numbers p and q, although other groups such as elliptic curves, abelian varieties, and even non-commutative matrix groups, have been described. However, this type of trap-door function requires large prime numbers, on the order of 100 digits each, making key creation cumbersome; and the exponentiation process used for encoding and decoding is computationally intensive, requiring many multiplications of hundred digit numbers and on the order of N
3
operations to encode or decode a message consisting of N bits.
A second type of trap-door function which has been used to create public key cryptosystems is based on the difficulty of determining which numbers are squares in a group, usually the multiplicative group modulo pq for large primes p and q. Just as in the first type, key creation is cumbersome and encoding and decoding are computationally intensive, requiring on the order of N
3
operations to encode or decode a message consisting of N bits.
A third type of trap-door function involves the discrete logarithm problem in a group, generally the multiplicative group or an elliptic curve modulo a large prime p. Again, key creation is cumbersome, since the prime p needs at least 150 digits and p−1 must have a large prime factor; and such systems use exponentiation, so again require on the order of N
3
operations to encode or decode a message consisting of N bits.
A fourth type of trap-door function which has been used to create public key cryptosystems is based on the knapsack, or subset sum, problem. These functions use a semigroup, normally the semigroup of positive integers under addition. Many public key cryptosystems of this type have been broken using lattice reduction techniques, so they are no longer considered secure systems.
A fifth type of trap-door function which has been used to create public key cryptosystems is based on error correcting codes, especially Goppa codes. These cryptosystems use linear algebra over a finite field, generally the field with two elements. There are linear algebra attacks on these cryptosystems, so the key for a secure cryptosystem is a large rectangular matrix, on the order of 400,000 bits. This is too large for most applications.
A sixth type of trap-door function which has been used to create public key cryptosystems is based on the difficulty of finding extremely short basis vectors in a lattice of large dimension N. The keys for such a system have length on the order of N
2
bits, which is too large for many applications. In addition, these lattice reduction public key cryptosystems are very new, so their security has not yet been fully analyzed.
Most users, therefore, would find it desirable to have a public key cryptosystem which combines relatively short, easily created keys with relatively high speed encoding and decoding processes.
It is among the objects of the invention to provide a public key encryption system for which keys are relatively short and easily created and for which the encoding and decoding processes can be performed rapidly. It is also among the objects hereof to provide a public key encryption system which has relatively low memory requirements and which depends on a variety of parameters that permit substantial flexibility in balancing security level, key length, encoding and decoding speed, memory requirements, and bandwidth.
SUMMARY OF THE INVENTION
The invention allows keys to be chosen essentially at random from a large set of vectors, with key lengths comparable to the key lengths in other common public key cryptosystems, and features an appropriate (e.g. ≈2
80
for current circumstances) security level, and provides encoding and decoding processes which are between one and two orders of magnitude faster than the most widely used public key cryptosystem, namely the exponentiation cryptosystem referenced above.
The encoding technique of an embodiment of the public key cryptosystem hereof uses a mixing system based on polynomial algebra and reduction modulo two numbers, p and q, while the decoding technique uses an unmixing system whose validity depends on elementary probability theory. The security of the public key cryptosystem hereof comes from the interaction of the polynomial mixing system with the independence of reduction modulo p and q. Security also relies on the experimentally observed fact that for most lattices, it is very difficult to find the shortest vector if there are a large number of vectors which are only moderately longer than the shortest vector.
An embodiment of the invention is in the form of a method for encoding and decoding a digital message m, comprising the following steps: selecting ideals p and q of a ring R; generating elements f and g of the ring R, and generating element F
q
which is an inverse of f (mod q), and generating element F
p
which is an inverse of f (mod p); producing a public key that includes h, where h is congruent, mod q, to a product that can be derived using g and F
q
; producing a private key from which f and F
p
can be derived; producing an encoded message e by encoding the message m using the public key and a random element ø; and producing a decoded message by decoding the encoded message e using the private key.
Further features and advantages of the invention will become more readily apparent from the following detailed description when taken in conjunction with the accompanying drawings.
REFERENCES:
patent: 4218582 (1980-08-01), Hellman et al.
patent: 4405829 (1983-09-01), Rivest et al.
patent: 4633036 (1986-12-01), Hellman et al.
patent: 4995082 (1991-02-01), Schnorr
patent: 5054066 (1991-10-01), Riek et al.
patent: 5231668 (1993-07-01), Kravitz
patent: 5276737 (1994-01-01), Micali
patent: 5299262 (1994-03-01), Brickell et al.
patent: 5351297 (1994-09-01), Miyaji et al.
patent: 5375170 (1994-12-01), Shamir
patent: 5577124 (1996-11-01), Anshel et al.
patent: 5600725 (1997-02-01), Rueppel et al.
patent: 5625692 (1997-04-01), Herzberg et al.
patent: 5696827 (1997-12-01), Brands
patent: 5790675 (1998-08-01), Patarin
patent: 5799088 (1998-08-01), Raike
patent: 5805703 (1998-09-01), Crandal
patent: 95/04417 (1995-02-01), None
Blum, M., Goldwasser, S., “An efficient Probabilistic Public-Key Encryption Scheme Which Hides all Partial Information,” Advances in Cryptology: Proceedings of CRYPTO 84, Lecture Notes in Computer Science, vol. 196, Springer-Verlag, 1985, pp. 289-299.
Coppersmith, D., Shamir, A., “Lattice
Hoffstein Jeffrey
Pipher Jill
Silverman Joseph H.
Darrow Justin T.
Novack Martin
NTRU Cryptosystems, Inc.
Swann Tod
LandOfFree
Ring-based public key cryptosystem method does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Ring-based public key cryptosystem method, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Ring-based public key cryptosystem method will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2593454