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. Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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. Google Scholar

[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.  Google Scholar

[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. Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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. Google Scholar

[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.  Google Scholar

[16]

W. Feller, An Introduction to Probability Theory and Its Applications, Volume 1, John Wiley & Sons, Inc., New York, N.Y., 1950.  Google Scholar

[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.  Google Scholar

[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. Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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. Google Scholar

[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. Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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. Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[35]

L. SunH. 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.  Google Scholar

[36]

E. W. Tischhauser, Mathematical Aspects of Symmetric-Key Cryptography, PhD thesis, Katholieke Universiteit Leuven, 2012. Google Scholar

[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.  Google Scholar

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. Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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. Google Scholar

[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.  Google Scholar

[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. Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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. Google Scholar

[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.  Google Scholar

[16]

W. Feller, An Introduction to Probability Theory and Its Applications, Volume 1, John Wiley & Sons, Inc., New York, N.Y., 1950.  Google Scholar

[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.  Google Scholar

[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. Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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. Google Scholar

[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. Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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. Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[35]

L. SunH. 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.  Google Scholar

[36]

E. W. Tischhauser, Mathematical Aspects of Symmetric-Key Cryptography, PhD thesis, Katholieke Universiteit Leuven, 2012. Google Scholar

[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.  Google Scholar

Figure 1.  Case $t_2\leq x_0 < t_1$
Figure 2.  Case $t_2 < t_1 < x_0$
Figure 3.  Case $x_0 < t_2 < t_1$
Table 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)
Table 2.  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 & Continuous Dynamical Systems - A, 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 & Continuous Dynamical Systems - A, 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]

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

[8]

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

[9]

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

[10]

Jianqin Zhou, Wanquan Liu, Xifeng Wang. Structure analysis on the k-error linear complexity for 2n-periodic binary sequences. Journal of Industrial & Management Optimization, 2017, 13 (4) : 1743-1757. doi: 10.3934/jimo.2017016

[11]

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 & Optimization, 2015, 5 (1) : 37-46. doi: 10.3934/naco.2015.5.37

[12]

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

[13]

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

[14]

G. R. Cirmi, S. Leonardi. Higher differentiability for solutions of linear elliptic systems with measure data. Discrete & Continuous Dynamical Systems - A, 2010, 26 (1) : 89-104. doi: 10.3934/dcds.2010.26.89

[15]

Valentin Afraimovich, Lev Glebsky, Rosendo Vazquez. Measures related to metric complexity. Discrete & Continuous Dynamical Systems - A, 2010, 28 (4) : 1299-1309. doi: 10.3934/dcds.2010.28.1299

[16]

Rainer Steinwandt, Adriana Suárez Corona. Cryptanalysis of a 2-party key establishment based on a semigroup action problem. Advances in Mathematics of Communications, 2011, 5 (1) : 87-92. doi: 10.3934/amc.2011.5.87

[17]

Paul Sacks, Mahamadi Warma. Semi-linear elliptic and elliptic-parabolic equations with Wentzell boundary conditions and $L^1$-data. Discrete & Continuous Dynamical Systems - A, 2014, 34 (2) : 761-787. doi: 10.3934/dcds.2014.34.761

[18]

Wen-Rong Dai. Formation of singularities to quasi-linear hyperbolic systems with initial data of small BV norm. Discrete & Continuous Dynamical Systems - A, 2012, 32 (10) : 3501-3524. doi: 10.3934/dcds.2012.32.3501

[19]

Valentin Afraimovich, Maurice Courbage, Lev Glebsky. Directional complexity and entropy for lift mappings. Discrete & Continuous Dynamical Systems - B, 2015, 20 (10) : 3385-3401. doi: 10.3934/dcdsb.2015.20.3385

[20]

H.T. Banks, Jimena L. Davis. Quantifying uncertainty in the estimation of probability distributions. Mathematical Biosciences & Engineering, 2008, 5 (4) : 647-667. doi: 10.3934/mbe.2008.5.647

2018 Impact Factor: 0.879

Article outline

Figures and Tables

[Back to Top]