Distinguished Research Fellow
Institute of
Information Science, Academia Sinica
Room 716 New
Building
No 128,
Academia Road, Section 2
Nankang, Taipei
11529, Taiwan
kmchung [at] iis.sinica.edu.tw
About
me
I am a researcher at Institute of Information
Science (IIS), Academia
Sinica. Prior to joining IIS, I was a postdoc at Cornell University working under the
supervision of Rafael Pass and
supported by Simons
Postdoctoral Fellowship. Before that, I received my Ph.D. in computer
science at Harvard University, where I
was very fortunate to have Salil
Vadhan as my advisor. My research interests are in the fields of (quantum)
cryptography, complexity theory, and pseudorandomness.
Here is my CV (updated August 20th, 2024).
News
I am looking for
talented and self-motivated students in theoretical computer science. If you
are interested in working with me, please do not hesitate to contact me via
email and/or apply for my research assistant position here.
People who are interested in joining the lab, please find related information here.
We are also recruiting postdocs with
multiple opening positions! Please see here for details and apply!
Course
113-1 [CSIE 5037] Theoretical Aspects of Modern Cryptography [course website]
111-2 [CSIE 5037] Theoretical Aspects of Modern Cryptography [course website]
110-2 [CSIE 5037] Theoretical Aspects of Modern Cryptography [course website]
109-2 [CSIE 5037] Theoretical Aspects of Modern Cryptography [course website]
Research
Ph.D.
Thesis
Efficient
Parallel Repetition Theorems with Applications to Security Amplification,
Ph.D.
Thesis (March 2011)
[
pdf ]
Conference Publications
On Central Primitives for Quantum Cryptography with Classical Communication,
CRYPTO, 2024
[ arxiv version ]
Best-of-Both-Worlds Multiparty Quantum Computation with
Publicly Verifiable Identifiable Abort,
Eurocrypt, 2024
[ arxiv version ]
On the (Im)possibility of Time-Lock Puzzles in the Quantum Random Oracle Model,
ASIACRYPT, 2023
[ ePrint version ]
AutoQ: An Automata-based Quantum Circuit Verifier,
CAV, 2023
On the Impossibility of General Parallel Fast-forwarding of Hamiltonian Simulation,
CCC, 2023
[ arxiv version ]
An Automata-based Framework for Verification and Bug Hunting in Quantum Circuits,
PLDI, 2023 (Distinguished Paper Award)
[ arxiv version ]
Black-Box Separations for Non-Interactive Commitments in a Quantum World,
Eurocrypt, 2023
[ ePrint version ]
Collusion-Resistant Functional Encryption for RAMs,
ASIACRYPT, 2022
[ ePrint version ]
On the Impossibility of Key Agreements from Quantum Random Oracles,
CRYPTO, 2022
[ ePrint version ]
Post-Quantum Simulatable Extraction with Minimal Assumptions: Black-Box and Constant-Round,
CRYPTO, 2022
[ arXiv version ]
Constant-round Blind Classical Verification of Quantum Sampling,
Eurocrypt, 2022
[ arXiv version ]
A Note on the Post-Quantum Security of (Ring) Signatures,
PKC, 2022
[ ePrint version ]
On the Impossibility of Post-Quantum Black-Box Zero-Knowledge in Constant Rounds,
FOCS, 2021 ; QCrypt, 2021 ; QIP, 2022
[ arXiv version ]
On the Concurrent Composition of Quantum Zero-Knowledge,
Round Efficient Secure Multiparty Quantum Computation with Identifiable Abort,
Game-Theoretic Fairness Meets Multi-Party Protocols: The Case of Leader Election,
A Black-Box Approach to Post-Quantum Zero-Knowledge in Constant Rounds,
Sample Efficient Algorithms for Learning Quantum Channels in PAC Model and the Approximate State Discrimination Problem,
On the Compressed-Oracle Technique, and Post-Quantum Security of Proofs of Sequential Work,
Classical Verification of Quantum Computations with Efficient Verifier,
Tight Quantum Time-Space Tradeoffs for Function Inversion,
On the Hardness of Massively Parallel Computation,
Lower Bounds for Function Inversion with Quantum Advice,
MPC for MPC: Secure Computation on a Massively Parallel Computing Architecture,
On the Need for Large Quantum Depth,
Adaptively Secure Garbling Schemes for Parallel Computations,
Interactive Leakage Chain Rule for Quantum Min-entropy,
A Quantum-Proof Non-Malleable Extractor With Application to Privacy Amplification against Active Quantum Adversaries,
On Quantum Advantage in Information Theoretic Single-Server PIR,
Eurocrypt, 2019
[ ePrint
version ]
Foundations of Differentially Oblivious Algorithms,
with T-H. Hubert Chan, Bruce Maggs
and Elaine Shi
SODA 2019
[ ePrint
version ]
On the Algorithmic Power of Spiking Neural
Networks,
with Chi-Ning Chou and Chi-Jen Lu
ITCS 2019
[ arXiv version ]
Game Theoretic Notions of Fairness in
Multi-Party Coin Toss,
with Yue Guo, Wei-Kai Lin, Rafael Pass and Elaine Shi
TCC 2018
On the Complexity of Simulating Auxiliary
Input,
with Yi-Hsiu
Chen and Jyun-Jie Liao
EUROCRYPT 2018
On the Depth of Oblivious Parallel RAM,
with T-H. Hubert Chan and Elaine Shi
ASIACRYPT 2017
Computational Notions of Quantum
Min-Entropy,
with Yi-Hsiu Chen, Ching-Yi Lai, Salil Vadhan and Xiaodi Wu
QCrypt 2017
[ Conference version ]
General Randomness Amplification with
Non-signaling Security,
with
Yaoyun Shi and Xiaodi Wu
QIP 2017
[ Conference
version ]
Delegating RAM Computations with Adaptive Soundness and Privacy,
with
Prabhanjan Ananth, Yu-Chi Chen, Huijia Lin and Wei-Kai Lin
TCC 2016-B
[ Conference version ]
Cryptography
for Parallel RAM from Indistinguishability Obfuscation,
with
Yu-Chi Chen, Sherman S. M. Chow, Russell W. F. Lai, Wei-Kai Lin and Hong-Sheng
Zhou
ITCS 2016
Oblivious
Parallel RAM and Applications,
with
Elette Boyle and Rafael Pass
TCC
2016
Constant-Round
Concurrent Zero-knowledge from Indistinguishability Obfuscation,
with Huijia
Rachel Lin and Rafael Pass
CRYPTO
2015
Large-Scale
Secure Computation: Multi-party Computation for (Parallel) RAM Programs,
with
Elette Boyle and Rafael Pass
CRYPTO
2015
Parallel
Repetition for Entangled k-player Games via Fast Quantum Search
with Xiaodi Wu and Henry S. Yuen
CCC
2015
Tight
Parallel Repetition Theorems for Public-Coin Arguments using KL-divergence
with
Rafael Pass
TCC
2015
From
Weak to Strong Zero-Knowledge and Applications,
with
Edward Lui and Rafael Pass
TCC
2015
On the Impossibility of Cryptography with Tamperable Randomness,
with Per Austrin, Mohammad
Mahmoody, Rafael Pass and Karn Seth
CRYPTO
2014
Distributed Algorithms for the Lovsz Local Lemma and Graph Coloring,
with Seth Pettie and Hsin-Hao Su
PODC 2014
Statistically-secure
ORAM with Õ (log² n) Overhead,
with Zhenming Liu and
Rafael Pass
ASIACRYPT 2014
Physical Randomness Extractors: Generating Random Numbers with Minimal Assumptions,
with Yaoyun Shi and Xiaodi Wu
QIP 2014
On Extractability (a.k.a.
Differing-Inputs) Obfuscation,
with Elette Boyle and Rafael Pass,
TCC 2014
4-Round Resettably-Sound
Zero Knowledge,
with Rafail Ostrovsky and Rafael Pass
and Muthuramakrishnan
Venkitasubramaniam and Ivan
Visconti,
TCC 2014
Constant-round Concurrent Zero-knowledge
from Falsifiable Assumptions,
with Huijia Rachel Lin, and Rafael Pass
FOCS 2013
[ Conference version, ePrint version ]
Interactive Coding, Revisited,
with Rafael Pass and Sidharth Telang
FOCS 2013
[ Conference version, ePrint version ]
Non-black-box Simulation from One-way
Functions and Applications to Resettable Security,
with Karn Seth and Rafael Pass
STOC 2013
Simultaneous Resettability
from One-Way Functions,
with Rafail Ostrovsky, Rafael Pass and Ivan Visconti
FOCS 2013
Functional Encryption from (Small)
Hardware Tokens,
with Jonathan Katz and Hong-Sheng
Zhou,
Asiacrypt 2013
On the Lattice Smoothing Parameter
Problem,
with Daniel
Dadush, Feng-Hao Liu, and Chris Peikert
CCC 2013
Randomness-Dependent Message Security,
with Eleanor Birrell, Rafael Pass, and Sidharth Telang
ITCS 2013
Can theories be tested?: a cryptographic treatment of forecast testing,
with Edward Lui, and Rafael Pass
ITCS 2013
On the Power of Non-uniform Proofs of
Security,
with Huijia Rachel Lin, Mohammad Mahmoody, and Rafael Pass
ITCS 2013
Chernoff-Hoeffding Bounds for Markov Chains: Generalized and
Simplified,
with Henry Lam, Zhenming Liu, and Michael Mitzenmacher
STACS 2012:
[ arXiv version ]
The Knowledge Tightness of Parallel Zero-Knowledge,
with Rafael Pass and Wei-Lung Dustin Tseng
TCC 2012
The Randomness Complexity of Parallel Repetition,
with Rafael Pass
FOCS 2011
Memory Delegation,
with Yael Tauman Kalai, Feng-Hao Liu, and Ran Raz
CRYPTO 2011
Efficient Secure Two-Party Exponentiation,
with Ching-Hua Yu, Sherman S.M. Chow, and Feng-Hao Liu
CT-RSA 2011
Improved Delegation of Computation Using Fully Homomorphic Encryption,
with Yael Tauman Kalai, and Salil Vadhan
CRYPTO 2010
Efficient String-Commitment from Weak Bit-Commitment,
with Feng-Hao Liu, Chi-Jen Lu,
and Bo-Yin Yang
AsiaCrypt 2010
[ Conference
version, Draft full version ] (See
also my Ph.D. thesis)
Parallel Repetition Theorems for
Interactive Arguments,
with Feng-Hao Liu
TCC 2010, Best Student Paper Award
[ Conferece version ] (See my Ph.D. thesis
for full details)
AMS Without 4-Wise Independence on Product
Domains,
with Vladmir
Braverman, Zhenming Liu,
Michael Mitzenmacher, and Rafail Ostrovsky
STACS 2010 (this paper is a result of a
merge)
[ Conference
version, Original version ]
Tight Bounds for Hashing Block Sources,
with Salil P. Vadhan
RANDOM 2008
S-T Connectivity on Digraphs with a Known
Stationary Distribution,
with Omer Reingold,
and Salil P. Vadhan
CCC 2007
Decomposition Methods for Linear Support
Vector Machines,
with Wei-Chun Kao, Chia-Liang Sun, and Chih-Jen Lin
ICASSP 2003
An Optimal Algorithm for the
Maximum-Density Segment Problem,
with Hsueh-I Lu
ESA 2003
Radius Margin Bounds for Support Vector
Machines with the RBF Kernel,
with Wei-Chun Kao, Chia-Liang Sun, Li-Lun Wang, and Chih-Jen Lin
ICONIP 2002
Journal Publications
On the Need for Large Quantum Depth,
The Journal of the ACM (JACM), volume 70, number 6, pages 1-38, February, 2023
[ Full version ]
Foundations of Differentially Oblivious Algorithms,
The Journal of the ACM (JACM), volume 69, number 4, pages 1-49, August, 2022. Featured Article
[ Full version ]
Cryptography with Disposable Backdoors,
Cryptography, 3(3): 22, 2019
[ Full version ]
Quantum encryption and generalized Shannon impossibility,
On Statistically-Secure Quantum Homomorphic Encryption,
Space-efficient classical and quantum algorithms for the shortest vector problem,
On the Impossibility of Cryptography, with Tamperable Randomness,
with Per Austrin and Mohammad
Mahmoody and Rafael Pass
and Karn Seth,
Algorithmica
2017
[ Full version ]
Distributed Algorithms for the Lovsz Local Lemma and Graph Coloring,
with Seth Pettie and Hsin-Hao Su,
Distributed Computing 2017
[ Full
version ]
Non-black-box Simulation from One-way
Functions and Applications to Resettable Security,
with Karn Seth, and Rafael Pass
SIAM J. on Computing 2016
[ Full version ]
Parallel repetition theorems for interactive arguments,
with Rafael Pass
SIGACT News 44(1): 50-69 (2013)
Why Simple Hash Functions Work: Exploiting the Entropy in a Data Stream,
with Michael Mitzenmacher, and Salil P. Vadhan
Theory of Computing 9: 897-945 (2013)
[ Full version ]
S-T Connectivity on Digraphs with a Known
Stationary Distribution,
with Omer Reingold,
and Salil P. Vadhan
ACM Transactions on Algorithms
2011
[ Full version ]
An Optimal Algorithm for the
Maximum-Density Segment Problem,
with Hsueh-I Lu
SIAM J. on Computing 2004
[ Full version ]
Decomposition Methods for Linear Support
Vector Machines,
with Wei-Chun Kao, Chia-Liang Sun, and Chih-Jen Lin
Neural Computation 2004
[ Full version ]
Radius Margin Bounds for Support Vector
Machines with the RBF Kernel,
with Wei-Chun Kao, Chia-Liang Sun, Li-Lun Wang, and Chih-Jen Lin
Neural Computation 2003
[ Full version ]
Manuscripts
Leakage
Chain Rule and Superdense Coding
with
Yi-Hsiu Chen, Ching-Yi Lai and Xiaodi Wu
Manuscript.
[ Full
version ]
Multi-Source Randomness Extractors Against Quantum Side Information, and their Applications,
with Xin Li, and Xiaodi Wu
Manuscript.
[ arXiv version ]
Unprovable Security of Two-Message Zero-Knowledge,
with
Edward Lui, Mohammad Mahmoody, and Rafael Pass
Manuscript.
[ Full
version ]
A
Simple ORAM,
with
Rafael Pass,
Manuscript.
[ Full version ]
Book Chapter
When Simple Hash Functions Suceffice
with
Michael Mitzenmacher and Salil Vadhan
Beyond the Worst-Case Analysis of Algorithms, Chapter 26.
[ Full version ]
Professional Activities
Program Committee Chair
The 30th Annual International Conference on the Theory and Applications of Cryptology and Information Security
(Asiacrypt 2024)
The 4th Information-Theoretic Cryptography conference (ITC 2023)
Program Committees
The 42nd Annual International Cryptology Conference (CRYTPO 2023)
The 26th Annual Conference on Quantum Information Processing (QIP 2023)
The 63rd Annual IEEE Symposium on Foundations of Computer Science (FOCS 2022)
The 54th Annual ACM Symposium on Theory of Computing (STOC 2022)
The 17th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2022)
The 3rd Conference on Information-Theoretic Cryptography (ITC 2022)
The 2nd Conference on Information-Theoretic Cryptography (ITC 2021)
The 27th Annual International Conference on The Theory and Application of Cryptology and Information Security (Asiacrypt 2021)
The 40th Annual International Conference on the Theory and Applications of Cryptographic Techniques (EUROCRYPT 2021)
The 18th Theory of Cryptography Conference (TCC 2020)
The Conference on Information-Theoretic Cryptography (ITC 2020)
The 23rd International Conference on the Theory and Practice of Public-Key Cryptography (PKC 2020)
The 17th Theory of Cryptography Conference (TCC 2019)
The 38th Annual International Cryptology Conference (CRYTPO 2019)
The 38th Annual International Conference
on the Theory and Applications of Cryptographic Techniques (EUROCRYPT 2019)
The 29th International Symposium on
Algorithms and Computation (ISAAC
2018)
The 8th International Conference on
Quantum Cryptography (QCrypt
2018)
The 21st International Conference on the
Theory and Practice of Public-Key Cryptography (PKC 2018)
The 23rd Annual International Conference
on The Theory and Application of Cryptology and Information Security (ASIACRYPT 2017)
The 15th IACR Theory of Cryptography
Conference (TCC 2017)
The 32nd Computational Complexity
Conference (CCC 2017)
The 14th IACR Theory of Cryptography
Conference-B (TCC 2016-B)
The 21st Annual International Conference
on The Theory and Application of Cryptology and Information Security (ASIACRYPT 2015)
The 26th International Symposium on
Algorithms and Computation (ISAAC
2015).
The 12th Theory of Cryptography Conference
(TCC 2015)
The 20th Annual International Conference
on The Theory and Application of Cryptology and Information Security (ASIACRYPT 2014)
The 11th IACR Theory of Cryptography
Conference (TCC 2014)
The 33rd International Cryptology
Conference (CRYPTO 2013)
Teaching
Teaching Fellow for CS225 Pseudorandomness, Spring 07 and 09, taught by Prof. Salil Vadhan
Received Certificate of Distinction in
Teaching in Spring 09