高木 剛（東京大學 研究生院資訊理工學系研究科 教授）
|公布量子電腦時代的新型密碼技術
東京大學研究生院資訊理工學系研究科的高木剛教授等人的研究團隊，公布了面向新一代電腦的新型數位簽章方案「QR-UOV」的技術規範。數位簽章方案是為網際網路上往來傳輸的文件與數據提供建立者身份以及內容擔保的機制。
QR-UOV是抗量子密碼的一種。抗量子密碼指的是，即便處理速度較傳統電腦有飛躍性提升的量子電腦實現實用化，仍極難被破解的密碼方案，目前正作為新一代資訊安全基礎，推進研究與標準化工作。
此次公開的QR-UOV具備安全性高、公鑰與簽章資料※1尺寸小的優勢，實現了安全性與效率的兼顧。該方案在美國國家標準與技術研究院（NIST）主辦的抗量子密碼標準化競賽中，是來自日本的方案中唯一晉級第二輪的提案。
※1 公鑰與簽章資料：公鑰是用於驗證數據及數位簽章是否確為生成者本人發佈的數據，具有防範身份冒充的作用。簽章資料是與公鑰配合使用，用以確認數據由本人生成、內容未遭篡改的數據。
圖1 QR-UOV方案的特點：安全性高，所需數據量不到傳統方案的一半。
|量子電腦的登場威脅密碼通信安全
數位簽章被廣泛應用於電子合同、軟體、個人認證等領域，是支撐資訊社會可信度的基礎技術。當前，主流數位簽章的安全性基於整數分解與離散對數問題的難度得以保障，但有觀點指出，當大規模量子電腦成為現實，便可輕鬆求解這類問題，從而可能導致密碼體系被破解並遭到惡意利用。
因此，即便使用了量子電腦仍可保障安全性的密碼技術——即所謂抗量子密碼，其研發工作正在全球範圍內推進。美國國家標準與技術研究院自2016年起推進抗量子密碼的標準化工作，正通過分階段遴選選定可作為國際標準的方案。
|以QR-UOV方式攻克公鑰長度難題
藉助剩餘類環大幅縮減數據量
QR-UOV以1999年提出的數位簽章方案UOV為基礎，針對該方案此前存在的公鑰數據尺寸大小問題進行了改良。傳統UOV方案將公鑰表示為數值縱橫排列的矩陣形式（圖2）。矩陣是電腦上數值計算時常用的表達形式，但存在數據尺寸易偏大的缺點。
另一方面，QR-UOV將公鑰表示為一種被稱為剩餘類環※2的代數框架下的多項式。剩餘類環是指在僅考慮除以某數所得餘數的規則下進行運算的框架，可避免計算結果無限增大。該方案在維持高安全性的同時，大幅削減了公鑰的數據尺寸。
※2 剩餘類環：常規運算中，反復進行加法與乘法會導致計算結果位數持續增加。而剩餘類環遵循「僅處理除以某數所得餘數」的規則開展運算。例如，計算除以5的餘數時，6按1處理、7按2處理。剩餘類環是通過這種方式，將計算結果的數據量限定在一定範圍內的機制。
圖2 QR-UOV方案示意圖
力爭成為抗量子密碼的標準規格
作為新規格的QR-UOV方案，針對傳統UOV方案長期存在的公鑰長度問題，重新調整了密碼結構的表達形式與計算方法。本成果使得該方案既滿足美國國家標準與技術研究院標準化競賽的性能要求，又同時具備面向實際系統部署的可行設計。
|致力於打造未來安全基礎技術
美國國家標準與技術研究院表示，將在未來數年內完成抗量子密碼標準方案的遴選。若QR-UOV被採納為標準規格，則有望作為量子電腦時代仍可安全使用的數位簽章方案，在全球範圍內得到廣泛應用。研究團隊今後將繼續推進QR-UOV的安全性評估和實現技術改進，開展面向國際標準化與社會應用的研發工作。
原文：JST 事業成果 資訊通信領域
翻譯：JST客觀日本編輯部
【論文資訊】
會議：NIST Post-Quantum Cryptography: Round 2 Additional Signatures
論文：Post-Quantum Cryptography: Additional Digital Signature Schemes
URL：https://csrc.nist.gov/Projects/pqc-dig-sig/round-2-additional-signatures
【相關閱讀】
KDDI綜合研究所與東京大學破解「抗量子計算密碼」創下世界紀錄
KDDI綜研與東京大學在抗量子電腦密碼破譯競賽中刷新世界紀錄
「日本產」量子計算時代的安全密碼——數位簽章方式「QR-UOV」，成功晉級美國標準化競賽第2輪
東京大學在新一代密碼破譯大賽中創下世界紀錄
