Kai-Min Chung

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 Mar. 05, 2018).




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.




ˇ       Ph.D. Thesis


Efficient Parallel Repetition Theorems with Applications to Security Amplification,

Ph.D. Thesis (March 2011)

[ pdf ]


ˇ       Publications


On the Complexity of Simulating Auxiliary Input

With Yi-Hsiu Chen and Jyun-Jie Liao
To appear in EUROCRYPT 2018


On the Depth of Oblivious Parallel RAM
With T-H. Hubert Chan and Elaine Shi

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


[ Conference version ]


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

With Elette Boyle and Rafael Pass


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


Statistically-secure ORAM with Ő (log˛ n) Overhead

with Zhenming Liu and Rafael Pass,


[ Conference version ]


On the Impossibility of Cryptography with Tamperable Randomness

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

CRYPTO 2014, To appear in Algorithmica 2016

[ Conference version, Full version]


Distributed Algorithms for the Lovász Local Lemma and Graph Coloring,

with Seth Pettie and Hsin-Hao Su,

PODC 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 ]


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 ]


Non-black-box Simulation from One-way Functions and Applications to Resettable Security,

With Karn Seth, and Rafael Pass

STOC 2013, SIAM J. on Computing 2016

[ Full version ]


On the Lattice Smoothing Parameter Problem,

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

[ Full version ]

CCC 2013


Randomness Dependent Message Security,

with Eleanor Birrell, Rafael Pass, and Sidharth Telang

TCC 2013

[ Full version ]


On the Power of Non-uniform Proofs of Security,

with Huijia Rachel Lin, Mohammad Mahmoody, and Rafael Pass

ITCS 2013

[ Conference version ]


A Cryptographic Treatment of Forecast Testing,

with Edward Lui, and Rafael Pass

ITCS 2013

[ Full version ]


The Knowledge Tightness of Parallel Zero-Knowledge,

with Rafael Pass, and Wei-Lung Dustin Tseng

TCC 2012

[ Full version ]


Chernoff-Hoeffding Bounds for Markov Chains: Generalized and Simplified,

with Henry Lam, Zhenming Liu, and Michael Mitzenmacher

STACS 2012

[ Full version ]


The Randomness Complexity of Parallel Repetition,

with Rafael Pass

FOCS 2011

[ Full version ]


Memory Delegation,

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


[ Full 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 P. Vadhan


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


[ Full version ]


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

with Omer Reingold, and Salil P. Vadhan

CCC 2007, ACM Transactions on Algorithms 2011

[ Full version ]


An Optimal Algorithm for the Maximum-Density Segment Problem,

with Hsueh-I Lu

ESA 2003, 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

ICASSP 2003, 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

ICONIP 2002, Neural Computation 2003

[ Full version ]


ˇ       Posters


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

with Divesh Aggarwal, Han-Hsuan Lin and Thomas Vidick

QIP 2018


On Statistically-Secure Quantum Homomorphic Encryption

with Ching-Yi Lai

QIP 2018


Space-efficient Classical and Quantum Algorithms for the Shortest Vector Problem

with Yanlin Chen and Ching-Yi Lai

QIP 2018


Computational Notions of Quantum Min-Entropy

with Yi-Hsiu Chen, Ching-Yi Lai, Salil Vadhan and Xiaodi Wu

QIP 2017


ˇ       Manuscripts


Leakage Chain Rule and Superdense Coding

with Yi-Hsiu Chen, Ching-Yi Lai and Xiaodi Wu


[ Full version ]


Unprovable Security of Two-Message Zero-Knowledge,

with Edward Lui, Mohammad Mahmoody, and Rafael Pass


[ Full version ]


A Simple ORAM,

with Rafael Pass,


[ Full version ]



Professional Activities


ˇ       Program Committees


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 Fellow for CS225 Pseudorandomness, Spring 07 and 09, taught by Prof. Salil Vadhan

Received Certificate of Distinction in Teaching in Spring 09