Page 68 - profile-ok

研究人員 ｜ Research Faculty

● Associate Research Fellow, IIS, Academia Sinica (2003/10 - 2008/11)
呂及人 Chi-Jen Lu ● Assistant Research Fellow, IIS, Academia Sinica (1999/8 - 2003/10)
● Assistant Professor, CSIE, National Chi-Nan University (1999/2 -
1999/7)
● M.S., CSIE, National Taiwan University (1990)
研究員 Research Fellow ● B.S., CSIE, National Taiwan University (1988)
Ph.D., Computer Science, University of Massachusetts at Amherst
Tel: +886-2-2788-3799 ext. 1820
Fax: +886-2-2782-4814
Email: cjlu@iis.sinica.edu.tw
http://www.iis.sinica.edu.tw/pages/cjlu

Research Description 代表著作 Publications
Randomness has become a valuable resource in computation. For many computa-
tional problems, randomized algorithms are simpler, more natural, or more efficient
than existing deterministic algorithms. However, randomized algorithms typically 1. David A. Mix Barrington, Chi-Jen Lu, Peter Bro Miltersen, Sven 17. Chia-Jung Lee, Chi-Jen Lu, and Shi-Chun Tsai. Deterministic extrac-
0
Skyum. Searching constant width mazes captures the AC hierarchy.
tors for independent-symbol sources. In Proceedings of the 33 In-
rd
depend on the availability of a perfect random source, the existence of which even
研究簡介 in Nature is debatable. One approach then is to study whether or not randomized Proceedings of the 15th Annual Symposium on Theoretical Aspects of ternational Colloquium on Automata, Languages and Programming
Computer Science (STACS), pp. 73-83, 1998.
(ICALP), pp. 84-95, 2006.
algorithms can be derandomized into deterministic ones without sacrificing the
亂數在計算上，已成為一個有用的資源。對於許多計算 performance too much. The other approach is to design procedures, called extrac- 2. Chi-Jen Lu. A deterministic approximation algorithm for a minmax 18. Chi-Jen Lu. On the complexity of parallel hardness amplification for
th
rd
問題，隨機演算法提供了最自然、最簡單、或最有效率 tors, which can extract almost perfect randomness from slightly random sources. integer programming problem. In Proceedings of the 10 ACM-SIAM one-way functions. In Proceedings of the 3 Theory of Cryptography
的解決方法。然而一般隨機演算法的設計，均假設有完 We have conducted some research on both approaches, which we describe in the Symposium on Discrete Algorithms (SODA), pp. 663-668, 1999. Conference (TCC), pp. 462-481, 2006.
美的亂數供其使用。但是電腦如何能產生完美的亂數？ following. 3. David A. Mix Barrington, Chi-Jen Lu, Peter Bro Miltersen, Sven Sky- 19. Chi-Jen Lu, Shi-Chun Tsai, and Hsin-Lung Wu. Improved hardness
th
就連自然界是否存在完美的亂數源，也是一個值得爭議 One standard approach to derandomization relies on constructing the so-called um. On monotone planar circuits. In Proceedings of the 14 Annual amplification in NP. Theoretical Computer Science, 370, pp. 293-298,
的問題。解決此困境的第一種方法，乃是研究如何將隨 pseudorandom generators (PRG), which stretch a short random seed into a long IEEE Conference on Computational Complexity (CCC), pp. 24-31, 2007.
機式演算法轉化成確定式演算法，而不至於大為降低其 pseudorandom string that looks random to circuits of polynomial size. So far, all 1999. 20. Chun-Yuan Hsiao and Chi-Jen Lu and Leonid Reyzin. Conditional
效率。第二種方法，乃是設計所謂的亂度淬取程序，來 known constructions of PRG have been based on unproven assumptions of the 4. Chi-Jen Lu. An exact characterization of symmetric functions in computational entropy, or toward separating pseudoentropy from
0
由稍具亂度的弱亂數源中，淬取近乎完美的亂數，以供 nature that certain functions are hard to compute. To obtain a stronger result, we qAC [2]. Theoretical Computer Science, 261(2), pp. 297-303, 2001. compressibility. Advances in Cryptology - EUROCRYPT 2007, pp.
隨機演算法使用。我們對這兩種方法皆有探討。 would like to start from a function that is only slightly hard to compute and convert 5. Chi-Jen Lu and Shi-Chun Tsai, A note on iterating an α-ary Gray 169-186, 2007.
it into a much harder one, before using it to construct a PRG. This task, known as code. SIAM Journal on Discrete Mathematics, 14 (2), pp. 237-239, 21. Chi-Jen Lu, Shi-Chun Tsai, and Hsin-Lung Wu. On the complexity of
一種解除隨機性的常用方法，乃是藉由所謂虛擬亂數產 hardness amplification, plays a crucial role in the study of pseudo-randomness. Un- 2001. hard-core set constructions. In Proceedings of the 34 International
st
生器，來產生一長串看似亂數的虛擬亂數。目前已知的 fortunately, all previous constructions of hardness amplification procedures leave Colloquium on Automata, Languages and Programming (ICALP), pp.
虛擬亂數產生器，其安全性都植基於某些函數難以計算 some unpleasant issues. The first is that when one wants to amplify the hardness 6. F. Thomson Leighton, Chi-Jen Lu, Satish Rao, and Aravind Srini- 183-194, 2007.
的假設。為了得到更強的結果，人們想從稍具難度的函 substantially, all the amplification procedures require a high computational com- vasan. New algorithmic aspects of the local lemma with applications 22. Chi-Jen Lu, Shi-Chun Tsai, and Hsin-Lung Wu. Impossibility results
to routing and partitioning. SIAM Journal on Computing, 31(2), pp.
數出發，將其轉化為一個具有很高難度的函數，再用以 plexity. The second issue is that hardness amplification typically involves non-uni- 626-641, 2001. on weakly black-box hardness amplification. In Proceedings of the
建構虛擬亂數產器。這樣的難度放大程序，在虛擬亂數 formity in the sense that hardness is measured against non-uniform circuits. Many 16 International Symposium on Fundamentals of Computation The-
th
的研究中，扮演了極重要的角色。然而已知的所有難度 researchers have tried to resolve these issues, but progress has been very limited. 7. Chi-Jen Lu. Derandomizing Arthur-Merlin games under uniform as- ory (FCT), pp. 400-411, 2007.
放大程序，都有兩個令人不滿意的問題。首先是這些程 We observe that almost all previous hardness amplification procedures were imple- sumptions. Computational Complexity, 10, pp. 247-259, 2001. 23. Chi-Jen Lu, Shi-Chun Tsai, and Hsin-Lung Wu. On the complexity
序皆需要很高的計算複雜度，其次是難度的衡量都是相 mented in a certain black-box way; and we show that when hardness amplification 8. Chi-Jen Lu. Improved pseudorandom generators for combinatorial of hardness amplification. IEEE Transaction on Information Theory,
對於非一致性的計算模式。雖然許多研究人員努力嘗試 is performed in this way, both issues are in fact unavoidable. rectangles. Combinatorica, 22(3), pp. 417-434, 2002. 54(10), pp. 4575-4586, 2008.
解決這些問題，但是始終沒有好的進展。我們發現幾乎 Extractors are functions that extract almost uniform bits from sources of biased and 9. Chi-Jen Lu, Omer Reingold, Salil Vadhan, and Avi Wigderson. Ex-
所有已知的難度放大程序都是以某種黑盒模式進行，而 correlated bits, usually with the help of an additional short random seed as a cata- tractors: optimal up to constant factors. Proceedings of the 35 ACM 24. Feng-Hao Liu, Chi-Jen Lu, and Bo-Yin Yang. Secure PRNGs from
th
specialized polynomial maps over any GF(q). In Proceedings of the
我們進而證明，若難度放大程序以此類黑盒模式進行， lyst. In addition to extracting randomness for randomized algorithms to use, extrac- Symposium on Theory of Computing (STOC), pp. 602-611, 2003. 2 international Workshop on Post-Quantum Cryptography, pp. 181-
nd
則以上兩個問題都是無法避免的。
tors have found a wide range of applications in various fields and have played a fun- 10. Chi-Jen Lu. Encryption against storage-bounded adversaries from on- 202, 2008.
亂度淬取程序能由稍具亂度的弱亂數源中，淬取近乎完 damental and unifying role in the theory of pseudo-randomness. We provided the line strong extractors. Journal of Cryptology, 17(1), pp. 27-42, 2004. 25. Chi-Yuan Chan, Shan-Chyun Ku, Chi-Jen Lu, and Biing-Feng Wang.
美的亂數。除了供隨機演算法使用之外，亂度淬取程序 first explicit construction of extractors which are simultaneously optimal (up to con- 11. Fu Chang, Chun-Jen Chen, and Chi-Jen Lu. A linear-time component- Efficient algorithms for two generalized 2-median problems and
亦在其他許多領域有意想不到的應用，因此其研究受到 stant factors) in both seed length and the number of bits extracted, settling an open labeling algorithm using contour tracing technique. Computer Vision the group median problem on trees. Theoretical Computer Science,
廣泛的重視。我們建構出目前已知最佳的亂度淬取程 problem that had been studied extensively for more than a decade. In addition, we and Image Understanding, 93(2), pp. 206-220, 2004. 410(8-10), pp. 867-876, 2009.
study the possibility of constructing extractors that do not need an additional seed,
序，從而解決了計算理論中一個具有多年歷史的難題。 and we have identified a general class of sources on which seedless extraction can 12. Chi-Jen Lu. Deterministic hypergraph coloring and its applications. 26. Chia-Jung Lee, Chi-Jen Lu and Shi-Chun Tsai. Extracting compu-
亂度淬取程序常會使用一個非常短的亂數來催化淬取過 be achieved. We also consider sources that are not at all random in the traditional, SIAM Journal on Discrete Mathematics, 18(2), pp. 320-331, 2004. tational entropy and learning noisy linear functions. In Proceedings
程，有時這會造成不便，因此我們也研究何時可以不需 statistical setting but look slightly random to computationally-bound observers, 13. Yan-Cheng Chang and Chi-Jen Lu. Oblivious polynomial evaluation of the 15 International Computing and Combinatorics Conference
th
使用這個額外的亂數。我們也研究如何由不具統計亂度 and we show how to extract randomness from such sources. Apart from construct- and oblivious neural learning. Theoretical Computer Science, 341(1- (COCOON), pp. 338-347, 2009.
但卻看似具有亂度(相對於計算能力受限的觀察者)的分 ing extractors, we have found a surprising application of extractors in cryptography. 3), pp. 39-54, 2005. 27. Chi-Jen Lu. On the security loss in cryptographic reductions. Advanc-
佈中，淬取近乎完美的亂數。此外，我們也將亂度淬取 In particular, we use extractors to build an encryption scheme with everlasting secu- 14. Chia-Jung Lee, Chi-Jen Lu, Shi-Chun Tsai, and Wen-Guey Tzeng. es in Cryptology - EUROCRYPT 2009, pp. 72-87.
程序應用於密碼學，而建構出具有永久安全性的加密系 rity, which will remain secure forever even against future attacks of any kind. Extracting randomness from multiple independent sources. IEEE 28. Chao-Kai Chiang and Chi-Jen Lu. Online Learning with Queries. In
統。 Transactions on Information Theory, 51(6), pp. 2224-2227, 2005. Proceedings of the 21 ACM-SIAM Symposium on Discrete Algo-
st
rithms (SODA), pp. 616-629, 2010.
15. Fu Chang, Chin-Chin Lin, and Chi-Jen Lu. Adaptive prototype learn-
ing algorithms: theoretical and experimental studies. Journal of Ma- 29. Jen-Hou Chou and Chi-Jen Lu. Communication requirements for sta-
chine Learning Research, 7, pp. 2125-2148, 2006. ble marriages. In Proceedings of the 7 International Conference on
th
Algorithms and Complexity, 2010.
16. Yan-Cheng Chang, Chun-Yun Hsiao, and Chi-Jen Lu. The impossibil-
ity of basing one-way permutations on central cryptographic primi-
tives. Journal of Cryptology, 19(1), pp. 97-114, 2006.
68 69