Your browser does not support JavaScript!
http://iet.metastore.ingenta.com
1887

access icon free Equivalent key attack against a public-key cryptosystem based on subset sum problem

  • Author(s): Jiayang Liu 1, 2  and  Jingguo Bi 2, 3
    • View affiliations
  • Source: Volume 12, Issue 6, November 2018, p. 498 – 501
    DOI:  10.1049/iet-ifs.2018.0041 , Print ISSN 1751-8709, Online ISSN 1751-8717
© The Institution of Engineering and Technology
Received 23/01/2018, Accepted 21/03/2018, Revised 04/03/2018, Published 27/04/2018

The decisional version and computational version of the subset sum problem are known to be NP-complete and NP-hard. At International Symposium on Information Theory and its Applications 2012, Yasuyuki Murakami, Shinsuke Hamasho and Masao Kasahara presented a knapsack scheme based on the decisional version of the odd order subset sum problem. They claimed that the public sequence is indistinguishable from uniformly distributed sequences. In this study, the authors present an equivalent key attack against this scheme. More precisely, they firstly observe that there are many groups of equivalent keys, which satisfy several necessary conditions. Subsequently, they show that one can recover a group of equivalent keys by using the orthogonal lattice technique. The feasibility of the attack is validated by the experimental data when the bit length of secret keys is not too large. Hence, the security of the proposed scheme is overestimated.

Inspec keywords: private key cryptography; knapsack problems; computational complexity

Other keywords: equivalent key attack; uniformly distributed sequences; decisional version subset sum problem; computational version subset sum problem; public sequence; public-key cryptosystem; knapsack scheme; odd order subset sum problem; secret keys

Subjects: Cryptography; Data security; Computational complexity

References

    1. 1)
      • 9. Murakami, Y., Hamasho, S., Kasahara, M.: ‘A public-key cryptosystem based on decision version of subset sum problem’. Information Theory and its Applications (ISITA), Honolulu, HI, USA, 2012, pp. 735–739.
    2. 2)
      • 6. Shamir, A.: ‘A polynomial time algorithm for breaking the basic Merkle-Hellman cryptosystems’. Proc. Crypto'82, Berlin, 1982 (LNCS), pp. 279–288.
    3. 3)
      • 4. Becker, A., Coron, J.-S.: ‘Antoine joux: improved generic algorithms for hard knapsacks’. EUROCRYPT, Tallinn, Estonia, 2011, pp. 364–385.
    4. 4)
      • 13. Kaib, M., Schnorr, C.P.: ‘The generalized gauss reduction algorithm’, J. Algorithms, 1996, 21, (3), pp. 565–578.
    5. 5)
      • 8. Coster, M.J., LaMacchia, B.A., Odlyzko, A.M., et al: ‘An improved low-density subset sum algorithm’. Advances in Cryptology Proc. EUROCRYPTO'91, Berlin, 1991 (LNCS), pp. 54–67.
    6. 6)
      • 2. Schroeppel, R., Shamir, A.: ‘A T = O(2n/2), S = O(2n/4) algorithm for certain NP-complete problems’, SIAM J. Comput, 1981, 10, (3), pp. 456–464.
    7. 7)
      • 11. Lenstra, A.K., Lenstra, H.W.Jr., Lovász, L.: ‘Factoring polynomials with rational coefficients’, Math. Ann., 1982, 261, pp. 513–534.
    8. 8)
      • 7. Lagarias, J.C., Odlyzko, A.M.: ‘Solving low density subset sum problems’, J. Assoc. Comp. Math., Preliminary version in Proc. 24th IEEE, 1985, 32, pp. 229–246.
    9. 9)
      • 12. Gauss, C.F.: ‘Disquisitiones arithmeticae’ (Leipzig, 1801): German translation: Untersuchungen über die hohere arithmetik (Springer, Berlin, 1889). (Reprint: Chelsea, New York, 1981).
    10. 10)
      • 14. Gomez-Perez, D., Gutierrez, J., Ibeas, A.: ‘Attacking the pollard generator’, IEEE Trans. Inf. Theory, 2006, 52, (12), pp. 5518–5523.
    11. 11)
      • 10. Nguyen, P.Q., Stern, J.: ‘Merkle-Hellman revisited: a cryptanalysis of the Qu–Vanstone cryptosystem based on group factorizations’. CRYPTO, Santa Barbara, CA, USA, 1997, pp. 198–212.
    12. 12)
      • 1. Shor, W.P.: ‘Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer’. Proc. 35th Annual Symp. on Foundations of Computer Science, IEEE Computer Society Press, (quant-ph/9508027), Santa Fe, NM, 20–22 November 1994, pp. 124–134.
    13. 13)
      • 3. Howgrave-Graham, N., Joux, A.: ‘New generic algorithms for hard knapsacks’. EUROCRYPT, Monaco, Monaco and Nice, France, 2010, pp. 235–256.
    14. 14)
      • 5. Merkle, R.C., Hellman, M.E.: ‘Hiding information and signatures in trapdoor knapsacks’, IEEE Trans. Inf. Theory, 1978, IT-24, (5), pp. 525–530.
    15. 15)
      • 15. Shoup, V.N.T.L.: Number theory C++ library. Available at http://www.shoup.net/ntl/.
http://iet.metastore.ingenta.com/content/journals/10.1049/iet-ifs.2018.0041
Loading

Related content

content/journals/10.1049/iet-ifs.2018.0041
pub_keyword,iet_inspecKeyword,pub_concept
6
6
Loading
Print this page
This is a required field
Please enter a valid email address