吉林大学学报(工学版) ›› 2018, Vol. 48 ›› Issue (1): 259-267.doi: 10.13229/j.cnki.jdxbgxb20161211
赵博1, 秦贵和1, 赵永哲1, 杨文迪2
ZHAO Bo1, QIN Gui-He1, ZHAO Yong-Zhe1, YANG Wen-Di2
摘要: 通过引入“半陷门单向函数”的概念来构造公钥密码,与陷门单向函数不同,由于半陷门单向函数是“半可逆”的,所以不能单独用来构造公钥密码。为此本文提出了一种基于半陷门单向函数的公钥密码构造方法。并结合SSP(子集和问题)的难解性和易解性,构造了“半超递增背包向量”,并基于半超递增背包向量对半陷门单向函数进行了具体实现。在此基础上,给出了一种新的公钥密码方案STOF_PKC。该方案在分类上属于背包密码,因而具有抗量子计算的潜力。
中图分类号:
[1] Diffie W,Hellman M E.New directions in cryptography[J]. IEEE Transactions on Information Theory, 1976, 22:644-654. [2] Merkle R C,Hellman M E.Hiding information and signatures in trapdoor knapsacks[J]. IEEE Transactions on Information Theory, 1978, 24:525-530. [3] Rivest R L.A method for obtaining digital signatures and public-key cryptosystems[J]. Communications of the Acm, 1983, 26:96-99. [4] Shor P W.In algorithms for quantum computation: Discrete logarithms and factoring, foundations of computer Science[C]∥Proceedings on Symposium,Murray Hill,NJ,USA, 1994:124-134. [5] Grover L K.A fast quantum mechanical algorithm for database search[C]∥Proceedings of the Twenty-eighth Annual ACM Symposium on Theory of Computing,Philade lphia,PA,USA, 1996:212-219. [6] Poulakis D.On the cryptographic long term security[J]. Journal of Applied Mathematics & Bioinformatics, 2013,3(1):1-15. [7] Courtois N, Finiasz M, Sendrier N.In how to achieve a mceliece-based digital signature scheme[C]∥ International Conference on the Theory and Application of Cryptology and Information Security, Gold Coast, Australia, 2001: 157-174. [8] Porras J, Baena J, Ding J Zhfe.A new multivariate public key encryption scheme[Z].Post-Quantum Cryptogaphy,2014:229-245. [9] Dehornoy P.Using shifted conjugacy in braid-based cryptography[J]. Computer Science,2006,418:65-73. [10] Okamoto T,Tanaka K,Uchiyama S.Quantum public-key cryptosystems[J]. International Journal of Theoretical Physics, 2011, 51:912-924. [11] Elkies N D.An improved lower bound on the greatest element of a sum-distinct set of fixed order[J]. Journal of Combinatorial Theory, 1986, 41:89-94. [12] Guy R K.Unsolved Problems in Number Theory[M].New York-Berlin:Springer-Verlag,2001:17-35. [13] Kate A, Goldberg I.Generalizing cryptosystems based on the subset sum problem[J]. International Journal of Information Security,2011, 10:189-199. [14] Brickell E F.Breaking iterated knapsacks[C]∥Advances in Cryptology, Proceedings of CRYPTO’84, Santa Barbara, California, USA, 1984:342-358. [15] Coster M J,Joux A, Lamacchia B A, et al.Improved low-density subset sum algorithms[J]. Computational Complexity 1999, 2:111-128. [16] Joux A.A practical Attack Against Knapsack based Hash Functions (Extended )[M].Berlin Heidelberg:Springer,1994:58-66. [17] Nguy?n P Q, Stern J. Adapting density attacks to low-weight knapsacks[J]. Lecture Notes in Computer Science, 2005, 3788: 41-58. [18] Impagliazzo R, Naor M.Efficient cryptographic schemes provably as secure as subset sum[J]. Journal of Cryptology,1996,9:199-216. [19] Schroeppel R, Shamir A.A T=O(2n/2),S=O(2n/4) algorithm for certain NP-complete problems[J]. Siam Journal on Computing, 1981,10(3): 456-464. [20] Li Qing-hua, Li Ken-li, Jiang Sheng-yi, et al.An optimal parallel algorithm for the knapsack problem[J]. Journal of Software, 2003, 14(14):891-896. [21] Christos H Papadimitriou.On the complexity of unique solutions[J]. Journal of the ACM, 1984, 31(2):392-400. [22] Shamir A.A polynomial time algorithm for breaking the basic Merkle-Hellman cryptosystem[J].IEEE Transactions on Information Theory,1984,30(5):699-704. |
[1] | 余宜诚, 胡亮, 迟令, 初剑峰. 一种改进的适用于多服务器架构的匿名认证协议[J]. 吉林大学学报(工学版), 2018, 48(5): 1586-1592. |
[2] | 董坚峰, 张玉峰, 戴志强. 改进的基于狄利克雷混合模型的推荐算法[J]. 吉林大学学报(工学版), 2018, 48(2): 596-604. |
[3] | 刘磊, 刘利娟, 吴新维, 张鹏. 基于ECPMR的编译器测试方法[J]. 吉林大学学报(工学版), 2017, 47(4): 1262-1267. |
[4] | 董立岩, 王越群, 贺嘉楠, 孙铭会, 李永丽. 基于时间衰减的协同过滤推荐算法[J]. 吉林大学学报(工学版), 2017, 47(4): 1268-1272. |
[5] | 于斌斌, 武欣雨, 初剑峰, 胡亮. 基于群密钥协商的无线传感器网络签名协议[J]. 吉林大学学报(工学版), 2017, 47(3): 924-929. |
[6] | 邓昌义, 郭锐锋, 张忆文, 王鸿亮. 基于平衡因子的动态偶发任务低功耗调度算法[J]. 吉林大学学报(工学版), 2017, 47(2): 591-600. |
[7] | 魏晓辉, 刘智亮, 庄园, 李洪亮, 李翔. 支持大规模流数据在线处理的自适应检查点机制[J]. 吉林大学学报(工学版), 2017, 47(1): 199-207. |
[8] | 郝娉婷, 胡亮, 姜婧妍, 车喜龙. 基于多管理节点的乐观锁协议[J]. 吉林大学学报(工学版), 2017, 47(1): 227-234. |
[9] | 魏晓辉, 李翔, 李洪亮, 李聪, 庄园, 于洪梅. 支持大规模流数据处理的弹性在线MapReduce模型及拓扑协议[J]. 吉林大学学报(工学版), 2016, 46(4): 1222-1231. |
[10] | 车翔玖, 梁森. 一种基于大顶堆的SPIHT改进算法[J]. 吉林大学学报(工学版), 2016, 46(3): 865-869. |
[11] | 董悦丽, 郭权, 孙斌, 康玲. 药物分子对接动态任务迁移优化[J]. 吉林大学学报(工学版), 2015, 45(4): 1253-1259. |
[12] | 匡哲君,师唯佳,胡亮. 基于无线传感器网络的角色成员关系剩余能量新算法[J]. 吉林大学学报(工学版), 2015, 45(2): 600-605. |
[13] | 张忆文,郭锐锋. 实时系统混合任务低功耗调度算法[J]. 吉林大学学报(工学版), 2015, 45(1): 261-266. |
[14] | 张忆文1, 2, 郭锐锋1. 制的容错节能调度算法[J]. 吉林大学学报(工学版), 2014, 44(4): 1112-1117. |
[15] | 付帅1, 马建峰1, 李洪涛1, 王长广2. 改进的基于分簇无线传感器网络的数据聚合算法[J]. 吉林大学学报(工学版), 2014, 44(4): 1118-1125. |
|