Cryptography – Communication system using cryptography – Data stream/substitution enciphering
Reexamination Certificate
2000-09-14
2002-08-20
Barron, Gilberto (Department: 2132)
Cryptography
Communication system using cryptography
Data stream/substitution enciphering
C380S028000, C380S043000, C380S046000
Reexamination Certificate
active
06438230
ABSTRACT:
The present invention relates to encryption or other data mapping and in particular to mappings from discrete characters to value ranges preferably permitting multiple parties to contribute to the encryption.
BACKGROUND INFORMATION
A number of data mapping or encryption systems involve mapping discrete characters or “tokens” from a character set onto a second plurality of characters. A simple example (and one which is relatively insecure) is a one-to-one cipher in which a set of characters, such as the letters of the English alphabet are mapped onto the same set of characters (i.e. mapped onto the characters of the English alphabet, in a “jumbled” order). A related (but still insecure) example is the one-to-one mapping of a character set onto a different character set (such as the mapping of characters of the English alphabet onto the well known ASCII codes for each letter. These simple examples have the advantage that the encryption and decryption are computationally non-demanding. Unfortunately, it is relatively easy for non-authorized persons to decrypt or “break” these types of encryptions or mappings.
As is well known to those of skill in the art, many more sophisticated types of encryption have been developed. All too often, techniques of code breaking have kept pace with developments in the encryption field. Many code breaking techniques depend on recognizing certain characteristics of the original text or language which may remain relatively invariant under the encryption processes. For example, in the simple examples described above, the frequency of occurrence of any given letter of the English alphabet in an English text (of sufficient length) is invariant after the one-to-one mappings described above. Thus, a sufficiently long cyphertext produced by the one-to-one techniques described above, might be broken by assuming the most-frequently-appearing character in the cyphertext corresponds to the letter which occurs most frequently in typical English language texts (i.e. the letter “e”), the second-most-frequent character in the cyphertext corresponds to the second most frequently used character in the English language, and so forth. Other relatively invariant language characteristics (such as relative frequency of word lengths, and the like), can similarly be of assistance to a would-be code-breaker.
Accordingly, it would be useful to provide encryption scheme which avoids the inclusion of information in the cyphertext which may assist in code-breaking. In particular, it would be useful to provide an encryption system which is not a one-to-one mapping.
As various encryption schemes have been developed, the encryption processes have often become relatively complex, to the point that many modem encryption and decryption processes are impractical without the use of computers. Even using computers, some encryption schemes can become so complex that encryption or decryption processes consume a perceptible, and in some cases unacceptable, delay in communications. Accordingly, it would be useful to provide an encryption scheme which achieves a desirable level of security but which is computationally relatively rapid.
Although the simple examples above were described in the context of a two-party transaction, there are situations in which a communication or transaction preferably involves three or more parties. For example, when it is desired to transfer funds from bank A to bank B, it may be desirable for the receiving bank B to have assurance in the validity of a transfer message, preferably from a third party such as a Federal Reserve Branch and/or a fourth party such as a parent bank of the originating “branch” bank. Accordingly, it would be useful to provide a system for encrypting a message in which two or more different parties participate in the encryption scheme, preferably such that some or all verifying entities cannot, by themselves, decrypt the resulting cyphertext.
SUMMARY OF THE INVENTION
The present invention involves a one-to-many mapping of a character set and/or an encryption scheme in which multiple parties can participate. As used herein, a “character” or “token” can be any unit which is to be encrypted including English or foreign letters, words, numbers, punctuation marks, symbols and the like.
In one aspect of the invention, a portion of the real number line is partitioned into a plurality of disjoint intervals and each character is mapped to a point in one (or more) of the intervals. One advantage to the mapping of a given unique-character to two or more intervals is that even if the significance of one of the intervals is ascertained by a would-be code-breaker, this will provide the code-breaker only with the plaintext characters which were mapped onto that interval and other instances of the same unique character, mapped onto other intervals, will not be determinable from a knowledge of the significance of the interval.
When a plaintext is encrypted, for each character of the plaintext, one of the intervals (if there is more than one) to which that character is mapped is selected (preferably randomly) and a real number which lies within that interval is selected (preferably randomly) for use as the encrypted form of that character. Thus, using this type and level of encryption, an English text would be represented by a series of real numbers. To decrypt such a series of real numbers and recover the original plaintext, the decrypting party can use information about the mapping of the characters to the intervals. Thus, for each real number in the cyphertext, the decrypting party will determine within which interval the real number lies. The decrypting party will then determine which character is mapped to that interval and will thus be able to recover the character of the plaintext corresponding to that real number of the cyphertext. Thus, even though a given letter may occur numerous times in the original plaintext, most, or preferably all, occurrences of that letter will be represented by different real numbers in the cyphertext. By judicious selection of the intervals and mappings (e.g. as described below), the resulting cyphertext can be made to resemble a plurality of numbers which are randomly distributed across a portion of the real number line, and thus the cyphertext can be substantially devoid of letter-frequency information or similar information sometimes used in code-breaking. Once a text is in the form of a series or plurality of real numbers, it is possible to perform additional mappings on the real numbers. Preferably, each such additional mapping is a one-to-one mapping, such as by application of a function which is monotonic at least over the portion of the real number line where the values of the text or cyphertext lie. It is possible to provide several levels of encryption in this fashion so that the final (communicated) cyphertext is the product of two or more functions. In this aspect of the invention, in order for the decrypter to recover the original plaintext, the decrypter will use not only the one-to-many mapping but also the transformation function or functions (or composites thereof). Preferably, although the parties may have agreed that one or more transformation functions are to be used, e.g. to indicate third party verification, as described more thoroughly below), no single party (other than the authorized sending and receiving parties) can use knowledge of a single transformation function (or fewer than all transformation functions) to recover the plaintext (or, preferably, even any substantial portion of the plaintext). In this way, several parties may contribute to the encryption process (e.g. to indicate their verification or authorization of the message) without any of the third parties (who are verifying the message) having sufficient information to decrypt the cyphertext.
Preferably, the functions, which need only be, e.g., monotone (over an interval) real number functions, are selected which are relatively rapid to compute, such as polynomial functions.
REFERENCES:
patent: 5193115 (1993-03-01), Vobach
pate
Barron Gilberto
Coinstar Inc.
Darrow Justin T.
Perkins Coie LLP
LandOfFree
Data mapping method and apparatus with multi-party capability does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Data mapping method and apparatus with multi-party capability, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Data mapping method and apparatus with multi-party capability will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2945684