Chinese
English
Research Fellow/Professor  |  Chung, Kai-Min  
 
contact
vita
education
experience
interests
activities
invited_talk
invited_visit
honors
publications
supervised
Personal (New window)
 
 
 
 
 
Publications
 
1. Kai-Min Chung, Mi-Ying Huang, Er-Cheng Tang, Jiapeng Zhang, "Best-of-Both-Worlds Multiparty Quantum Computation with Publicly Verifiable Identifiable Abort," to appear in The 43rd Annual International Conference on the Theory and Applications of Cryptology and Information Security (Eurocrypt 2024),.
2. Abtin Afshar, Kai-Min Chung, Yao-Ching Hsieh, Yao-Ting Lin, Mohammad Mahmoody, "On the (Im)possibility of Time-Lock Puzzles in the Quantum Random Oracle Model," The 29th Annual International Conference on the Theory and Applications of Cryptology and Information Security (ASIACRYPT 2023), December 2023.
3. Yu-Fang Chen, Kai-Min Chung, Ondřej Lengál, Jyun-Ao Lin, Wei-Lun Tsai, "AutoQ: An Automata-based Quantum Circuit Verifier," The 35th International Conference on Computer Aided Verification (CAV 2023), July 2023.
4. Nai-Hui Chia, Kai-Min Chung, Yao-Ching Hsieh, Han-Hsuan Lin, Yao-Ting Lin, Yu-Ching Shen, "On the Impossibility of General Parallel Fast-forwarding of Hamiltonian Simulation," The 38nd Annual IEEE Conference on Computational Complexity (CCC 2023), July 2023.
5. Yu-Fang Chen, Kai-Min Chung, Ondřej Lengál, Jyun-Ao Lin, Wei-Lun Tsai, Di-De Yen, "An Automata-based Framework for Verification and Bug Hunting in Quantum Circuits," The 44th ACM SIGPLAN Conference on Programming Language Design and Implementation (PLDI 2023), June 2023.
6. Kai-Min Chung, Yao-Ting Lin, Mohammad Mahmoody, "Black-Box Separations for Non-Interactive Commitments in a Quantum World," The 42nd Annual International Conference on the Theory and Applications of Cryptology and Information Security (Eurocrypt 2023), April 2023.
7. Nai-Hui Chia, Kai-Min Chung, Ching-Yi Lai, "On the Need for Large Quantum Depth," The Journal of the ACM (JACM), volume 70, number 6, pages 1-38, February 2023.
8. Prabhanjan Ananth, Kai-Min Chung, Xiong Fan, Luowen Qian, "Collusion-Resistant Functional Encryption for RAMs," The 28th Annual International Conference on the Theory and Applications of Cryptology and Information Security (ASIACRYPT 2022), December 2022.
9. T-H. Hubert Chan, Kai-Min Chung, Bruce Maggs, Elaine Shi, "Foundations of Differentially Oblivious Algorithms," The Journal of the ACM (JACM), volume 69, number 4, pages 1-49, August 2022.
10. Per Austrin, Hao Chung, Kai-Min Chung, Shiuan Fu, Yao-Ting Lin, Mohammad Mahmoody, "On the Impossibility of Key Agreements from Quantum Random Oracles," The 42nd International Cryptology Conference (CRYPTO 2022), August 2022.
11. Nai-Hui Chia, Kai-Min Chung, Xiao Liang, Takashi Yamakawa, "Post-Quantum Simulatable Extraction with Minimal Assumptions: Black-Box and Constant-Round," The 42nd International Cryptology Conference (CRYPTO 2022), August 2022.
12. Kai-Min Chung, Yi Lee, Han-Hsuan Lin, Xiaodi Wu, "Constant-round Blind Classical Verification of Quantum Sampling," The 41st Annual International Conference on the Theory and Applications of Cryptology and Information Security (Eurocrypt 2022), May 2022.
13. Rohit Chatterjee, Kai-Min Chung, Xiao Liang, Giulio Malavolta, "A Note on the Post-Quantum Security of (Ring) Signatures," The 25th International Conference on Practice and Theory of Public-Key Cryptography (PKC 2022), March 2022.
14. Nai-Hui Chia, Kai-Min Chung, Qipeng Liu and Takashi Yamakawa, "On the Impossibility of Post-Quantum Black-Box Zero-Knowledge in Constant Rounds," The 62nd Annual IEEE Symposium on Foundations of Computer Science (FOCS 2021), February 2022, Contributed talk at QCrypt 2021 and QIP 2022. :::icon
15. Kai-Min Chung, Serge Fehr, Yu-Hsuan Huang, Tai-Ning Liao, "On the Compressed-Oracle Technique, and Post-Quantum Security of Proofs of Sequential Work," The 40th Annual International Conference on the Theory and Applications of Cryptographic Techniques (Eurocrypt 2021), October 2021, Contributed talk at QCrypt 2021.
16. Kai-Min Chung, T-H. Hubert Chan, Ting Wen, and Elaine Shi, "Game-Theoretic Fairness Meets Multi-Party Protocols: The Case of Leader Election," The 41st International Cryptology Conference (CRYPTO 2021), August 2021.
17. Bar Alon, Hao Chung, Kai-Min Chung, Mi-Ying Huang, Yi Lee, and Yu-Ching Shen, "Round Efficient Secure Multiparty Quantum Computation with Identifiable Abort," The 41st International Cryptology Conference (CRYPTO 2021), August 2021.
18. Prabhanjan Ananth, Kai-Min Chung, and Rolando L. La Placa, "On the Concurrent Composition of Quantum Zero-Knowledge," The 41st International Cryptology Conference (CRYPTO 2021), August 2021.
19. Nai-Hui Chia, Kai-Min Chung, and Takashi Yamakawa, "A Black-Box Approach to Post-Quantum Zero-Knowledge in Constant Rounds," The 41st International Cryptology Conference (CRYPTO 2021), August 2021.
20. Kai-Min Chung and Han-Hsuan Lin, "Sample Efficient Algorithms for Learning Quantum Channels in PAC Model and the Approximate State Discrimination Problem," The 16th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2021), July 2021.
21. Nai-Hui Chia, Kai-Min Chung and Takashi Yamakawa, "Classical Verification of Quantum Computations with Efficient Verifier," Theory of Cryptography Conference (TCC 2020), November 2020.
22. Kai-Min Chung, Siyao Guo, Qipeng Liu and Luowen Qian, "Tight Quantum Time-Space Tradeoffs for Function Inversion," The 61st Annual IEEE Symposium on Foundations of Computer Science (FOCS), November 2020.
23. Kai-Min Chung, Kuan-Yi Ho and Xiaorui Sun, "On the Hardness of Massively Parallel Computation," The 32nd ACM Symposium on Parallelism in Algorithms and Architectures(SPAA 2020), July 2020.
24. Kai-Min Chung, Tai-Ning Liao, Luowen Qian, "Lower Bounds for Function Inversion with Quantum Advice," The 1st Information-Theoretic Cryptography (ITC 2020), June 2020.
25. Nai-Hui Chia, Kai-Min Chung, Ching-Yi Lai, "On the Need for Large Quantum Depth," The 52nd Annual ACM Symposium on Theory of Computing 2020 (STOC 2020), June 2020, Contributed talk at QIP 2020.
26. T-H. Hubert Chan, Kai-Min Chung, Wei-Kai Lin and Elaine Shi, "MPC for MPC: Secure Computation on a Massively Parallel Computing Architecture," The 11th Innovations in Theoretical Computer Science (ITCS 2020), January 2020. :::icon
27. Kai-Min Chung and Luowen Qian, "Adaptively Secure Garbling Schemes for Parallel Computations," Theory of Cryptography Conference (TCC 2019), December 2019.
28. Kai-Min Chung, Marios Georgiou, Ching-Yi Lai and Vassilis Zikas, "Cryptography with Disposable Backdoors," Cryptography, volume 3, number 3, pages 22, September 2019.
29. Ching-Yi Lai and Kai-Min Chung, "Interactive Leakage Chain Rule for Quantum Min-entropy," International Symposium on Information Theory (ISIT 2019), July 2019.
30. Dorit Aharonov, Zvika Brakerski, Ayal Green, Ching-Yi La, Kai-Min Chung and Or Sattath, "On Quantum Advantage in Information Theoretic Single-Server PIR," The 38th Annual International Conference on the Theory and Applications of Cryptographic Techniques (Eurocrypt 2019), May 2019.
31. Thomas Vidick, Han-hsuan Lin, Divesh Aggarwal and Kai-Min Chung, "A Quantum-Proof Non-Malleable Extractor With Application to Privacy Amplification against Active Quantum Adversaries," The 38th Annual International Conference on the Theory and Applications of Cryptographic Techniques (Eurocrypt 2019), May 2019.
32. Chi-Ning Chou, Kai-Min Chung and Chi-Jen Lu, "On the Algorithmic Power of Spiking Neural Networks," The 10th Innovations in Theoretical Computer Science (ITCS 2019), January 2019.
33. Ching-Yi Lai and Kai-Min Chung, "Quantum encryption and generalized Shannon impossibility," Design, Codes and Cryptography, volume 87, number 9, pages 1961-1972, January 2019.
34. T-H. Hubert Chan, Kai-Min Chung, Bruce Maggs and Elaine Shi, "Foundations of Differentially Oblivious Algorithms," ACM-SIAM Symposium on Discrete Algorithms (SODA 2019), January 2019.
35. Kai-Min Chung, Yue Guo, Wei-Kai Lin, Rafael Pass and Elaine Shi, "Game Theoretic Notions of Fairness in Multi-Party Coin Toss," The 16th Theory of Cryptography Conference (TCC 2018), November 2018.
36. Ching-Yi Lai and Kai-Min Chung, "On Statistically-Secure Quantum Homomorphic Encryption," Quantum Information & Computation, volume 18, number 9&10, pages 785-794, August 2018.
37. Yi-Hsiu Chen, Kai-Min Chung, Jyun-Jie Liao, "On the Complexity of Simulating Auxiliary Input," The 37th Annual International Conference on the Theory and Applications of Cryptographic Techniques (EUROCRYPT 2018), April 2018.
38. Yanlin Chen, Kai-Min Chung, and Ching-Yi Lai, "Space-efficient Classical and Quantum Algorithms for the Shortest Vector Problem," Quantum Information & Computation, volume 18, number 3&4, pages 285-306, March 2018.
39. Divesh Aggarwal, Kai-Min Chung, Han-Hsuan Lin and Thomas Vidick, "A Quantum-Proof Non-Malleable Extractor, With Application to Privacy Amplification against Active Quantum Adversaries," The 21st Annual Conference on Quantum Information Processing (QIP 2018; Poster), January 2018.
40. T-H. Hubert Chan, Kai-Min Chung, Elaine Shi, "On the Depth of Oblivious Parallel RAM," The 23rd Annual International Conference on the Theory and Applications of Cryptology and Information Security (ASIACRYPT 2017), December 2017.
41. Per Austrin, Kai-Min Chung, Mohammad Mahmoody, Rafael Pass and Karn Seth, "On the Impossibility of Cryptography with Tamperable Randomness," Algorithmica, volume 79, number 4, pages 1052-1101, December 2017.
42. Yi-Hsiu Chen, Kai-Min Chung, Ching-Yi Lai, Salil Vadhan and Xiaodi Wu, "Computational Notions of Quantum Min-Entropy," The 7th International Conference on Quantum Cryptography (QCrypt 2017), September 2017.
43. Kai-Min Chung, Seth Pettie, and Hsin-Hao Su, "Distributed algorithms for the Lovász local lemma and graph coloring," Distributed Computing, volume 30, number 4, pages 261-280, August 2017.
44. Kai-Min Chung, Yaoyun Shi and Xiaodi Wu, "General Randomness Amplification with Non-signaling Security," The 20th Annual Conference on Quantum Information Processing (QIP2017), January 2017. :::icon
45. Prabhanjan Ananth, Yu-Chi Chen, Kai-Min Chung, Huijia Lin, Wei-Kai Lin, "Delegating RAM Computations with Adaptive Soundness and Privacy," 14th IACR Theory of Cryptography Conference - TCC 2016-B, November 2016.
46. Kai-Min Chung, Rafael Pass, Karn Seth, "Non-Black-Box Simulation from One-Way Functions And Applications to Resettable Security," SIAM Journal on Computing, volume 45, number 2, pages 415-458, May 2016.
47. Yu-Chi Chen and Sherman S. M. Chow and Kai-Min Chung and Russell W. F. Lai and Wei-Kai Lin and Hong-Sheng Zhou, "Cryptography for Parallel RAM from Indistinguishability Obfuscation," The 7th Innovations in Theoretical Computer Science (ITCS 2016), January 2016. :::icon
48. Elette Boyle and Kai-Min Chung and Rafael Pass, "Oblivious Parallel RAM and Applications," The 13th IACR Theory of Cryptography Conference (TCC2016), January 2016. :::icon
49. Kai-Min Chung and Huijia Lin and Rafael Pass, "Constant-Round Concurrent Zero-knowledge from Indistinguishability Obfuscation," The 35th International Cryptology Conference (CRYPTO), August 2015. :::icon
50. Elette Boyle and Kai-Min Chung and Rafael Pass, "Large-Scale Secure Computation: Multi-party Computation for (Parallel) RAM Programs," The 35th International Cryptology Conference (CRYPTO), August 2015. :::icon
51. Xiaodi Wu and Kai-Min Chung and Henry S. Yuen, "Parallel Repetition for Entangled k-player Games via Fast Quantum Search," Computational Complexity Conference (CCC), June 2015.
52. Kai-Min Chung and Rafael Pass, "Tight Parallel Repetition Theorems for Public-Coin Arguments using KL-divergence," The 12th Theory of Cryptography Conference (TCC), March 2015.
53. Kai-Min Chung and Edward Lui and Rafael Pass, "From Weak to Strong Zero-Knowledge and Applications," The 12th Theory of Cryptography Conference (TCC), March 2015.
54. Kai-Min Chung; Zhenming Liu; Rafael Pass, "Statistically-secure ORAM with Õ (log² n) Overhead," The 20th Annual International Conference on the Theory and Application of Cryptology and Information Security (ASIACRYPT), December 2014. :::icon
55. Per Austrin and Kai-Min Chung and Mohammad Mahmoody and Rafael Pass and Karn Seth, "On the Impossibility of Cryptography with Tamperable Randomness," The 34th International Cryptology Conference (CRYPTO), Lecture Notes in Computer Science, August 2014. :::icon
56. Kai-Min Chung and Seth Pettie and Hsin-Hao Su, "Distributed Algorithms for the Lovász Local Lemma and Graph Coloring," ACM Symposium on Principles of Distributed Computing (PODC), Shlomi Dolev, editor, ACM, July 2014.
57. Kai-Min Chung and Yaoyun Shi and Xiaodi Wu, "Physical Randomness Extractors," The 17th Conference on Quantum Information Processing (QIP), Renato Renner, editor, February 2014, Accepted as a *plenary talk* at the 17th Conference on Quantum Information Processing (QIP) February 2014.
58. Elette Boyle and Kai-Min Chung and Rafael Pass, "On Extractability (a.k.a. Differing-Inputs) Obfuscation," The 11th IACR Theory of Cryptography Conference (TCC), Yehuda Lindell, editor, Springer, February 2014.
59. Kai-Min Chung and Rafail Ostrovsky and Rafael Pass and Muthuramakrishnan Venkitasubramaniam and Ivan Visconti, "4-Round Resettably-Sound Zero Knowledge," The 11th IACR Theory of Cryptography Conference (TCC), Lecture Notes in Computer Science, Yehuda Lindell, editor, Springer, February 2014.
60. Kai-Min Chung and Jonathan Katz and Hong-Sheng Zhou, "Functional Encryption from (Small) Hardware Tokens," The 19th Annual International Conference on the Theory and Application of Cryptology and Information Security (ASIACRYPT), Lecture Notes in Computer Science, Kazue Sako and Palash Sarkar, editor, Springer, pages 120-139, December 2013.
61. Kai-Min Chung, Michael Mitzenmacher, Salil P. Vadhan, "Why Simple Hash Functions Work: Exploiting the Entropy in a Data Stream," ACM Transactions on Algorithms, volume 9, pages 897-945, December 2013.
62. Kai-Min Chung and Rafail Ostrovsky and Rafael Pass and Ivan Visconti, "Simultaneous Resettability from One-Way Functions," The 54th Annual IEEE Symposium on Foundations of Computer Science (FOCS), Omer Reingold, editor, IEEE, pages 60-69, October 2013.
63. Kai-Min Chung and Huijia Lin and Rafael Pass, "Constant-Round Concurrent Zero Knowledge From P-Certificates," The 54th Annual IEEE Symposium on Foundations of Computer Science (FOCS), Omer Reingold, editor, IEEE, pages 50-59, October 2013.
64. Kai-Min Chung and Rafael Pass and Sidharth Telang, "Interactive Coding, Revisited," The 54th Annual IEEE Symposium on Foundations of Computer Science (FOCS), Omer Reingold, editor, IEEE, pages 449-458, October 2013.
65. Kai-Min Chung and Rafael Pass and Karn Seth, "Non-Black-Box Simulation from One-Way Functions And Applications to Resettable Security," The 45th ACM Symposium on Theory of Computing (STOC), Dan Boneh and Tim Roughgarden and Joan Feigenbaum, editor, ACM, pages 231-240, June 2013. :::icon
66. Kai-Min Chung and Daniel Dadush and Feng-Hao Liu and Chris Peikert, "On the Lattice Smoothing Parameter Problem," The 28nd Annual IEEE Conference on Computational Complexity (CCC), Chris Umans, editor, IEEE Computer Society, pages 230-241, June 2013.
67. Eleanor Birrell and Kai-Min Chung and Rafael Pass and Sidharth Telang, "Randomness-Dependent Message Security," The 10th IACR Theory of Cryptography Conference (TCC), Lecture Notes in Computer Science, volume 7785, Amit Sahai, editor, Springer, pages 700-720, March 2013.
68. Kai-Min Chung and Rafael Pass, "Parallel Repetition Theorems for Interactive Arguments," SIGACT News, volume 44, number 1, pages 50-69, March 2013, Complexity Theory Column
69. Kai-Min Chung and Edward Lui and Rafael Pass, "Can Theories be Tested? A Cryptographic Treatment of Forecast Testing," The 4th Innovations in Theoretical Computer Science (ITCS), Robert D. Kleinberg, editor, ACM, pages 47-56, January 2013.
70. Kai-Min Chung and Huijia Lin and Mohammad Mahmoody and Rafael Pass, "On the Power of Nonuniformity in Proofs of Security," The 4th Innovations in Theoretical Computer Science (ITCS), Robert D. Kleinberg, editor, ACM, pages 389-400, January 2013.
71. Kai-Min Chung and Rafael Pass and Wei-Lung Dustin Tseng, "The Knowledge Tightness of Parallel Zero-Knowledge," The 9th IACR Theory of Cryptography Conference (TCC), Lecture Notes in Computer Science, volume 7194, Lecture Notes in Computer Science, Ronald Cramer, editor, Springer, pages 512-529, March 2012.
72. Kai-Min Chung and Henry Lam and Zhenming Liu and Michael Mitzenmacher, "Chernoff-Hoeffding Bounds for Markov Chains: Generalized and Simplified," The 28th International Symposium on Theoretical Aspects of Computer Science (STACS), volume 14, LIPIcs, Christoph Dürr, editor, Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, pages 124-135, February 2012.
73. Kai-Min Chung and Rafael Pass, "The Randomness Complexity of Parallel Repetition," The 52nd Annual IEEE Symposium on Foundations of Computer Science (FOCS), Rafail Ostrovsky, editor, IEEE, pages 658-667, October 2011.
74. Kai-Min Chung and Yael Tauman Kalai and Feng-Hao Liu and Ran Raz, "Memory Delegation," The 31st Annual Cryptology Conference (CRYPTO), Lecture Notes in Computer Science, volume 6841, Lecture Notes in Computer Science, Phillip Rogaway, editor, Springer, pages 151-168, August 2011.
75. Kai-Min Chung and Omer Reingold and Salil Vadhan, "S-t Connectivity on Digraphs with a Known Stationary Distribution," ACM Transactions on Algorithms, volume 7, number 3, pages 30:1-21, July 2011.
76. Ching-Hua Yu and Sherman S.M. Chow and Kai-Min Chung and Feng-Hao Liu, "Efficient Secure Two-Party Exponentiation," The Cryptographer's Track at the RSA Conference (CT-RSA), Lecture Notes in Computer Science, volume 6558, Lecture Notes in Computer Science, Aggelos Kiayias, editor, Springer, pages 17-32, February 2011.
77. Kai-Min Chung, Feng-Hao Liu, Chi-Jen Lu, and Bo-Yin Yang, "Efficient String-commitment From Weak Bit-commitment," In Proceedings of the 16th Annual International Conference on the Theory and Application of Cryptology and Information Security (ASIACRYPT), December 2010.
78. Kai-Min Chung and Yael Tauman Kalai and Salil P. Vadhan, "Improved Delegation of Computation Using Fully Homomorphic Encryption," The 30th Annual Cryptology Conference (CRYPTO), Lecture Notes in Computer Science, volume 6223, Lecture Notes in Computer Science, Tal Rabin, editor, Springer, pages 483-501, August 2010.
79. Vladimir Braverman and Kai-Min Chung and Zhenming Liu and Michael Mitzenmacher and Rafail Ostrovsky, "AMS Without 4-Wise Independence on Product Domains," The 26th International Symposium on Theoretical Aspects of Computer Science (STACS), LIPIcs, Jean-Yves Marion and Thomas Schwentick, editor, Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, pages 119-130, March 2010.
80. Kai-Min Chung and Feng-Hao Liu, "Parallel Repetition Theorems for Interactive Arguments," The 7th IACR Theory of Cryptography Conference (TCC), Lecture Notes in Computer Science, volume 5978, Lecture Notes in Computer Science, Daniele Micciancio, editor, Springer, pages 19-36, February 2010, Best Student Paper Award; Invited to Journal of Cryptology
81. Kai-Min Chung and Salil Vadhan, "Tight Bounds for Hashing Block Sources," Approximation, Randomization and Combinatorial Optimization. Algorithms and Techniques, 12th International Workshop, RANDOM 2008 (RANDOM),, Lecture Notes in Computer Science, volume 5171, Lecture Notes in Computer Science, Ashish Goel and Klaus Jansen and Jos{\\\\\\\\'e} D. P. Rolim and Ronitt Rubinfeld, editor, Springer, pages 357-370, August 2008.
82. Kai-Min Chung and Omer Reingold and Salil Vadhan, "S-t Connectivity on Digraphs with a Known Stationary Distribution," The 22nd Annual IEEE Conference on Computational Complexity (CCC), Pierre McKenzie, editor, IEEE Computer Society, pages 236-249, June 2007.
83. Kai-Min Chung and Wei-Chun Kao and Chia-Liang Sun and Chih-Jen Lin, "Decomposition Methods for Linear Support Vector Machines," Neural Computation, volume 16, number 8, pages 1689-1704, August 2004.
84. Kai-Min Chung and Hsueh-I Lu, "An Optimal Algorithm for Maximum-Density Segment Problem," SIAM Journal on Computing, volume 34, number 2, pages 373-387, March 2004.
85. Kai-Min Chung and Wei-Chun Kao and Chia-Liang Sun and Li Lun Wang, Chih-Jen Lin, "Radius Margin Bounds for Support Vector Machines with RBF Kernel," Neural Computation, volume 15, number 11, pages 2643-2681, November 2003.
86. Kai-Min Chung and Hsueh-I Lu, "An Optimal Algorithm for Maximum-Density Segment Problem," The 11th Annual European Symposium on Algorithms (ESA), Lecture Notes in Computer Science, volume 2832, Lecture Notes in Computer Science, Giuseppe Di Battista and Uri Zwick, editors, Springer, pages 136-147, September 2003.
 
 
bg