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

• Orginal Article • Previous Articles     Next Articles

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)

253

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.

CLC Number: 

  • 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] YU Bin-bin, WU Xin-yu, CHU Jian-feng, HU Liang. Signature protocol for wireless sensor network based on group key agreement [J]. 吉林大学学报(工学版), 2017, 47(3): 924-929.
[2] WEI Xiao-hui, LI Xiang, LI Hong-liang, LI Cong, ZHUANG Yuan, YU Hong-mei. Flexible Online MapReduce model and topology protocols supporting large-scale stream data processing [J]. 吉林大学学报(工学版), 2016, 46(4): 1222-1231.
[3] CHE Xiang-jiu, LIANG Sen. Improved algorithm of SPIHT based on Max-Heap tree [J]. 吉林大学学报(工学版), 2016, 46(3): 865-869.
[4] FU Shuai, MA Jian-feng, LI Hong-tao, WANG Chang-guang. Improved data aggregation algorithm based on clustered wireless sensor network [J]. 吉林大学学报(工学版), 2014, 44(4): 1118-1125.
[5] HU Liang, CHI Ling, YUAN Wei, CHU Jian-feng, XU Xiao-bo. Improvements against fault induction attack for RC4 algorithm [J]. , 2012, 42(05): 1231-1236.
[6] LIU San-min, SUN Zhi-xin. P2P traffic identification based on support vector data description [J]. , 2012, 42(04): 947-951.
[7] ZHANG Rui-Hua, CHENG He-You, JIA Zhi-Beng. Energyefficient clustering algorithm for wireless sensor networks [J]. 吉林大学学报(工学版), 2010, 40(06): 1663-1667.
[8] LIU Yan-Hang, SUN Xin, WANG Jian, LI Wei-Ping, ZHU Jian-Qi. Emailworm propagation with user behavior and network topology [J]. 吉林大学学报(工学版), 2010, 40(06): 1655-1662.
[9] WEI Da, Gu-Xiang-Peng, WANG Jian, Liu-Yan-Hang. New access model and implementation of trusted network based on trusted certificate [J]. 吉林大学学报(工学版), 2010, 40(02): 496-0500.
[10] LIU Yan-Heng, SUN Lei, TIAN Da-Xin, WU Jing. Method of anomaly detection based on fusion principal components match [J]. 吉林大学学报(工学版), 2009, 39(05): 1314-1320.
[11] WANG Xiao-yan,LIU Shu-fen,YU Hai . Interface automata based approach to Web service composition [J]. 吉林大学学报(工学版), 2009, 39(03): 743-0748.
[12] MEI Fang，LIU Yan-heng，ZHANG Xu-li，Gu Tian-ye，WANG Wang . Dynamic conflict resolution mechanism for resource
management policy in mobile network
 [J]. 吉林大学学报(工学版), 2009, 39(02): 430-0435.
[13] SUN Zhi-xin, YANG Xi, GONG Jing . New P2P architecture description language [J]. 吉林大学学报(工学版), 2008, 38(05): 1131-1135.
[14] Yang Chao，Cao Chun-jie，Wang Wei，Ma Jian-feng . New authentication protocol of roaming for wireless mesh network [J]. 吉林大学学报(工学版), 2008, 38(02): 423-0428.
[15] Hu De-bin,Wang Jin-ling,Yu Meng-tao,Lin Yu,Hu Liang . ID alias IBE scheme with a trusted third party [J]. 吉林大学学报(工学版), 2008, 38(02): 419-0422.
Viewed
Full text


Abstract

Cited
  Shared   
  Discussed   
No Suggested Reading articles found!
Copyright © Journal of Jilin University(Engineering and Technology Edition), All Rights Reserved.
Tel: +86-431-85095297　Fax: +86-431-85094074　E-mail: xbgxb@jlu.edu.cn
Powered by Beijing Magtech Co. Ltd