Electrical computers and digital processing systems: support – Multiple computer communication using cryptography – Particular communication authentication technique
Reexamination Certificate
1999-08-02
2003-07-22
Peeso, Thomas R. (Department: 2132)
Electrical computers and digital processing systems: support
Multiple computer communication using cryptography
Particular communication authentication technique
C713S152000, C713S152000, C713S152000
Reexamination Certificate
active
06598163
ABSTRACT:
FIELD OF THE INVENTION
This invention relates to improved methods and apparatus for mix networks.
BACKGROUND OF THE INVENTION
In a mix-network, a list of encrypted inputs is iteratively permuted and re-encrypted (or blinded, or decrypted, depending on the specific implementation) by a set of cooperating mix servers. As long as at least one of these servers is honest, the privacy of the output is guaranteed in that it is infeasible for cheaters to match items of the final mix network output list to items of the initial mix network input list with a probability non-negligibly exceeding that of guessing uniformly at random.
Early mix networks were not “robust” meaning that one or more mix servers could corrupt the computation causing an incorrect final mix network output list without this being noticed. Various mix networks have been proposed that have greater “robustness” but these entail a high amount of computation. All mix networks to date require each mix server to know a portion of the secret key corresponding to the public key used for the initial encryption.
The applicant's previous mix network has a cost per input item (of the initial input encrypted list) and per active mix server of about eighty exponentiations, each one of which costs about 200 multiplications for an exponent size of 160, bits using standard window based exponentiation techniques. Although this amount of computation may be favorable compared to other mix networks there is a need for greater efficiency, along with robustness and privacy.
SUMMARY OF THE INVENTION
The present invention provides an efficient mix network in one embodiment in which an initial list of encrypted inputs is duplicated to provide a plurality of list copies. Each list copy is then subjected to a chain of re-encryptions performed by a plurality of mix servers. There are a plurality of chains, one for each input list copy. The final output lists of each chain of re-encryptions is sorted so that the output lists can be compared with one another. If the outputs are the same (after sorting) then further computations can be conducted. If not then one of the mix servers has cheated.
Sorting can be performed by the use of tag lists. Each item of each input list can have a tag associated with it. The same tag is associated to corresponding items of each input list copy. Each tag, or a modification of each tag, remains attached to the same item (or a modification of the same item) even after the items have been modified by permutations and re-encryptions. Each item of each final output list has associated with it a tag of an output tag list. The final output lists, for the first input copy, second input copy, etc., each have the same output tag list associated with them with the exception that the tags are in different orders. The final output lists can be sorted with respect to the tag values.
The final sorted output lists of the first chain and the second chain can be compared by applying to the sorted second chain output list the difference between re-encryptions applied for the second chain and re-encryptions applied for the first chain of re-encryptions. These re-encryption differences can be determined from a plurality re-encryption differences received from plurality of mix servers. The final sorted output lists of the first chain and other chains can be compared in similar manners.
The mix network of an embodiment of the present invention provides a robust technique, meaning that cheating mix servers can easily be detected. It also provides for privacy, in that the items of the final output list cannot be related back to items of the initial encrypted list by any of the mix servers assuming at least one mix server is honest. The amount of computation required in the mix network of an embodiment of the present invention is drastically less than prior art mix networks. In addition, there is no need to know the secret keys corresponding to the public key under which encryption is done.
The present invention in one embodiment takes a list of ciphertexts and produces a permuted list of ciphertexts, so that the output list corresponds to the same plaintext values as the input ciphertext list element does, but in a different and random order. This could be used for voting schemes where votes need to be “mixed” so that it is not possible to determine who voted what.
REFERENCES:
patent: 4757533 (1988-07-01), Allen et al.
patent: 4965568 (1990-10-01), Atalla et al.
patent: 5485519 (1996-01-01), Weiss
Prior Art—“Addition Chain Heuristics”, Jurjen Bos et al, pp. 400-407, The Netherlands.
Lucent Technologies - Inc.
Peeso Thomas R.
LandOfFree
Flash mixing apparatus and 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 Flash mixing apparatus and method, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Flash mixing apparatus and method will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3032058