Page 63 - profile2012.indd

Research Faculty 研究人員

研究員 副研究員
呂及人 Chi-Jen Lu 呂俊賢 Chun-Shien Lu

Research Fellow Associate Research Fellow
Ph.D., Computer Science, University of Massachusetts at Amherst Ph.D., Electrical Engineering, National Cheng-Kung University

Tel: +886-2-2788-3799 ext. 1820 Fax: +886-2-2782-4814 Tel: +886-2-2788-3799 ext. 1513 Fax: +886-2-2782-4814
Email: cjlu@iis.sinica.edu.tw Email: lcs@iis.sinica.edu.tw
http://www.iis.sinica.edu.tw/pages/cjlu http://www.iis.sinica.edu.tw/~lcs

● Research Fellow, IIS, Academia Sinica (2008 - present) ● Ph.D., Computer Science, University of Massachusetts at Amherst ● Associate Research Fellow, Institute of Information Science, Aca- ● Ph.D., Electrical Engineering, National Cheng-Kung University,
● Associate Research Fellow, IIS, Academia Sinica (2003 - 2008) M.S., CSIE, National Taiwan University B.S., CSIE, National Taiwan demia Sinica, Taiwan (2006/7–present) Taiwan (1998)
● Assistant Research Fellow, IIS, Academia Sinica (1999 - 2003) University ● Adjunct Associate Professor, Department of Computer Science and ● Associate Editor, IEEE Trans. on Image Processing (2010/12~2013/12)
● Assistant Professor, CSIE, National Chi-Nan University (1999 - 1999) Information Engineering, National Taipei University of Technology, ● Ta-You Wu Memorial Award, National Science Council, Taiwan (2007)
Taiwan (2006/9–2008/1)
Research Description Publications Research Description Publications

Randomness has become a valuable resource in computa- 1. Chi-Jen Lu. Hitting set generators for sparse polynomials over My current research interests mainly focus on (1) Secu- 1. Li-Wei Kang, Chao-Yung Hsu, Hung-Wei Chen, Chun-Shien

th
tion, as randomized algorithms have provided the most ef- any finite fields. In Proceedings of the 27 Annual IEEE Con- rity and Privacy in Multimedia and Sensor Network and Lu, Chih-Yang Lin, and Soo-Chang Pei, “Feature-based

cient solutions for many important computational prob- ference on Computational Complexity (CCC), 2012. (2) Compressed Sensing (algorithm design and applica- Sparse Representation for Image Similarity Assessment,’’
IEEE Trans. on Multimedia, Vol. 13, No. 5, pp. 1019-1030,
lems. However, randomized algorithms typically depend 2. Chia-Jung Lee, Chi-Jen Lu and Shi-Chun Tsai. Extracting tions). Security and Privacy are long-studied problems 2011.
on the availability of a perfect random source, the exist- computational entropy and learning noisy linear functions. but we focus on relevant and common issues, including 2. Chao-Yung Hsu, Chun-Shien Lu, and Soo-Chang Pei, “Tem-
ence of which even in Nature may be debatable. One ap- IEEE Transaction on Information Theory, 57(8), pp. 5485- content authentication, integrity detection, and privacy- poral Frequency of Flickering-Distortion Optimized Video
proach then is to study whether or not randomized algo- 5496, 2011. preserving, in Multimedia and Sensor Network, in addition Halftoning for Electronic Paper,’’ IEEE Trans. on Image Pro-
rithms can be e ciently derandomized into deterministic 3. Chi-Jen Lu, Shi-Chun Tsai, and Hsin-Lung Wu. Complexity to our previous researches on multimedia data hiding/wa- cessing, Vol. 20, No. 9, pp. 2502-2514, 2011.

ones. The other approach is to design procedures, called of hard-core set proofs. Computational Complexity, 20(1), pp. termarking and hashing. As for sensor network security, 3. Chia-Mu Yu, Yao-Tung Tsou, Chun-Shien Lu, and Sy-Yen
extractors, which can extract almost perfect randomness 145-171, 2011. we have developed a non-interactive key pre-distribution Kuo, “Practical and Secure Multidimensional Queries in
Tiered Sensor Networks,’’ IEEE Trans. on Information Fo-
from slightly random sources. 4. Chi-Jen Lu and Wei-Fu Lu. Making online decisions with mechanism, a message authentication method, and a rensics and Security, vol. 6, no. 2, pp. 241-255, 2011.
nd
bounded memory. In Proceedings of the 22 International privacy-preserving query scheme. We are currently try-
One key step in the approach of derandomization is the Conference on Algorithmic Learning Theory (ALT), 2011. 4. Chia-Mu Yu, Yao-Tung Tsou, Chun-Shien Lu, and Sy-Yen
task known as hardness ampli cation, but unfortunately, 5. Chia-Jung Lee, Chi-Jen Lu, and Shi-Chun Tsai. Computation- ing to build a secure sensor network system composed Kuo, “Constrained Function based Message Authentication

all previous ampli cation procedures have some undesir- al randomness from generalized hardcore sets. In Proceed- of several security components. Recently, with an eye on for Sensor Networks,’’ IEEE Trans. on Information Forensics
and Security, vol. 6, no. 2, pp. 407-425, 2011.
able properties. We observe that almost all these proce- ings of the 20th International Symposium on Fundamentals of the fact that compressed sensing (CS) is a revolutionary 5. Chia-Mu Yu, Chun-Shien Lu, and Sy-Yen Kuo, “Non-Interac-
dures were implemented in a certain black-box way; we Computation Theory (FCT), pp. 78-89, 2011. technology of simultaneously sensing and compressing tive Pairwise Key Establishment for Sensor Networks,’’ IEEE
show that when hardness ampli cation is performed in 6. Chi-Jen Lu and Hsin-Lung Wu. On the hardness against con- signals, and builds a new sampling theorem beyond the Trans. on Information Forensics and Security, Vol. 5, No. 3,

this way, the undesirable properties are in fact unavoid- stant-depth linear-size circuits. Discrete Mathematics, Algo- Nyquist rate, we study the fundamental issues, including pp. 556-569, 2010.
able. On the positive side, for some complexity classes, we rithms and Applications, 2(4), pp. 515-526, 2010. dictionary learning for sparsifying signals, and more accu- 6. Li-Wei Kang, Chao-Yung Hsu, Hung-Wei Chen, and Chun-
obtain ampli cation procedures which are more e cient 7. Chia-Jung Lee, Chi-Jen Lu, and Shi-Chun Tsai. Deterministic rate and fast CS recovery, in compressed sensing of sig- Shien Lu, ``Secure SIFT-based Sparse Representation for Im-

than the existing ones, while for some others, we are able extractors for independent-symbol sources. IEEE Transaction nals and images. We have developed a distributed com- age Copy Detection and Recognition,’’ Proc. IEEE Int. Conf.
on Multimedia and Expo, Singapore, July 2010. (oral paper
to obtain hard functions directly without going through on Information Theory, 56(12), pp. 6501-6512, 2010. pressive video sensing (DCVS) method to simultaneously with acceptance rate 15%)
hardness ampli cation. 8. Fu Chang, Chien-Yang Guo, Xiao-Rong Lin, and Chi-Jen Lu. sensing and compressing videos. We also have presented 7. Chia-Mu Yu, Chun-Shien Lu, and Sy-Yen Kuo, “A Simple

Tree decomposition for large-scale SVM Problems. Journal of a compressed image sensing (CIS) method for turbo fast Non-Interactive Pairwise Key Establishment Scheme in Sen-
For the second approach, we provide the rst explicit Machine Learning Research, 11(Oct), pp. 2935-2972, 2010. recovery of images from (far) fewer measurements. We sor Networks,’’ Proc. The 6 IEEE Communications Society

th
construction of seeded extractors which are simultane- are currently studying a fast Orthogonal Matching Pur- Conference on Sensor, Mesh and Ad Hoc Communications
ously optimal in both seed length and the number of bits 9. Kai-Min Chung, Feng-Hao Liu, Chi-Jen Lu, and Bo-Yin Yang. suit (FOMP) algorithm by reformulating OMP in terms of and Networks (SECON), June 22-26, 2009. (acceptance rate

extracted. Furthermore, we study the possibility of con- Efficient string-commitment from weak bit-commitment and re ning L2-norm solutions in a greedy manner. Our FOMP 18.5%)

full-spectrum amplification theorem for puzzles. Advances in
structing extractors that do not need an additional seed, Cryptology - ASIACRYPT 2010, pp. 268-282, 2010. method not only provides theoretic guarantee of recov- 8. Yu-Chen Huang, Chun-Shien Lu, and Hsiao-Kuang Wu, “Jit-
and we identify a general class of sources on which seed- ery based on Mutual Incoherence Property (MIP) but also terPath: One-Way Delay Jitter-based Available Bandwidth Es-
timation for Multimedia QoS,’’ IEEE Trans. on Multimedia,
less extraction can be achieved. We also consider sources 10. Chao-Kai Chiang and Chi-Jen Lu. Online Learning with Que- provides a more practical exact recovery analysis via order Vol. 9, No. 4, pp. 798-812, 2007.
st
ries. In Proceedings of the 21 ACM-SIAM Symposium on
that are not at all random in the traditional, statistical set- Discrete Algorithms (SODA), pp. 616-629, 2010. statistics. We plan to investigate CS-based applications, 9. Chun-Shien Lu and Chao-Yong Hsu, “Anti-Disclosure Wa-
ting but look slightly random to computationally-bound including sparse representation and compressive sensing termark Giving Multiple Watermark Embedding Approaches
observers, and we show how to extract randomness from problems related to multimedia, node replica detection in Resistance to Estimation Attack,’’ IEEE Trans. on Circuits
such sources. sensor network, space shift keying in MIMO, etc., based on and Systems for Video Technology, Vol. 17, No. 4, pp. 454-
467, 2007.
exploiting the sparsity of signals we would like to explore.
10. Chun-Shien Lu, Shih-Wei Sun, Chao-Yong Hsu, and Pao-Chi
Chang, “Media Hash-dependent Image Watermarking Resil-
ient Against Both Geometric Attacks and Estimation Attacks
Based on False Positive-Oriented Detection,’’ IEEE Trans. on
Multimedia, Vol. 8, No. 4, pp. 668-685, 2006.
研究人員
62 Research Faculty
63