access icon free Deterministic lattice reduction on knapsacks with collision-free properties

© The Institution of Engineering and Technology
Received 04/03/2017, Accepted 08/12/2017, Revised 18/11/2017, Published 08/12/2017

The knapsack problem is an important problem in computer science and had been used to design public key cryptosystems. Low-density subset sum algorithms are powerful tools to reduce the security of trapdoor knapsacks to the shortest vector problem (SVP) over lattices. Several knapsack ciphers Chor–Rivest, Okamoto–Tanaka–Uchiyama, and Kate–Goldberg were proposed to defend low-density attacks by utilising low-weight knapsack problems. Some evidence was also found on the vulnerabilities of the above three knapsack ciphers to lattice attacks. However, previous lattice-based cryptanalytic results have been established via a probabilistic approach. The authors investigate some collision-free properties and derive from the properties a deterministic reduction from the knapsack problems in the Chor–Rivest, Okamoto–Tanaka–Uchiyama, and Kate–Goldberg knapsack ciphers to SVP without imposing any restriction and assumption. To the best of the authors' knowledge, the proposed reduction is the first deterministic reduction from public key cryptographic knapsacks to SVP.

Inspec keywords: knapsack problems; probability; public key cryptography

Other keywords: collision-free properties; Kate-Goldberg knapsack ciphers; Okamoto-Tanaka-Uchiyama knapsack ciphers; low-weight knapsack problems; deterministic lattice reduction; trapdoor knapsack security; public key cryptosystems; low-density subset sum algorithms; Chor-Rivest knapsack ciphers; computer science; lattice-based cryptanalytic; low-density attacks; public key cryptographic knapsacks; shortest vector problem; probabilistic approach; SVP; lattice attacks

Subjects: Other topics in statistics; Cryptography; Cryptography theory; Other topics in statistics

References

    1. 1)
      • 14. Chor, B., Rivest, R.L.: ‘A knapsack-type public key cryptosystem based on arithmetic in finite fields (preliminary draft)’. Advances in Cryptology CRYPTO'84, Santa Barbara, California, USA, August 19–22, 1984 (LNCS, 196), pp. 54–65.
    2. 2)
      • 8. Brickell, E.F.: ‘Solving low density knapsacks’, in Chaum, D.(ed.): ‘Advances in cryptology’ (Springer, Boston, MA, 1984), pp. 25–37.
    3. 3)
      • 9. Lagarias, J.C., Odlyzko, A.M.: ‘Solving low-density subset sum problems’. 24th Annual Symp. on Foundations of Computer Science (FOCS 1983), Tucson, Arizona, USA, 7–9 November 1983, pp. 229–246.
    4. 4)
      • 24. Oomura, K., Tanaka, K.: ‘Density attack to the knapsack cryptosystems with enumerative source encoding’, IEICE Trans. Fund., 2001, E84-A, (1), pp. 1564–1569.
    5. 5)
      • 16. Vaudenay, S.: ‘Cryptanalysis of the Chor-Rivest cryptosystem’, J. Cryptol., 2001, 14, pp. 87–100.
    6. 6)
      • 10. Lagarias, J. C., Odlyzko, A. M.: ‘Solving low-density subset sum problems’, J. ACM, 1985, 32, pp. 229–246.
    7. 7)
      • 32. Nguyen, P.Q.: ‘Cryptanalysis of the Goldreich–Goldwasser–Halevi cryptosystem from Crypto'97’. Advances in Cryptology – CRYPTO 1999, Santa Barbara, California, USA, August 15–19, 1999 (LNCS, 1666), pp. 288–304.
    8. 8)
      • 35. Damgard, I.B.: ‘A design principle for hash functions’. Advances in Cryptology – CRYPTO'89, Santa Barbara, California, USA, August 20–24, 1989 (LNCS, 435), pp. 416–427.
    9. 9)
      • 7. Lai, M.K.: ‘Knapsack cryptosystems: the past and the future’, available athttp://www.ics.uci.edu/mingl/knapsack.html, accessed 2003.
    10. 10)
      • 12. Joux, A., Stern, J.: ‘Improving the critical density of the Lagarias-Odlyzko attack against subset sum problems’. Proc. 8th Int. Conf. of Fundamentals of Computation Theory – FCT 1991, Gosen, Germany, September 9–13, 1991 (LNCS, 529), pp. 258–264.
    11. 11)
      • 27. Kunihiro, N.: ‘New definition of density on knapsack cryptosystems’. Progress in Cryptology – AFRICACRYPT 2008, June 11–14, 2008 (LNCS, 5023), pp. 156–173.
    12. 12)
      • 13. Coster, M.J., Joux, A., LaMacchia, B.A., et al: ‘Improved low-density subset sum algorithms’, Comput. Complexity, 1992, 2, (2), pp. 111–128.
    13. 13)
      • 33. Lee, M.S., Hahn, S.G.: ‘Cryptanalysis of the GGH cryptosystem’, Math. Comput. Sci., 2010, 3, (2), pp. 201–208.
    14. 14)
      • 23. Damgard, I., Jurik, M.: ‘A generalisation, a simplification and some applications of Paillier's probabilistic public-key system’. Proc. 4th Int. Conf. on Practice and Theory in Public-Key Cryptography – PKC '01, Cheju Island, Korea, February 13–15, 2001 (LNCS, 1992), pp. 119–136.
    15. 15)
      • 20. Okamoto, T., Tanaka, K., Uchiyama, S.: ‘Quantum public-key cryptosystems’. Advances in Cryptology – Crypto 2000, Santa Barbara, California, USA, August 20–24, 2000 (LNCS, 1880), pp. 147–165.
    16. 16)
      • 28. Ajtai, M.: ‘The shortest vector problem in L2 is NP-hard for randomized reductions (extended abstract)’. Proc. 13th Annual ACM Symp. on the Theory of Computing-STOC 1998, Dallas, Texas, USA, 24–26 May 1998, pp. 10–19.
    17. 17)
      • 17. Encinas, L.H., Masqué, J. M., Dios, A.Q.: ‘Maple implementation of the Chor-Rivest cryptosystem’. Proc. 6th Int. Conf. on Computational Science – ICCS 2006, Reading, UK, May 28–31, 2006 (LNCS, 3992), pp. 438–445.
    18. 18)
      • 30. Schnorr, C.P.: ‘A hierarchy of polynomial time lattice basis reduction algorithms’, Theoret. Comput. Sci., 1987, 53, (2–3), pp. 201–224.
    19. 19)
      • 11. Coster, M.J., LaMacchia, B.A., Odlyzko, A.M., et al: ‘An improved low-density subset sum algorithm’. Advances in Cryptology – EUROCRYPT'91, April 8–11, 1991 (LNCS, 547), pp. 54–67.
    20. 20)
      • 3. Becker, A., Coron, J., Joux, A.: ‘Improved generic algorithms for hard knapsacks’, inAdvances in Cryptology – EUROCRYPT 2011, Tallinn, Estonia, May 15–19, 2011 (LNCS, 6632), pp. 364–385.
    21. 21)
      • 26. Izu, T., Kogure, J., Koshiba, T., et al: ‘Low-density attack revisited’, Des. Codes Cryptogr., 2007, 43, (1), pp. 47–59.
    22. 22)
      • 29. Lenstra, A.K., Lenstra, H.W., Lovász, L.: ‘Factoring polynomials with rational coefficients’, Math. Ann., 1982, 261, (4), pp. 513–534.
    23. 23)
      • 19. Encinas, L.H., Masqué, J.M., Dios, A.Q.: ‘Analysis of the efficiency of the Chor-Rivest cryptosystem implementation in a safe-parameter range’, Inf. Sci., 2009, 179, (24), pp. 4219–4226.
    24. 24)
      • 15. Chor, B., Rivest, R.L..: ‘A knapsack-type public key cryptosystem based on arithmetic in finite fields’, IEEE Trans. Inf. Theory, 1988, IT-34, pp. 901–909.
    25. 25)
      • 21. Shor, P.W.: ‘Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer’, SIAM J. Comput., 1997, 26, 5, pp. 1484–1509.
    26. 26)
      • 6. Odlyzko, A.M.: ‘The rise and fall of knapsack cryptosystems’, in ‘Cryptology and computational number theory’, Proc. Symposia in Applied Mathematics, vol. 42 (American Mathematical Society, Providence, 1990), pp. 75–88.
    27. 27)
      • 1. Schroeppel, R., Shamir, A.: ‘A T=O(2n/2),S=O(2n/4) algorithm for certain NP-complete problems’, SIAM J. Computing, 1981, 10, (3), pp. 456–464.
    28. 28)
      • 34. Schnorr, C.P., Hörner, H.H.: ‘Attacking the Chor–Rivest cryptosystem by improved lattice reduction’. Advances in Cryptology – Eurocrypt 1995, Saint-Malo, France, May 21–25, 1995 (LNCS, 921), pp. 1–12.
    29. 29)
      • 22. Kate, A., Goldberg, I.: ‘Generalizing cryptosystems based on the subset sum problem’, Int. J. Inf. Secur., 2011, 10, (3), pp. 189–199.
    30. 30)
      • 5. Merkle, R.C., Hellman, M.E.: ‘Hiding information and signatures in trapdoor knapsacks’, IEEE Trans. Inf. Theory, 1978, 24, (5), pp. 525–530.
    31. 31)
      • 25. Nguyen, P., Stern, J.: ‘Adapting density attacks to low-weight knapsacks’. Advances in Cryptology – ASIACRYPT 2005, Chennai, India, December 4–8, 2005 (LNCS, 3788), pp. 41–58.
    32. 32)
      • 4. Garey, M.R., Johnson, D.S.: ‘Computers and intractability, a guide to the theory of NP-completeness’ (W. H. Freeman, New York, USA, 1979, 1st edn.).
    33. 33)
      • 18. Encinas, L.H., Masqué, J.M., Dios, A.Q.: ‘Safer parameters for the Chor-Rivest cryptosystem’, Comput. Math. Appl., 2008, 56, (11), pp. 2883–2886.
    34. 34)
      • 2. Howgrave-Graham, N., Joux, A.: ‘New generic algorithms for hard knapsacks’. Advances in Cryptology – EUROCRYPT 2010, French Riviera, May 30–June 3, 2010 (LNCS, 6110), pp. 235–256.
    35. 35)
      • 31. Nguyen, P. Q., Stehle, D.: ‘An LLL algorithm with quadratic complexity’, SIAM J. Comput., 2009, 39, 3, pp. 874–903.
http://iet.metastore.ingenta.com/content/journals/10.1049/iet-ifs.2017.0107
Loading

Related content

content/journals/10.1049/iet-ifs.2017.0107
pub_keyword,iet_inspecKeyword,pub_concept
6
6
Loading