Analysis of Two Public Key Cryptosystems Based on Randomized Knapsack Sequences

PENG Liqiang; ZUO Jinyin; HU Lei; XU Jun

Article Contents

Article Navigation > Chinese Journal of Electronics > 2014 > 23(1): 175-178

PENG Liqiang, ZUO Jinyin, HU Lei, et al., “Analysis of Two Public Key Cryptosystems Based on Randomized Knapsack Sequences,” Chinese Journal of Electronics, vol. 23, no. 1, pp. 175-178, 2014,

Citation:

PENG Liqiang, ZUO Jinyin, HU Lei, et al., “Analysis of Two Public Key Cryptosystems Based on Randomized Knapsack Sequences,” Chinese Journal of Electronics, vol. 23, no. 1, pp. 175-178, 2014,

PENG Liqiang, ZUO Jinyin, HU Lei, et al., “Analysis of Two Public Key Cryptosystems Based on Randomized Knapsack Sequences,” Chinese Journal of Electronics, vol. 23, no. 1, pp. 175-178, 2014,

Citation:

PENG Liqiang, ZUO Jinyin, HU Lei, et al., “Analysis of Two Public Key Cryptosystems Based on Randomized Knapsack Sequences,” Chinese Journal of Electronics, vol. 23, no. 1, pp. 175-178, 2014,

PDF( 153 KB)

Analysis of Two Public Key Cryptosystems Based on Randomized Knapsack Sequences

PENG Liqiang^1,2,
ZUO Jinyin³,
HU Lei¹,
XU Jun^1,2,4

1.
State Key Laboratory of Information Security, Institute of Information Engineering, Chinese Academy of Sciences, Beijing 100093, China;
2.
University of Chinese Academy of Sciences, Beijing 100049, China;
3.
PLA Unit 95899, Beijing 100085, China;
4.
School of Mathematical Science, Anhui University, Hefei 230601, China

Funds: This work is supported by the National Basic Research Program of China (No.2013CB834203), the National Natural Science Foundation of China (No.61070172, No.10990011), the Strategic Priority Research Program of Chinese Academy of Sciences (No.XDA06010702).

Received Date: 2012-11-01
Rev Recd Date: 2013-03-01
Publish Date: 2014-01-05

Abstract

Abstract

Two knapsack public key cryptosystems based on randomized knapsack sequences were proposed in 2009 and 2011 respectively, where the secret knapsack sequence is transformed by secret modular linear transforms into one or three public randomized knapsack sequences with appropriate density. In this paper, we recover the secret modular linear transforms by simultaneous Diophantine approximation and propose secret key recovery attacks on these two cryptosystems. Practical attack experiments are done within one minute.
- Knapsack public key cryptosystem,
- Simultaneous Diophantine approximation,
- Lattice,
- L³ algorithm

FullText(HTML)

References(12)

References

R.C.Merkle, M.E. Hellman,"Hiding information and signatures in trapdoor knapsack", IEEE Transaction on Information Theory, Vol.24, No.5, pp.525-530, 1978.

A. Shamir,"A polynomial-time algorithm for breaking the basic Merkle-Hellman", Proceedings of the 23rd Annual Symposium on Foundations of Computer Science, pp.145-152, 1982.

J.C. Lagarias, A.M. Odlyzko,"Solving low-density subset sum problems", Journal of the ACM (JACM), Vol.32, No.1, pp.229246, 1985.

M.J. Coster, A. Joux, B.A. La Macchia, A.M. Odlyzko, C.P. Schnorr, J. Stern,"An improved low-density subset sum algorithm", Computational Complexity, Vol.2, No.2, pp.111-128, 1992.

Y. Murakami,"A new construction of knapsack PKC by using a random sequence", Global Telecommunications Conference, Hawaii, USA, pp.1-6, 2009.

Y. Murakami, M. Kasahara,"A differential knapsack publickey cryptosystem", 2011 6th International Conference on Computer Sciences and Convergence Information Technology, Seogwipo, Korea, pp.613-617, 2011.

A.J. Menezes, P.C. van Oorshot, S.A. Vanstone, Handbook of Applied Cryptography, CRC Press, pp.117-122, 1996.

A.K. Lenstra, H.W. Lenstra, L. Lovász,"Factoring polynomials with rational coefficients", Mathematische Annalen, Vol.261, No.4, pp.515-534, 1982.

D. Micciancio, S. Goldwasser, Complexity of Lattice Problems: A Cryptographic Perspective, Kluwer Academic Publishers, Boston, Massachusetts, pp.11-14, 2002.

P. Zhang, J. Yu, T. Wang,"A homomorphic aggregate signature scheme based on lattice", Chinese Journal of Electronics, Vol.21, No.4, pp.701-704, 2012.

W. Bosma, J. Cannon, C. Playoust,"The magma algebra system I: The user language" Journal of Symbolic Computation, Vol.24, No.3, pp.235-265, 1997.

J. Xu, L. Hu, S. Sun,"Implicit polynomial recovery and cryptanalysis of a combinatorial key cryptosystem", 14th International Conference on Information and Communications Security, Hong Kong, China, pp.45-57, 2012.

Relative Articles

Supplements(0)

Cited By

Proportional views