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

 

News | Research | Professional Activities | Past Teaching

 

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 Mar. 18, 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

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
  •  

    Best-of-Both-Worlds Multiparty Quantum Computation with Publicly Verifiable Identifiable Abort,

    with Mi-Ying Huang, Er-Cheng Tang, Jiapeng Zhang
    Eurocrypt, 2024

    arxiv version ]

    On the (Im)possibility of Time-Lock Puzzles in the Quantum Random Oracle Model,

    with Abtin Afshar, Yao-Ching Hsieh, Yao-Ting Lin, Mohammad Mahmoody
    ASIACRYPT, 2023

    ePrint version ]

    AutoQ: An Automata-based Quantum Circuit Verifier,

    with Yu-Fang Chen, Ondřej Lengál, Jyun-Ao Lin, Wei-Lun Tsai, Di-De Yen
    CAV, 2023

    On the Impossibility of General Parallel Fast-forwarding of Hamiltonian Simulation,

    with Nai-Hui Chia, Yao-Ching Hsieh, Han-Hsuan Lin, Yao-Ting Lin, Yu-Ching Shen
    CCC, 2023

    arxiv version ]

    An Automata-based Framework for Verification and Bug Hunting in Quantum Circuits,

    with Yu-Fang Chen, Ondřej Lengál, Jyun-Ao Lin, Wei-Lun Tsai, Di-De Yen
    PLDI, 2023 (Distinguished Paper Award)

    arxiv version ]

    Black-Box Separations for Non-Interactive Commitments in a Quantum World,

    with Yao-Ting Lin, Mohammad Mahmoody
    Eurocrypt, 2023

    ePrint version ]

    Collusion-Resistant Functional Encryption for RAMs,

    with Prabhanjan Ananth, Xiong Fan, Luowen Qian
    ASIACRYPT, 2022

    ePrint version ]

    On the Impossibility of Key Agreements from Quantum Random Oracles,

    with Per Austrin, Hao Chung, Shiuan Fu, Yao-Ting Lin, Mohammad Mahmoody
    CRYPTO, 2022

    ePrint version ]

    Post-Quantum Simulatable Extraction with Minimal Assumptions: Black-Box and Constant-Round,

    with Nai-Hui Chia, Xiao Liang and Takashi Yamakawa
    CRYPTO, 2022

    arXiv version ]

    Constant-round Blind Classical Verification of Quantum Sampling,

    with Yi Lee, Han-hsuan Lin and Xiaodi Wu
    Eurocrypt, 2022

    arXiv version ]

    A Note on the Post-Quantum Security of (Ring) Signatures,

    with Rohit Chatterjee, Xiao Liang and Giulio Malavolta
    PKC, 2022

    ePrint version ]

    On the Impossibility of Post-Quantum Black-Box Zero-Knowledge in Constant Rounds,

    with Nai-Hui Chia, Qipeng Liu and Takashi Yamakawa
    FOCS, 2021 ; QCrypt, 2021 ; QIP, 2022

    arXiv version ]

     

    On the Concurrent Composition of Quantum Zero-Knowledge,

    with Prabhanjan Ananth and Rolando L. La Placa
    CRYPTO, 2021

    ePrint version ]

     

    Round Efficient Secure Multiparty Quantum Computation with Identifiable Abort,

    with Bar Alon, Hao Chung, Mi-Ying Huang, Yi Lee and Yu-Ching Shen
    CRYPTO, 2021

    ePrint version ]

     

    Game-Theoretic Fairness Meets Multi-Party Protocols: The Case of Leader Election,

    with T-H. Hubert Chan, Ting Wen and Elaine Shi
    CRYPTO, 2021

    ePrint version ]

     

    A Black-Box Approach to Post-Quantum Zero-Knowledge in Constant Rounds,

    with Nai-Hui Chia and Takashi Yamakawa
    CRYPTO, 2021

    ePrint version ]

     

    Sample Efficient Algorithms for Learning Quantum Channels in PAC Model and the Approximate State Discrimination Problem,

    with Han-hsuan Lin
    TQC, 2021

    arXiv version ]

     

    On the Compressed-Oracle Technique, and Post-Quantum Security of Proofs of Sequential Work,

    with Serge Fehr, Yu-Hsuan Huang and Tai-Ning Liao
    Eurocrypt, 2021 ; QCrypt, 2021

    arXiv version ]

    Classical Verification of Quantum Computations with Efficient Verifier,

    with Nai-Hui Chia and Takashi Yamakawa
    TCC, 2020

    arXiv version ]

    Tight Quantum Time-Space Tradeoffs for Function Inversion,

    with Siyao Guo, Qipeng Liu and Luowen Qian
    FOCS, 2020

    arXiv version ]

    On the Hardness of Massively Parallel Computation,

    with Kuan-Yi Ho and Xiaorui Sun
    SPAA, 2020

    Conference version ]

    Lower Bounds for Function Inversion with Quantum Advice,

    with Tai-Ning Liao and Luowen Qian
    ITC, 2020

    arXiv version ]

    MPC for MPC: Secure Computation on a Massively Parallel Computing Architecture,

    On the Need for Large Quantum Depth,

    with Nai-Hui Chia, and Ching-Yi Lai
    STOC, 2020 ; QIP, 2020

    arXiv version ]

    Adaptively Secure Garbling Schemes for Parallel Computations,

    with Luowen Qian
    TCC, 2019

    ePrint version ]

    Interactive Leakage Chain Rule for Quantum Min-entropy,

    with Ching-Yi Lai
    ISIT, 2019

    arXiv version ]

    A Quantum-Proof Non-Malleable Extractor With Application to Privacy Amplification against Active Quantum Adversaries,

    On Quantum Advantage in Information Theoretic Single-Server PIR,

    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

    [ Conference version ]

     

    On the Complexity of Simulating Auxiliary Input,

    with Yi-Hsiu Chen and Jyun-Jie Liao
    EUROCRYPT 2018

    [ Conference version ]

     

    On the Depth of Oblivious Parallel RAM,
    with T-H. Hubert Chan and Elaine Shi
    ASIACRYPT 2017

    [ Conference version ]


    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

    [ Conference version ]

     

    Oblivious Parallel RAM and Applications,

    with Elette Boyle and Rafael Pass

    TCC 2016

    [ Conference version ]

     

    Constant-Round Concurrent Zero-knowledge from Indistinguishability Obfuscation,

    with Huijia Rachel Lin and Rafael Pass

    CRYPTO 2015

    [ Conference version ]

     

    Large-Scale Secure Computation: Multi-party Computation for (Parallel) RAM Programs,

    with Elette Boyle and Rafael Pass

    CRYPTO 2015

    [ Conference version ]

     

    Parallel Repetition for Entangled k-player Games via Fast Quantum Search

    with Xiaodi Wu and Henry S. Yuen

    CCC 2015

    [ Conference version ]

     

    Tight Parallel Repetition Theorems for Public-Coin Arguments using KL-divergence

    with Rafael Pass

    TCC 2015

    [ Conference version ]

     

    From Weak to Strong Zero-Knowledge and Applications,

    with Edward Lui and Rafael Pass

    TCC 2015

    [ Conference version ]


    On the Impossibility of Cryptography with Tamperable Randomness,

    with Per Austrin, Mohammad Mahmoody, Rafael Pass and Karn Seth

    CRYPTO 2014

    [ Conference version ]

     

    Distributed Algorithms for the Lovsz Local Lemma and Graph Coloring,

    with Seth Pettie and Hsin-Hao Su

    PODC 2014

    [ Conference version ]

     

    Statistically-secure ORAM with Õ (log² n) Overhead,

    with Zhenming Liu and Rafael Pass

    ASIACRYPT 2014

    [ Conference version ]

     

    Physical Randomness Extractors: Generating Random Numbers with Minimal Assumptions,

    with Yaoyun Shi and Xiaodi Wu

    QIP 2014

    [ Conference version ]

     

    On Extractability (a.k.a. Differing-Inputs) Obfuscation,

    with Elette Boyle and Rafael Pass,

    TCC 2014

    [ Conference version]

     

    4-Round Resettably-Sound Zero Knowledge,

    with Rafail Ostrovsky and Rafael Pass and Muthuramakrishnan Venkitasubramaniam and Ivan Visconti,

    TCC 2014

    [ Conference version]

     

    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

    [ Conference version ]

     

    Simultaneous Resettability from One-Way Functions,

    with Rafail Ostrovsky, Rafael Pass and Ivan Visconti

    FOCS 2013

    [ Conference version ]

     

    Functional Encryption from (Small) Hardware Tokens,

    with Jonathan Katz and Hong-Sheng Zhou,

    Asiacrypt 2013

    [ Conference version ]

    On the Lattice Smoothing Parameter Problem,

    with Daniel Dadush, Feng-Hao Liu, and Chris Peikert

    CCC 2013

    [ Conference version ]

     

    Randomness-Dependent Message Security,

    with Eleanor Birrell, Rafael Pass, and Sidharth Telang

    ITCS 2013

    [ Conference version ]

     

    Can theories be tested?: a cryptographic treatment of forecast testing,

    with Edward Lui, and Rafael Pass

    ITCS 2013

    [ Conference version ]

     

    On the Power of Non-uniform Proofs of Security,

    with Huijia Rachel Lin, Mohammad Mahmoody, and Rafael Pass

    ITCS 2013

    [ Conference version ]

     

    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

    [ Conference version ]

     

    The Randomness Complexity of Parallel Repetition,

    with Rafael Pass

    FOCS 2011

    [ Conference version ]

     

    Memory Delegation,

    with Yael Tauman Kalai, Feng-Hao Liu, and Ran Raz

    CRYPTO 2011

    [ Conference version ]

     

    Efficient Secure Two-Party Exponentiation,

    with Ching-Hua Yu, Sherman S.M. Chow, and Feng-Hao Liu

    CT-RSA 2011

    [ Conference version ]

     

    Improved Delegation of Computation Using Fully Homomorphic Encryption,

    with Yael Tauman Kalai, and Salil Vadhan

    CRYPTO 2010

    [ Conference version ]

     

    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

    [ Conference version ]

    S-T Connectivity on Digraphs with a Known Stationary Distribution,

    with Omer Reingold, and Salil P. Vadhan

    CCC 2007

    [ Conference version ]

    Decomposition Methods for Linear Support Vector Machines,

    with Wei-Chun Kao, Chia-Liang Sun, and Chih-Jen Lin

    ICASSP 2003

    [ Conference version ]

     

    An Optimal Algorithm for the Maximum-Density Segment Problem,

    with Hsueh-I Lu

    ESA 2003

    [ Conference 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

    ICONIP 2002

    [ Conference version ]

          
  • Journal Publications

  • On the Need for Large Quantum Depth,

    with Nai-Hui Chia and Ching-Yi Lai
    The Journal of the ACM (JACM), volume 70, number 6, pages 1-38, February, 2023
    [ Full version ]

    Foundations of Differentially Oblivious Algorithms,

    with T-H. Hubert Chan, Bruce Maggs and Elaine Shi
    The Journal of the ACM (JACM), volume 69, number 4, pages 1-49, August, 2022. Featured Article
    [ Full version ]

    Cryptography with Disposable Backdoors,

    with Marios Georgiou, Ching-Yi Lai, and Vassilis Zikas,
    Cryptography, 3(3): 22, 2019
    [ Full version ]

    Quantum encryption and generalized Shannon impossibility,

    with Ching-Yi Lai,
    Design, Codes and Cryptography, 87(9): 1961-1972, 2019
    [ Full version ]

    On Statistically-Secure Quantum Homomorphic Encryption,

    with Ching-Yi Lai,
    Quantum Information and Computation, 18(9-10): 785-794, 2018
    [ Full version ]

    Space-efficient classical and quantum algorithms for the shortest vector problem,

    with Ching-Yi Lai, and Yanlin Chen
    Quant. Inf. Comput., 2018
    [ Full version ]

    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)

    [ ACM Digital Library ]


    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