Associate 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 May. 17, 2019).

 

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.


We are also recruiting postdocs with multiple opening positions! Please see here for details and apply!

 

Research

 

      
  • Ph.D. Thesis
  •  

    Efficient Parallel Repetition Theorems with Applications to Security Amplification,

    Ph.D. Thesis (March 2011)

    [ pdf ]

     

          
  • Conference Publications
  •  

    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,

    with Thomas Vidick, Han-hsuan Lin, and Divesh Aggarwal
    Eurocrypt, 2019

    arXiv version ]

    On Quantum Advantage in Information Theoretic Single-Server PIR,

    with Dorit Aharonov, Zvika Brakerski, Ayal Green, Ching-Yi La and Or Sattath
    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

    [ 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 and Yu-Chi Chen and Huijia Lin and Wei-Kai Lin
    TCC 2016-B
    [ Conference version ]

     

    Cryptography for Parallel RAM from Indistinguishability Obfuscation,

    With Yu-Chi Chen and Sherman S. M. Chow and Russell W. F. Lai and 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 and Mohammad Mahmoody and 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 and 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

    IEEE 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: 124-135

    [ arXiv version ]

     

    Efficient Secure Two-Party Exponentiation,

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

    CT-RSA 2011

    [ 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

  • Generalized Quantum Shannon Impossibility for Quantum Encryption,

    with Ching-Yi Lai,
    Design, Codes and Cryptography, 2019
    [ Full version ]

    On Statistically-Secure Quantum Homomorphic Encryption,

    with Ching-Yi Lai,
    Quant. Inf. Comput., 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 ]


    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 ]

     

    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 ]

     

     

    Professional Activities

     

          
  • Program Committees
  •  

    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