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

Compress multiple ciphertexts using ElGamal encryption schemes

김지혜|천정희|김명선
대한수학회 (The Korean Mathematical Society)|2013.03|대한수학회지 (Journal of the KMS)|제50권 제2호|pp. 361-377

2

조회

0

다운로드

0

인용

0

참고문헌

키워드

decomposabilityciphertext compressionmessage rate
주제분류수학

초록

In this work we deal with the problem of how to squeeze multiple ciphertexts without losing original message information. To do so, we formalize the notion of decomposability for public-key encryption and investigate why adding decomposability is challenging. We construct an ElGamal encryption scheme over extension fields, and show that it supports the efficient decomposition. We then analyze security of our scheme under the standard DDH assumption, and evaluate the performance of our construction.

Abstract

In this work we deal with the problem of how to squeeze multiple ciphertexts without losing original message information. To do so, we formalize the notion of decomposability for public-key encryption and investigate why adding decomposability is challenging. We construct an ElGamal encryption scheme over extension fields, and show that it supports the efficient decomposition. We then analyze security of our scheme under the standard DDH assumption, and evaluate the performance of our construction.

참고문헌 (55)

  1. M. Abdalla, "The oracle Diffie-Hellman assumptions and an analysis of DHIES, CT-RSA, David Naccache", LNCS 2020, pp.143~158 (2001)
  2. M. Abe, "Chosen ciphertext security with optimal ciphertext overhead, Advances in Cryptology-AsiaCrypt, Josef Pieprzyk", LNCS, 5350, pp.355~371 (2008)
  3. M. Abe, "Compact CCA-secure encryption for messages of arbitrary length, PKC, Stanis-law Jarecki and Gene Tsudik", LNCS, 5443, pp.377~392 (2009)
  4. L. Adleman, "The function field sieve, ANTS, Leonard Adleman and Ming-Deh Huang", LNCS, 877, pp.108~121 (1994)
  5. P. Bateman, "A heuristic asymptotic formula concerning the distribution of prime numbers", Math. Comp, 16, pp.363~367 (1962)
  6. P. Bateman, "Waring’s problem for algebraic number fields and primes of the form (pr− 1)", (pd− 1), 1962, pp.6(1), 142~156
  7. K. Barr, "Energy-aware lossless data compression", ACMTrans. Comput. Syst, 24(3), pp.250~291 (2006)
  8. E. Berlekamp, "Factoring polynomials over large finite fields", Math. Comp, 24, pp.713~735 (1970)
  9. D. Boneh, "The decision Diffie-Hellman problem, ANTS, Joe Buhler", LNCS, 1423, pp.48~63 (1998)
  10. D. Boneh, "Why textbook ElGamal and RSA encryption are insecure, Advances in Cryptology-AsiaCrypt, Tatsuaki Okamoto", LNCS, 1976, pp.30~43 (2000)
  11. R. Brent, "An improved Monte Carlo factorization algorithm", BIT, 20(2), pp.176~184 (1980)
  12. D. Cantor, "A new algorithm for factoring polynomials over finite fields", Math. Comp, 36(154), pp.587~592 (1981)
  13. G. Castagnos, "Towards a DL-based additively homomorphic encryption scheme, ISC, Juan Garay and Arjen Lenstra and Masahiro Mambo and Ren´e Peralta", LNCS, 4779, pp.362~375 (2007)
  14. H. Chan, "Secure distributed data aggregation", Foundations and Trends in Databases, 3(3), pp.149~201 (2011)
  15. J. Cooley, "An algorithm for the machine calculation of complex Fourier series", Math. Comp, 19, pp.297~301 (1965)
  16. I. Damg°ard, "A generalisation, a simplification and some applications of Paillier’s probabilistic public-key system, Public Key Cryptography, Kwangjo Kim", LNCS, 1992, pp.119~136 (2001)
  17. J. von zur Gathen, "Who was who in polynomial factorization", ISSAC, Barry Trager, 2 (2006)
  18. J. von zur Gathen, "Factoring polynomials over finite fields: A survey", J. Symb. Comput, 31(1-2), pp.3~17 (2001)
  19. J. von zur Gathen, "Computing Frobenius maps and factoring polynomials", Comput. Complexity, 2(3), pp.187~224 (1992)
  20. J. Fraleigh, "A First Course in Abstract Algebra" (2003), Pearson Education
  21. T. El Gamal, "A Public key cryptosystem and a signature scheme based on discrete logarithms", IEEE Trans. Inform. Theory, 31(4), pp.469~472 (1985)
  22. C. Gentry, "How to compress Rabin ciphertexts and signatures (and more), Advances in Cryptology-Crypto, Matthew K. Franklin", LNCS, 3152, pp.179~200 (2004)
  23. O. Goldreich, "S. Micali, and A. Wigderson, Proofs that yield nothing but their validity, or All languages in NP have zero-knowledge proof systems", J. Assoc. Comput. Mach, 38(3), pp.691~729 (1991)
  24. D. Goldschlag, "Onion routing", Commun. ACM, 42(2), pp.39~41 (1999)
  25. S. Goldwasser, "Probabilistic encryption", J. Comput. System Sci, 28(2), pp.270~299 (1984)
  26. D. M. Gordon, "Discrete logarithms in GF(p) using the number field sieve", SIAM J. Discrete Math, 6(1), pp.124~138 (1993)
  27. J. Gower, "Prime order primitive subgroups in torus-based cryptography", IACR Cryptol-ogy ePrint Archive, 2006, pp.466~ (2006)
  28. R. Granger, "On the discrete logarithm problem on algebraic tori, Advances in Cryptology-Crypto, Victor Shoup", LNCS, 3621, pp.66~85 (2005)
  29. R. Heath-Brown, "Differences between consecutive primes", Seminar on Number Theory, 1979-80, (14) (1980), Univ. Bordeaux I
  30. J. Hong, "Constant-round privacy pre-serving multiset union", Cryptology ePrint Archive, 2011, pp.138~ (2011)
  31. T. W. Hungerford, "Algebra" (1980), Springer
  32. M. Huxley, "On the difference between consecutive primes", Invent. Math, 15, pp.164~170 (1972)
  33. G. Itkis, "Forward-secure signatures with optimal signing and verifying, Advances in Cryptology-Crypto, Joe Kilian", LNCS, 2139, pp.332~354 (2001)
  34. R. Johnson, "Homomorphic signature schemes, CT-RSA, Bart Preneel", LNCS, 2271, pp.244~262 (2002)
  35. A. Joux, "The function field sieve in the medium prime case, Advances in Cryptology-EuroCrypt, Serge Vaudenay", LNCS, 4004, pp.254~270 (2006)
  36. A. Joux, "The number field sieve in the medium prime case, Advances in Cryptology-Crypto, Cynthia Dwork", LNCS, 4117, pp.326~344 (2006)
  37. E. Kaltofen, "Polynomial factorization: a success story", ISSAC, J. Rafael Sendra, 3(4) (2003)
  38. E. Kaltofen, "Subquadratic-time factoring of polynomials over finite fields", Math. Comp, 67(223), pp.1179~1197 (1998)
  39. A. Karatsuba, "Multiplication of multidigit numbers on automata", Soviet Physics Doklady, 7, pp.595~596 (1963)
  40. N. Kayal, "On the ring isomorphism & automorphism problems", Electronic Colloquium on Computational Complexity (ECCC), 11(109) (2004)
  41. M. Kim, "Mutual Private Set Intersection with Linear Complexity" (2011), WISA
  42. H. W. Lenstra Jr., "Factoring integers with elliptic curves", Ann. of Math, 126(3), pp.649~673 (1987)
  43. H. W. Lenstra Jr, "Finding isomorphisms between finite fields", Math. Comp, 56(193), pp.329~347 (1991)
  44. D. Ma, "New adversary and new threats: security in unat-tended sensor networks", IEEE Network, 23(2), pp.43~48 (2009)
  45. D. Ma, "Extended abstract: forward-secure sequential aggregate authenti-cation", IEEE Symposium on Security and Privacy, pp.86~91 (2007)
  46. H. Maier, "Primes in short intervals", Michigan Math. J, 32(2), pp.221~225 (1985)
  47. T. Okamoto, "A new public-key cryptosystem as secure as factoring, Advances in Cryptology-EuroCrypt, Kaisa Nyberg", LNCS, 1403, pp.308~318 (1998)
  48. P. Paillier, "Public-key cryptosystems based on composite degree residuosity classes, Ad-vances in Cryptology-EuroCrypt, Jacques Stern", LNCS, 1592, pp.223~238 (1999)
  49. R. Peralta, "On the distribution of quadratic residues and nonresidues modulo a prime number", Math. Comp, 58(197), pp.433~440 (1992)
  50. D. H. Phan, "Chosen-ciphertext security without redundancy, Ad- vances in Cryptology-AsiaCrypt, Chi-Sung Laih", LNCS, 2894, pp.1~18 (2003)
  51. J. Pollard, "Theorems on factorization and primality testing", Proc. Cambridge Philos. Soc, 76, pp.521~528 (1974)
  52. V. Shoup, "A Computational Introduction to Number Theory and Algebra" (2005), Cambridge University Press
  53. C. Umans, "Fast polynomial factorization and modular composition in small character-istic", STOC’08, pp.481~490 (2008), ACM
  54. A. C. Yao, "Protocols for secure computations", FOCS, pp.160~164 (1982)
  55. T. Yonemura, "Generating pa-rameters for algebraic torus-based cryptosystems, CANS, Swee-Huay Heng and Rebecca Wright and Bok-Min Goi", LNCS, 6467, pp.156~168 (2010)

관련 논문AI추천

Constant-round privacy preserving multiset union김정우, 김지혜, 박근수, 천정희, 홍정대대한수학회 · 대한수학회보2013 · 제50권 제6호New Construction of Order-Preserving Encryption Based on Order-Revealing Encryption김기성한국정보처리학회 · JIPS(Journal of Information Processing Systems)2019 · 제15권 제5호Efficient and General PVSS Based on ElGamal EncryptionKun Peng한국정보처리학회 · JIPS(Journal of Information Processing Systems)2012 · 제8권 제2호Cryptanalysis of a dynamic threshold decryption scheme김경희, 김기태, 이익권, Seongan Lim대한수학회 · 대한수학회논문집2009 · 제24권 제1호A Strong Designated Verifiable DL Based Signcryption SchemeBanshidhar Majhi, Sujata Mohanty한국정보처리학회 · JIPS(Journal of Information Processing Systems)2012 · 제8권 제4호Zero-Knowledge Proofs from spLWE-based Commitments김두영, 김진수영남수학회 · East Asian Mathematical Journal2022 · 제38권 제1호

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

Orthogonal almost complex structures on the Riemannian products of even-dimensional round spheresKouei Sekigawa, 어은희pp. 231-240Cubic symmetric graphs of order 10p3Mohsen Ghasemipp. 241-257An approach to solution of the Schrodinger equation using Fourier-type functionals장승준, 정현수, 최재길pp. 259-274Invariant differential operators on the Minkowski-Euclid space양재현pp. 275-306On m,n-balanced projective and m,n-totally projective primary abelian groupsPatrick W. Keef, Peter V. Danchevpp. 307-330
원문 보기