Page 92 - profile2014.indd

助研究員
鐘楷閔 Kai-Min Chung

Assistant Research Fellow
Ph.D., Computer Science, Harvard University
Tel: +886-2-2788-3799 ext. 1716 Fax: +886-2-2782-4814
Email: kmchung@iis.sinica.edu.tw
http://www.iis.sinica.edu.tw/pages/kmchung

● Ph.D., Computer Science, Harvard Research Description
University, United States (2005/9
- 2011/3) My research lies in the eld of Cryptography, and I have a broad interest in theoretical computer

● B.S., Computer Science and In- science. Cryptography aims to (i) model desirable security tasks that often seem paradoxical at

formation Engineering, National rst glance, and (ii) search for mathematically-rigorous assumptions and constructions to prova-
Taiwan University, Taiwan (1996/9 bly realize these tasks. In addition to Cryptography, I am also excited about investigating subjects
- 2003/6) from other elds through a “cryptographic lens”, as well as conducting research in theoretical

● Assistant Research Fellow, computer science in general through collaborations.
Academia Sinica, Institute of • Zero-knowledge Proofs: Zero-knowledge proofs are a cornerstone of Cryptography that allows
Information Science, Taiwan
(2013/9–present) a party to prove the validity of a statement (e.g., his identity) without revealing any additional

information. We have demonstrated the rst constant-round concurrent zero-knowledge proofs
● Postdoctoral Research Associate, based on a new assumption, and the rst simultaneous resettable zero-knowledge proofs based

Cornell University, Department of on the minimal assumption of one-way functions, both of which make progress on decades-old
Computer Science, United States open problems.
(2010/8–2013/8)
• Physical Randomness Extractors: Randomness is a precious resource pervasive in our daily life,
but how can we be certain that any source of randomness is indeed truly random? Here, we
propose a new framework of physical randomness extractors for extracting randomness from
physical systems, combining ideas from cryptography, complexity theory, and quantum information. Our framework circumvents the hard-to-
enforce independence assumption from existing answers, and provably relies on the minimal assumption of a source with only constant bits of
(min-) entropy. Our result also implies an optimal dichotomy theorem for experimentally certifying truly random events in physics.

• Cryptographic Lens: We can shed new light on subjects beyond Cryptography by using a cryptographic lens. For interactive coding from
coding theory, we have introduced knowledge-preserving interactive coding to formalize its desirable security properties. For forecast testing
studied in economics, we provide a comprehensive cryptographic treatment to investigate its feasibility in the computational setting.

Publications

1. Kai-Min Chung and Feng-Hao Liu, “Parallel Repetition The- Science (FOCS), Omer Reingold, editor, IEEE, pages 50-59,
orems for Interactive Arguments,” The 7th IACR Theory of October 2013.
Cryptography Conference (TCC), Lecture Notes in Computer
6. Kai-Min Chung and Rafail Ostrovsky and Rafael Pass and
Science, volume 5978, Lecture Notes in Computer Science,
Ivan Visconti, “Simultaneous Resettability from One-Way
Daniele Micciancio, editor, Springer, pages 19-36, February
Functions,” The 54 Annual IEEE Symposium on Foundations
th
2010, Best Student Paper Award; Invited to Journal of Cryp-
of Computer Science (FOCS), Omer Reingold, editor, IEEE,
tology.
pages 60-69, October 2013.
2. Kai-Min Chung and Rafael Pass, “The Randomness Com-
nd
plexity of Parallel Repetition,” The 52 Annual IEEE Sym- 7. Kai-Min Chung and Rafael Pass and Sidharth Telang, “Inter-
th
posium on Foundations of Computer Science (FOCS), Rafail active Coding, Revisited,” The 54 Annual IEEE Symposium
Ostrovsky, editor, IEEE, pages 658-667, October 2011. on Foundations of Computer Science (FOCS), Omer Rein-
gold, editor, IEEE, pages 449-458, October 2013.
3. Kai-Min Chung and Rafael Pass, “Parallel Repetition Theo- 8. Elette Boyle and Kai-Min Chung and Rafael Pass, “Extracta-
rems for Interactive Arguments,” SIGACT News, volume 44, ble Obfuscation and Applications,” to appear in The 11 IACR
th
number 1, pages 50-69, March 2013, Complexity Theory Col- Theory of Cryptography Conference (TCC), Yehuda Lindell,
umn.
editor, Springer.
4. Kai-Min Chung and Rafael Pass and Karn Seth, “Non-Black-
9. Kai-Min Chung and Seth Pettie and Hsin-Hao Su, “Distrib-
Box Simulation from One-Way Functions And Applications
th
to Resettable Security,” The 45 ACM Symposium on Theory uted Algorithms for the Lovász Local Lemma and Graph Col-
oring,” to appear in ACM Symposium on Principles of Distrib-
of Computing (STOC), Dan Boneh and Tim Roughgarden and
uted Computing (PODC), Shlomi Dolev, editor, ACM.
Joan Feigenbaum, editor, ACM, pages 231-240, June 2013.
10. Kai-Min Chung and Yaoyun Shi and Xiaodi Wu, “Physical
5. Kai-Min Chung and Huijia Lin and Rafael Pass, “Constant-

Round Concurrent Zero Knowledge From P-Certificates,” The Randomness Extractors,” Accepted as a *plenary talk* at the
th
54 Annual IEEE Symposium on Foundations of Computer 17 Conference on Quantum Information Processing (QIP).
th
92 研究人員 Research Faculty