基于Falcon的盲签名方案

A New Blind Signature Scheme Based on Falcon

基于格的密码体系是后量子密码时代的重要研究方向,构造格上的盲签名方案具有重要意义.本文结合NIST后量子密码标准化项目的优胜算法Falcon,设计了一个NTRU格上紧凑型的盲签名方案.消息盲化时,用户先将签名者产生的320 bit均匀分布的随机比特串和一个本地均匀生成的等长随机比特串进行异或运算,得到真实签名组合中的320 bit长的随机值,实现该部分签名的盲性.接着用户计算原始消息拼接上新生成的随机向量的哈希值,然后将一个任意选取的整数和两个离散高斯分布随机选择的向量作为盲因子对哈希值进行盲化,实现消息对签名者的盲性.将原始消息与上述生成的均匀随机比特串做拼接的操作可以使得一个消息拥有多个合法签名.在“先哈希再签名”范式下,签名者利用快速傅里叶陷门采样器从NTRU格上寻找离其陪集上一点最近的格点,计算出符合要求的盲签名.用户对盲签名去盲后可以得到消息的合法签名.在随机谕言机模型下,基于NTRU格上SIS问题的困难性假设,证明本文方案满足强不可伪造性.依据效率分析,本文方案产生的公钥和签名组合尺寸较小,可以有效节约带宽资源.

Lattice based cryptosystem is a mainstream research direction in post quantum cryptography.Therefore,it is of great significance to construct blind signature schemes on lattices.Based on the theory of blind signature and NTRU lattice,and combining the winning algorithm Falcon of the NIST post quantum cryptography standardization project,this paper designs a compact blind signature scheme.During the process of message blinding,the user performs a bitwise XOR operation on a random binary string with a size of 320 bits generated by the signer and a locally uniformly generated random string of equal length to obtain a 320-bit random binary string in a real signature combination,thereby achieving the blindness of this part of the signature.Splicing the original message with the uniformly generated random string described above can get a message with multiple legitimate signatures.Under the“Hash-then-Sign”paradigm,the signer uses the fast Fourier trapdoor sampler to find a closest lattice point to a point on its coset on an NTRU lattice.After that,the blind signature that meets the requirements can be calculated.The user can obtain a legal signature of the message by performing an unblind operation on the blind signature.Based on the hardness assumption of the SIS problem on NTRU lattice,it is proved that the proposed scheme satisfies strong unforgeability in a random oracle model.The efficiency analysis shows that,both the size of the public key and that of signature combination generated by this scheme are small,which can effectively save bandwidth resources.