Page 38 - profile2012.indd
P. 38
Research Laboratories 研究群
計算理論與演算法實驗室
Computation Theory
and Algorithms Laboratory
研究人員
王大為 Da-Wei Wang 呂及人 Chi-Jen Lu 李德財 Der-Tsai Lee 高明達 Ming-Tat Ko 徐讚昇 Tsan-sheng Hsu 楊柏因 Bo-Yin Yang 廖純中 Churn-Jung Liau 劉進興 Jing-Sin Liu
Research Fellow Research Fellow Distinguished Research Fellow Research Fellow Research Fellow Associate Research Fellow Research Fellow Associate Research Fellow
研究群介紹
一、圖論與圖論演算法 亂度淬取程序,來由稍具亂度的弱亂數源中,淬取近乎完美的亂數,以
供隨機演算法使用。我們建構出目前最有效率的亂度淬取程序,而我們
基礎圖論:圖論可以解決許多實際應用問題,而且也是很 也發現亂度淬取程序於密碼學的應用。
多理論研究的工具。我們通常先由基礎圖論性質的研究著
手,然後藉由新性質的發現,設計高效率演算法,再進一 六、密碼學 計算理論和演算法研究在
步探討理論之突破,以及可能的應用價值。我們探討於實
際應用產生的圖論演算法問題。 特殊硬體密碼學:包括微控制器晶片 (microcontroller, 即智慧卡的主 探討計算問題本身的極限
要組件),可即時重新程式化的電路陣列 (Field Programmable Gate 和效用,為電腦科學之基
網路設計與分析:網路設計問題探討的是如何將許多不同 Array, FPGA) 上面的密碼學演算法。利用計算機的顯示晶片來做橢圓曲
位置的站點,經由適當的網路架構連結以滿足特定的需 線的計算,可在破密上獲得破紀錄的速度。我們也做出低電流低耗能可 石。
求。這類問題涵括了許多不同領域內的核心議題,例如超 以在 RFID 上執行的數位簽章演算法。最近也進行使用智慧型手機或其
大型積體電路設計、無線傳感器網路、生物資訊學及通訊 他類似的裝置來協助進行認證的資訊交換,或其他實用上的資訊安全研
網路等。在不同的應用領域,這些問題透過各式各樣的效 究。
能評估方式及限制條件,以不同的形式出現,而其間又存
在著微妙的共通性。 後量子密碼學:研究一種以處理多個小有限體中的變數,來取代大代數
結構中的元素的多變量的公鑰密碼系統(MPKC),它被認為是在量子電腦
二、幾何計算 四、資料密集計算 發明之後可能存續的公鑰密碼系統 (Post-Quantum Public-Key Cryp-
tosystem) 的一個重要分類,該類系統一般也有高效能的名聲,適合用
Voronoi圖形有非常廣泛的用途,是幾何計算領域學者長期 巨量資料之邏輯與知識表達:巨量資料之中隱藏許多有用 在小或嵌入式系統上。
研究的重要幾何結構。此結構所具有的性質及複雜度,還 的資訊與知識,我們將以形式邏輯的方法來探討相關的知
有如何計算而得等等都是幾何計算演算法的基本問題。當 識表徵與推理問題。 代數攻擊:XL 演算法為一種解方程式的技巧,幫助終結了線性回饋平移
引進不同的「距離」概念時,例如「時間距離」,Voronoi 暫存器 (Linear Feedback Shift Register) 作為加密技術的時代,我們對
圖形也會跟著變化。而其特性與所選定的「距離」如何互 巨量資料相關之高速演算法設計:近年來大量資訊很容易 它首度作了完整的分析,並推廣到一些其他的應用。
動改變,如何利用「距離」的某些性質,設計更有效率的 在線上取得。我們研究如何利用這些巨量資料進行快速計
演算法是我們所欲探討的問題。 算。研究題目包含資料隱私保護、多方私密計算、電腦對
局理論和實作及大型社群網路的動態模擬。
三、機器人相關系統
五、複雜度理論
發展機器人相關的系統設計、感測、規畫、控制的基礎理
論和整合技術、情感與認知計算,讓人能安全舒適的與機 亂數在計算上,已成為一個有用的資源,因為隨機演算法
器人進行必要的互動,使機器人能成為人類生活(包含食、 對許多重要計算問題提供了目前最有效率的解決方法。然
衣、住、行、育、樂)的好夥伴與好幫手,是當前及未來機 而一般隨機演算法的設計,均假設有完美的亂數供其使
器人研發的重要課題。我們正進行機器人的模擬與實驗研 用。然而電腦或自然界能否存產生完美的亂數,也是一個
究為:基於地圖重建的自主導航與控制,平滑路徑規劃的 值得爭議的問題。解決此困境的第一種方法,乃是研究如
軟性計算方法,以及整合感測網路與機器人的研究。 何將隨機式演算法有效率的轉化成確定式演算法。我們研
究如何在合理的假設下達成這個目的,我們也研究這種方
法的可能極限。解決困境的第二種方法,乃是設計所謂的
研究群
38 Research Laboratories
39