Verification of a Paillier based shuffle using representations of the symmetric group

다국어 초록 (Multilingual Abstract)

We use an idea of linear representations of the symmetric group to
reduce the number of communication rounds in the verification
protocol, proposed in Crypto 2005 by Peng et al., of a shuffling. We
assume Paillier encryption scheme with which we can apply some known
zero-knowledge proofs following the same line of approaches of Peng
et al. Incidence matrices of 1-subsets and 2-subsets of a finite
set is intensively used for the implementation, and the idea of
λ-designs is employed for the improvement of the
computational complexity.

다국어 초록 (Multilingual Abstract)

We use an idea of linear representations of the symmetric group to
reduce the number of communication rounds in the verification
protocol, proposed in Crypto 2005 by Peng et al., of a shuffling. We
assume Paillier encryption scheme with which we can apply some known
zero-knowledge proofs following the same line of approaches of Peng
et al. Incidence matrices of 1-subsets and 2-subsets of a finite
set is intensively used for the implementation, and the idea of
λ-designs is employed for the improvement of the
computational complexity.

참고문헌 (Reference)

1 L. Nguyen, "Verifiable shuffles: A formal model and a Paillier-based efficient construction with provable security, ACNS" Springer 3089 : 61-75, 2004

2 J. Groth, "Verifiable shuffle of large size ciphertexts, Public key cryptography— PKC 2007" Springer 4450 : 377-392, 2007

3 D. Chaum, "Untraceable electronic mail, return addresses, and digital pseudonyms" 24 (24): 84-88, 1981

4 P. Golle, "Universal re-encryption for mixnets, Topics in cryptology—CT-RSA 2004" Springer 2964 : 163-178, 2004

5 C. D´ıaz, "Towards measuring anonymity"

6 A. Serjantov, "Towards an information theoretic metric for anonymity"

7 R. Dingledine, "Tor: The second-generation onion router" USENIX 303-320, 2004

8 B. E. Sagan, "The symmetric group. Representations, combinatorial algorithms, and symmetric functions, The Wadsworth & Brooks/Cole Mathematics Series. Wadsworth & Brooks/Cole Advanced Books & Software" Pacific Grove 1991

9 K. Peng, "Simple and efficient shuffling with provable correctness and ZK privacy, Advances in cryptology—CRYPTO 2005" Springer 3621 : 188-204, 2005

10 W. Fulton, "Representation Theory, A First Course, Graduate Texts in Mathematics" Springer 129-, 1991

11 P. Paillier, "Public-key cryptosystems based on composite degree residuosity classes, Advances in cryptology—EUROCRYPT ’99" Springer 1592 : 223-238, 1999

12 S. Cho, "Proving a shuffle using representations of the symmetric group, ICISC 2008" Springer 5461 : 354-367, 2009

13 R. Dingledine, "Privacy enhancing technologies, Second international workshop, pet 2002" Springer 2482 : 14-15, 2003

14 P. Golle, "Optimistic mixing for exitpolls, Advances in cryptology—ASIACRYPT 2002" Springer 2501 : 451-465, 2002

15 G. Danezis, "Mixminion: Design of a type iii anonymous remailer protocol" IEEE Computer Society 2-15, 2003

16 G. Danezis, "Mix-networks with restricted routes, Privacy Enhancing Technologies" Springer 2760 : 1-17, 2003

17 M. Abe, "Mix-networks on permutation networks, Advances in cryptology—ASIACRYPT ’99" Springer 1716 : 258-273, 1999

18 P. Frankl, "Intersection theorems and mod p rank of inclusion matrices" 54 (54): 85-94, 1990

19 B. Pfitzmann, "How to break the direct RSA-implementation of mixes"

20 B. Pfitzmann, "How to break another provably secure payment system"

21 Y. Desmedt, "How to break a practical mix and design a new one"

22 W Ogata, "Fault tolerant anonymous channel, Proc. ICICS ’97" Springer 1334 : 440-444, 1997

23 E.-J. Goh, "Encryption schemes from bilinear maps" Stanford University 2007

24 C. Park, "Efficient anonymous channel and all/nothing election scheme, Advances in cryptology—EUROCRYPT ’93" Springer 765 : 248-259, 1994

25 P. J. Cameron, "Designs, Graphs, Codes and Their Links, London Mathematical Society Student Texts" Cambridge University Press 22-, 1991

26 M. Mitomo, "Attack for flash MIX, Advances in cryptology— ASIACRYPT 2000" Springer 1976 : 192-204, 2000

27 J. Furukawa, "An efficient scheme for proving a shuffle, Advances in cryptology—CRYPTO 2001" Springer 2139 : 368-387, 2001

28 J. Groth, "A verifiable secret shuffle of homomorphic encryptions, Public key cryptography— PKC 2003" Springer 2567 : 145-160, 2002

29 C. A. Neff, "A verifiable secret shuffle and its application to e-voting" 116-125, 2001

30 D. Wikstr¨om, "A sender verifiable mix-net and a new proof of a shuffle, Advances in cryptology—ASIACRYPT 2005" Springer 3788 : 273-292, 2005

31 R. Dingledine, "A reputation system to increase mix-net reliability, Information Hiding" Springer 2137 : 126-141, 2001

32 R. M. Wilson, "A diagonal form for the incidence matrices of t-subsets vs. k-subsets" 11 (11): 609-615, 1990

33 K. Peng, "A correct, private, and efficient mix network, Public key cryptography—PKC 2004" Springer 2947 : 439-454, 2004

34 J. H. van Lint, "A Course in Combinatorics" Cambridge University Press 1992