Method and apparatus for encrypting, decrypting, and providing privacy for data values

• US 6,049,613 A
• Filed: 01/13/1998
• Issued: 04/11/2000
• Est. Priority Date: 03/07/1997
• Status: Expired due to Fees

• Current Assignee: Markus Jakobsson
• Original Assignee: Markus Jakobsson
• Inventors: Jakobsson, Markus
• Primary Examiner(s): Swann, Tod R.
• Assistant Examiner(s): Darrow, Justin T.
• Application Number:
  US09/005,920
• Time in Patent Office: 819 Days
• Field of Search: 380/28, 380/21, 380/44, 380/47, 380/279, 708/174, 708/210, 712/7, 713/155
• US Class Current: 380/47
• CPC Class Codes: H04L 2209/04 Masking or blinding
• CPC Class Codes: H04L 9/06 the encryption apparatus using shift registers or memories for block-wise or stream coding, e.g. DES systems or RC4; Hash functions; Pseudorandom sequence generators

Abstract

A mix network with superior privacy and robustness is provided. An apparatus comprising a duplicator and first and second operation modules is disclosed. The first and second operation modules are each comprised of first and second processors. Each processor is comprised of a partial operation device. The duplicator preferably duplicates a vector of encrypted inputs, and provides first and second substantially similar duplicated vectors, to the first and second operation modules, respectively. The partial operation device of the first processor of the first operation module partially operates on the first duplicated vector, then supplies the result to the partial operation device of the second processor of the first operation module which partially operates on it to provide a fully operated on first duplicated vector. Likewise, the partial operation device of the first processor of the second operation module partially operates on the second duplicated vector, then supplies the result to the partial operation device of the second processor of the second operation module which partially operates on the partially operates on the second duplicated vector to provide a fully operated on first duplicated vector. A means for comparing compares the fully operated on first duplicated vector with the fully operated on second duplicated vector.

Claims

1. An apparatus comprising:

a duplicator for duplicating a first vector of encrypted inputs;

a first operation module comprised of a first and a second processor, the first and second processors of the first operation module each comprised of a partial operation device;

a second operation module comprised of a first and a second processor, the first and second processors of the second operation module each comprised of a partial operation device;

wherein the duplicator duplicates the first vector of encrypted inputs to provide first and second duplicated vectors,

wherein the first duplicated vector is supplied to and operated on by the first operation module by supplying the first duplicated vector to the first processor of the first operation module whose partial operation device partially operates on the first duplicated vector, and then by supplying the partially operated on first duplicated vector to the second processor of the first operation module whose partial operation device partially operates on the already partially operated on first duplicated vector to form a fully operated on first duplicated vector;

wherein the second duplicated vector is supplied to and operated on by the second operation module by supplying the second duplicated vector to the first processor of the second operation module whose partial operation device partially operates on the first duplicated vector, and then by supplying the partially operated on first duplicated vector to the second processor of the second operation module whose partial operation device partially operates on the already partially operated on second duplicated vector to form a fully operated on second duplicated vector;

wherein the apparatus is further comprised of a means for comparing which compares the fully operated on first duplicated vector with the fully operated on second duplicated vector;

and wherein the first vector, the first and second duplicated vectors, the partially operated on first and second duplicated vectors, and the fully operated on first and second duplicated vectors each are comprised of one or more data values on one or more data lines.

2. The apparatus of claim 1 and further comprising:

a plurality of further operation modules each comprised of a plurality of further processors, the plurality of further processors each comprised of a partial operation device;

wherein the duplicator duplicates the vector of encrypted inputs to provide a plurality of further substantially similar duplicated vectors to the plurality of further operation modules;

wherein each of the plurality of further duplicated vectors is supplied to and operated on by one of the plurality of further operation modules;

wherein each of the plurality of further duplicated vectors is supplied to and operated on by one of the plurality of further operation modules by supplying each of the plurality of further duplicated vectors to a chain of the plurality of processors and their corresponding partial operation devices within a respective operation module, to form a plurality of further fully operated on duplicated vectors;

the means for comparing compares the plurality of further fully operated on duplicated vectors with one another

and wherein the plurality of further substantially similar duplicated vectors, and the plurality of further fully operated on duplicated vectors are each comprised of one or more data values on one or more data lines.

3. The apparatus of claim 1 wherein:

the first and second operation modules are decryption modules; and

the partial operation devices are partial decryption devices.

4. The apparatus of claim 2 wherein:

the first, second, and plurality of further operation modules are decryption modules; and

the partial operation devices are partial decryption devices.

5. The apparatus of claim 1 wherein:

the first and second operation modules are encryption modules; and

the partial operation devices are partial encryption devices.

6. The apparatus of claim 2 wherein:

the first, second, and plurality of further operation modules are encryption modules; and

the partial operation devices are partial encryption devices.

7. The apparatus of claim 1 wherein:

the first and second operation modules are re-encryption modules; and

the partial operation devices are partial re-encryption devices.

8. The apparatus of claim 2 wherein:

the first, second, and plurality of further operation modules are re-encryption modules; and

the partial operation devices are partial re-encryption devices.

9. The apparatus of claim 1 wherein:

the first and second operation modules are permutation modules; and

the partial operation devices are permutation devices.

10. The apparatus of claim 2 wherein:

the first, second, and plurality of further operation modules are permutation modules; and

the partial operation devices are partial permutation devices.

11. The apparatus of claim 1 further comprising:

a first blinding layer comprised of a first blinding section which receives a pre-first encrypted vector of inputs, performs a blinding operation on the pre-first vector of inputs and outputs the first vector of encrypted inputs to the duplicator;

and wherein the pre-first encrypted vector of inputs is comprised of one or more data values on one or more data lines.

12. The apparatus of claim 11 wherein:

the first blinding section of the first blinding layer permutes and re-encrypts the pre-first encrypted vector of inputs.

13. The apparatus of claim 11 further comprising:

a first unblinding layer comprised of a first unblinding section which performs an unblinding operation on the fully operated on first and second duplicated vectors.

14. The apparatus of claim 13 and wherein:

the first unblinding section of the first unblinding layer performs the unblinding operation only if the means for comparing has determined that the first and second fully operated on duplicated vectors are the same.

15. The apparatus of claim 11 further comprising:

a second blinding layer comprised of first and second blinding sections;

wherein the first duplicated vector is supplied to the first blinding section of the second blinding layer;

the second duplicated vector is supplied to the second blinding section of the second blinding layer;

and the first and second blinding sections of the second blinding layer each perform a blinding operation on the first and second duplicated vectors respectively and then output the result to the first and second operation modules, respectively,

and wherein supplying the first and second duplicated vectors to the first and second operation modules, respectively is defined as supplying first and second duplicated vectors which have been first blinded by the first and second blinding sections of the second blinding layer, respectively, to the first and second operation modules.

16. The apparatus of claim 15 further comprising:

a second unblinding layer comprised of first and second unblinding sections;

wherein the first and second unblinding sections perform unblinding operations on the fully operated on first and second duplicated vectors, respectively.

17. The apparatus of claim 1 wherein:

the means for comparing includes first and second sorting sections which sort the first and second fully operated on duplicated vectors respectively, so that they can be compared.