Taechan Kim
Taechan Kim has a total of 17 co-authors. Here are the top co-authors by number of shared publications:
- Mehdi Tibouchi
NTT Social Informatics Laboratories, Tokyo, Japan
3 shared publications - Jung Hee Cheon
Seoul National University
2 shared publications - Yongsoo Song
Seoul National University
2 shared publications Byung Joon Baek
Samsung Electronics Co., Ltd
1 shared publicationChangmin Lee
Seoul National University
1 shared publication- Dongwon Lee
Seoul National University
1 shared publication
Latest Publications
- Open Access
- 15 November 2023
- Published by Association for Computing Machinery (ACM)
- p. 726-740
Asymptotically Faster Multi-Key Homomorphic Encryption from Homomorphic Gadget Decomposition
Homomorphic Encryption (HE) is a cryptosytem that allows us to perform an arbitrary computation on encrypted data. The standard HE, however, has a disadvantage in that the authority is concentrated in the secret key owner since computations can only be performed on ciphertexts encrypted under the same secret key. To resolve this issue, research is underway on Multi-Key Homomorphic Encryption (MKHE), which is a variant of HE supporting computations on ciphertexts possibly encrypted under different keys. Despite its ability to provide privacy for multiple parties, existing MKHE schemes suffer from poor performance due to the cost of multiplication which grows at least quadratically with the number of keys involved. In this paper, we revisit the work of Chen et al. (ACM CCS 2019) on MKHE schemes from CKKS and BFV and significantly improve their performance. Specifically, we redesign the multi-key multiplication algorithm and achieve an asymptotically optimal complexity that grows linearly with the number of keys. Our construction relies on a new notion of gadget decomposition, which we call homomorphic gadget decomposition, where arithmetic operations can be performed over the decomposed vectors with guarantee of its functionality. Finally, we implement our MKHE schemes and demonstrate their benchmarks. For example, our multi-key CKKS multiplication takes only 0.5, 1.0, and 1.9 seconds compared to 1.6, 5.9, and 23.0 seconds of the previous work when 8, 16, and 32 keys are involved, respectively.
- 15 November 2023
- Published by Association for Computing Machinery (ACM)
- p. 726-740
Open AccessAsymptotically Faster Multi-Key Homomorphic Encryption from Homomorphic Gadget Decomposition
Homomorphic Encryption (HE) is a cryptosytem that allows us to perform an arbitrary computation on encrypted data. The standard HE, however, has a disadvantage in that the authority is concentrated in the secret key owner since computations can only be performed on ciphertexts encrypted under the same secret key. To resolve this issue, research is underway on Multi-Key Homomorphic Encryption (MKHE), which is a variant of HE supporting computations on ciphertexts possibly encrypted under different keys. Despite its ability to provide privacy for multiple parties, existing MKHE schemes suffer from poor performance due to the cost of multiplication which grows at least quadratically with the number of keys involved. In this paper, we revisit the work of Chen et al. (ACM CCS 2019) on MKHE schemes from CKKS and BFV and significantly improve their performance. Specifically, we redesign the multi-key multiplication algorithm and achieve an asymptotically optimal complexity that grows linearly with the number of keys. Our construction relies on a new notion of gadget decomposition, which we call homomorphic gadget decomposition, where arithmetic operations can be performed over the decomposed vectors with guarantee of its functionality. Finally, we implement our MKHE schemes and demonstrate their benchmarks. For example, our multi-key CKKS multiplication takes only 0.5, 1.0, and 1.9 seconds compared to 1.6, 5.9, and 23.0 seconds of the previous work when 8, 16, and 32 keys are involved, respectively.
- 25 November 2017
- Published by Springer Nature
- p. 371-391
Lattice Reductions over Euclidean Rings with Applications to Cryptanalysis
- 25 November 2017
- Published by Springer Nature
- p. 371-391
Lattice Reductions over Euclidean Rings with Applications to Cryptanalysis
- 26 February 2017
- Published by Springer Nature
- p. 388-408
Extended Tower Number Field Sieve with Application to Finite Fields of Arbitrary Composite Extension Degree
- 26 February 2017
- Published by Springer Nature
- p. 388-408
Extended Tower Number Field Sieve with Application to Finite Fields of Arbitrary Composite Extension Degree
- 24 October 2016
- Published by Springer Nature in Designs, Codes and Cryptography
- Vol. 82 (1-2) , 161-177
Improved elliptic curve hashing and point representation
- 24 October 2016
- Published by Springer Nature in Designs, Codes and Cryptography
- Vol. 82 (1-2) , 161-177
Improved elliptic curve hashing and point representation
- Top Cited Papers
- 21 July 2016
- Published by Springer Nature
- p. 543-571
Extended Tower Number Field Sieve: A New Complexity for the Medium Prime Case
- 21 July 2016
- Published by Springer Nature
- p. 543-571
Top Cited PapersExtended Tower Number Field Sieve: A New Complexity for the Medium Prime Case
- 1 January 2016
- Published by Wiley in LMS Journal of Computation and Mathematics
- Vol. 19 (1) , 1-15
A new approach to the discrete logarithm problem with auxiliary inputs
- 1 January 2016
- Published by Wiley in LMS Journal of Computation and Mathematics
- Vol. 19 (1) , 1-15
A new approach to the discrete logarithm problem with auxiliary inputs
- 1 January 2015
- Published by Springer Nature
- p. 174-188
Multiple Discrete Logarithm Problems with Auxiliary Inputs
- 1 January 2015
- Published by Springer Nature
- p. 174-188
Multiple Discrete Logarithm Problems with Auxiliary Inputs
- 21 May 2014
- Published by Springer Nature in Lecture Notes in Computer Science
- p. 121-135
A Group Action on ${\mathbb Z}_p^{\times }$ and the Generalized DLP with Auxiliary Inputs- 21 May 2014
- Published by Springer Nature in Lecture Notes in Computer Science
- p. 121-135
A Group Action on ${\mathbb Z}_p^{\times }$ and the Generalized DLP with Auxiliary Inputs- 1 January 2014
- Published by Springer Nature
- p. 163-180
Bit-Flip Faults on Elliptic Curve Base Fields, Revisited
- 1 January 2014
- Published by Springer Nature
- p. 163-180
Bit-Flip Faults on Elliptic Curve Base Fields, Revisited