近日，2018级博士研究生宋永成（导师：黄欣沂教授）在Science China Information Sciences（SCIS）和Theoretical Computer Science（TCS）分别发表了题为“An Improved Durandal Signature Scheme”（如图1所示）和“A Code-based Signature Scheme from the Lyubashevsky Framework”（如图2所示）的学术论文。Science China Information Sciences和Theoretical Computer Science是CCF（中国计算机学会）推荐的B类国际学术期刊。

图1：SCIS论文发表

图2：TCS论文发表

基于编码的密码体制有望成为后量子时代密码标准之一，但是设计基于编码的安全高效数字签名一直是一个公开问题。目前，通过Lyubashevsky框架构造基于编码的签名方案是一个有希望的新方法，但是这类签名方案的公钥尺寸和签名尺寸依然较大。因此需要进一步优化它们，或者通过Lyubashevsky框架构造基于编码的新签名方案。

宋永成等针对基于编码的Lyubashevsky框架签名方案做了以下两个研究工作：（1）优化基于秩距离码的Durandal签名方案；（2）使用汉明距离随机线性码，构造基于编码的新签名方案。

在2019年欧密会上，Aragon等提出Durandal签名方案，该方案使用Lyubashevsky框架的变形。Durandal方案生成的签名具有更好的随机性，能够实现标准的安全性要求：在自适应选择消息攻击下满足存在不可伪造性。但是，该方案的公钥尺寸和签名尺寸依然较大，效率较低。为了进一步提高效率，宋永成等利用理想码优化Durandal签名方案（该研究工作发表于SCIS）。新方法能够精简Durandal签名方案构造，降低公钥和签名尺寸，提高签名效率，增强所依赖困难问题的可靠度。在128比特安全要求下，新签名方案的性能（如表1、表2所示）：公钥长度减少22.1%，签名长度减少20.5%，密钥生成时间减少92.4%。

为了进一步减小签名尺寸，宋永成等根据Lyubashevsky框架,使用汉明距离随机线性码，设计一个基于编码的新签名方案（该研究工作发表于TCS）。在新签名方案中：（1）私钥矩阵每一行的重量都接近GV界，这使得从公钥恢复私钥等价于解译码困难问题；（2）生成签名的重量接近GV界，这使得解译码困难问题的复杂度更高，直接伪造签名更困难。新签名方案能够抵抗当前对基于编码签名方案的攻击。在 128 比特安全要求下，新签名方案的性能（如表3:Para-2所示）：（1）当与基于编码的Durandal（EUROCRYPT 2019）和Wave（ASIACRYPT 2019）签名方案比较时，签名尺寸有明显优势，分别减少 72.1% 和 30.2%；（2）当与Wave 签名方案比较时，公钥长度减少75.0%。

表1：公钥尺寸和签名尺寸的比较，单位：bit

表2：密钥生成、生成签名和验证签名时间的比较，单位: ms

表3：与Durandal 和Wave 签名方案的比较

上述研究工作受到国家自然科学基金项目（项目编号:61822202、61841701、61872087、61872089、61902070）和广东自然科学基金项目（项目编号：2019B010137002）的支持。