基于格的變色龍哈希函數(shù)研究概述

蔣 芬 傅海明

廣州華夏職業(yè)學(xué)院 廣東 廣州 510000

研究背景

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

哈希函數(shù)是密碼算法中非常重要的構(gòu)建,針對(duì)給定向信息找其哈希值實(shí)際也就是計(jì)算其數(shù)字指紋。給定信息A情況下,找到信息B,使得二者哈希值一樣是非常困難的,甚至任意找兩個(gè)信息使得二者哈希值一樣都非常困難,即計(jì)算碰撞的困難性。傳統(tǒng)哈希函數(shù)計(jì)算碰撞的困難性保障了信息的安全,同時(shí)也產(chǎn)生了一定的應(yīng)用的局限性。

變色龍哈希函數(shù)相對(duì)于傳統(tǒng)的哈希函數(shù)最大的特點(diǎn)是其在秘鑰的控制下計(jì)算碰撞成為可能。綜上,對(duì)基于格的變色龍哈希函數(shù)的研究成為一個(gè)趨勢(shì)。比如在文獻(xiàn)[1]中,朱艷艷等人就闡述了傳統(tǒng)哈希函數(shù)應(yīng)用在區(qū)塊鏈上的局限性,并基于變色龍哈希函數(shù)對(duì)基于區(qū)塊鏈設(shè)計(jì)的指紋識(shí)別系統(tǒng)進(jìn)行了設(shè)計(jì)。Wu Chunhui;

Ke Lishan;Du Yusong等人則在文獻(xiàn)[2]中考慮了變色龍哈希函數(shù)對(duì)量子計(jì)算的抵抗弱的特點(diǎn),而對(duì)基于格的變色龍哈希函數(shù)進(jìn)行了系列算法研究和應(yīng)用實(shí)現(xiàn)。

基于格的變色龍哈希函數(shù)理論基礎(chǔ)

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

從格的概念可以看出格空間其實(shí)是網(wǎng)格狀的,a1,a2…,an的坐標(biāo)都是整數(shù),那么可以得到整數(shù)格。

格上的困難問(wèn)題[3]:

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

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

在密碼算法的安全性都基于的困難問(wèn)題是可以規(guī)約到以上兩個(gè)困難問(wèn)題上的?；诟竦拿艽a體制的優(yōu)勢(shì)主要體現(xiàn)在:(1)計(jì)算速度更快;(2)安全性更高。

基于格的變色龍哈希函數(shù)的研究現(xiàn)狀

1998年,Krawczyk和Rabin[4]初次提出變色龍哈希函數(shù)的概念,并詳細(xì)給出了基于數(shù)論難題的變色龍哈希函數(shù)的構(gòu)造方法,基于的數(shù)論難題構(gòu)造的密碼算法存在量子計(jì)算機(jī)下多項(xiàng)式時(shí)間內(nèi)的求解算法,故基于此類問(wèn)題構(gòu)造的變色龍哈希函數(shù)安全性也受到量子攻擊的威脅。

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

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

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

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

2013年謝璇等在文獻(xiàn)[7]中也給予SIS和ISIS的困難性假設(shè),構(gòu)造了變色龍哈希函數(shù)并應(yīng)用在變色龍簽名方案中。

以上方案中的原像采樣陷門函數(shù),理論是齊次線性方程組和對(duì)應(yīng)的非其次線性方程組的解的關(guān)系上構(gòu)建的陷門函數(shù)。非齊次線性方程做的系數(shù)矩陣A作為公鑰,系數(shù)矩陣的極大線性無(wú)關(guān)組作為B作為私鑰,在私鑰的計(jì)算碰撞。顯然如果要做到變色龍哈希函數(shù),A的秩要大于B的秩。

2018年,Zhang C,Ma W 和Zhao F[8]基于環(huán)上的錯(cuò)誤學(xué)習(xí)問(wèn)題(Ring-Learning with Error,R-LWE),結(jié)合工具矩陣提出了一種陷門函數(shù)的構(gòu)造方案,其安全性依賴于R-LWE問(wèn)題;

2019年,楊慧慧在其碩士論文[9]中基于LWE問(wèn)題進(jìn)行了基于格的變色龍哈希函數(shù)及其應(yīng)用研究;

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

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

目前對(duì)于變色龍哈希函數(shù)的算法構(gòu)造研究和應(yīng)用并申請(qǐng)相關(guān)專利成為一個(gè)比較熱門的方向?；诟駱?gòu)造的變色龍哈希函數(shù)或者其相關(guān)應(yīng)用方面的專利更是屈指可數(shù),目前如專利[10]和[11]基于格設(shè)計(jì)了一定應(yīng)用價(jià)值的基于格變色龍哈希函數(shù)。

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

基于格的變色龍哈希函數(shù)的研究?jī)r(jià)值

對(duì)于基于格空間的變色龍哈希函數(shù)的研究具備非常重要的研究?jī)r(jià)值,主要體現(xiàn)在以下幾個(gè)方面重要的應(yīng)用。

電子選舉:在電子選舉過(guò)程當(dāng)中,可以用來(lái)隱藏敏感的投票人信息和選票信息。

數(shù)據(jù)凈化:對(duì)于原始數(shù)據(jù)的敏感信息可以適當(dāng)修改,而不影響數(shù)據(jù)的來(lái)源和完整性的確認(rèn)等。

代理簽名:對(duì)于電子簽名過(guò)程當(dāng)中,如果簽名內(nèi)容是可以根據(jù)實(shí)際情況修改的,那么可以運(yùn)用變色龍哈希函數(shù)。

電子合同:可以用來(lái)在電子合同的簽署過(guò)程當(dāng)中,把部分合同內(nèi)容的確定權(quán)限賦予簽署合同的人。

可編輯區(qū)塊鏈:針對(duì)傳統(tǒng)區(qū)塊鏈的不可修改性,提出相對(duì)比較靈活性的可編輯區(qū)塊鏈,在可編輯區(qū)塊鏈中,某些信息可以被修改和不影響整個(gè)鏈條的完整性驗(yàn)證。