看看密碼學專家 2019 年在安全多方計算、零知識證明、同態加密等密碼學技術做出的努力及其成果。

原文標題:《年度盤點!2019 年矩陣元參與全球密碼學頂級會議及其最佳論文(附鏈接)》
作者:矩陣元

密碼學是一門古老的學科,發展至現代後,主要研究構造和分析信息系統以防止私密信息被竊取,涉及信息的機密性、完整性、真實性和不可抵賴性,以及在分佈式計算中產生的來源於內部和外部的攻擊的所有信息安全問題。

近些年來,密碼學作爲區塊鏈網絡中最基礎的存在,不僅保護了整個網絡的安全,更解決了很多交易中的證明問題。2019 年,矩陣元團隊在精研自身技術的同時,將足跡遍佈全球,承辦或參與頂尖密碼學會議,學習借鑑最新算法技術。

接下來,讓我們一起盤點 2019 年矩陣元協辦或參與的全球頂尖密碼學會議及其最佳論文,帶大家回顧今年密碼學專家在安全多方計算、零知識證明、同態加密等密碼學技術做出的努力及其成果,精彩不要錯過!

1. 2019 年歐密會

5 月 19 日至 5 月 23 日,矩陣元受邀參與的 2019 年歐密會 (Eurocrypt 2019) 在德國達姆施塔特召開。歐密會是密碼學界的三大密碼學術會議之一,於每年春季在歐洲各地舉行,2019 年已舉辦到第 24 屆。

Eurocrypt 2019 最佳論文

Quantum Lightning Never Strikes the Same State Twice
作者:Mark Zhandry

論文簡介: 來自普林斯頓大學的 Mark Zhandry 研究了量子閃電和量子貨幣,做了顯著的成果,包括:(1)提出了一系列可實踐的應用,包括帶可證明熵的隨機字符串生成以及無需區塊鏈的密碼貨幣;(2)給出了關於量子貨幣和量子閃電的「二選一」(Either/OR) 關係結論,即要麼數字簽名 / 哈希 / 承諾方案滿足非常強的安全性,要麼可以根據這些密碼學原語構造量子貨幣或者量子閃電方案;(3)通過 STOC’12 上 Aaronson 和 Christiano 的量子貨幣方案與抗量子攻擊的不可區分混淆的安全性 (indistinguishability obfuscation) 相結合,證明了可以構造出一個安全的量子貨幣方案;(4)提出了一個可靠的量子閃電構造,並且在基於二度哈希算法的抗多碰撞性的安全模型下給出了安全性證明。這個構造方案也是基於前述哈希方案的二選一關係結論,併產生了第一個在標準模型下的構造設計,即非坍縮 (non-collapsing) 的抗碰撞哈希算法。

原文鏈接

Eurocrypt 2019 最佳青年學者論文

Efficient Verifiable Delay Functions
作者:Benjamin Wesolowski

論文簡介: 來自洛桑聯邦理工學院和荷蘭國家數學與計算機科學研究中心的 Benjamin Wesolowski 提出了一個高效的可驗證延遲函數 (Verifiable Delay Function, VDF)。VDF 是一種易於驗證、但是計算過程必須經過一定步驟且無法利用並行計算來加速優化的函數;VDF 在分佈式系統中有很多應用,例如可信隨機數生成。作者構造了一種帶陷門 (trapdoor) 的 VDF。獲知陷門的參與者可以很容易計算 VDF。通過巧妙的設計,構造出了一種 VDF 方案可以將陷門完全隱藏,即使是該執行 VDF 方案初始化過程的參與者也無法獲知陷門信息。作者主要利用階未知的羣構造 VDF 方案,包括 RSA 羣和 imaginary quadratic field(虛二次域);方案中 VDF 函數的輸出長度非常短(計算結果和正確性證明均是一個羣元素),且正確性證明的驗證非常高效。

原文鏈接

2. 2019 年美密會

8 月 18 日至 22 日,矩陣元受邀參與的 2019 年美密會(CRYPTO 2019)在美國聖巴巴拉成功召開。

美密會是「國際密碼學協會」(IACR,International Association of Cryptological Research)所主辦的三個大會(美密會、歐密會、亞密會)中水平最高的密碼學會議。

2019 年美密會開展期間,來自全球密碼學領域的專家學者分享最新學術成果,包括安全多方計算、零知識證明、同態加密等方向的研究論文。

一文瀏覽 2019 全球頂尖密碼學會議及最佳論文成果

全球安全多方計算領域的權威專家美國馬里蘭大學 Jonathan Katz 教授,向來自世界各地的頂尖密碼學研究者們闡述了 MPC 領域當前的研究與發展狀況,並且列舉了全球範圍內在 MPC 領域尋求突破的機構與企業。
自成立以來,矩陣元長期耕耘於密碼學領域及隱私計算技術,不僅全力支持國內密碼學領域的發展與實際應用落地,而且積極參與推動全球範圍內的密碼學探索研究。

Crypto 2019 最佳論文

Cryptanalysis of OCB2 : Attacks on Authenticity and Confidentiality

作者:Akiko Inoue, Tetsu Iwata, Kazuhiko Minematsu, Bertram Poettering

論文簡介:這是本次會議最佳論文,來自一個日本的團隊。他們成功地破解了認證加密(Authenticated Encryption)的 OCB2 模式。起初他們只是發現了 OCB2 相關的某個證明裏的一個漏洞,本想將其修復,然而窺一斑而知全豹,從這點出發,該團隊構造出了對 OCB2 模式非常徹底的攻擊方案,攻破了 OCB2 的「真實性」(authenticity)和「保密性」(confidentiality)。值得注意的是,OCB2 已在 2009 年被納入 ISO 國際標準,由於此論文的研究成果,ISO 正在執行移除此項標準的流程手續。

原文鏈接

Crypto 2019 相關論文

Scalable Zero Knowledge with no Trusted Setup
作者:Eli Ben-Sasson, Iddo Bentov, Yinon Horesh, Michael Riabzev

論文簡介:自上世紀 90 年代零知識證明被提出以來,構造零知識參數都依賴於稱爲「概率檢驗證明」(Probabilistically Checkable Proofs,PCPs)的技術。直到現在,這些早期的構造方案均未被實現,其原因是因爲證明過程所需時間太長。爲了解決此問題,今年來也相繼出現一些研究成果,但仍未尋找到最佳的解決方案。來自以色列的密碼學研究員 Eli Ben-Sasson 等人提出了一種新型的「交互式預言機證明」(interactive oracle proofs,IOPs)系統——zk-STIK,並在論文中給出了形式化的定義。論文成果表明,該構造方案漸進地改進了現有方案中的證明過程以及驗證過程的計算複雜度,將這兩個過程的計算複雜度均降低了 poly(log(T)) 倍(其中 T 爲計算的大小)。同時,該研究團隊也給出了此係統的實現庫 libSTARK,並已開源。相比於先前的部分零知識證明實現的複雜計算度,其證明生成執行效率提高了 10 倍,驗證所需時間降低了 7-40 倍,並且通信複雜度也降低了 3-20 倍。

原文鏈接

3. 2019 年中密會

11 月 1 日至 3 日,中國密碼學會 2019 年學術會議(ChinaCrypt 2019)在西安隆重召開。本次會議由中國密碼學會主辦,西安電子科技大學和中國科學院信息保障技術重點實驗室聯合承辦,矩陣元技術(深圳)有限公司協辦,吸引來自全國高等院校、科研院所、公司企業等從事密碼算法研究的人員約 800 餘人參加會議。

會議期間,矩陣元 COO 謝紅軍擔任組織委員會成員,矩陣元首席密碼科學家何德彪教授出席會議,算法科學家謝翔博士作爲特邀嘉賓出席並發表了《高等級密碼學算法的應用和挑戰》主題報告。

一文瀏覽 2019 全球頂尖密碼學會議及最佳論文成果

一直以來,矩陣元積極推進國內密碼研究與發展,曾協辦並參與中國密碼學會 2018 年會,分享自身在隱私性和拓展性方面的研究與應用。目前,矩陣元已經聚集了一批密碼學科研和技術人員,推動密碼算法與區塊鏈技術的應用融合。

4. 全球信息安全盛會 ACM CCS 2019

11 月 11 日至 15 日,矩陣元受邀參與的全球信息安全頂級盛會 ACM CCS 2019 (ACM Conference on Computer and Communications Security 2019)在英國倫敦的希爾頓大都會酒店舉行,這是信息安全領域的頂級學術會議,與 IEEE S&P、USENIX Security 和 NDSS 並稱計算機安全領域「四大安全頂級會議」, 每年都有來自全球頂尖高校以及研究機構的衆多研究人員投稿和參會。

一文瀏覽 2019 全球頂尖密碼學會議及最佳論文成果

會議爲期 5 天,同期舉辦 13 個信息安全領域不同方向的研討會,涵蓋雲安全、移動安全、隱私數據安全、機器學習安全、密碼學、區塊鏈安全等主題,共接收 149 篇論文。

ACM CCS 2019 最佳論文

Where Does It Go? Refining Indirect-Call Targets with Multi-Layer Type Analysis
作者:KangJie Liu,Hong Hu

論文簡介:來自明尼蘇達大學的 KangJie Liu 和來自佐治亞理工學院的 Hong Hu 兩位華人學者提出的針對系統軟件中的間接調用 (indirect calls) 識別和分析的全新理論和方法,獲得了本屆大會的最佳論文獎。傳統的對間接調用的識別方法基於類型分析,存在較高的假陽性概率。論文中提出了一種多層類型分析 (Multi-Layer Type Analysis, MLTA) 技術,可以有效地在 C/C++程序中識別間接調用的目標。作者通過基於 LLVM 實現了 MTLA 技術,在 Linux 內核、FreeBSD 內核和 Firefox 瀏覽器內核中進行了相應測試,評估後發現識別率是傳統方法的 1.86-1.98 倍,同時通過該項實驗,作者進一步發現了 Linux 內核中潛在的 35 個語義漏洞。

原文鏈接

5. 第五屆全國密碼技術競賽

11 月 22 至 24 日,由中國密碼學會主辦的第五屆全國密碼技術競賽決賽在北京郵電大學舉行,矩陣元首席密碼科學家何德彪教授指導的武漢大學國家網絡安全學院「no_warning」參賽隊作品「輕量級 SM2 盲簽名方案的設計與實現」,從全國 74 所高校、357 支參賽隊脫穎而出,獲得大賽特等獎。何德彪教授由此榮獲優秀指導教師獎。

「輕量級 SM2 盲簽名方案的設計與實現」是根據矩陣元需要設計的算法,是對國家商用密碼標準 SM2 數字簽名算法的進一步擴展,能夠在保護用戶隱私發麪發揮重要作用,因其具有良好的性能和輕量性特點,更加適用於移動設備,且方案對簽名端的算法改動較小,對於市場上已有設備方便升級,該方案的這些功能特點將更加有助於推動國家商用密碼標準應用於更多的應用場景。

一文瀏覽 2019 全球頂尖密碼學會議及最佳論文成果矩陣元首席密碼科學家何德彪教授 (右二)

爲打造強隱私保護、可擴展、高性能的分佈式計算網絡,矩陣元自成立起深耕密碼學領域及其技術,注重密碼學領域人才的培養與建設,引入國內外密碼學專家,2019 年已完成組建以博士爲主的高水平密碼算法團隊。建立以密碼學爲主的「創新研究院」,爲促進密碼學算法研究及其工程化實現共同努力。

2019 年密碼學領域年底頂尖會議精彩預告

2019 年亞密會

12 月 8 日至 12 日,矩陣元受邀參與的 2019 年亞密會(Asiacrypt 2019),即第 25 屆年度國際密碼學與信息安全理論與應用國際會議,將在日本神戶隆重舉行,公佈全球頂級的密碼學論文。

亞密會與美密會、歐密會同屬密碼學領域的三大頂尖級會議,其論文集中收錄的成果可以代表領域內同期最高水平。

Asiacrypt 2019 最佳論文

Wave: A New Family of Trapdoor One-Way Preimage Sampleable Functions Based on Codes
作者:Thomas Debris-Alazard, Nicolas Sendrier, Jean-Pierre Tillich

論文簡介:來自索邦大學的 Thomas Debris-Alazard 和 Nicolas Sendrier,與來自法國國家信息與自動化研究所的 Jean-Pierre Tillich,提出了一系列新穎的陷門原像採樣函數。這種陷門單向函數基於兩類假設:1. 高權重通用解碼的困難性;2. 通用「(U,U+V)-編碼」的不可區分性。作者通過新的陷門原像採樣函數與通用「(U,U+V)-編碼」結合,首次提出了一類基於編碼的「hash-and-sign」模式的數字簽名方案,該方案滿足在隨機預言機模型下的 EUF-CMA 安全性強度,即在可適配的選擇消息攻擊下,攻擊者無法僞造簽名。

原文鏈接

Asiacrypt 2019 相關論文

Valiant’s Universal Circuits Revisited: An Overall Improvement and a Lower Bound
作者:Shuoyao Zhao, Yu Yu, Jiang Zhang, Hanlin Liu

論文簡介:這是青年長江學者、上海交通大學鬱昱教授署名文章,主要介紹通用電路 (Universal Circuits, UC) 是一種可以模擬任意電路的通用型電路。頂級理論計算機會議 STOC ’1976 上,Valiant 提出了一種基於圖理論構建通用電路的方法,將通用電路表示爲邊通用圖 (edge universal graph, EUG),並且利用一種特定的圖對象(稱爲「超級頂點」)通過遞歸的方式進行構造。Valiant 提出的構造方案(包括 4 路 19 個超級頂點和 4.75nlogn 的 EUG 長度)在 40 年之後仍然是目前最高效的方法。論文提出了一種更高效的方案,僅需要 4 路 18 個超級頂點以及 4.5nlogn 的 EUG 長度。新方案構建的通用電路的大小規模和與門 (AND gates) 的個數降低了 5%,將使得所有基於通用電路的密碼學方案在整體性能上獲得顯著提升。同時作者給出了 Valiant 框架下的 EUG 和 UC 的規模的下限,這大大改善了 UC 大小的一般下限,縮短了通用電路的理論與實踐之間的差距。

原文鏈接

Asiacrypt 2019 相關論文

Divisible E-Cash from Constrained Pseudo-Random Functions
作者:Florian Bourse, David Pointcheval, Olivier Sanders

論文簡介:Florian Bourse, David Pointcheval 和 Olivier Sanders 在電子現金領域,針對可分割性問題方面進行了拓展性的工作。目前這方面的研究存在許多困難,包括構造的複雜性、現有構造依賴於特定的環境設定、安全模型和安全證明的缺失等,作者首次提出了電子現金可分割性方面的完整的安全模型,並且結合受約束的僞隨機函數給出了兩類可分割的電子現金框架,即滿足密鑰的同態性,或者滿足可委託性,且均給出了安全性證明。作者還提出了一種叫做「clearing」(安全清算) 的安全性,即只允許交易的接收者來進行存款;並且揭示了此前多數關於「exculpability」(可免責性,即應該防止誠實用戶被錯誤指控) 的安全性證明均存在漏洞且難以在標準模型下得到修復,因此作者提出了一個在標準模型下的安全構造方案。

原文鏈接

2019 年,是密碼學獲得廣泛關注的一年,也是得以快速發展的一年,爲使密碼學技術在全社會應用並不斷進步,全世界的密碼學團隊及其研究人員仍在繼續精進密碼技術,而矩陣元作爲其中一員,將持續保持初心、精耕細作,爲促進密碼學算法的優化和應用不斷做貢獻!