2017年07月17日 瀏覽次數(shù): 0
姚班計科30班陳立杰同學(xué)的研究論文《On the Power of Statistical Zero Knowledge》7月1日被第五十八屆IEEE計算機科學(xué)基礎(chǔ)年會（58th Annual IEEE Symposium on Foundations of Computer Science，FOCS 2017）接收。該論文是陳立杰同學(xué)2016年與美國麻省理工學(xué)院及雅虎的幾位合作者共同完成的，解決了計算復(fù)雜性領(lǐng)域的一個重要難題。
零知識證明(zero knowledge proofs systems)在密碼學(xué)理論和復(fù)雜度理論中都有著非常重要的地位。具體來講，在一個零知識證明系統(tǒng)中，一個證明者要向一個驗證者在證明一個命題的正確性的同時，不能讓驗證者獲得除了這個命題的正確性以外的任何信息。 而其中要求最苛刻的被稱為統(tǒng)計零知識證明系統(tǒng)(statistical zero knowledge proofs systems，簡稱SZK)。
?????? 訪問MIT期間，陳立杰同學(xué)發(fā)現(xiàn)了指導(dǎo)教師Scott Aaronson教授2010年在STOC會議上發(fā)表的研究BQP復(fù)雜類（BQP表示量子算法在多項式時間內(nèi)可以計算的問題的集合）的論文中，關(guān)于BQP與SZK復(fù)雜類之間關(guān)系的證明存在漏洞，并寫了一篇論文彌補此漏洞，得到指導(dǎo)教授的高度評價。
在指導(dǎo)老師的鼓勵下，陳立杰與合作者研究了SZK和另一個復(fù)雜度類PP的關(guān)系，PP代表多項式時間內(nèi)可以以嚴格大于1/2的概率計算正確的問題的集合。該問題在2002年由著名量子信息學(xué)者John Watrous教授提出，在當時Scott Aaronson博士構(gòu)造了一個SZK和BQP之間的喻示分割，說明了并不存在一個量子的黑盒算法可以破解SZK。在很多情況下，如果將量子力學(xué)的法則稍作修改，就可能得具有更強大的計算能力的計算復(fù)雜度類，但這些復(fù)雜度類基本都包含于PP之中，可見復(fù)雜度類PP是BQP的一個最自然的拓展。陳立杰與合作者在論文中給出了一個SZK和PP的喻示分割(Oracle Separation)，這代表了PP中沒有一個黑盒算法(black box algorithm) 可以解決SZK中的全部問題。換句話說，他們證明哪怕有比量子計算（對應(yīng)BQP）更強計算能力的計算機（對應(yīng)PP），依然沒有黑盒算法可以解決SZK中的所有問題。
該研究工作也順帶提出一些新的喻示分割，并且給出了關(guān)于通信復(fù)雜度(Communication Complexity)類的結(jié)構(gòu)的一些結(jié)果。陳立杰是論文的主要貢獻者之一，結(jié)合了之前提出的一些工具，構(gòu)造了SZK和PP之間的喻示分割，隨后又與合作者一起加強了這個結(jié)論。
FOCS是理論計算機領(lǐng)域最頂級的國際學(xué)術(shù)會議，已連續(xù)舉辦57屆，擁有極高的領(lǐng)域影響力，本年度論文接收率約為27.9%。FOCS 2017將于十月在美國加州召開，屆時該論文將在大會上以報告形式進行展示。
版權(quán)與免責(zé)聲明：本網(wǎng)頁的內(nèi)容由收集互聯(lián)網(wǎng)上公開發(fā)布的信息整理獲得。目的在于傳遞信息及分享，并不意味著贊同其觀點或證實其真實性，也不構(gòu)成其他建議。僅提供交流平臺，不為其版權(quán)負責(zé)。如涉及侵權(quán)，請聯(lián)系我們及時修改或刪除。郵箱：sales@allpeptide.com