吉林大学学报(工学版) ›› 2018, Vol. 48 ›› Issue (1): 259-267.doi: 10.13229/j.cnki.jdxbgxb20161211

• 论文 • 上一篇    下一篇

基于半陷门单向函数的公钥密码

赵博1, 秦贵和1, 赵永哲1, 杨文迪2   

  1. 1.吉林大学 计算机科学与技术学院,长春 130012;
    2.华东师范大学 计算机科学与软件工程学院,上海 200062
  • 收稿日期:2016-11-10 出版日期:2018-02-26 发布日期:2018-02-26
  • 通讯作者: 赵永哲(1961-),男,教授,博士. 研究方向:信息安全. E-mail:yongzhe@jlu.edu.cn
  • 作者简介:赵博(1988-),男,博士研究生.研究方向:图像处理,信息安全. E-mail:wolfers509@126.com
  • 基金资助:
    吉林省科技发展计划项目(20150204034GX)

Public key cryptosystem based on semi-trapdoor one-way function

ZHAO Bo1, QIN Gui-He1, ZHAO Yong-Zhe1, YANG Wen-Di2   

  1. 1.College of Computer Science and Technology, Jilin University. Changchun 130012, China;
    2.College of Computer Science and Software Engineering, East China Normal University, Shanghai 200062, China
  • Received:2016-11-10 Online:2018-02-26 Published:2018-02-26

RICH HTML

0   

PDF (PC)

256

摘要： 通过引入“半陷门单向函数”的概念来构造公钥密码,与陷门单向函数不同,由于半陷门单向函数是“半可逆”的,所以不能单独用来构造公钥密码。为此本文提出了一种基于半陷门单向函数的公钥密码构造方法。并结合SSP(子集和问题)的难解性和易解性,构造了“半超递增背包向量”,并基于半超递增背包向量对半陷门单向函数进行了具体实现。在此基础上,给出了一种新的公钥密码方案STOF_PKC。该方案在分类上属于背包密码,因而具有抗量子计算的潜力。

关键词: 计算机系统结构, 半陷门单向函数, 半超递增背包向量, 抗量子计算的公钥密码, 背包公钥密码

Abstract: In this paper, we introduce the concept of Semi-trapdoor One-way Function (STOF) to implement the Public Key Cryptosystem (PKC), which is different from the One-way Function. STOF is semi-invertible, so it can be directly used to implement the PKC. For this characteristic we develop a method to construct a PKC based on the STOF. Combined with the difficulty and solvability of the Subset Sum Problem (SSP), we can construct a Semi-supper Increasing Knapsack (SSIK). Based on SSIK a scheme of STOF is designed and realized. ON this basis, we propose two new knapsack public key schemes, STOF_PKC. STOF_PKC belongs to knapsack cryptosystem, thus has the potential to resist quantum attack.

Key words: computer system organization, semi-trapdoor one-way function, semi-super increasing knapsack, quantum resistant public key cryptography, knapsack public key cryptosystem.

中图分类号: 

  • TP309.7
[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.
Viewed
Full text


Abstract

Cited
  Shared   
  Discussed   
No Suggested Reading articles found!
版权所有 © 《吉林大学学报(工学版)》编辑部
地址：长春市人民大街5988号　电话：+86-431-85095297　传真：+86-431-85094074　E-mail: xbgxb@jlu.edu.cn
本系统由北京玛格泰克科技发展有限公司设计开发