A highly efficient mix network for small numbers of inputs is provided.
Four data messages would be a typical number of inputs. The structure of
sorting/permutation networks is used to permute the input. This is done in
a way that changes the position of pairs of items. A mix network is
provided which is highly efficient on small input batches and is robust
and private in the face of collusion by any minority set of mix servers.
Additionally, the mix network method and apparatus has the feature of
being publicly verifiable because the mixing method yields a transcript of
results that can demonstrate to a third party that the mix proceeded
correctly. An apparatus comprised of a plurality of mix servers is
provided. Each mix server includes a randomizer network. 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. 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. Each randomizer network is comprised of a plurality of
randomizers, wherein each randomizer receives first and second input data
messages and produces first and second output data messages, wherein the
first output data message is a re-encryption of either the first or the
second input data message and the second output data message is a
re-encryption of the other input data message. A bulletin board having
computer memory may be provided, to which each mix server produces proof
that each randomizer of each randomizer network has re-encrypted and
permuted in a proper manner.
Una red altamente eficiente de la mezcla para una pequeña cantidad de entradas se proporciona. Cuatro mensajes de datos serían un número típico de entradas. La estructura de las redes de sorting/permutation se utiliza para permutar la entrada. Esto se hace de una manera que cambie la posición de pares de artículos. Se proporciona una red de la mezcla que es altamente eficiente en las hornadas pequeñas de la entrada y es robusta y privada en la cara de la colusión por cualquier sistema de la minoría de servidores de la mezcla. Además, el método de la red de la mezcla y el aparato tiene la característica de ser público comprobables porque el método que se mezcla rinde una transcripción de los resultados que pueden demostrar a terceros que procedió la mezcla correctamente. Un aparato abarcado de una pluralidad de servidores de la mezcla se proporciona. Cada servidor de la mezcla incluye una red del randomizer. Cada red del randomizer recibe una pluralidad de mensajes de datos de entrada y realiza operaciones del re-cifrado y de la permutación en la pluralidad de mensajes de datos de entrada para formar una pluralidad de mensajes de datos de la salida. Las redes del randomizer de la pluralidad de servidores de la mezcla se arreglan en una cadena de modo que la primera red del randomizer del primer servidor de la mezcla en la cadena reciba su pluralidad de mensajes de datos de entrada y proporcione su pluralidad de mensajes de datos de la salida a la red siguiente del randomizer del servidor siguiente de la mezcla en la cadena. Cada red del randomizer se abarca de una pluralidad de randomizers, en donde cada randomizer recibe primero y los segundos mensajes de datos de entrada y produce primero y los segundos mensajes de datos de la salida, en donde el primer mensaje de datos de la salida es un re-cifrado de el primer o segundo mensaje de datos de entrada y el segundo mensaje de datos de la salida es un re-cifrado del otro mensaje de datos de entrada. Un tablón de anuncios que tiene memoria de computadora puede ser proporcionado, a la cual cada servidor de la mezcla produce la prueba que cada randomizer de cada red del randomizer re-ha cifrado y permutado de una manera apropiada.
