基于格的变色龙哈希函数研究概述

蒋 芬 傅海明

广州华夏职业学院 广东 广州 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]在多方参与的情况下如何公平快速地实现碰撞的计算等都是值得研究的方向。

基于格的变色龙哈希函数的研究价值

对于基于格空间的变色龙哈希函数的研究具备非常重要的研究价值,主要体现在以下几个方面重要的应用。

电子选举:在电子选举过程当中,可以用来隐藏敏感的投票人信息和选票信息。

数据净化:对于原始数据的敏感信息可以适当修改,而不影响数据的来源和完整性的确认等。

代理签名:对于电子签名过程当中,如果签名内容是可以根据实际情况修改的,那么可以运用变色龙哈希函数。

电子合同:可以用来在电子合同的签署过程当中,把部分合同内容的确定权限赋予签署合同的人。

可编辑区块链:针对传统区块链的不可修改性,提出相对比较灵活性的可编辑区块链,在可编辑区块链中,某些信息可以被修改和不影响整个链条的完整性验证。