## Browse

S-Space
College of Natural Sciences (자연과학대학)
Dept. of Mathematical Sciences (수리과학부)
Theses (Ph.D. / Sc.D._수리과학부)

Cryptographic Shuffles and Their Applications

- Authors
- 김명선

- Advisor
- 천정희

- Major
- 자연과학대학 수리과학부

- Issue Date
- 2012-08

- Publisher
- 서울대학교 대학원

- Description
- 학위논문 (박사)-- 서울대학교 대학원 : 수리과학부, 2012. 8. 천정희.

- Abstract
- 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

schemes.

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

verifiable.

- Language
- English

- Files in This Item:

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