一个基于ISIS问题签名方案的分析与改进  

Analysis and improvement of a signature scheme based on ISIS problem

作　　者：夏天 邓伦治 XIA Tian;DENG Lunzhi(School of Mathematical Science,Guizhou Normal University,Guiyang,Guizhou 550025,China)

机构地区：[1]贵州师范大学数学科学学院,贵州贵阳550025

出　　处：《贵州师范大学学报（自然科学版）》2021年第2期57-63,共7页Journal of Guizhou Normal University：Natural Sciences

基　　金：国家自然科学基金项目(61962011);贵州省教育厅创新群体重大研究项目(黔教合KY字[2016]026号);贵州省科学技术基金重点项目(黔科合基础[2019]1434号)。

摘　　要：量子计算具有强大的计算能力。利用量子计算,一些传统的数学困难问题可以被解决,例如:基于大整数因子分解问题、离散对数问题等。2017年,Gupta提出了一个基于格的签名方案,在基于格理论的SIS问题和ISIS问题困难性假设前提下,称提出的签名方案是不可伪造的。笔者对Gupta的方案进行了研究,指出在适应性选择消息攻击下方案是不安全的,并给出了一个新方案。在随机预言模型下证明了新方案的安全性,并将新方案与同类型的5个方案在存储成本方面进行了比较,结果显示出新方案具有更高的效率。Quantum computing has great computing power.Using the Quantum computing power,we can deal with some traditional mathematical computation problems,such as factorization problem based on large integers,discrete logarithm problem and so on.In 2017,a lattice-based signature scheme was proposed by Gupta,under the assumption that SIS and ISIS are difficult problems based on lattice theory and that the proposed signature scheme is unforgeable.We study the scheme.It is pointed out that the scheme is not secure under adaptive choice message atttack,and a new scheme is given.We prove that the new scheme is safe under the random oracle model and the storage cost of the new scheme is compared with that of five similar schemes.The result shows that the new scheme has higher efficiency.

关 键 词：格 最短向量问题 最近向量问题 小整数解问题 非齐次小整数解问题 

分 类 号：TP309[自动化与计算机技术—计算机系统结构]