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