Page 42 - profile2014.indd

Computation theory and algorithms is the
foundation of Computer Science with studies of
power and limits of computing problems.

Computation Theory

and Algorithms Lab

Lab

Research Faculty
Bo-Yin Yang Computational Learning Theory: Many situations in daily life require us to make re-
Research Fellow peated decisions before knowing the resulting outcomes. This motivates the study
of the so-called online decision problem, in which one must iteratively choose an
Kai-Min Chung
Assistant Research Fellow action and then receive some corresponding loss for a number of rounds. For this
problem, we identify natural scenarios in which online algorithms with improved
Tsan-sheng Hsu performances can be designed. Moreover, we are discovering new applications of
Research Fellow
this problem in different areas, such as machine learning, game theory, and com-
Ming-Tat Ko plexity theory.
Research Fellow
Der-Tsai Lee (1) Cryptography
Distinguished Research Fellow
Churn-Jung Liau • Efficient Cryptography and CHES (Crypto Hardware and Embedded Systems): We
Research Fellow are working on designing cryptographical approaches for specialized hardware, in-
Jing-Sin Liu cluding implementing cryptographical algorithms in vector units in CPUs, FPGAs,
Associate Research Fellow ASICs, and GPU (graphic processing units). One of our record-breaking results is the
Chi-Jen Lu use of GPUs to assist in cryptanalytic computations. We also study the implementa-
Research Fellow tion of practical information security algorithms, such as using intelligent agents to
assist server-less authenticated information exchanges.
Da-Wei Wang
Research Fellow
• Post-Quantum Cryptography: Our work on MPKCs (Multivariate Public-Key Cryp-
tosystems) has advanced our understanding of the field from both theoretical and
practical viewpoints. MPKCs operate on a vector of variables over a small field, in-
stead of on an element in a huge algebraic structure (as in RSA or ECC). This key
characteristic makes MPKCs faster while maintaining comparable design security;
hence, they are useful for low-resource environments, such as embedded systems
and smart cards.

• Algebraic Cryptanalysis: We work on faster implementations and additional theory
behind such system-solvers. This work also relates to that on MPKCs, since an attack
on an MPKC is equivalent to solving a multivariate quadratic system (MQ) or the
extended isomorphism of polynomials (EIP).

• Theoretical Cryptography: Theoretical cryptography aims to understand the fea-
sibility and limitations of various
ambitious cryptographic tasks. Re-
cently, there has been very rapid
progress in cryptography, realizing
strong primitives that were not
even imaginable before. We have
participated in this development,
proposing new notions of program
obfuscations and new construc-
tions of functional encryptions.
Additionally, we are identifying
and obtaining new desiderata for
large-scale multi-party computa-
tion, motivated by the explosion in

42 研究群 Research Laboratories