Mixing in small batches

An apparatus comprised of:

• a plurality of mix servers
• wherein each mix server includes a randomizer network;
• wherein each randomizer network receives a plurality of input data messages and performs decryption and permutation operations on the plurality of input data messages to form a plurality of output data messages, wherein each one of the plurality of output data messages is a decrypted version of one of the plurality of input data messages;
• wherein the randomizer networks of the plurality of mix servers are arranged in a chain so that the first randomizer network of the first mix server in the chain receives its plurality of input data messages and provides its plurality of output data messages to the next randomizer network of the following mix server in the chain;
• and wherein any further randomizer networks of any further mix servers in the chain receive their plurality of input data messages from a preceding randomizer network of a preceding mix server and provide their plurality of output data messages to a following randomizer network of the following mix server in the chain;
• and wherein each randomizer network is comprised of a plurality of randomizers including a first randomizer and a second randomizer, wherein each randomizer receives first and second input data messages and produces first and second output data messages, wherein the first randomizer of each randomizer network supplies at least one of its first and second output data messages to the second randomizer of each randomizer network, wherein each randomizer performs a random permutation operation such that the first output data message of each randomizer is a decryption of either the first or the second input data message of each randomizer and the second output data message of each randomizer is a decryption of the other input data message of each randomizer.

An apparatus comprised of:

• a first mix server;
• the first mix server including a first randomizer network;
• the first randomizer network comprised of first, second, third, fourth, and fifth randomizers, each randomizer having an input port comprised of two input lines and an output port comprised of two output lines;
• wherein the first randomizer network first randomizer:
• receives a first randomizer network first randomizer first input data message on its first input line and a first randomizer network first randomizer second input data message on its second input line;
• re-encrypts the first randomizer network first randomizer first input data message to form a first randomizer network first randomizer first re-encrypted data message and re-encrypts the first randomizer network first randomizer second input data message to form a first randomizer network first randomizer second re-encrypted data message;
• and performs a permutation by outputting the first randomizer network first randomizer first re-encrypted data message on either the first output line or the second output line of the first randomizer network first randomizer and by outputting the first randomizer network first randomizer second re-encrypted data message on the other output line;
• wherein the first randomizer network second randomizer:
• receives a first randomizer network second randomizer first input data message on its first input line and a first randomizer network second randomizer second input data message on its second input line;
• re-encrypts the first randomizer network second randomizer first input data message to form a first randomizer network second randomizer first re-encrypted data message and re-encrypts the first randomizer network second randomizer second input data message to form a first randomizer network second randomizer second re-encrypted data message;
• and performs a permutation by outputting the first randomizer network second randomizer first re-encrypted data message on either the first output line or the second output line of the first randomizer network second randomizer and by outputting the first randomizer network second randomizer second re-encrypted data message on the other output line;
• wherein the first randomizer network third randomizer:
• receives a first randomizer network third randomizer first input data message on its first input line and a first randomizer network third randomizer second input data message on its second input line, wherein the first randomizer network third randomizer first input data message is one of the first randomizer network first randomizer first or second re-encrypted data messages, and the first randomizer network third randomizer second input data message is one of the first randomizer network second randomizer first or second re-encrypted data messages;
• re-encrypts the first randomizer network third randomizer first input data message to form a first randomizer network third randomizer first re-encrypted data message and re-encrypts the first randomizer network third randomizer second input data message to form a first randomizer network third randomizer second re-encrypted data message;
• and performs a permutation by outputting the third randomizer first re-encrypted data message on either the first output line or the second output line of the first randomizer network third randomizer and by outputting the first randomizer network third randomizer second re-encrypted data message on the other output line;
• wherein the first randomizer network fourth randomizer:
• receives a first randomizer network fourth randomizer first input data message on its first input line and a first randomizer network fourth randomizer second input data message on its second input line, wherein the first randomizer network fourth randomizer first input data message is one of the first randomizer network first randomizer first or second re-encrypted data messages, and the first randomizer network fourth randomizer second input data message is one of the first randomizer network second randomizer first or second re-encrypted data messages;
• re-encrypts the first randomizer network fourth randomizer first input data message to form a first randomizer network fourth randomizer first re-encrypted data message and re-encrypts the first randomizer network fourth randomizer second input data message to form a first randomizer network fourth randomizer second re-encrypted data message;
• and wherein the first randomizer network fourth randomizer performs a permutation by outputting the first randomizer network fourth randomizer first re-encrypted data message on either the first output line or the second output line of the first randomizer network fourth randomizer and by outputting the first randomizer network fourth randomizer second re-encrypted data message on the other output line
• wherein the first randomizer network fifth randomizer:
• receives a first randomizer network fifth randomizer first input data message on its first input line and a first randomizer network fifth randomizer second input data message on its second input line, wherein the first randomizer network fifth randomizer first input data message is the first randomizer network third randomizer second re-encrypted data message, and the first randomizer network fifth randomizer second input data message is the first randomizer network fourth randomizer first re-encrypted data message;
• re-encrypts the first randomizer network fifth randomizer first input data message to form a first randomizer network fifth randomizer first re-encrypted data message and re-encrypts the first randomizer network fifth randomizer second input data message to form a first randomizer network fifth randomizer second re-encrypted data message;
• wherein the first randomizer network fifth randomizer performs a permutation by outputting the first randomizer network fifth randomizer first re-encrypted data message on either the first output line or the second output line of the first randomizer network fifth randomizer and by outputting the first randomizer network fifth randomizer second re-encrypted data message on the other output line;
• and
• wherein each permutation is random.

A method comprising the steps of:

• receiving at least four input data messages comprised of first, second, third, and fourth input data messages;
• providing a first randomizer network which
• subjects the first and second input data messages to a first permutation and first re-encryption operation to provide first and second output data messages
• subjects the third and fourth input data messages to a second permutation and a second re-encryption operation to provide third and fourth output data messages;
• subjects either the first or the second output data message to a third permutation and a third re-encryption operation to provide a first modified output data message;
• subjects either the first or the second output data message to a fourth permutation and a fourth re-encryption operation to provide a second modified output data message;
• subjects either the third or the fourth output data message to a third permutation and a third re-encryption operation to provide a third modified output data message;
• subjects either the third or the fourth output data message to a fourth permutation and a fourth re-encryption operation to provide a fourth modified output data message;
• subjects the second modified output data message to a fifth permutation and a fifth re-encryption operation to provide a second further modified output data message;
• and
• subjects the third modified output data message to a fifth permutation and a fifth re-encryption operation to provide a third further modified output data message;
• and
• wherein each of the first, second, third, fourth, and fifth permutations are random.

An apparatus comprised of:

• a plurality of mix servers
• wherein each mix server includes a randomizer network;
• wherein each randomizer network receives a plurality of input data messages and performs re-encryption and permutation operations on the plurality of input data messages to form a plurality of output data messages, wherein each one of the plurality of output data messages is a re-encrypted version of one of the plurality of input data messages;
• wherein the randomizer networks of the plurality of mix servers are arranged in a chain so that the first randomizer network of the first mix server in the chain receives its plurality of input data messages and provides its plurality of output data messages to the next randomizer network of the following mix server in the chain;
• and wherein any further randomizer networks of any further mix servers in the chain receive their plurality of input data messages from a preceding randomizer network of a preceding mix server and provide their plurality of output data messages to a following randomizer network of the following mix server in the chain;
• and wherein each randomizer network is comprised of a plurality of randomizers;
• and
• wherein each of the permutation operations are random.