中央研究院 資訊科學研究所

研究

友善列印

列印可使用瀏覽器提供的(Ctrl+P)功能

2015 重要研究成果

:::

軟體定義網路之可靠多點傳輸技術

IEEE International Conference on Computer Communications, IEEE INFOCOM (2015).

沈上翔、 黃良豪、 楊得年陳文村

作者所屬單位
  • 中央研究院資訊科學研究所

目前軟體定義網路的流量工程研究均著重在單點傳輸。相較之下,多點傳輸更可以有效地減少網路資源使用量而增進網路效率。然而,目前多點傳輸應用均要求資料不可遺漏,故可預見當網路營運者在使用軟體定義網路時,可靠多點傳輸技術將扮演必要之角色。目前網際網路所使用之最短路徑樹形傳輸在設計上並未能減少網路資源使用量,而圖論中之史坦爾樹亦由於未考慮資料回復節點之配置,亦無法支援可靠多點傳輸。因此,我們提出一個嶄新的可靠樹形傳輸理論,其不僅可滿足流量工程對於網路資源使用效率之要求,可對回復節點進行最佳配置。然而,找到最佳可靠多點傳播樹是非常困難的,我們證明此問題為 NP-Hard 且無法在 k 以內近似 ( 其中 k 為多點傳播目標數量 ),並設計了一個最佳的近似演算法。對真實網路拓樸進行模擬實驗與實際實作結果顯示,可靠多點傳播優於傳統最短路徑樹與史坦爾樹,且運算時間極短故可支援大量網路傳輸需求。

演算法示意圖

實驗結果圖

 檢視全文

零知識協定上的非黑箱技術

Paper presented at the 35th International Cryptology Conference (2015).

鐘楷閔

作者所屬單位
  • 中央研究院資訊科學研究所

簡介我們在零知識證明 (zero-knowledge proofs; ZK 證明 ) 上近年的研究。ZK 證明是重要的密碼學基元 (primitive),允許一個證明者 (prover) 去說服一個驗證者 (verifier) 一個給定命題的正確性,但同時不洩漏任何額外知識給驗證者。例如:一探員可證明他有資格進入某機構,但不洩漏其身分或密碼。雖看似矛盾,ZK 證明在密碼學上有無所不在的應用。 大部分的 ZK 證明構造都是所謂〝黑箱〞(black-box) 構造,但這被證明無法達到幾個較強版本的 ZK 證明,因此達成這樣的目標往往是多年未解的難題。我們發展所謂非黑箱技術 (non-black-box techniques),並以此構造了下述兩個較強 的 ZK 證明:
(1) 常數回合並發 ZK 證明 (concurrent ZK),基於不可區分程序混淆基元 (indistinguishability obfuscation)。( 主要相關著作 )
(2) 同時重設安全 ZK 證明 (simultaneously resettable ZK),基於最弱的單向函數 (one-way function) 假設。( 發表於 FOCS 2013)

零知識證明
(左)零知識證明;(中)常數回合並發零知識證明;(右)同時重設安全 ZK 證明

相關論文: 1 2 3 4