基于格的變色龍哈希函數研究概述

蔣 芬 傅海明

廣州華夏職業學院 廣東 廣州 510000

研究背景

通信安全主要經歷了兩個階段:第一階段經典信息安全,基本采取的是將字母替換或者代換等操作,比如凱撒密碼等,還包括與此對應的密碼安全攻防相關信息安全策略;第二階段為現代信息安全,包括現代密碼理論,以AES,RSA等密碼算法的提出為標志。目前,隨著量子計算等技術日益發展,基于格的密碼算法能抵抗量子計算攻擊,從而對其研究成為重要方向之一。

哈希函數是密碼算法中非常重要的構建,針對給定向信息找其哈希值實際也就是計算其數字指紋。給定信息A情況下,找到信息B,使得二者哈希值一樣是非常困難的,甚至任意找兩個信息使得二者哈希值一樣都非常困難,即計算碰撞的困難性。傳統哈希函數計算碰撞的困難性保障了信息的安全,同時也產生了一定的應用的局限性。

變色龍哈希函數相對于傳統的哈希函數最大的特點是其在秘鑰的控制下計算碰撞成為可能。綜上,對基于格的變色龍哈希函數的研究成為一個趨勢。比如在文獻[1]中,朱艷艷等人就闡述了傳統哈希函數應用在區塊鏈上的局限性,并基于變色龍哈希函數對基于區塊鏈設計的指紋識別系統進行了設計。Wu Chunhui;

Ke Lishan;Du Yusong等人則在文獻[2]中考慮了變色龍哈希函數對量子計算的抵抗弱的特點,而對基于格的變色龍哈希函數進行了系列算法研究和應用實現。

基于格的變色龍哈希函數理論基礎

格的定義[3]:Rn空間一線性無關的向量組a1,a2…,an,在整系數z1,z2…,zn下,空間?={(a1,a2…,an)·(z1,z2…,zn)}稱為格。a1,a2…,an為格的一組基,n稱為格的維度。

從格的概念可以看出格空間其實是網格狀的,a1,a2…,an的坐標都是整數,那么可以得到整數格。

格上的困難問題[3]:

最短向量問題(SVP):格中尋找最短的非零向量,即尋找一個向量v∈L其歐幾里得范數||v||最小;

最近向量問題(CVP):對給定的非格中的向量w,尋找格中向量v,使得其歐幾里得范數||w-v||最小。

在密碼算法的安全性都基于的困難問題是可以規約到以上兩個困難問題上的。基于格的密碼體制的優勢主要體現在:(1)計算速度更快;(2)安全性更高。

基于格的變色龍哈希函數的研究現狀

1998年,Krawczyk和Rabin[4]初次提出變色龍哈希函數的概念,并詳細給出了基于數論難題的變色龍哈希函數的構造方法,基于的數論難題構造的密碼算法存在量子計算機下多項式時間內的求解算法,故基于此類問題構造的變色龍哈希函數安全性也受到量子攻擊的威脅。

2008年,Gentry,Peikert 和Vaikuntanatha[5]給出了原像采樣陷門函數的定義,該陷門函數的構造是基于困難格假設的,其安全性依賴于求解格上小整數解問題(Short Integer Solution,SIS)的困難性;

SIS:隨機矩陣A∈作為公開的部分,然后找到短向量x∈zn×1使得Ax=0modq。

隨后,D.Cash[6]等人于2010年基于格上難題:小整數解(Short Integer Solution,SIS)和非齊次小整數解問題(Inhomogeneous Short Integer Solution,ISIS),將消息和隨機數應用于原像采樣陷門函數設計了首個基于ISIS的變色龍哈希函數;

ISIS:隨機矩陣A∈Zm×nq作為公開部分,給定非零向量ε∈Zn,然后找到短向量ε∈Zn使得Ax=εmodq。

2013年謝璇等在文獻[7]中也給予SIS和ISIS的困難性假設,構造了變色龍哈希函數并應用在變色龍簽名方案中。

以上方案中的原像采樣陷門函數,理論是齊次線性方程組和對應的非其次線性方程組的解的關系上構建的陷門函數。非齊次線性方程做的系數矩陣A作為公鑰,系數矩陣的極大線性無關組作為B作為私鑰,在私鑰的計算碰撞。顯然如果要做到變色龍哈希函數,A的秩要大于B的秩。

2018年,Zhang C,Ma W 和Zhao F[8]基于環上的錯誤學習問題(Ring-Learning with Error,R-LWE),結合工具矩陣提出了一種陷門函數的構造方案,其安全性依賴于R-LWE問題;

2019年,楊慧慧在其碩士論文[9]中基于LWE問題進行了基于格的變色龍哈希函數及其應用研究;

LWE(Learning With Error)問題是格上的困難問題,主要表現為已知矩陣A以及關系式b=Ax+e,其中e是固定范圍內隨機采集的噪音向量,能否通過A和b確定x的問題。LWE問題與最近向量問題相似,其實兩個問題都樣,需要找到一組“系數”使得一組基向量A的線性組合無限逼近目標向量b,誤差噪音e的大小來定義距離目標向量b多近。

2020年,Wu Chunhui;Ke Lishan;Du Yusong等人在文[2]中構建了基于格的變色龍哈希函數,并同時考慮到秘鑰的泄露問題;

目前對于變色龍哈希函數的算法構造研究和應用并申請相關專利成為一個比較熱門的方向。基于格構造的變色龍哈希函數或者其相關應用方面的專利更是屈指可數,目前如專利[10]和[11]基于格設計了一定應用價值的基于格變色龍哈希函數。

對變色龍哈希函數的研究上目前仍然有非常大的研究空間,比如文獻[12]中基于身份的變色龍哈希函數的應用研究在格空間上的實現,文獻[13]的門限機制在格空間的實現,文獻[2]針對格上的變色龍哈希函數考慮了秘鑰的泄露的問題,專利[10]在多方參與的情況下如何公平快速地實現碰撞的計算等都是值得研究的方向。

基于格的變色龍哈希函數的研究價值

對于基于格空間的變色龍哈希函數的研究具備非常重要的研究價值,主要體現在以下幾個方面重要的應用。

電子選舉:在電子選舉過程當中,可以用來隱藏敏感的投票人信息和選票信息。

數據凈化:對于原始數據的敏感信息可以適當修改,而不影響數據的來源和完整性的確認等。

代理簽名:對于電子簽名過程當中,如果簽名內容是可以根據實際情況修改的,那么可以運用變色龍哈希函數。

電子合同:可以用來在電子合同的簽署過程當中,把部分合同內容的確定權限賦予簽署合同的人。

可編輯區塊鏈:針對傳統區塊鏈的不可修改性,提出相對比較靈活性的可編輯區塊鏈,在可編輯區塊鏈中,某些信息可以被修改和不影響整個鏈條的完整性驗證。