Kai-Min Chung

Assistant 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 12/16/2014).

 

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.

 

Research

 

ˇ       Ph.D. Thesis

 

Efficient Parallel Repetition Theorems with Applications to Security Amplification,

Ph.D. Thesis (March 2011)

[ pdf ]

 

ˇ       Publications

 

Nearly optimal parallel repetition for entangled games under the product distribution, with any number of players

with Henry Yuen and Xiaodi Wu

Poster Session, QIP 2015

 

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

with Zhenming Liu and Rafael Pass,

ASIACRYPT 2014

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

 

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 

[ 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

CRYPTO 2011

[ 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

CRYPTO 2010

[ 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

RANDOM 2008

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

 

ˇ       Manuscripts

 

Unprovable Security of Two-Message Zero-Knowledge,

with Edward Lui, Mohammad Mahmoody, and Rafael Pass

Manuscript.

[ Full version ]

 

On the (Im)Possibility of Tamper-Resilient Cryptography:

Using Fourier Analysis in Computer Viruses,

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

Manuscript.

 

 

Professional Activities

 

ˇ       Program Committees

 

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 33rd International Cryptology Conference (CRYPTO 2013)

The 11th IACR Theory of Cryptography Conference (TCC 2014)

 

Teaching

 

Teaching Fellow for CS225 Pseudorandomness, Spring 07 and 09, taught by Prof. Salil Vadhan

Received Certificate of Distinction in Teaching in Spring 09