Chinese
English
Associate Research Fellow  |  Chung, Kai-Min  
 
contact
vita
education
experience
interests
descriptions
activities
invited_talk
invited_visit
publications
supervised
Personal (New window)
 
 
 
 
 
Publications
 
1. Per Austrin, Kai-Min Chung, Mohammad Mahmoody, Rafael Pass and Karn Seth, "On the Impossibility of Cryptography with Tamperable Randomness," to appear in Algorithmica.
2. Yi-Hsiu Chen, Kai-Min Chung, Ching-Yi Lai, Salil Vadhan and Xiaodi Wu, "Computational Notions of Quantum Min-Entropy," to appear in The 7th International Conference on Quantum Cryptography (QCrypt 2017),.
3. T-H. Hubert Chan, Kai-Min Chung, Elaine Shi, "On the Depth of Oblivious Parallel RAM," to appear in The 23rd Annual International Conference on the Theory and Applications of Cryptology and Information Security (ASIACRYPT 2017),.
4. 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.
5. Prabhanjan Ananth, Yu-Chi Chen, Kai-Min Chung, Huijia Lin and Wei-Kai Lin, "Delegating RAM Computations with Adaptive Soundness and Privacy," Fourteenth IACR Theory of Cryptography Conference - TCC 2016-B, November 2016.
6. 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.
7. 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 via Indistinguishability Obfuscation," The 7th Innovations in Theoretical Computer Science (ITCS 2016), January 2016.
8. Elette Boyle and Kai-Min Chung and Rafael Pass, "Oblivious Parallel RAM and Applications," The 13th IACR Theory of Cryptography Conference (TCC2016), January 2016.
9. 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.
10. 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.
11. 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.
12. 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.
13. 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.
14. Prabhanjan Ananth, Yu-Chi Chen, Kai-Min Chung, Huijia Lin and Wei-Kai Lin, "Delegating RAM Computations with Adaptive Soundness and Privacy,", Cryptology ePrint Archive, Report 2015/1082. 2015.
15. 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.
16. 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.
17. 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.
18. 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.
19. 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.
20. 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.
21. 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.
22. 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.
23. 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.
24. 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.
25. 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.
26. 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.
27. 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.
28. 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.
29. 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
30. 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.
31. 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.
32. 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.
33. 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.
34. 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.
35. 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.
36. 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.
37. 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.
38. 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.
39. 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.
40. 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
41. 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.
42. 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.
43. 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.
44. 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.
45. 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.
46. 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