Institute of Information Science
計算理論與演算法實驗室
Principal Investigators:
呂及人 Chi-Jen Lu (Chair) 王大為 Da-Wei Wang 李德財 Der-Tsai Lee
徐讚昇 Tsan-sheng Hsu 高明達 Ming-Tat Ko 楊柏因 Bo-Yin Yang
廖純中 Churn-Jung Liau 劉進興 Jing-Sin Liu 鐘楷閔 Kai-Min Chung

[研究群介紹]
機器學習理論:在日常生活中,我們時常必須不斷在未知的環境中作決定,並為此付出代價。這可被抽象化為所謂的線上決策問題,而我們希望能為此問題設計出好的線上演算法,可以從過去的歷史中學習,而能在未來做出好的決定。對此問題,我們刻畫出一些自然而常見的環境條件,並在這些條件下設計出更有效率的線上演算法。此外,我們也為此問題在機器學習、賽局理論、複雜度理論等研究領域中找到新的應用。

一、密碼學
理論密碼學:理論密碼學致力於了解各種密碼學任務的可行性與極限。最近在密碼學有非常快速的進展,實現了許多甚至是過去無法想像的密碼學元件。我們參與了這項發展,並提出創新的程式混淆定義與功能加密系統的構造。另外,基於在網路上爆炸性成長的海量資料我們指出大規模多方安全計算的新需求,並提出新的構造滿足這些新的需求。我們也對以密碼學的角度來研究資訊領域以外的課題感興趣, 希望能引進新的視角去研究這些課題。量子密碼學:量子密碼學的主要目的之一是利用量子力學來實現古典框架下無法達成的密碼學任務。我們對於所謂的【設備無關量子密碼學】架構特別感興趣。此架構假設唯一的量子功能是來自於不可信的,甚至可能是敵人所準備的量子設備。此架構可說是最強的安全目標,因其對量子操作的信任假設最低。我們在這個方向上探索可被達成的任務,例如設備無關量子密鑰分配(deviceindependentquantum key distribution; DI-QKD)、物理系統亂 數抽取器(physical randomness extractors; PRE)。特殊硬體密碼學:包括微控制器晶片 (microcontroller, 即智慧卡的主要組件),可即時重新程式化的電路陣列 (Field Programmable Gate Array, FPGA) 上面的密碼學演算法。利用計算機的顯示晶片來做橢圓曲線的計算,可在破密上獲得破紀錄的速度。我們也做出低電流低耗能可以在 RFID 上執行的數位簽章演算法。最近也進行使用智慧型手機或其他類似的裝置來協助進行認證的資訊交換,或其他實用上的資訊安全研究。後量子密碼學:量子電腦發明之後可能存續的公鑰密碼系統(Post-Quantum Public-Key Cryptosystem), 特別是其中一個重要分類,多變量的公鑰密碼系統(MPKC),研究一種以處理多個小有限體中的變數,來取代大代數結構中的元素。該類系統一般也有高效能的名聲,適合用在小或嵌入式系統上。代數攻擊:XL演算法為一種解方程式的技巧,幫助終結線性回饋平移暫存器 (Linear Feedback Shift Register) 作為加密技術的時代,我們對它首度作完整的分析,並推廣到一些其他的應用。
排版插圖


二、巨量資料
巨量資料之邏輯與知識表達:巨量資料之中隱藏許多有用的資訊與知識,我們將以形式邏輯的方法來探討相關的知識表徵與推理問題。巨量資料相關之高速演算法設計:近年來大量資訊很容易在線上取得。我們研究如何利用這些巨量資料進行快速計算。研究題目包含資料隱私保護、多方私密計算、電腦對局理論和實作及大型社群網路的動態模擬。

三、圖論與圖論演算法
基礎圖論:圖論可以解決許多實際應用問題,而且也是很多理論研究的工具。我們通常先由基礎圖論性質的研究著手,然後藉由新性質的發現,設計高效率演算法,再進一步探討理論之突破,以及可能的應用價值。我們探討於實際應用產生的圖論演算法問題。網路設計與分析:網路設計問題探討的是如何將許多不同位置的站點,經由適當的網路架構連結以滿足特定的需求。這類問題含括了許多不同領域內的核心議題,例如超大型積體電路設計、無線傳感器網路、生物資訊學及通訊網路等。在不同的應用領域,這些問題透過各式各樣的效能評估方式及限制條件,以不同的形式出現,而其間又存在著微妙的共通性。
幾何計算:Voronoi圖形有非常廣泛的用途,是幾何計算領域學者長期研究的重要幾何結構。此結構所具有的性質及複雜度,還有如何計算而得等,都是幾何計算演算法的基本問題。當引進不同的「距離」概念時,例如「時間距離」,Voronoi圖形也會跟著變化。而其特性與所選定的「距離」如何互動改變,如何利用「距離」的某些性質,設計更有效率的演算法是我們所欲探討的問題。

四、機器人相關系統
發展機器人相關的系統設計、感測、規畫、控制的基礎理論和整合技術、情感與認知計算,讓人能安全舒適的與機器人進行必要的互動,使機器人能成為人類生活(包含食、衣、住、行、育、樂)的好夥伴與得力幫手,是當前及未來機器人研發的重要課題。我們正進行機器人的模擬與實驗研究為:基於地圖重建的自主導航與控制,平滑路徑規劃的軟性計算方法,以及整合感測網路與機器人的研究。
排版插圖

相關資訊

TOP
Academia Sinica 資訊科學研究所 Academia Sinica