基于多离散对数问题的公钥密码的分析  

Analysis of a Public-Key Cryptograph Based on Multi-Discrete Logarithm Problems

作　　者：苏盛辉 孙国栋[2] 

机构地区：[1]南京航空航天大学计算机学院,江苏南京211106 [2]北京工业大学计算机学院,北京100124 [3]南京理工大学公共安全科技创新中心,江苏南京210094

出　　处：《电子学报》2018年第1期218-222,共5页Acta Electronica Sinica

基　　金：国家863高技术研究发展计划(No.2009AA01Z441)

摘　　要：本文对一个特定群生成元系中元素的阶数的选取做了讨论,对多离散对数问题和基于它的公钥加密方案做了分析.指出在原文所述情况下,多离散对数问题可转化为离散对数问题,从而,该问题存在亚指数时间解,并导致相关私钥在大多数情况下是亚指数时间不安全的.本文进一步指出,在几乎任何情况下,密文还原问题都可转化为离散对数问题,从而,它也存在亚指数时间解.所以,要把离散对数问题和El Gamal公钥密码改造成抗Shor量子算法攻击的,还需做更深入的、持久的探索.The paper discusses the selection of orders of elements in one generator set for a specified group, and analyzes multi-discrete logarithm problems（ MDLP） and a public key encryption scheme based on the MDLP. The paper points out that under the circumstances described by the original paper, the MDLP may be transformed into a discrete logarithm problem,which manifests that there exists a sub-exponential time solution for the MDLP, and causes a related private key insecure in sub-exponential time in most cases. Further, in almost any case,a ciphertext inversion problem may be transformed into a discrete logorithm problem,which illustrates that there also exists a sub-exponential time solution to the ciphertext.Therefore, to convert a discrete logarithm and the ElGamal cryptosystem into those which are resistant to the Shor quantum alg. orithm attack, the people still need to make deeper and longer explorations.

关 键 词：多离散对数问题 公钥密码 安全性 量子算法 亚指数时间解 

分 类 号：TN918[电子电信—通信与信息系统]