杨新泉
（菏泽学院计算机与信息工程系，山东菏泽274015）
【摘要】数据查询认证是保证信息安全的关键技术。基于格论的哈希函数解决了传统哈希函数易受到攻击的问题，增强了其抗碰撞性。本文将基于格论的哈希函数应用到数据查询认证过程之中，阐述如何将基于格论的哈希函数和格摘要的思想应用到各实体运行算法之中，阐述其实体构成，描述实体间的通信协议，并对实体的空间和时间复杂度进行详细分析。经对比，该方案明显降低了数据查询认证过程的复杂度。
教育期刊网 http://www.jyqkw.com
关键词 数据查询认证；抗碰撞；格摘要；矩阵；复杂度
0引言
数据查询认证主要是为了解决如何在不可信的示证者P和验证者V之间，对集合S的隶属关系进行真实性查询认证问题。这里，S属于某个数据拥有者，即数据源Source；验证者V是查询的用户Clients；而示证者P则是网络上某些不可信的第三方发布服务器Servers，如门户网站等。例如，银行、股票交易所、政府等重要部门的信息，大都通过门户网站提供在线交易、市场报价等财经信息，每时每刻都有数以万计访问者通过Internet进行大量数据查询和处理。因此，如何在不可信数据发布服务器或敌手攻击数据发布环境下，保证发布的数据具有真实性的认证成为当前研究的热点问题。
式中，q表示对数据结构Di的一个查询；∏(q)表示由发布服务器提供的关于查询q的证明信息。这里还要求数据源签名的摘要di也要作为输入。
令{accept,reject}=check(q,a(q),Di)为一个确定性算法，在给定对数据结构Di上的一个查询q，以及这个查询的结果a(q)，那么这个算法能够检查这个结果是否是该查询的正确结果。
本文提出的数据查询认证模型，也是一个基于哈希函数和数字签名的认证方案，通过抗碰撞哈希函数和数字签名方案来达到以上关于安全性的需求。任何一种类型的攻击最终都可以规约到对签名方案或者抗碰撞哈希函数的攻击上来，因此认证方案的安全性也就自然规约到哈希方案的安全性上来了，可以将敌手攻击归约到对基于格论的哈希函数和签名方案的攻击，只要系统构建满足基于格论的哈希函数的困难性要求，且签名方案没有被攻破，那么该模型的安全性是能够得到保证的。
4结论
本文所提出的基于格论的哈希函数在数据查询认证中的应用方案可以得到如下结论：
（１）数据源更新时间为O(1)，且涉及O(1)次操作，存储空间是O(n)级。
（2）发布服务器的更新时间是O(logn)级，且涉及O(logn)次组操作，存储空间是O(n)级，查询时间是O(logn)级。
（3）用户端存储空间为O(1)，验证查询时间是O(n)，这涉及O(n)次操作。
（4）对于查询的证明信息大小为O(logn)级，由O(logn)个元素组成。
（5）更新的证明信息大小为O(1)级，由O(1)组元素组成。
教育期刊网 http://www.jyqkw.com
参考文献
［１］徐茂智,游林.信息安全与密码学[M].北京:清华大学出版社,2007.
［２］徐剑,周福才,杨牧洲,等.面向分布式查询认证的分层哈希链表[J].计算机研究与发展,2012,49(7):1533-1544.
［３］GoodrichMT,TamassiaR,SchwerinA.Implementationofanauthenticateddictionarywithskiplistsandcommutativehashing[C]//ProceedingsofDARPAInformationSurvivabilityConferenceandExpositionII.2001:68-82.
［４］PeikertC,RosenA.Efficientcollision-resistanthashingfromworst-caseassumptionsoncycliclattices[C]//ProceedingsofTCC’10.2006:145-166.
［５］ChristofPaar,JanPelzl.马小婷,译.深入浅出密码学——常用加密技术原理与应用[M].北京:清华大学出版社,2012.
［责任编辑：汤静］