计算合数阶群中低重量离散对数的低存储算法*

朱玉清, 刘吉强

1. 北京交通大学 智能交通数据安全与隐私保护技术北京市重点实验室, 北京 100044 2. 北京交通大学 计算机与信息技术学院, 北京 100044

1 引言

设G=〈g〉是有限循环群,h ∈G, 离散对数问题(discrete logarithm problem, DLP) 是计算使得h=gx成立的最小正整数x. 当G是有限域的乘法群或椭圆曲线点群时, 离散对数问题通常是困难的. 基于离散对数问题的难解性, 研究学者设计了许多公钥密码方案, 如Diffie-Hellman 密钥交换协议[1]、ElGamal 加密方案[2]、Schnorr 签名算法[3]、数字签名标准(DSS)、国密SM2 和SM9 算法以及基于pairing 的相关密码方案.

本文的余下章节安排如下: 在第2 节, 回顾计算低Hamming 重量离散对数的相关算法. 在第3 节, 给出计算低Hamming 重量离散对数的低存储算法. 在第4 节, 对算法的复杂度进行分析, 并给出并行实施的方法. 在第5 节, 对本文进行总结.

2 相关工作

本节我们首先回顾计算低Hamming 重量离散对数的相关算法, 更多细节可以参考文献[8,10]. 接着我们介绍针对合数阶群的May-Ozerov 算法[11].

图1 May-Ozerov 算法碰撞搜索策略Figure 1 Collision search in May-Ozerov algorithm

在2020 年欧密会上, Esser 和May[12]提出首个低Hamming 重量的低存储碰撞搜索算法, 通过构造低Hamming 重量集上的伪随机函数, 使用ρ方法进行碰撞搜索, 以达到降低存储的目的. 本文将该技术用在合数阶群中, 以改进May-Ozerov 算法.

3 合数阶群中低Hamming 重量离散对数问题的低存储算法

本节我们给出合数阶群中低Hamming 重量离散对数问题的低存储算法. 我们将目标元素的离散对数分成两段, 记前n −t比特为v, 后t比特为w, 则x=v2t+w. 我们希望根据图2 搜索x1,x2使得x=x1+x2. 设xi的前n −t比特为vi, 后t比特为wi,i=0,1.

图2 本文的碰撞搜索策略……