一种基于格理论的签名方案及其安全线性网络编码方法

摘要

一种基于格理论的签名方案，包括参数生成、签名生成、签名验证。主要利用陷门产生函数进行参数生成，利用格向量选取函数进行签名生成，利用签名长度和格判断进行签名验证。本发明将消息向量依次在格基的各向量上映射生成签名，具有高斯随机性，并能保证所选向量不会泄露关于消息以及格私钥的任何信息。一种基于格签名方案的安全线性网络编码方法，有效融合基于格理论的签名方案和随机线性网络编码，相较于传统的安全网络编码方法，该方法具有低复杂度的签名运算，而且能够抵御量子计算机条件下的污染攻击，提高网络传输的安全性。

主权项

一种基于格理论的签名方案，其特征在于：它包括以下3个部分内容：(1)参数生成算法：选定一个整数n，选定一个素数q，保证q≥3，并选定任意一个正整数m，保证m≥5nlgq，利用陷门产生函数计算出(A,T)，其中A为公钥，T为私钥；(2)签名生成算法：给定私钥T和消息x，选择哈希函数H:{0,1}ⁿ→{0,1}^m，对消息x计算其哈希值H(x)；利用格向量选择函数，在格Λ^⊥(A)中高斯随机选取向量v，保证v满足||H(x)‑v||≤ρ；其中ρ为γ‑CVP问题中的距离d，其值为γ·μ，γ＝2(2/3)ⁿ，μ为一常数；(3)签名验证算法：给定公钥A，原始消息x，签名v，首先计算消息x的哈希值H(x)，然后判断签名的长度是否小于界限值，即||H(x)‑v||≤ρ；最后判断该签名v是否在格Λ^⊥(A)中，即判断等式A·v＝0是否成立，如果成立，则签名得到验证；其中，所述内容(1)中的陷门产生函数，其实现步骤如下：(1.1)输入任意大于零的数C和δ，大于等于3的素数q以及任意矩阵令m₁≥d＝(1+δ)nlg(q),m₂≥(4+2δ)nlg(q),m＝m₁+m₂；(1.2)计算格Λ^⊥(A)的基底T，其中||T||≤L＝m^1+ε，ε为任意大于0的数；(1.3)计算矩阵其中A服从上的均匀分布；其中，所述内容(2)中利用格向量选择函数，其实现步骤如下：(2.1)输入消息向量x和格Λ^⊥(A)的“好”基T＝[t₁,t₂,…,t_m]；(2.2)计算格Λ^⊥(A)中与x距离小于等于ρ的向量v。