1.一种强抗碰撞变色龙哈希函数的构造方法,其特征在于,该方法使用以下q元格:定
义参数s>0,中心 的m维格Λ上的离散高斯分布为:其中ρs,c(Λ)=∑x∈Λρs,c(x), 当c=0时,记ρs,0和 分t
别为ρs和 令整数n≥1,q≥2, 矩阵 由向量g=[1 2 4 … k‑1
2 ]组成,即 其中 代表张量积;令 消息空间 随机向量(r,t)采样自 该方法包括以下步骤:S1、系统参数生成算法KGen:输入安全参数n,系统生成公私钥对(PK,SK),其中公钥PK可以指定消息空间 随机空间 以及变色龙哈希函数范围 输入安全参数n,选择素数q≥2,整数k>1, 和m>2nlog q,以及高斯参数选择一个哈希函数 运行算法 生成随机矩阵和陷门 输出公私钥对(PK,SK)=(A,B);所述步骤S1中算法TrapGen的主要流程为:令整数n≥1,q≥2, 以及参数的离散高斯分布 则存在一个高效的算法 输入w和可逆矩阵 输出一个统计均匀的矩阵 和陷门所述算法TrapGen具体流程为:令整数n≥1,q≥2,高斯参数 首先将原始矩阵 扩展成其中随机选择的矩阵 可逆矩阵 然后A′乘以一个单模矩阵得到 其中
是从高斯分布 中采样得到的陷门;
S2、哈希算法CHash:输入由KGen生成的公钥PK以及一个消息 哈希算法输出哈希 和随机 所述步骤S2的具体过程为:输入公钥A和消息 从 和高斯分布 中分别采样随机向量t和r;计算h=H(m∥t)+Ar并输出(h,(t,r));
S3、哈希检查算法HCheck:输入公钥PK,消息 一个哈希 和随机向量检查算法输出b∈{0,1};如果b=1,那么(y,r)是消息m的有效哈希,否则是无效的;
所述步骤S3具体过程为:输入公钥A,消息m,一个哈希h以及随机向量(r,t),如果h=H(m∥t)+Ar且 则输出1,否则输出0;
S4、哈希改编算法HAdapt:输入私钥SK,消息 和一个相应的哈希随机对(y,r),以及一个新的消息 输出满足HCheck(PK,m′,y,r′)=1的随机向量r′;所述步骤S4具体包括两步骤:
A1:输入私钥B,消息m和相关的哈希随机对(h,(t,r)),新的消息 以及高斯参数 其中
A2:从 中选择一个随机向量t′,运行算法SampleD(A,B,h‑H(m′∥t′),s′)得到r′,输出(t′,r′);
所述步骤A2中算法SampleD的主要流程为:令整数n≥1,q≥2,和 则存在一个高效的算法SampleD(A,B,H,u,s):输入矩阵可逆矩阵 向量 高斯参数
其中
输出统计接近分布 的向量
所述算法SampleD的主要流程为:令整数n≥1,q≥2, 和首先选择扰动向量 其中
t
B 是矩阵B的转置矩阵,Im是m×m的单位矩阵,Iw是w×w的单‑1 ‑1
位矩阵;然后采样 使得Gz=H (u‑Ap),其中v=H (u‑Ap);最后输出