Cryptographic Shuffles and Their Applications

Cited 0 time in Web of Science Cited 0 time in Scopus
자연과학대학 수리과학부
Issue Date
서울대학교 대학원
ShuffleVerifiable Secret ShufflePublic ShuffleMix-netEl-Gamal Encryption
학위논문 (박사)-- 서울대학교 대학원 : 수리과학부, 2012. 8. 천정희.
For anonymization purposes, one can use a mix-net.
A mix-net is a multi-party protocol to
shuffle elements so that neither of the parties knows the permutation linking the
input and output.
One way to construct
a mix-net is to let a set of mixers, so called mix-servers, take turns in permuting and re-encrypting or
decrypting the inputs. If at least one of the mixers is honest, the input data and
the output data can no longer be linked.
In this role, shuffling
constitutes an important building block in anonymization protocols and voting
The problem is that
the standard shuffle requires anyone who shuffles the input messages
to keep his random permutation and randomizers secret.
The assumption of a party keeping the secret information
may be in some ways quite strong.

Secondly, for this anonymization guarantee to
hold we do need to ensure that all mixers act according to the protocol.
In general, zero-knowledge proofs (ZKPs) are used for this purpose.
However, ZKPs requires the expensive cost in the light of
computation and communication.

In TCC 2007, Adida and Wikstr\"{o}m proposed a novel approach to
shuffle, called a public shuffle,
in which a shuffler can perform shuffle publicly without needing information kept secret.
Their scheme uses an encrypted permutation matrix to shuffle
ciphertexts publicly.
This approach significantly reduces the cost of constructing a mix-net
to verifiable joint decryption. Though their method is successful in making
shuffle to be a public operation, their scheme
still requires that some trusted parties should choose a permutation
to be encrypted and construct zero-knowledge proofs on the
well-formedness of this permutation.

In this dissertation, we study a method to construct a public shuffle
without relying on permutations generated privately: Given an
$n$-tuple of ciphertext $(c_1,\dots,c_n)$, our shuffle algorithm
computes $f_i(c_1,\dots,c_n)$ for $i=1,\dots,\ell$ where each
$f_i(x_1,\dots,x_n)$ is a symmetric polynomial in $x_1,\dots,x_n$.
Depending on the symmetric polynomials we use, we propose two concrete constructions.
One is to use ring homomorphic encryption with a constant ciphertext
complexity and the other is to use simple ElGamal encryption with a
linear ciphertext complexity in the number of users. Both
constructions are free of zero-knowledge proofs and publicly
Files in This Item:
Appears in Collections:
College of Natural Sciences (자연과학대학)Dept. of Mathematical Sciences (수리과학부)Theses (Ph.D. / Sc.D._수리과학부)
  • mendeley

Items in S-Space are protected by copyright, with all rights reserved, unless otherwise indicated.