Page 40 - profile-ok

研究群 ｜ Research Laboratories

Computation Theory and

Algorithms Laboratory

Research Faculty Group Profile

Ming-Tat Ko 1. Graph Theory and Algorithms optimization problems. Most of these problems have been shown to erlasting security. We will extend the scope of extractors to consider
Research Fellow be computationally intractable. Thus, we will explore the underlying the possibility of extracting randomness from sources that only look
Computer Science , National Tsing-Hua University Graphs are used to model many important applications and are a main tool for solving many structures or properties of these problems, and attempt to obtain somewhat random to computationally-bounded observers, but con-
theoretical problems. We often start with probing fundamental theoretical problems such as suitable approximation solutions or heuristics that are practically ac- tain no randomness at all in a statistical sense.
Tsan-sheng Hsu the structure of graphs with certain properties. With these properties, we then design efficient ceptable for the situation under consideration.
Research Fellow solutions to them. We work on algorithmic graph problems arisen from real-world applications. 6. Cryptography
Computer Sciences , University of Texas at Austin From phylogenetics, we work on two basic problems, the Steiner root problem and the super- 4. Data intensive computation: theory Efficient Cryptography and CHES (Crypto Hardware and Em-
tree construction problem. For a set of taxa with similarity relations represented by a graph, ●
Der-Tsai Lee the Steiner root problem is to find a phylogenetic tree of these taxa whose power is exactly the Logic and knowledge representation for massive data: Much infor- bedded Systems):
Distinguished Research Fellow graph. The supertree construction problem is to yield a phylogenetic tree from a set of small mation and knowledge are implicit in massive data. In recent years, Some situations call for the utmost effort in optimization. Here, it is
Computer Science , University of Illinois at Urbana- phylogenetic trees with different but overlapped taxa sets. Though there exist many supertree intelligent agent systems with learning and reasoning ability have
Champaign received much attention. We want to study the knowledge represen- not just cryptanalytic efforts that require the highest efficiency, in
construction algorithms, biologists still desire an efficient algorithm providing comprehensive many cases so does encryption. Sometimes it is because resources
Churn-Jung Liau information of phylogenetic relation among taxa. We also study fundamental algorithms aris- tation and inference problems relevant to intelligent agent systems are limited: It seems that computers are ubiquitous, and will soon be
based on formal logics. We will study methods to inductively produce
Research Fellow en from applications with massive data. One of the areas involves augmentation algorithms useful rules and knowledge with special attention provided to the working invisibly and seamlessly in many ways; hence, security and
CSIE , National Taiwan University on graphs with partition constraints. This stems from data privacy protection problems, and privacy are becoming pressing issues. RSA may lose its dominance
has applications in various fault tolerant designs. One other area of our research concerns representation problem of such extracted knowledge. With a proper within 5-10 years, even without quantum computers, because it is
Jing-Sin Liu algorithms for finding the tree editing distance when the distance has a limited bound. This knowledge representation framework, derived knowledge can serve too heavy-weight for low-resource use. Indeed, because of the need
Associate Research Fellow problem has applications in comparing large trees, which are models for many applications as the basis for further reasoning and decision making of the intel- for better security in pervasive or ubiquitous computing, NATO is
EE , National Taiwan University including several problems in the area of bioinformatics. ligent agent systems. Different agent systems can exchange knowl- planning to adopt ECC (ECIES, ECDSA) as its next standard. In the
Chi-Jen Lu 2. Geometric Computing edge based on the common representation, and agent systems can opposite direction, higher efficiency in encryption algorithms can
produce even more complex knowledge by invoking a proper fusion
Research Fellow mechanism to incorporate knowledge from various sources. The fully result in higher security levels, or cheaper components for the same
Computer Science , University of Massachusetts at The Voronoi diagram is a very versatile and well-studied geometric construct in geometric distributed yet coordinated knowledge extraction and processing security.
Amherst computing. The properties, complexity, and computation of Voronoi diagram are among the mechanism can derive useful knowledge for decision making from a
fundamental problems to study. By introducing different metrics, such as time-distance, the In this area, we study topics ranging from restricted linear algebra
Da-Wei Wang diagram will change. In general, we plan to study how the properties of the Voronoi diagram massive data set. This can effectively mitigate the information explo- and resource-limited arithmetic, to fast arithmetic and efficient
Research Fellow vary with the metric selected, and how we make use of the properties of the selected metric, sion problem for decision makers. primitives. We are known for designing cryptographical approach-
Computer Science , Yale University es for specialized hardware, including implementing cryptographi-
if any, to construct the diagram. Other problems such as Map Labeling, i.e., how to label given Algorithms and protocols for privacy enhancing technology with cal algorithms on vector units in CPUs, FPGAs, ASICs, and GPU
Bo-Yin Yang features of a map so that these labels do not overlap, and Defensive Competitive Facility Loca- massive data: In recent years, many institutions have collected mas- (graphic processing units). One of our record-breaking results is
Associate Research Fellow tion, i.e., finding the location of a facility so that the gain of prospective competitors is mini- sive and comprehensive individual data for various purposes. To using GPUs to assist cryptanalytic computations. We also study the
Mathematics (Applied) , Massachusetts Institute of mized according to certain rules of competition, are also of interest. In biological computing share those data can be beneficial to society, but it also poses a great implementation of practical information security algorithms, such
Technology we use some important techniques, such as random sampling, parametric search, geometric threat to individual privacy. How to share the data and keep indi- as using intelligent agents to assist server-less authenticated infor-
cutting, expander graph, matrix searching, etc. to tackle certain subsequence problems in a vidual privacy intact is the topic we are interested in. We proposed
given DNA or arbitrary sequence, e.g., finding a maximum density subsequence or a maxi- a logic framework to study risks to privacy when publishing micro- mation exchanges.
mum sum subsequence. We hope to use geometric techniques to solve additional problems data, and a quantitative measurement for the privacy threat. We are ● Post-Quantum Cryptography:
in biological computing, and moreover, apply them to problems in pattern recognition, image working on a more challenging issue involving the database linkage
processing, data mining, and so on. problem: how to get the intended final answers without really linking This term has two major meanings. One is the study of cryptosys-
3. Network Design and Analysis the databases. Multiparty privacy computation can be applied and tems using quantum effects to establish security and privacy, such
as the famous BB84 protocol. The other is the study of cryptography
we plan to use secure scalar product as a building block to construct
The network design problem considers how to connect a collection of sites by a network such basic functions which in turn can be used to build various application that does not fall with the advent of quantum computers, which
that certain requirements are met. Topics in network design arise as central issues in wide are- systems. The ultimate goal is to develop a complete system, in which are expected to become a reality within two decades. Our research
as, such as VLSI design, wireless sensor network, bioinformatics, and communication networks. users can write their program in certain high level languages and the on MPKCs (Multivariate Public-Key Cryptosystems) has advanced
With respect to different applications, these issues demonstrate themselves in different forms, code will be automatically translated into a secure multiparty code the understanding of the field from both theoretical and practical
with subtle similarities via various quality measurements and constraints in practice. From an by a compiler. viewpoints. MPKCs operate on a vector of variables over a small
algorithmic point of view, we consider the construction and evaluation of networks under one 5. Computational Complexity field, instead of on an element in a huge algebraic structure (as
or more objective functions. We focus on several important measures to evaluate the quality in RSA or ECC). This key characteristic makes MPKCs faster while
of networks, including weight (total length of all edges), diameter (longest path between any Randomness has become a valuable resource in computation. For maintaining comparable design security; hence, they are useful for
two nodes), dilation (largest ratio of network distance to Euclidean distance), routing cost (total many computational problems, randomized algorithms are simpler, low-resource environments, such as embedded systems and smart
sum over the network distances between all vertex pairs), bottleneck bandwidth or capacity, more natural, or more efficient than the deterministic algorithms cur- cards. Recently, we have conducted several analyses and proposed
etc. We will also address issues about fault tolerance and dynamic maintenance of networks rently known. However, randomized algorithms typically depend on improvements to the design of such primitives. Today we have one
under node/link-transient failures. We will extend our research to related multi-criteria network the availability of a perfect random source, whose existence even in of the leading research teams in multivariate cryptosystems.
the nature is debatable. There are two approaches to resolve this is- ● Algebraic Cryptanalysis:
sue. One approach is to study whether or not randomized algorithms
can be derandomized into deterministic ones without sacrificing the We have made practical advances in equation-solving and alge-
performance too much. We show how such derandomization can be braic cryptanalysis, especially in Groebner Bases and the related XL
achieved under reasonable assumptions, and we also study its po- (eXtended Linearization) method and its variants. These system-
tential limitation. We will study how to derandomize special classes solving methods have shaken the field of stream ciphers, and re-
of randomized algorithms, such as those using logarithmic space or searchers are still looking for a replacement to the venerable RC4
constant parallel time, without relying on any assumption. The other cipher. We are still working on faster implementations and addi-
approach is to design procedures, called extractors, which can extract tional theory behind such system-solvers. This work also relates to
almost perfect randomness from slightly random sources. We provide the previously mentioned area above, since an attack on an MPKC
an optimal construction of extractors, which settles a long-standing is equivalent to solving an instance of the multivariate quadratic
open problem, and we also find a surprising application of extrac- systems (MQ) or the extended isomorphism of polynomials (EIP)
tors in cryptography, for building an encryption scheme with an ev- problems.
40 41