본문 바로가기
KERD
논문KCI 등재

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

Soojin Cho|Manpyo Hong
대한수학회 (The Korean Mathematical Society)|2009.07|대한수학회보 (Bulletin of the KMS)|제46권 제4호|pp. 771-787

2

조회

0

다운로드

0

인용

0

참고문헌

키워드

homomorphic encryptionproof of shufflemix-netrepresentation of symmetric groupλ-designs
주제분류수학

초록

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.

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.

참고문헌 (34)

  1. M. Abe, "Mix-networks on permutation networks, Advances in cryptology—ASIACRYPT ’99", Lecture Notes in Comput. Sci, 1716, pp.258~273 (1999), Springer
  2. P. J. Cameron, "Designs, Graphs, Codes and Their Links, London Mathematical Society Student Texts", pp.22~ (1991), Cambridge University Press
  3. D. Chaum, "Untraceable electronic mail, return addresses, and digital pseudonyms", Commun. ACM, 24(2), pp.84~88 (1981)
  4. S. Cho, "Proving a shuffle using representations of the symmetric group, ICISC 2008", Lecture Notes in Computer Science, 5461, pp.354~367 (2009), Springer
  5. G. Danezis, "Mix-networks with restricted routes, Privacy Enhancing Technologies", Lecture Notes in Computer Science, 2760, pp.1~17 (2003), Springer
  6. G. Danezis, "Mixminion: Design of a type iii anonymous remailer protocol", IEEE Symposium on Security and Privacy, pp.2~15 (2003), IEEE Computer Society
  7. Y. Desmedt, "How to break a practical mix and design a new one", EUROCRYPT, 557~572 (2000)
  8. C. D´ıaz, "Towards measuring anonymity", in Dingledine and Syverson 11, 54~68
  9. R. Dingledine, "A reputation system to increase mix-net reliability, Information Hiding", Lecture Notes in Computer Science, 2137, pp.126~141 (2001), Springer
  10. R. Dingledine, "Tor: The second-generation onion router", USENIX Security Symposium, pp.303~320 (2004), USENIX
  11. R. Dingledine, "Privacy enhancing technologies, Second international workshop, pet 2002", Lecture Notes in Computer Science, 2482, pp.14~15 (2003), Springer
  12. P. Frankl, "Intersection theorems and mod p rank of inclusion matrices", J. Combin. Theory Ser. A, 54(1), pp.85~94 (1990)
  13. W. Fulton, "Representation Theory, A First Course, Graduate Texts in Mathematics", pp.129~ (1991), Springer
  14. J. Furukawa, "An efficient scheme for proving a shuffle, Advances in cryptology—CRYPTO 2001", Lecture Notes in Comput. Sci, 2139, pp.368~387 (2001), Springer
  15. E.-J. Goh, "Encryption schemes from bilinear maps", 박사, Computer Science, pp.2007
  16. P. Golle, "Universal re-encryption for mixnets, Topics in cryptology—CT-RSA 2004", Lecture Notes in Comput. Sci, 2964, pp.163~178 (2004), Springer
  17. P. Golle, "Optimistic mixing for exitpolls, Advances in cryptology—ASIACRYPT 2002", Lecture Notes in Comput. Sci, 2501, pp.451~465 (2002), Springer
  18. J. Groth, "A verifiable secret shuffle of homomorphic encryptions, Public key cryptography— PKC 2003", Lecture Notes in Comput. Sci, 2567, pp.145~160 (2002), Springer
  19. J. Groth, "Verifiable shuffle of large size ciphertexts, Public key cryptography— PKC 2007", Lecture Notes in Comput. Sci, 4450, pp.377~392 (2007), Springer
  20. J. H. van Lint, "A Course in Combinatorics" (1992), Cambridge University Press
  21. M. Mitomo, "Attack for flash MIX, Advances in cryptology— ASIACRYPT 2000", Lecture Notes in Comput. Sci, 1976, pp.192~204 (2000), Springer
  22. C. A. Neff, "A verifiable secret shuffle and its application to e-voting", ACM Conference on Computer and Communications Security, pp.116~125 (2001)
  23. L. Nguyen, "Verifiable shuffles: A formal model and a Paillier-based efficient construction with provable security, ACNS", Lecture Notes in Computer Science, 3089, pp.61~75 (2004), Springer
  24. W Ogata, "Fault tolerant anonymous channel, Proc. ICICS ’97", Lecture Notes in Comput. Sci, 1334, pp.440~444 (1997), Springer
  25. P. Paillier, "Public-key cryptosystems based on composite degree residuosity classes, Advances in cryptology—EUROCRYPT ’99", Lecture Notes in Comput. Sci, 1592, pp.223~238 (1999), Springer
  26. C. Park, "Efficient anonymous channel and all", nothing election scheme, Advances in cryptology—EUROCRYPT ’93, 1994, pp.765, 248~259[DOI]
  27. K. Peng, "Simple and efficient shuffling with provable correctness and ZK privacy, Advances in cryptology—CRYPTO 2005", Lecture Notes in Comput. Sci, 3621, pp.188~204 (2005), Springer
  28. K. Peng, "A correct, private, and efficient mix network, Public key cryptography—PKC 2004", Lecture Notes in Comput. Sci, 2947, pp.439~454 (2004), Springer
  29. B. Pfitzmann, "How to break the direct RSA-implementation of mixes", EUROCRYPT, 373~381 (1989)
  30. B. Pfitzmann, "How to break another provably secure payment system", EUROCRYPT, 121~132 (1995)
  31. Cole Mathematics Series. Wadsworth & Brooks, "The symmetric group. Representations, combinatorial algorithms, and symmetric functions, The Wadsworth & Brooks", pp.Pacific Grove, Cole Advanced Books & Software
  32. , 41~53
  33. D. Wikstr¨om, "A sender verifiable mix-net and a new proof of a shuffle, Advances in cryptology—ASIACRYPT 2005", Lecture Notes in Comput. Sci, 3788, pp.273~292 (2005), Springer
  34. R. M. Wilson, "A diagonal form for the incidence matrices of t-subsets vs. k-subsets", European J. Combin, 11(6), pp.609~615 (1990)

관련 논문AI추천

Constant-round privacy preserving multiset union김정우, 김지혜, 박근수, 천정희, 홍정대대한수학회 · 대한수학회보2013 · 제50권 제6호Attack and Correction: How to Design a Secure and Efficient Mix NetworkKun Peng한국정보처리학회 · JIPS(Journal of Information Processing Systems)2012 · 제8권 제1호Zero-Knowledge Proofs from spLWE-based Commitments김두영, 김진수영남수학회 · East Asian Mathematical Journal2022 · 제38권 제1호Analysis of privacy-preserving element reduction of a multiset서재홍, 천정희, 홍도원, HyoJin Yoon, Seongan Lim대한수학회 · 대한수학회지2009 · 제46권 제1호Efficient Proof of Vote Validity Without Honest-Verifier Assumption in Homomorphic E-VotingKun Peng한국정보처리학회 · JIPS(Journal of Information Processing Systems)2011 · 제7권 제3호Threshold Encryption Scheme based on Cocks' IBE Scheme김대엽, Sergey V. Bezzateev한국정보처리학회 · 정보처리학회논문지C2012 · 제19권 제4호

이 간행물의 다른 논문 (14건)

On the complex oscillation of higher order linear differential equationsLian-Zhong Yang, Kai Liupp. 607-615On complete convergence for weighted sums of i.i.d. random variables with application to moving average processesSoo Hak Sungpp. 617-626Optimal error estimate for semi-discrete gauge-Uzawa method for the Navier-Stokes equationsJae-Hong Pyopp. 627-644On the Hyers-Ulam-Rassias stability of Jensen's equationDongyan Zhang, Jian Wangpp. 645-656A structure theorem for complete intersections최은정, 고형준, Oh-Jin Kangpp. 657-671
원문 보기