Page 138 - My FlipBook
P. 138
大
實驗
室
計算理論與演算法實驗室
Research Laboratories 研究人員
廖純中 / 召集人 本組的研究目標在探討計算問題本身的極限和效用，並為資訊科學其他領域建立穩固的理
論基礎。以下簡述幾個我們進行的研究主題。
研究員
一、量子與後量子密碼學
王大為
量子密碼學的目標是了解量子計算在密碼學中扮演的角色。對密碼學來說量子可說
研究員 是一把雙面刃：在壞人手中，大型的量子電腦可以通過秀爾演算法 (Shor’s algorithm)
攻破現行的大多數公鑰密碼系統實作。做為好人的一方，我們則需發展後量子密碼
呂及人 學 (Post-quantum Cryptography; PQC) 來應對。後量子密碼學 是研究在量子電腦攻擊
下仍然安全的密碼學演算法（通常專指公鑰密碼系統）的學科。另一方面，量子也增
研究員 強了好人的能力。量子密碼學廣泛的探索如何利用這樣的能力來達到更高的安全性或
更多的功能性。我們對於這兩個研究方向都有興趣，也同時從理論與實務的角度來進
李德財 行研究。在前者，我們積極的參與美國國家標準局 (NIST) 後量子密碼學標準的公開
徵選，我們提出的一個候選的密碼系統也順利晉級到目前第二輪的徵選階段。在理論
客座講座 方面，我們廣泛的參與多項研究課題，包含設備無關量子密碼學 (Device-indpendent
Cryptography)、古典委任量子計算 (Classical Delegation of Quantum Computation)、安
徐讚昇 全多方量子計算 (Secure Multiparty Quantum Computation) 與量子預言機模型下的安全
性 (Security in the Quantum Random Oracle Model) 等。
研究員
二、幾何計算
高明達
幾何計算考慮的是與幾何物件相關的計算問題，以及其演算法之開發。在這個領域中，
研究員 最常用的距離度量是歐式距離；但在許多實際的應用中，也有需要導入其他距離度量
以符合現實情境。舉例來說，曼哈頓距離用來表示在棋盤狀市區中的步行距離，而時
楊柏因 間距離則用來描述在不同速度的載具所形成的交通路網中所需要的移動時間。如果對
傳統的幾何問題（如沃羅諾伊圖形、凸包、路線規劃、設施放置等）導入不同的距離
研究員 度量，我們將會衍生具有理論重要性的幾何問題，在交通網路、無線感測網路、或是
超大型積體電路設計等不同的領域裡也可找到對應的實際應用。我們探討這些問題的
劉進興 性質與所選定的度量有何相依性，並利用新的性質設計高效率的演算法。
副研究員 三、組合最佳化與近似演算法
鐘楷閔 組合最佳化這個領域考慮如何在有限卻龐大的解集合中，找出最佳解的相關問題與方
法。在大部分的情況下，窮舉搜尋法對這領域的最佳化問題都不切實際，因此我們多
研究員 半訴諸於啟發式演算法、隨機演算法或是近似演算法，取得儘可能接近最佳的解。近
數十年來，設施放置問題（包括無容量限制與有容量限制）是這個領域中一個重要的
研究課題。由於此問題在模型上的簡單性與基礎性、以及在抽象的線性規劃表述裡所
表現出的多樣性，它在近代的近似演算法設計中扮演了非常重要的角色。我們基於過
去的相關研究成果，試圖以不同的觀點來解析設施放置問題。在演算法的研究過程中，
我們不僅想為這些問題設計高效率的演算法或最佳的近似解，而且要獲得更根本的分
析技巧與工具，用以解決組合最佳化領域中更多的相關問題。
136
實驗
室
計算理論與演算法實驗室
Research Laboratories 研究人員
廖純中 / 召集人 本組的研究目標在探討計算問題本身的極限和效用，並為資訊科學其他領域建立穩固的理
論基礎。以下簡述幾個我們進行的研究主題。
研究員
一、量子與後量子密碼學
王大為
量子密碼學的目標是了解量子計算在密碼學中扮演的角色。對密碼學來說量子可說
研究員 是一把雙面刃：在壞人手中，大型的量子電腦可以通過秀爾演算法 (Shor’s algorithm)
攻破現行的大多數公鑰密碼系統實作。做為好人的一方，我們則需發展後量子密碼
呂及人 學 (Post-quantum Cryptography; PQC) 來應對。後量子密碼學 是研究在量子電腦攻擊
下仍然安全的密碼學演算法（通常專指公鑰密碼系統）的學科。另一方面，量子也增
研究員 強了好人的能力。量子密碼學廣泛的探索如何利用這樣的能力來達到更高的安全性或
更多的功能性。我們對於這兩個研究方向都有興趣，也同時從理論與實務的角度來進
李德財 行研究。在前者，我們積極的參與美國國家標準局 (NIST) 後量子密碼學標準的公開
徵選，我們提出的一個候選的密碼系統也順利晉級到目前第二輪的徵選階段。在理論
客座講座 方面，我們廣泛的參與多項研究課題，包含設備無關量子密碼學 (Device-indpendent
Cryptography)、古典委任量子計算 (Classical Delegation of Quantum Computation)、安
徐讚昇 全多方量子計算 (Secure Multiparty Quantum Computation) 與量子預言機模型下的安全
性 (Security in the Quantum Random Oracle Model) 等。
研究員
二、幾何計算
高明達
幾何計算考慮的是與幾何物件相關的計算問題，以及其演算法之開發。在這個領域中，
研究員 最常用的距離度量是歐式距離；但在許多實際的應用中，也有需要導入其他距離度量
以符合現實情境。舉例來說，曼哈頓距離用來表示在棋盤狀市區中的步行距離，而時
楊柏因 間距離則用來描述在不同速度的載具所形成的交通路網中所需要的移動時間。如果對
傳統的幾何問題（如沃羅諾伊圖形、凸包、路線規劃、設施放置等）導入不同的距離
研究員 度量，我們將會衍生具有理論重要性的幾何問題，在交通網路、無線感測網路、或是
超大型積體電路設計等不同的領域裡也可找到對應的實際應用。我們探討這些問題的
劉進興 性質與所選定的度量有何相依性，並利用新的性質設計高效率的演算法。
副研究員 三、組合最佳化與近似演算法
鐘楷閔 組合最佳化這個領域考慮如何在有限卻龐大的解集合中，找出最佳解的相關問題與方
法。在大部分的情況下，窮舉搜尋法對這領域的最佳化問題都不切實際，因此我們多
研究員 半訴諸於啟發式演算法、隨機演算法或是近似演算法，取得儘可能接近最佳的解。近
數十年來，設施放置問題（包括無容量限制與有容量限制）是這個領域中一個重要的
研究課題。由於此問題在模型上的簡單性與基礎性、以及在抽象的線性規劃表述裡所
表現出的多樣性，它在近代的近似演算法設計中扮演了非常重要的角色。我們基於過
去的相關研究成果，試圖以不同的觀點來解析設施放置問題。在演算法的研究過程中，
我們不僅想為這些問題設計高效率的演算法或最佳的近似解，而且要獲得更根本的分
析技巧與工具，用以解決組合最佳化領域中更多的相關問題。
136
