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

Computing Low Weight Discrete Logarithms in Composite Order Groups with Low Memory

作　　者：朱玉清 刘吉强[1,2] ZHU Yu-Qing;LIU Ji-Qiang(Beijing Key Laboratory of Security and Privacy in Intelligent Transportation,Beijing Jiaotong University,Beijing 100044,China;School of Computer and Information Technology,Beijing Jiaotong University,Beijing 100044,China)

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

出　　处：《密码学报》2021年第3期444-451,共8页Journal of Cryptologic Research

基　　金：国家自然科学基金(62002015,61672092);国家重点研发计划(2020YFB2103802);山东省重大科技创新工程(2019JZZY020128)。

摘　　要：设合数阶有限循环群G=G 1×G 2,其中2^(n−1)<|G|≤2 n,p是|G 1|的最大素因子.对于Hamming重量为δn的离散对数问题,其中δ∈(0,1),May和Ozerov给出了时间复杂度为˜O(√p+√|G2|^(H(δ)))、空间复杂度为˜O(√|G2|^(H(δ)))的一般性算法.为了降低空间复杂度,本文给出了计算合数阶群中低Hamming重量离散对数的低存储算法.基于启发式假设,该算法的时间复杂度为˜O(√p+√|G2|^(2H(δ)−H(ϕ(δ))))、空间复杂度为O(1).进一步,我们给出算法的并行版本.当我们将空间复杂度提高至˜O(|G2|^(H(δ)−H(ϕ(δ))))时,时间复杂度可以降低至˜O(√p+√|G2|^(H(δ))),和May-Ozerov算法一致,但空间复杂度更低.Assume that G=G1×G2 is a cyclic group with composite order,where 2^(n−1)<|G|≤2 n and p is the largest prime factor of|G 1|.May and Ozerov presented a generic algorithm to solve the discrete logarithm problem with Hamming weightδn,δ∈(0,1),in time˜O(√p+√|G2|^(H(δ)))and space˜O(√|G2|^(H(δ))).To reduce the space complexity,a generic algorithm with low storage is given to solve the discrete logarithm problem with low Hamming weight in a composite order group.Heuristically,the time complexity of this algorithm is˜O(√p+√|G2|^(2H(δ)−H(ϕ(δ)))),while the space complexity is O(1).Furthermore,a variant suitable for parallelization is given.By increasing the storage to˜O(|G2|^(H(δ)−H(ϕ(δ)))),the time complexity can be reduced to˜O(√p+√|G2|^(H(δ))),which is the same as the May-Ozerov algorithm but with lower storage.

关 键 词：离散对数问题 低Hamming重量 一般性算法 

分 类 号：TP309.7[自动化与计算机技术—计算机系统结构]