Volume 15, Issue 3 (12-2018)                   JSDP 2018, 15(3): 47-58 | Back to browse issues page


XML Persian Abstract Print


Download citation:
BibTeX | RIS | EndNote | Medlars | ProCite | Reference Manager | RefWorks
Send citation to:

Gharavi N H, Mirqadri A, Abdollahi azgomi M, Mousavi S A. Expected coverage rate for the Hellman matrices. JSDP 2018; 15 (3) :47-58
URL: http://jsdp.rcisp.ac.ir/article-1-607-en.html
Abstract:   (3476 Views)

Hellman’s time-memory trade-off is a probabilistic method for inverting one-way functions, using pre-computed data. Hellman introduced this method in 1980 and obtained a lower bound for the success probability of his algorithm.  After that, all further analyses of researchers are based on this lower bound.
In this paper, we first studied the expected coverage rate (ECR) of the Hellman matrices, which are constructed by a single chain. We showed that the ECR of such matrices is maximum and equal to 0.85. In this process, we find out that there exists a gap between the Hellman’s lower bound and experimental coverage rate of a Hellman matrix. Specifically, this gap is larger, when considering the Hellman matrices constructed with one single chain. So, we are investigated to obtain an accurate formula for the ECR of a Hellman matrix. Subsequently, we presented a new formula that estimate the ECR of a Hellman matrix more accurately than the Hellman’s lower bound. We showed that the given formula is closely match experimental data.
In the last, we introduced a new method to construct matrices which have much more ECR than Hellman matrices. In fact, each matrix in this new method is constructed with one single chain, which is non-repeating trajectory from a random point. So, this approach result in a number of matrices that each one contains a chain with variable length. The main advantage of this method is that we have more probability of success than Hellman method, however online time and memory requirements are increased. We have also verified theory of this new method with experimental results.
 

Full-Text [PDF 4821 kb]   (1047 Downloads)    
Type of Study: Research | Subject: Paper
Received: 2017/12/7 | Accepted: 2018/07/25 | Published: 2018/12/19 | ePublished: 2018/12/19

References
1. [1] E. Barkan, E. Biham and A. Shamir, "Rigorous bounds on cryptanalytic time/memory tradeoffs", in Advances in Cryptology: Proceedings of Crypto, LNCS, 2006, 4117, pp. 1–21.
2. [2] J. Borst, "Block Ciphers: Design, Analysis and Side-Channel Analysis", PhD thesis, Katholieke Universiteit Leuven, 2001.
3. [3] D.E. Denning, Cryptography and data security, Addison-Wesley, 1982.
4. [4] P. Flajolet, and A. Odlyzko, "Random mapping statistics", Advances in Cryptology, Proceedings of Eurocrypt'89, LNCS, 1990, 434, pp. 329–354.
5. [5] P. Flajolet, and R. Sedgewick, An introduction to analysis of algorithms, Addison-Wesley, 2013.
6. [6] B. Harris, "Probability distributions related to random mappings", The Annals of Mathematical Statistics, pp. 1045–1062, 1960. [DOI:10.1214/aoms/1177705677]
7. [7] M. Hellman, "A cryptanalytic time-memory trade-off", IEEE Transactions on Information Theory IT, vol. 26, pp. 401–406, 1980. [DOI:10.1109/TIT.1980.1056220]
8. [8] J. Hong, and S. Moon, "A comparison of cryptanalytic tradeoff algorithms", Journal of cryptology, vol. 26 (4), pp. 559-637, 2013. [DOI:10.1007/s00145-012-9128-3]
9. [9] J. Hong and B.I. Kim, "Performance comparison of cryptanalytic time memory data tradeoff methods", Bull. Korean Math. Soc., vol. 53(5), pp. 1439-1446, 2016. [DOI:10.4134/BKMS.b150754]
10. [10] V. Kolchin, "Random mapp-ings", Translations series in mathematics and engineering, Optimization Software, Inc., Publications Division, 1986.
11. [11] K. Kusuda, and T. Matsumoto, "Optimization of time-memory trade-off cryptanalysis and is application to DES", FEAL-32, and Skipjack, E-79A, pp. 35–48, 1996.
12. [12] G. W. Lee, and J. Hong, "Comparison of perfect table cryptanalytic tradeoff algorithms", Designs, Codes and Cryptography, pp. 473-523, 2016. [DOI:10.1007/s10623-015-0116-0]
13. [13] R.C. Phan, "Mini advanced encryption standard (mini-AES): a testbed for cryptanalysis students", Cryptologia, vol. 26(4), pp. 283-306, 2002. [DOI:10.1080/0161-110291890948]
14. [14] Ph. Oechslin, "Making a faster cryptanaly-tic time-memory trade-off", Annual International Cryptology Conference, Springer Berlin Heidelberg, 2003.

Add your comments about this article : Your username or Email:
CAPTCHA

Send email to the article author


Rights and permissions
Creative Commons License This work is licensed under a Creative Commons Attribution-NonCommercial 4.0 International License.

© 2015 All Rights Reserved | Signal and Data Processing