Low weight discrete logarithm and subset sum in \(2^{0.65n}\) with polynomial memory. (English) Zbl 1479.94165
Canteaut, Anne (ed.) et al., Advances in cryptology – EUROCRYPT 2020. 39th annual international conference on the theory and applications of cryptographic techniques, Zagreb, Croatia, May 10–14, 2020. Proceedings. Part III. Cham: Springer. Lect. Notes Comput. Sci. 12107, 94-122 (2020).
Summary: We propose two heuristic polynomial memory collision finding algorithms for the low Hamming weight discrete logarithm problem in any abelian group \(G\). The first one is a direct adaptation of the Becker-Coron-Joux (BCJ) algorithm for subset sum to the discrete logarithm setting. The second one significantly improves on this adaptation for all possible weights using a more involved application of the representation technique together with some new Markov chain analysis. In contrast to other low weight discrete logarithm algorithms, our second algorithm’s time complexity interpolates to Pollard’s \(|G|^{\frac{1}{2}}\) bound for general discrete logarithm instances.
We also introduce a new heuristic subset sum algorithm with polynomial memory that improves on BCJ’s \(2^{0.72n}\) time bound for random subset sum instances \(a_1, \ldots , a_n, t \in \mathbb{Z}_{2^n} \). Technically, we introduce a novel nested collision finding for subset sum – inspired by the NestedRho algorithm from [I. Dinur et al., Lect. Notes Comput. Sci. 9815, 185–206 (2016; Zbl 1372.94423)] – that recursively produces collisions. We first show how to instantiate our algorithm with run time \(2^{0.649n} \). Using further tricks, we are then able to improve its complexity down to \(2^{0.645n} \).
For the entire collection see [Zbl 1475.94009].
We also introduce a new heuristic subset sum algorithm with polynomial memory that improves on BCJ’s \(2^{0.72n}\) time bound for random subset sum instances \(a_1, \ldots , a_n, t \in \mathbb{Z}_{2^n} \). Technically, we introduce a novel nested collision finding for subset sum – inspired by the NestedRho algorithm from [I. Dinur et al., Lect. Notes Comput. Sci. 9815, 185–206 (2016; Zbl 1372.94423)] – that recursively produces collisions. We first show how to instantiate our algorithm with run time \(2^{0.649n} \). Using further tricks, we are then able to improve its complexity down to \(2^{0.645n} \).
For the entire collection see [Zbl 1475.94009].
MSC:
| 94A60 | Cryptography |
Citations:
Zbl 1372.94423References:
| [1] | Abboud, A., Bringmann, K., Hermelin, D., Shabtay, D.: Seth-based lower bounds for subset sum and bicriteria path. In: Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 41-57. Society for Industrial and Applied Mathematics (2019) · Zbl 1431.68040 |
| [2] | Alekhnovich, M.: More on average case vs approximation complexity. In: 44th Annual Symposium on Foundations of Computer Science, Cambridge, MA, USA, 11-14 October 2003, pp. 298-307. IEEE Computer Society Press (2003) |
| [3] | Bansal, N., Garg, S., Nederlof, J., Vyas, N.: Faster space-efficient algorithms for subset sum and k-sum. In: Hatami, H., McKenzie, P., King, V. (eds.) 49th Annual ACM Symposium on Theory of Computing, Montreal, QC, Canada, 19-23 June 2017, pp. 198-209. ACM Press (2017) · Zbl 1369.68348 |
| [4] | Becker, A.; Coron, J-S; Joux, A.; Paterson, KG, Improved generic algorithms for hard knapsacks, Advances in Cryptology - EUROCRYPT 2011, 364-385 (2011), Heidelberg: Springer, Heidelberg · Zbl 1281.94014 · doi:10.1007/978-3-642-20465-4_21 |
| [5] | Becker, A.; Joux, A.; May, A.; Meurer, A.; Pointcheval, D.; Johansson, T., Decoding random binary linear codes in 2^n/20: how 1 + 1 = 0 improves information set decoding, Advances in Cryptology - EUROCRYPT 2012, 520-536 (2012), Heidelberg: Springer, Heidelberg · Zbl 1291.94206 · doi:10.1007/978-3-642-29011-4_31 |
| [6] | Bernstein, DJ; Jeffery, S.; Lange, T.; Meurer, A.; Gaborit, P., Quantum algorithms for the subset-sum problem, Post-Quantum Cryptography, 16-33 (2013), Heidelberg: Springer, Heidelberg · Zbl 1295.68127 · doi:10.1007/978-3-642-38616-9_2 |
| [7] | Bos, JW; Kaihara, M.; Kleinjung, T.; Lenstra, AK; Montgomery, PL, Solving 112-bit prime ECDLP on game consoles using sloppy reduction, Int. J. Appl. Cryptogr., 2, ARTICLE, 212-228 (2012) · Zbl 1276.94008 · doi:10.1504/IJACT.2012.045590 |
| [8] | Chor, B.; Rivest, RL; Blakley, GR; Chaum, D., A knapsack type public key cryptosystem based on arithmetic in finite fields (preliminary draft), Advances in Cryptology, 54-65 (1985), Heidelberg: Springer, Heidelberg · Zbl 0571.94013 · doi:10.1007/3-540-39568-7_6 |
| [9] | Dinur, I.; Dunkelman, O.; Keller, N.; Shamir, A.; Robshaw, M.; Katz, J., Memory-efficient algorithms for finding needles in haystacks, Advances in Cryptology - CRYPTO 2016, 185-206 (2016), Heidelberg: Springer, Heidelberg · Zbl 1372.94423 · doi:10.1007/978-3-662-53008-5_7 |
| [10] | Esser, A.; Kübler, R.; May, A.; Katz, J.; Shacham, H., LPN decoded, Advances in Cryptology - CRYPTO 2017, 486-514 (2017), Cham: Springer, Cham · Zbl 1410.94065 · doi:10.1007/978-3-319-63715-0_17 |
| [11] | Faust, S.; Masny, D.; Venturi, D.; Cheng, C-M; Chung, K-M; Persiano, G.; Yang, B-Y, Chosen-ciphertext security from subset sum, Public-Key Cryptography - PKC 2016, 35-46 (2016), Heidelberg: Springer, Heidelberg · Zbl 1388.94053 · doi:10.1007/978-3-662-49384-7_2 |
| [12] | Galbraith, SD, Mathematics of Public Key Cryptography (2012), Cambridge: Cambridge University Press, Cambridge · Zbl 1238.94027 · doi:10.1017/CBO9781139012843 |
| [13] | Galbraith, SD; Gaudry, P., Recent progress on the elliptic curve discrete logarithm problem, Des. Codes Crypt., 78, 1, 51-72 (2015) · Zbl 1364.11164 · doi:10.1007/s10623-015-0146-7 |
| [14] | Halderman, JA, Lest we remember: cold-boot attacks on encryption keys, Commun. ACM, 52, 5, 91-98 (2009) · doi:10.1145/1506409.1506429 |
| [15] | Herold, G.; May, A.; Fehr, S., LP solutions of vectorial integer subset sums – cryptanalysis of Galbraith’s binary matrix LWE, Public-Key Cryptography - PKC 2017, 3-15 (2017), Heidelberg: Springer, Heidelberg · Zbl 1404.94081 · doi:10.1007/978-3-662-54365-8_1 |
| [16] | Impagliazzo, R.; Naor, M., Efficient cryptographic schemes provably as secure as subset sum, J. Cryptol., 9, 4, 199-216 (1996) · Zbl 0862.94015 · doi:10.1007/BF00189260 |
| [17] | Knuth, D.E: The Art of Computer Programming, Volume II: Seminumerical Algorithms, 3rd edn. Addison-Wesley (1998). http://www.worldcat.org/oclc/312898417. ISBN: 0201896842 · Zbl 0895.68054 |
| [18] | Lagarias, JC; Odlyzko, AM, Solving low-density subset sum problems, J. ACM (JACM), 32, 1, 229-246 (1985) · Zbl 0632.94007 · doi:10.1145/2455.2461 |
| [19] | Lyubashevsky, V.; Palacio, A.; Segev, G.; Micciancio, D., Public-key cryptographic primitives provably as secure as subset sum, Theory of Cryptography, 382-400 (2010), Heidelberg: Springer, Heidelberg · Zbl 1274.94096 · doi:10.1007/978-3-642-11799-2_23 |
| [20] | May, A.; Ozerov, I.; Joux, A.; Youssef, A., A generic algorithm for small weight discrete logarithms in composite groups, Selected Areas in Cryptography - SAC 2014, 278-289 (2014), Cham: Springer, Cham · Zbl 1382.94139 · doi:10.1007/978-3-319-13051-4_17 |
| [21] | Merkle, R.; Hellman, M., Hiding information and signatures in trapdoor knapsacks, IEEE Trans. Inf. Theory, 24, 5, 525-530 (1978) · Zbl 1487.94132 · doi:10.1109/TIT.1978.1055927 |
| [22] | Nivasch, G., Cycle detection using a stack, Inform. Process. Lett., 90, 3, 135-140 (2004) · Zbl 1178.68648 · doi:10.1016/j.ipl.2004.01.016 |
| [23] | Odlyzko, AM, The rise and fall of knapsack cryptosystems, Cryptol. Comput. Number Theory, 42, 75-88 (1990) · Zbl 0733.94012 · doi:10.1090/psapm/042/1095552 |
| [24] | Pollard, JM, A monte carlo method for factorization, BIT Numer. Math., 15, 3, 331-334 (1975) · Zbl 0312.10006 · doi:10.1007/BF01933667 |
| [25] | Regev, O.: On lattices, learning with errors, random linear codes, and cryptography. In: Gabow, H.N., Fagin, R. (eds.) 37th Annual ACM Symposium on Theory of Computing, Baltimore, MA, USA, 22-24 May 2005, pp. 84-93. ACM Press, Baltimore (2005) · Zbl 1192.94106 |
| [26] | Shanks, D.: Five number-theoretic algorithms. In: Proceedings of the Second Manitoba Conference on Numerical Mathematics (Winnipeg), 1973 (1973) · Zbl 0307.10015 |
| [27] | Stinson, D., Some baby-step giant-step algorithms for the low hamming weight discrete logarithm problem, Math. Comput., 71, 237, 379-391 (2002) · Zbl 0977.68040 · doi:10.1090/S0025-5718-01-01310-2 |
| [28] | Van Oorschot, P.C., Wiener, M.J.: Parallel collision search with application to hash functions and discrete logarithms. In: Proceedings of the 2nd ACM Conference on Computer and Communications Security, pp. 210-218. ACM (1994) |
| [29] | van Oorschot, PC; Wiener, MJ, Parallel collision search with cryptanalytic applications, J. Cryptol., 12, 1, 1-28 (1999) · Zbl 0992.94028 · doi:10.1007/PL00003816 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
