# American Institute of Mathematical Sciences

November  2019, 13(4): 645-688. doi: 10.3934/amc.2019040

## Another look at success probability of linear cryptanalysis

 Applied Statistics Unit, Indian Statistical Institute, 203, B.T.Road, Kolkata, 700108, India

* Corresponding author

Received  October 2018 Revised  January 2019 Published  June 2019

This work studies the success probability of key recovery attacks based on using a single linear approximation. Previous works had analysed success probability under different hypotheses on the distributions of correlations for the right and wrong key choices. This work puts forward a unifying framework of general key randomisation hypotheses. All previously used key randomisation hypotheses as also zero correlation attacks can be seen as special cases of the general framework. Derivations of expressions for the success probability are carried out under both the settings of the plaintexts being sampled with and without replacements. Compared to previous analysis, we uncover several new cases which have not been considered in the literature. For most of the cases which have been considered earlier, we provide complete expressions for the respective success probabilities. Finally, the full picture of the dependence of the success probability on the data complexity is revealed. Compared to the extant literature, our work provides a deeper and more thorough understanding of the success probability of single linear cryptanalysis.

Citation: Subhabrata Samajder, Palash Sarkar. Another look at success probability of linear cryptanalysis. Advances in Mathematics of Communications, 2019, 13 (4) : 645-688. doi: 10.3934/amc.2019040
##### References:
 [1] T. Ashur, T. Beyne and V. Rijmen, Revisiting the wrong-key-randomization hypothesis, IACR Cryptology ePrint Archive, 2016 (2016), 990, Available at http://eprint.iacr.org/2016/990. [2] T. Baignères, P. Junod and S. Vaudenay, How far can we go beyond linear cryptanalysis?, In Pil Joong Lee, editor, Advances in Cryptology - ASIACRYPT 2004, 10th International Conference on the Theory and Application of Cryptology and Information Security, Jeju Island, Korea, December 5-9, 2004, Proceedings, volume 3329 of Lecture Notes in Computer Science, 432–450. Springer, 2004. ISBN: 3-540-23975-8. doi: 10.1007/978-3-540-30539-2_31. [3] T. Baignères, P. Sepehrdad and S. Vaudenay, Distinguishing distributions using chernoff information, In Swee-Huay Heng and Kaoru Kurosawa, editors, Provable Security - 4th International Conference, ProvSec 2010, Malacca, Malaysia, October 13-15, 2010. Proceedings, volume 6402 of Lecture Notes in Computer Science, pages 144–165. Springer, 2010. ISBN: 978-3-642-16279-4. doi: 10.1007/978-3-642-16280-0_10. [4] A. Biryukov, C. De Cannière and M. Quisquater, On multiple linear approximations, Advances in cryptology–CRYPTO 2004, Lecture Notes in Comput. Sci., Springer, Berlin, 3152 (2004), 1–22. doi: 10.1007/978-3-540-28628-8_1. [5] C. Blondeau, B. Gérard and K. Nyberg, Multiple differential cryptanalysis using LLR and $\chi^{2}$ statistics, Security and Cryptography for Networks, 343–360, Lecture Notes in Comput. Sci., 7485, Springer, Heidelberg, 2012. doi: 10.1007/978-3-642-32928-9_19. [6] C. Blondeau and M. Minier, Analysis of impossible, integral and zero-correlation attacks on type-ii generalized feistel networks using the matrix method, Fast Software Encryption - 22nd International Workshop, FSE 2015, Istanbul, Turkey, March 8-11, 2015, Revised Selected Papers, Lecture Notes in Computer Science, Springer, 9054 (2015), 92–113. doi: 10.1007/978-3-662-48116-5_5. [7] C. Blondeau and K. Nyberg, Improved parameter estimates for correlation and capacity deviates in linear cryptanalysis, IACR Transactions Symmetric Cryptology, 2016 (2016), 162–191. https://www.doi.org/10.13154/tosc.v2016.i2.162-191. [8] C. Blondeau and K. Nyberg, Joint data and key distribution of simple, multiple, and multidimensional linear cryptanalysis test statistic and its impact to data complexity, Design Codes Cryptography, 82 (2017), 319-349.  doi: 10.1007/s10623-016-0268-6. [9] A. Bogdanov, H. Geng, M. Wang, L. Wen and B. Collard, Zero-correlation linear cryptanalysis with fft and improved attacks on iso standards camellia and CLEFIA, In Tanja Lange, Kristin E. Lauter, and Petr Lisonek, editors, Selected Areas in Cryptography - SAC 2013 - 20th International Conference, Burnaby, BC, Canada, August 14-16, 2013, Revised Selected Papers, volume 8282 of Lecture Notes in Computer Science, Springer, (2014), 306–323. https://www.doi.org/10.1007/978-3-662-43414-7_16, ISBN: 978-3-662-43413-0. [10] A. Bogdanov, G. Leander, K. Nyberg and M. Wang, Integral and multidimensional linear distinguishers with correlation zero, In Xiaoyun Wang and Kazue Sako, editors, Advances in Cryptology - ASIACRYPT 2012 - 18th International Conference on the Theory and Application of Cryptology and Information Security, Beijing, China, December 2-6, 2012. Proceedings, volume 7658 of Lecture Notes in Computer Science, pages 244–261. Springer, 2012. ISBN: 978-3-642-34960-7. doi: 10.1007/978-3-642-34961-4_16. [11] A. Bogdanov and V. Rijmen, Linear hulls with correlation zero and linear cryptanalysis of block ciphers, Design Codes Cryptography, 70 (2014), 369-383.  doi: 10.1007/s10623-012-9697-z. [12] A. Bogdanov and E. Tischhauser, On the wrong key randomisation and key equivalence hypotheses in matsui's algorithm 2, In Shiho Moriai, editor, Fast Software Encryption - 20th International Workshop, FSE 2013, Singapore, March 11-13, 2013. Revised Selected Papers, volume 8424 of Lecture Notes in Computer Science, pages 19–38. Springer, 2014. ISBN: 978-3-662-43932-6. doi: 10.1007/978-3-662-43933-3_2. [13] A. Bogdanov and M. Wang, Zero correlation linear cryptanalysis with reduced data complexity, In Anne Canteaut, editor, Fast Software Encryption - 19th International Workshop, FSE 2012, Washington, DC, USA, March 19-21, 2012. Revised Selected Papers, volume 7549 of Lecture Notes in Computer Science, pages 29–48. Springer, 2012. ISBN: 978-3-642-34046-8. doi: 10.1007/978-3-642-34047-5_3. [14] J. Daemen and V. Rijmen, Probability distributions of correlation and differentials in block ciphers, IACR Cryptology ePrint Archive, 2005: 212, 2005. Available at http://eprint.iacr.org/2005/212. [15] J. Daemen and V. Rijmen, Probability distributions of correlation and differentials in block ciphers, Journal of Mathematical Cryptology, 1 (2007), 221-242.  doi: 10.1515/JMC.2007.011. [16] W. Feller, An Introduction to Probability Theory and Its Applications, Volume 1, John Wiley & Sons, Inc., New York, N.Y., 1950. [17] B. Gérard and J.-P. Tillich, On linear cryptanalysis with many linear approximations, In Matthew G. Parker, editor, Cryptography and Coding, 12th IMA International Conference, Cryptography and Coding 2009, Cirencester, UK, December 15-17, 2009. Proceedings, volume 5921 of Lecture Notes in Computer Science, 112–132. Springer, 2009. doi: 10.1007/978-3-642-10868-6_8. [18] C. Harpes, G. G. Kramer and J. L. Massey, A generalization of linear cryptanalysis and the applicability of matsui's piling-up lemma, In Louis C. Guillou and Jean-Jacques Quisquater, editors, Advances in Cryptology - EUROCRYPT '95, International Conference on the Theory and Application of Cryptographic Techniques, Saint-Malo, France, May 21-25, 1995, Proceeding, volume 921 of Lecture Notes in Computer Science, 24–38. Springer, 1995. https://www.doi.org/10.1007/3-540-49264-X_3. [19] M. Hermelin, J. Y. Cho and K. Nyberg, Multidimensional extension of matsui's algorithm 2, In Fast Software Encryption, 16th International Workshop, FSE 2009, Leuven, Belgium, February 22-25, 2009, Revised Selected Papers, volume 5665 of Lecture Notes in Computer Science, 209–227. Springer, 2009. doi: 10.1007/978-3-642-03317-9_13. [20] J. Huang, S. Vaudenay, X. Lai and K. Nyberg, Capacity and data complexity in multidimensional linear attack, In Rosario Gennaro and Matthew Robshaw, editors, Advances in Cryptology - CRYPTO 2015 - 35th Annual Cryptology Conference, Santa Barbara, CA, USA, August 16-20, 2015, Proceedings, Part I, volume 9215 of Lecture Notes in Computer Science, 141–160, Springer, 2015. doi: 10.1007/978-3-662-47989-6_7. [21] B. S. Kaliski Jr. and M. J. B. Robshaw, Linear cryptanalysis using multiple approximations, In Yvo Desmedt, editor, Advances in Cryptology - CRYPTO '94, 14th Annual International Cryptology Conference, Santa Barbara, California, USA, August 21-25, 1994, Proceedings, volume 839 of Lecture Notes in Computer Science, 26–39, Springer, 1994. doi: 10.1007/3-540-48658-5_4. [22] P. Junod, On the complexity of matsui's attack, In Serge Vaudenay and Amr M. Youssef, editors, Selected Areas in Cryptography, 8th Annual International Workshop, SAC 2001 Toronto, Ontario, Canada, August 16-17, 2001, Revised Papers, volume 2259 of Lecture Notes in Computer Science, 199–211, Springer, 2001. doi: 10.1007/3-540-45537-X_16. [23] P. Junod, On the optimality of linear, differential, and sequential distinguishers, In Eli Biham, editor, Advances in Cryptology - EUROCRYPT 2003, International Conference on the Theory and Applications of Cryptographic Techniques, Warsaw, Poland, May 4-8, 2003, Proceedings, volume 2656 of Lecture Notes in Computer Science, 17–32, Springer, 2003. doi: 10.1007/3-540-39200-9_2. [24] P. Junod and S. Vaudenay, Optimal key ranking procedures in a statistical cryptanalysis, In Thomas Johansson, editor, Fast Software Encryption, 10th International Workshop, FSE 2003, Lund, Sweden, February 24-26, 2003, Revised Papers, volume 2887 of Lecture Notes in Computer Science, 235–246, Springer, 2003. doi: 10.1007/978-3-540-39887-5_18. [25] S. N. Lahiri and A. Chatterjee, A Berry-Esseen theorem for hypergeometric probabilities under minimal conditions, Proceedings of the American Mathematical Society, 135 (2007), 1535-1545.  doi: 10.1090/S0002-9939-07-08676-5. [26] M. Matsui, Linear cryptanalysis method for des cipher, In Tor Helleseth, editor, Advances in Cryptology - EUROCRYPT '93, Workshop on the Theory and Application of of Cryptographic Techniques, Lofthus, Norway, May 23-27, 1993, Proceedings, volume 765 of Lecture Notes in Computer Science, 386–397, Springer, 1994. https://www.doi.org/10.1007/3-540-48285-7_33. [27] M. Matsui, The first experimental cryptanalysis of the data encryption standard, In Yvo Desmedt, editor, Advances in Cryptology - CRYPTO '94, 14th Annual International Cryptology Conference, Santa Barbara, California, USA, August 21-25, 1994, Proceedings, volume 839 of Lecture Notes in Computer Science, 1–11, Springer, 1994. https://www.doi.org/10.1007/3-540-48658-5_1. [28] S. Murphy, The independence of linear approximations in symmetric cryptanalysis, IEEE Transactions on Information Theory, 52 (2006), 5510-5518.  doi: 10.1109/TIT.2006.885528. [29] S. Samajder and P. Sarkar, Another look at normal approximations in cryptanalysis, Journal Mathematical Cryptology, 10 (2016), 69-99.  doi: 10.1515/jmc-2016-0006. [30] S. Samajder and P. Sarkar, A new test statistic for key recovery attacks using multiple linear approximations, In Raphael C.-W. Phan and Moti Yung, editors, Paradigms in Cryptology - Mycrypt 2016. Malicious and Exploratory Cryptology - Second International Conference, Mycrypt 2016, Kuala Lumpur, Malaysia, December 1-2, 2016, Revised Selected Papers, volume 10311 of Lecture Notes in Computer Science, 277–293, Springer, 2017, https://www.doi.org/10.1007/978-3-319-61273-7_14. [31] S. Samajder and P. Sarkar, Rigorous upper bounds on data complexities of block cipher cryptanalysis, Journal of Mathematical Cryptology, 11 (2017), 147-175.  doi: 10.1515/jmc-2016-0026. [32] S. Samajder and P. Sarkar, Success Probability of Multiple/Multidimensional Linear Cryptanalysis Under General Key Randomisation Hypotheses, Cryptography and Communications, 10 (2018), 835-879.  doi: 10.1007/s12095-017-0257-2. [33] A. A. Selçuk, On probability of success in linear and differential cryptanalysis, Journal of Cryptology, 21 (2008), 131-147.  doi: 10.1007/s00145-007-9013-7. [34] H. Soleimany and K. Nyberg, Zero-correlation linear cryptanalysis of reduced-round lblock, Design Codes Cryptography, 73 (2014), 683-698.  doi: 10.1007/s10623-014-9976-y. [35] L. Sun, H. Chen and M. Wang, Zero-correlation attacks: Statistical models independent of the number of approximations, Designs, Codes and Cryptography, 86 (2018), 1923-1945.  doi: 10.1007/s10623-017-0430-9. [36] E. W. Tischhauser, Mathematical Aspects of Symmetric-Key Cryptography, PhD thesis, Katholieke Universiteit Leuven, 2012. [37] A. M. Walker, A note on the asymptotic distribution of sample quantiles, Journal of the Royal Statistical Society. Series B (Methodological), 30 (1968), 570-575.  doi: 10.1111/j.2517-6161.1968.tb00757.x.

show all references

##### References:
 [1] T. Ashur, T. Beyne and V. Rijmen, Revisiting the wrong-key-randomization hypothesis, IACR Cryptology ePrint Archive, 2016 (2016), 990, Available at http://eprint.iacr.org/2016/990. [2] T. Baignères, P. Junod and S. Vaudenay, How far can we go beyond linear cryptanalysis?, In Pil Joong Lee, editor, Advances in Cryptology - ASIACRYPT 2004, 10th International Conference on the Theory and Application of Cryptology and Information Security, Jeju Island, Korea, December 5-9, 2004, Proceedings, volume 3329 of Lecture Notes in Computer Science, 432–450. Springer, 2004. ISBN: 3-540-23975-8. doi: 10.1007/978-3-540-30539-2_31. [3] T. Baignères, P. Sepehrdad and S. Vaudenay, Distinguishing distributions using chernoff information, In Swee-Huay Heng and Kaoru Kurosawa, editors, Provable Security - 4th International Conference, ProvSec 2010, Malacca, Malaysia, October 13-15, 2010. Proceedings, volume 6402 of Lecture Notes in Computer Science, pages 144–165. Springer, 2010. ISBN: 978-3-642-16279-4. doi: 10.1007/978-3-642-16280-0_10. [4] A. Biryukov, C. De Cannière and M. Quisquater, On multiple linear approximations, Advances in cryptology–CRYPTO 2004, Lecture Notes in Comput. Sci., Springer, Berlin, 3152 (2004), 1–22. doi: 10.1007/978-3-540-28628-8_1. [5] C. Blondeau, B. Gérard and K. Nyberg, Multiple differential cryptanalysis using LLR and $\chi^{2}$ statistics, Security and Cryptography for Networks, 343–360, Lecture Notes in Comput. Sci., 7485, Springer, Heidelberg, 2012. doi: 10.1007/978-3-642-32928-9_19. [6] C. Blondeau and M. Minier, Analysis of impossible, integral and zero-correlation attacks on type-ii generalized feistel networks using the matrix method, Fast Software Encryption - 22nd International Workshop, FSE 2015, Istanbul, Turkey, March 8-11, 2015, Revised Selected Papers, Lecture Notes in Computer Science, Springer, 9054 (2015), 92–113. doi: 10.1007/978-3-662-48116-5_5. [7] C. Blondeau and K. Nyberg, Improved parameter estimates for correlation and capacity deviates in linear cryptanalysis, IACR Transactions Symmetric Cryptology, 2016 (2016), 162–191. https://www.doi.org/10.13154/tosc.v2016.i2.162-191. [8] C. Blondeau and K. Nyberg, Joint data and key distribution of simple, multiple, and multidimensional linear cryptanalysis test statistic and its impact to data complexity, Design Codes Cryptography, 82 (2017), 319-349.  doi: 10.1007/s10623-016-0268-6. [9] A. Bogdanov, H. Geng, M. Wang, L. Wen and B. Collard, Zero-correlation linear cryptanalysis with fft and improved attacks on iso standards camellia and CLEFIA, In Tanja Lange, Kristin E. Lauter, and Petr Lisonek, editors, Selected Areas in Cryptography - SAC 2013 - 20th International Conference, Burnaby, BC, Canada, August 14-16, 2013, Revised Selected Papers, volume 8282 of Lecture Notes in Computer Science, Springer, (2014), 306–323. https://www.doi.org/10.1007/978-3-662-43414-7_16, ISBN: 978-3-662-43413-0. [10] A. Bogdanov, G. Leander, K. Nyberg and M. Wang, Integral and multidimensional linear distinguishers with correlation zero, In Xiaoyun Wang and Kazue Sako, editors, Advances in Cryptology - ASIACRYPT 2012 - 18th International Conference on the Theory and Application of Cryptology and Information Security, Beijing, China, December 2-6, 2012. Proceedings, volume 7658 of Lecture Notes in Computer Science, pages 244–261. Springer, 2012. ISBN: 978-3-642-34960-7. doi: 10.1007/978-3-642-34961-4_16. [11] A. Bogdanov and V. Rijmen, Linear hulls with correlation zero and linear cryptanalysis of block ciphers, Design Codes Cryptography, 70 (2014), 369-383.  doi: 10.1007/s10623-012-9697-z. [12] A. Bogdanov and E. Tischhauser, On the wrong key randomisation and key equivalence hypotheses in matsui's algorithm 2, In Shiho Moriai, editor, Fast Software Encryption - 20th International Workshop, FSE 2013, Singapore, March 11-13, 2013. Revised Selected Papers, volume 8424 of Lecture Notes in Computer Science, pages 19–38. Springer, 2014. ISBN: 978-3-662-43932-6. doi: 10.1007/978-3-662-43933-3_2. [13] A. Bogdanov and M. Wang, Zero correlation linear cryptanalysis with reduced data complexity, In Anne Canteaut, editor, Fast Software Encryption - 19th International Workshop, FSE 2012, Washington, DC, USA, March 19-21, 2012. Revised Selected Papers, volume 7549 of Lecture Notes in Computer Science, pages 29–48. Springer, 2012. ISBN: 978-3-642-34046-8. doi: 10.1007/978-3-642-34047-5_3. [14] J. Daemen and V. Rijmen, Probability distributions of correlation and differentials in block ciphers, IACR Cryptology ePrint Archive, 2005: 212, 2005. Available at http://eprint.iacr.org/2005/212. [15] J. Daemen and V. Rijmen, Probability distributions of correlation and differentials in block ciphers, Journal of Mathematical Cryptology, 1 (2007), 221-242.  doi: 10.1515/JMC.2007.011. [16] W. Feller, An Introduction to Probability Theory and Its Applications, Volume 1, John Wiley & Sons, Inc., New York, N.Y., 1950. [17] B. Gérard and J.-P. Tillich, On linear cryptanalysis with many linear approximations, In Matthew G. Parker, editor, Cryptography and Coding, 12th IMA International Conference, Cryptography and Coding 2009, Cirencester, UK, December 15-17, 2009. Proceedings, volume 5921 of Lecture Notes in Computer Science, 112–132. Springer, 2009. doi: 10.1007/978-3-642-10868-6_8. [18] C. Harpes, G. G. Kramer and J. L. Massey, A generalization of linear cryptanalysis and the applicability of matsui's piling-up lemma, In Louis C. Guillou and Jean-Jacques Quisquater, editors, Advances in Cryptology - EUROCRYPT '95, International Conference on the Theory and Application of Cryptographic Techniques, Saint-Malo, France, May 21-25, 1995, Proceeding, volume 921 of Lecture Notes in Computer Science, 24–38. Springer, 1995. https://www.doi.org/10.1007/3-540-49264-X_3. [19] M. Hermelin, J. Y. Cho and K. Nyberg, Multidimensional extension of matsui's algorithm 2, In Fast Software Encryption, 16th International Workshop, FSE 2009, Leuven, Belgium, February 22-25, 2009, Revised Selected Papers, volume 5665 of Lecture Notes in Computer Science, 209–227. Springer, 2009. doi: 10.1007/978-3-642-03317-9_13. [20] J. Huang, S. Vaudenay, X. Lai and K. Nyberg, Capacity and data complexity in multidimensional linear attack, In Rosario Gennaro and Matthew Robshaw, editors, Advances in Cryptology - CRYPTO 2015 - 35th Annual Cryptology Conference, Santa Barbara, CA, USA, August 16-20, 2015, Proceedings, Part I, volume 9215 of Lecture Notes in Computer Science, 141–160, Springer, 2015. doi: 10.1007/978-3-662-47989-6_7. [21] B. S. Kaliski Jr. and M. J. B. Robshaw, Linear cryptanalysis using multiple approximations, In Yvo Desmedt, editor, Advances in Cryptology - CRYPTO '94, 14th Annual International Cryptology Conference, Santa Barbara, California, USA, August 21-25, 1994, Proceedings, volume 839 of Lecture Notes in Computer Science, 26–39, Springer, 1994. doi: 10.1007/3-540-48658-5_4. [22] P. Junod, On the complexity of matsui's attack, In Serge Vaudenay and Amr M. Youssef, editors, Selected Areas in Cryptography, 8th Annual International Workshop, SAC 2001 Toronto, Ontario, Canada, August 16-17, 2001, Revised Papers, volume 2259 of Lecture Notes in Computer Science, 199–211, Springer, 2001. doi: 10.1007/3-540-45537-X_16. [23] P. Junod, On the optimality of linear, differential, and sequential distinguishers, In Eli Biham, editor, Advances in Cryptology - EUROCRYPT 2003, International Conference on the Theory and Applications of Cryptographic Techniques, Warsaw, Poland, May 4-8, 2003, Proceedings, volume 2656 of Lecture Notes in Computer Science, 17–32, Springer, 2003. doi: 10.1007/3-540-39200-9_2. [24] P. Junod and S. Vaudenay, Optimal key ranking procedures in a statistical cryptanalysis, In Thomas Johansson, editor, Fast Software Encryption, 10th International Workshop, FSE 2003, Lund, Sweden, February 24-26, 2003, Revised Papers, volume 2887 of Lecture Notes in Computer Science, 235–246, Springer, 2003. doi: 10.1007/978-3-540-39887-5_18. [25] S. N. Lahiri and A. Chatterjee, A Berry-Esseen theorem for hypergeometric probabilities under minimal conditions, Proceedings of the American Mathematical Society, 135 (2007), 1535-1545.  doi: 10.1090/S0002-9939-07-08676-5. [26] M. Matsui, Linear cryptanalysis method for des cipher, In Tor Helleseth, editor, Advances in Cryptology - EUROCRYPT '93, Workshop on the Theory and Application of of Cryptographic Techniques, Lofthus, Norway, May 23-27, 1993, Proceedings, volume 765 of Lecture Notes in Computer Science, 386–397, Springer, 1994. https://www.doi.org/10.1007/3-540-48285-7_33. [27] M. Matsui, The first experimental cryptanalysis of the data encryption standard, In Yvo Desmedt, editor, Advances in Cryptology - CRYPTO '94, 14th Annual International Cryptology Conference, Santa Barbara, California, USA, August 21-25, 1994, Proceedings, volume 839 of Lecture Notes in Computer Science, 1–11, Springer, 1994. https://www.doi.org/10.1007/3-540-48658-5_1. [28] S. Murphy, The independence of linear approximations in symmetric cryptanalysis, IEEE Transactions on Information Theory, 52 (2006), 5510-5518.  doi: 10.1109/TIT.2006.885528. [29] S. Samajder and P. Sarkar, Another look at normal approximations in cryptanalysis, Journal Mathematical Cryptology, 10 (2016), 69-99.  doi: 10.1515/jmc-2016-0006. [30] S. Samajder and P. Sarkar, A new test statistic for key recovery attacks using multiple linear approximations, In Raphael C.-W. Phan and Moti Yung, editors, Paradigms in Cryptology - Mycrypt 2016. Malicious and Exploratory Cryptology - Second International Conference, Mycrypt 2016, Kuala Lumpur, Malaysia, December 1-2, 2016, Revised Selected Papers, volume 10311 of Lecture Notes in Computer Science, 277–293, Springer, 2017, https://www.doi.org/10.1007/978-3-319-61273-7_14. [31] S. Samajder and P. Sarkar, Rigorous upper bounds on data complexities of block cipher cryptanalysis, Journal of Mathematical Cryptology, 11 (2017), 147-175.  doi: 10.1515/jmc-2016-0026. [32] S. Samajder and P. Sarkar, Success Probability of Multiple/Multidimensional Linear Cryptanalysis Under General Key Randomisation Hypotheses, Cryptography and Communications, 10 (2018), 835-879.  doi: 10.1007/s12095-017-0257-2. [33] A. A. Selçuk, On probability of success in linear and differential cryptanalysis, Journal of Cryptology, 21 (2008), 131-147.  doi: 10.1007/s00145-007-9013-7. [34] H. Soleimany and K. Nyberg, Zero-correlation linear cryptanalysis of reduced-round lblock, Design Codes Cryptography, 73 (2014), 683-698.  doi: 10.1007/s10623-014-9976-y. [35] L. Sun, H. Chen and M. Wang, Zero-correlation attacks: Statistical models independent of the number of approximations, Designs, Codes and Cryptography, 86 (2018), 1923-1945.  doi: 10.1007/s10623-017-0430-9. [36] E. W. Tischhauser, Mathematical Aspects of Symmetric-Key Cryptography, PhD thesis, Katholieke Universiteit Leuven, 2012. [37] A. M. Walker, A note on the asymptotic distribution of sample quantiles, Journal of the Royal Statistical Society. Series B (Methodological), 30 (1968), 570-575.  doi: 10.1111/j.2517-6161.1968.tb00757.x.
Case $t_2\leq x_0 < t_1$
Case $t_2 < t_1 < x_0$
Case $x_0 < t_2 < t_1$
Here "type" denotes whether $p = 1/2$ or not; srswr (resp. srswor) denotes sampling with (resp. without) replacement; RKRH (resp. WKRH) is an abbreviation for right (resp. wrong) key randomisation hypothesis; std (resp. adj) denotes whether the standard (resp. adjusted) key randomisation hypothesis is considered
 type samp. RKRH WKRH cond. previous $P_{S}$ new $P_{S}$ $p \neq 1/2$ wr std std - [33] Section 5.4, Eqn (41) std adj - [12] Section 5.5, Eqn (44) adj std - - Section 5.6, Eqn (46) adj adj - [8] Section 5.7, Eqn (48) wor std std - - Section 5.4, Eqn (42) std adj - [1] Section 5.5, Eqn (44) adj std - - Section 5.6, Eqn (47) adj adj - - Section 5.7, Eqn (49) $p = 1/2$ wr std adj - - Section 7.1, Eqn (57) adj std - - Section 7.2, Eqn (60) adj adj ${\mathtt{ELP}}>2^{-n}$ [7] Section 7.3, Eqn (62) adj adj ${\mathtt{ELP}} < 2^{-n}$ - Section 7.3, Eqn (63) wor std adj - - Section 7.1, Eqn (58) adj std - - Section 7.2, Eqn (61) adj adj ${\mathtt{ELP}}>2^{-n}$ [7] Section 7.3, Eqn (64) adj adj ${\mathtt{ELP}} < 2^{-n}$ - Section 7.3, Eqn (65)
 type samp. RKRH WKRH cond. previous $P_{S}$ new $P_{S}$ $p \neq 1/2$ wr std std - [33] Section 5.4, Eqn (41) std adj - [12] Section 5.5, Eqn (44) adj std - - Section 5.6, Eqn (46) adj adj - [8] Section 5.7, Eqn (48) wor std std - - Section 5.4, Eqn (42) std adj - [1] Section 5.5, Eqn (44) adj std - - Section 5.6, Eqn (47) adj adj - - Section 5.7, Eqn (49) $p = 1/2$ wr std adj - - Section 7.1, Eqn (57) adj std - - Section 7.2, Eqn (60) adj adj ${\mathtt{ELP}}>2^{-n}$ [7] Section 7.3, Eqn (62) adj adj ${\mathtt{ELP}} < 2^{-n}$ - Section 7.3, Eqn (63) wor std adj - - Section 7.1, Eqn (58) adj std - - Section 7.2, Eqn (61) adj adj ${\mathtt{ELP}}>2^{-n}$ [7] Section 7.3, Eqn (64) adj adj ${\mathtt{ELP}} < 2^{-n}$ - Section 7.3, Eqn (65)
Summary of the different cases and sub-cases showing the dependence of the success probability on the data complexity for $p\neq 1/2$. Here $n$ is the block size, $\epsilon = p-1/2$, $\mathfrak{s}_0^2 = ({\mathtt{ELP}}-4\epsilon^2)/4$, $\mathfrak{s}_1^2 = 2^{-n-2}$ and $\gamma ={{\mathit{\Phi} }^{-1}}\left( 1-\frac{{{2}^{m-a-1\;\;\;}}}{{{2}^{m}}-1\;\;\;\;} \right)$
 [1] Stefano Galatolo. Orbit complexity and data compression. Discrete and Continuous Dynamical Systems, 2001, 7 (3) : 477-486. doi: 10.3934/dcds.2001.7.477 [2] Enrico Capobianco. Born to be big: Data, graphs, and their entangled complexity. Big Data & Information Analytics, 2016, 1 (2&3) : 163-169. doi: 10.3934/bdia.2016002 [3] Yannick Privat, Emmanuel Trélat, Enrique Zuazua. Complexity and regularity of maximal energy domains for the wave equation with fixed initial data. Discrete and Continuous Dynamical Systems, 2015, 35 (12) : 6133-6153. doi: 10.3934/dcds.2015.35.6133 [4] William Chad Young, Adrian E. Raftery, Ka Yee Yeung. A posterior probability approach for gene regulatory network inference in genetic perturbation data. Mathematical Biosciences & Engineering, 2016, 13 (6) : 1241-1251. doi: 10.3934/mbe.2016041 [5] Alina Ostafe, Igor E. Shparlinski, Arne Winterhof. On the generalized joint linear complexity profile of a class of nonlinear pseudorandom multisequences. Advances in Mathematics of Communications, 2010, 4 (3) : 369-379. doi: 10.3934/amc.2010.4.369 [6] Uwe Helmke, Jens Jordan, Julia Lieb. Probability estimates for reachability of linear systems defined over finite fields. Advances in Mathematics of Communications, 2016, 10 (1) : 63-78. doi: 10.3934/amc.2016.10.63 [7] Yanjun Wang, Shisen Liu. Relaxation schemes for the joint linear chance constraint based on probability inequalities. Journal of Industrial and Management Optimization, 2021  doi: 10.3934/jimo.2021132 [8] Joan-Josep Climent, Elisa Gorla, Joachim Rosenthal. Cryptanalysis of the CFVZ cryptosystem. Advances in Mathematics of Communications, 2007, 1 (1) : 1-11. doi: 10.3934/amc.2007.1.1 [9] Thomas R. Cameron, Sebastian Charmot, Jonad Pulaj. On the linear ordering problem and the rankability of data. Foundations of Data Science, 2021, 3 (2) : 133-149. doi: 10.3934/fods.2021010 [10] Liqin Hu, Qin Yue, Fengmei Liu. Linear complexity of cyclotomic sequences of order six and BCH codes over GF(3). Advances in Mathematics of Communications, 2014, 8 (3) : 297-312. doi: 10.3934/amc.2014.8.297 [11] Zhixiong Chen, Vladimir Edemskiy, Pinhui Ke, Chenhuang Wu. On $k$-error linear complexity of pseudorandom binary sequences derived from Euler quotients. Advances in Mathematics of Communications, 2018, 12 (4) : 805-816. doi: 10.3934/amc.2018047 [12] Jianqin Zhou, Wanquan Liu, Xifeng Wang. Structure analysis on the k-error linear complexity for 2n-periodic binary sequences. Journal of Industrial and Management Optimization, 2017, 13 (4) : 1743-1757. doi: 10.3934/jimo.2017016 [13] Siqi Li, Weiyi Qian. Analysis of complexity of primal-dual interior-point algorithms based on a new kernel function for linear optimization. Numerical Algebra, Control and Optimization, 2015, 5 (1) : 37-46. doi: 10.3934/naco.2015.5.37 [14] Lin Yi, Xiangyong Zeng, Zhimin Sun, Shasha Zhang. On the linear complexity and autocorrelation of generalized cyclotomic binary sequences with period $4p^n$. Advances in Mathematics of Communications, 2021  doi: 10.3934/amc.2021019 [15] Ayache Benhadid, Fateh Merahi. Complexity analysis of an interior-point algorithm for linear optimization based on a new parametric kernel function with a double barrier term. Numerical Algebra, Control and Optimization, 2022  doi: 10.3934/naco.2022003 [16] Giacomo Micheli. Cryptanalysis of a noncommutative key exchange protocol. Advances in Mathematics of Communications, 2015, 9 (2) : 247-253. doi: 10.3934/amc.2015.9.247 [17] Jianqin Zhou, Wanquan Liu, Xifeng Wang. Complete characterization of the first descent point distribution for the k-error linear complexity of 2n-periodic binary sequences. Advances in Mathematics of Communications, 2017, 11 (3) : 429-444. doi: 10.3934/amc.2017036 [18] Jianqin Zhou, Wanquan Liu, Xifeng Wang, Guanglu Zhou. On the $k$-error linear complexity for $p^n$-periodic binary sequences via hypercube theory. Mathematical Foundations of Computing, 2019, 2 (4) : 279-297. doi: 10.3934/mfc.2019018 [19] Luis Corchón, Marco Serena. Properties of contests: Constructing contest success functions from best-responses. Journal of Dynamics and Games, 2022, 9 (2) : 151-163. doi: 10.3934/jdg.2022001 [20] G. R. Cirmi, S. Leonardi. Higher differentiability for solutions of linear elliptic systems with measure data. Discrete and Continuous Dynamical Systems, 2010, 26 (1) : 89-104. doi: 10.3934/dcds.2010.26.89

2021 Impact Factor: 1.015