Page 103 - untitled

ѐʿɛ

Lu, Chi-Jen ޼Ӻᔊʧ Research Description
Research Description
޼Ӻᔊʧ

٤ගၾ̻Бࠇၑٙࣛගd̙Ⴍ݊௰ਿ͉ٙՇ Parallel time and space are perhaps the two limited in some way. We also show that the ques-
most fundamental resources in computation. They tion of whether or not randomness helps non-de-
၇ࠇၑ༟๕fɓছɛ̙ঐ˸މɚ٫૩ೌᗫஹdШ̈ may appear totally unrelated, but surprisingly some terminism is related to the non-determinism versus
ɛจ̮ٙίݔԬઋرɨdɚ٫πίݔ၇࿁၈ᗫڷd duality phenomena between them have been ob- determinism problem and the sequential time versus
ʪ஢ɚ٫ԉЍٙ࿁ሜfఊዹϾԊd٤ගٙ̌ঐЧ˷ served, where their roles can be switched. However, space problem. The other approach is to design pro-
space alone seems to be a more powerful resource cedures, called randomness extractors, which can
༰̻Бࣛග੶ɽdΪމࣛගࠢՓə༟ৃݴਗٙఊɓ than parallel time alone, as information can only extract almost perfect randomness from slightly ran-
˙Σ׌fϾҢࡁɰٝ༸ίݔ၇ઋرɨdɚ٫ٙ࿁၈ flow unidirectionally in time, and duality relations dom sources. We provide the first explicit construc-
ᗫڷᆽྼʔπίfҢࡁٙ޼Ӻᜑͪd̥߰ʪ஢༟ৃ are known to fail in some circumstance. Our re- tion of extractors which are optimal up to constant Research Fellows
search shows that, when information is only allowed factors.
ԱݔԬࠢՓШΥଣٙ˙όٙݴਗdۆவʊٝٙʔ࿁ to flow in some restricted but natural fashion, this
၈ᗫڷਗ਼ऊ̰d˲һεٙ࿁၈ᗫڷਗ਼ओତfவЧ˷ discrepancy disappears and more duality relations Extractors turn out to be intimately related to
several other fundamental objects and have vari-
emerge. This seems to suggest that some deep rela-
ܔᙄഹ٤ගၾ̻Бࣛගʘගdπίഹݔ၇ଉՍٙᗫ
tion between parallel time and space exists that gov- ous applications in other fields. We found their
ڷdϞܙҢࡁ̘ᐝ༆f erns all these, and this is what we really would like application in cryptography. Under the assumption
that an adversary has a bounded amount of storage,
to understand.
Research Fellows
ਿ ͉ ༟ ࣘ
ਿ ͉ ༟ ࣘ ᎇዚܓɗ̤݊ɓࡈϞٙ͜༟๕f࿁׵ݔԬࠠ Aumann, Ding, and Rabin proposed encryption
Randomness is another useful resource. There schemes with a nice property called everlasting se-
ࠅٙࠇၑਪᕚdᎇዚစၑج౤ԶəͦۃසϞٙϞࣖ
are several important problems for which the most curity. The security is guaranteed by the limitation
ᔖcc၈jਓ޼ӺࡰAssociate Research Fellow ˙جf್ϾᎇዚόစၑجٙࣖঐdɓছѩӔ֛׵݊ efficient algorithms known are randomized. How- of current storage technology, and will last forever,
௰৷ኪዝj Ph.D., Computer Science, University of щϞɓࡈҁߕٙ඾ᅰ๕ԶՉԴ͜d್ϾІ್ޢ݊щ ever, randomized algorithms typically depend on even against future advances of any kind. We show
the availability of a perfect random source, whose that any strong extractor immediately yields such
Massachusetts at Amherst πίҁߕٙ඾ᅰ๕dʥ್݊ɓࡈ࠽੻نᙄٙਪᕚf
existence even in nature is debatable. One approach an encryption scheme. We also construct efficient
༆ӔϤѢྤٙୋɓ၇˙جdɗ݊޼ӺνОਗ਼ᎇዚό
ཥcc༑j+886-2-2788-3799 ext. 1820 then is to study whether or not randomized algo- on-line strong extractors which give encryption
စၑجᔷʷϓӔ֛όစၑجf݊щהϞٙᎇዚόစ rithms can be converted into deterministic ones. We schemes outperforming previous ones.
ෂccॆj+886-2-2782-4814 show how to do this when space or parallel time is
ၑجே̙˸஗ᔷʷϓӔ֛όစၑجdϾʔЇ׵ɽމ
ཥɿڦᇌjcjlu@iis.sinica.edu.tw ࠥЭՉࣖଟkவͦۃʥ್݊ɓࡈᘔϾ͊Ӕٙਪᕚf
ၣccࠫjhttp://www.iis.sinica.edu.tw/pages/cjlu ຅ᎇዚစၑجٙࣛගא٤ගաՑݔԬࠢՓࣛdҢࡁ Selected Publications
Selected Publications
ϞɓԬڋӉٙ޼Ӻϓ؈fҢࡁ͵޼Ӻᎇዚစၑج݊
щϞпڢᆽ֛όࠇၑٙਪᕚdνОᗫஹՑᆽ֛όࠇ 1. David A. Mix Barrington, Chi-Jen Lu, Peter Bro Miltersen, Sven 10. Chi-Jen Lu. Encryption against storage-bounded adversaries from on-
• Assistant Research Fellow (1999/8--2003/10) Skyum. Searching constant width mazes captures the AC hierarchy. line strong extractors. Journal of Cryptology, 17(1), pp. 27-42, 2004.
0
ၑ޴࿁ڢᆽ֛όࠇၑeʿࣛග޴࿁٤ගٙਪᕚf༆
Proceedings of the 15th Annual Symposium on Theoretical Aspects of 11. Fu Chang, Chun-Jen Chen, and Chi-Jen Lu. A linear-time component-
• Assistant Professor, National Chi-Nan University ӔѢྤٙୋɚ၇˙جdɗ݊ணࠇהፗٙ඾ܓଏ՟೻ Computer Science, pp. 73-83, 1998. labeling algorithm using contour tracing technique. Computer Vision
(1999/2--1999/7) 2. David A. Mix Barrington, Chi-Jen Lu, Peter Bro Miltersen, Sven and Image Understanding, 93(2), pp. 206-220, 2004.
ҏdԸ͟೹Ո඾ܓٙࢮ඾ᅰ๕ʕdଏ՟ڐ˷ҁߕٙ
Skyum. On monotone planar circuits. Proceedings of the 14th Annual 12. Chi-Jen Lu. Deterministic hypergraph coloring and its applications.
• M.S., CSIE, National Taiwan University (1990) ඾ᅰd˸ԶᎇዚစၑجԴ͜fவ˙ࠦٙ޼ӺʊϞʔ IEEE Conference on Computational Complexity, pp. 24-31, 1999. SIAM Journal on Discrete Mathematics, 18(2), pp. 320-331, 2004.
• B.S., CSIE, National Taiwan University (1988) ೵ٙዝ̦dϾҢࡁܔ࿴̈ͦۃʊٝ௰Գٙ඾ܓଏ՟ 3. Shan-Chyun Ku, Chi-Jen Lu, Biing-Feng Wang, Tzu-Chin Lin. Effi - 13. Yan-Cheng Chang and Chi-Jen Lu. Oblivious polynomial evalua-
cient algorithms for two generalized 2-median problems on trees. Pro- tion and oblivious neural learning. Theoretical Computer Science,
೻ҏf ceedings of the 12th Annual International Symposium on Algorithms 341(1-3), pp. 39-54, 2005.
And Computation (ISAAC), pp. 768-778, 2001. 14. Chia-Jung Lee, Chi-Jen Lu, Shi-Chun Tsai, and Wen-Guey Tzeng. Ex-
௰ڐ೯ତd඾ܓଏ՟೻ҏၾՉ˼ɓԬ༟ৃ߅ 4. Chi-Jen Lu. An exact characterization of symmetric functions in tracting randomness from multiple independent sources. IEEE Trans-
0
ኪʕٙਿ͉ܔ࿴dϞ޴຅੗ʲٙᗫڷdԨՉ˼ჯਹ qAC [2]. Theoretical Computer Science, 261(2), pp. 297-303, 2001. actions on Information Theory, 51(6), pp. 2224-2227, 2005.
5. Chi-Jen Lu and Shi-Chun Tsai, A note on iterating an α-ary Gray code. 15. Chi-Jen Lu, Shi-Chun Tsai, and Hsin-Lung Wu. On the complexity of
ʕϞจซʔՑٙᏐ͜fҢࡁਗ਼Չ༶͜ί੗ᇁኪʕf SIAM Journal on Discrete Mathematics, 14 (2), pp. 237-239, 2001. hardness amplifi cation. In Proceedings of the 20th Annual IEEE Con-
AumanneDingeʿRabin౤̈ɓࢁஷৃ̋੗ᅼόd 6. F. Thomson Leighton, Chi-Jen Lu, Satish Rao, and Aravind Sriniva- ference on Computational Complexity (CCC), pp.170-182, 2005.
san. New algorithmic aspects of the local lemma with applications 16. Yan-Cheng Chang, Chun-Yun Hsiao, and Chi-Jen Lu. On the impossi-
ί᛿ᛓ٫ՈϞࠢাኳ᜗ٙ৿ணɨdঐڭᗇՈϞ͑ɮ to routing and partitioning. SIAM Journal on Computing, 31(2), pp. bility of basing one-way permutations on central cryptographic primi-
ٙτΌ׌fϤτΌ׌ሯ̥ਿ׵຅ʦাኳ᜗Ҧஔٙڻ 626-641, 2001. tives. Journal of Cryptology, 19(1), pp. 97-114, 2006.
7. Chi-Jen Lu. Derandomizing Arthur-Merlin games under uniform as- 17. Chi-Jen Lu. On the complexity of parallel hardness amplifi cation for
ࠢdϾఱၑ˚ܝழ೷᜗ί೯༺dʥ್͑Ⴣೌجॎ sumptions. Computational Complexity, 10, pp. 247-259, 2001. one-way functions. In Proceedings of the 3rd Theory of Cryptography
༆fҢࡁ޼Ӻ೯ତd΂О඾ܓଏ՟೻ҏޫ̙͜Ըྼ 8. Chi-Jen Lu. Improved pseudorandom generators for combinatorial Conference (TCC), pp. 462-481, 2006.
rectangles. Combinatorica, 22(3), pp. 417-434, 2002. 18. Chia-Jung Lee, Chi-Jen Lu, and Shi-Chun Tsai. Deterministic Extrac-
ତՈϞνϤ͑ɮτΌ׌ٙ̋੗ᅼόfҢࡁ͵ணࠇঐ
9. Chi-Jen Lu, Omer Reingold, Salil Vadhan, and Avi Wigderson. Ex- tors for Independent-Symbol Sources. To appear in Proceedings of
ආБᇞɪࠇၑٙ඾ܓଏ՟೻ҏd˸Ϥପ͛ٙ̋੗೻ tractors: optimal up to constant factors. Proceedings of the 35th ACM the 33rd International Colloquium on Automata, Languages and Pro-
Symposium on Theory of Computing (STOC), pp. 602-611, 2003. gramming (ICALP), 2006.
ҏdՉࣖଟჃ৷׵ʊϞٙܔ࿴f

88 89