fa امید ریاضی نرخ پوشش برای ماتریس‌های هلمن مقالات گروه رمز Paper پژوهشي Research <p dir="RTL" style="text-align: justify;"><strong><span style="font-family:b nazanin;">مصالحه حافظه‌زمان یک الگوریتم احتمالاتی برای وارون‌کردن توابع یک‌طرفه، با استفاده از داده‌های </span></strong><strong><span style="font-family:b nazanin;">از </span></strong><strong><span style="font-family:b nazanin;">پیش محاسبه‌شده است. هلمن در سال ۱۹۸۰ این روش را معرفی</span></strong> <strong><span style="font-family:b nazanin;">کرد و یک کران پایین برای احتمال موفقیت آن به‌دست آورد. پس از آن نیز تحلیل‌های پژوهش‌گران برای بررسی احتمال موفقیت، بر اساس همین کران پایین بوده است</span></strong><strong><span style="font-family:b nazanin;">. در این مقاله، ابتدا به بررسی</span></strong> <strong><span style="font-family:b nazanin;">امید ریاضی نرخ پوشش یک ماتریس هلمن می‌پردازیم؛ سپس، </span></strong><strong><span style="font-family:b nazanin;">این </span></strong><strong><span style="font-family:b nazanin;">نرخ را برای ماتریس‌های هلمنی که فقط از یک زنجیره تشکیل شده‌اند، محاسبه کرده‌ایم. نشان داده‌ایم که امید ریاضی نرخ پوشش برای چنین ماتریس‌هایی بیشینه و برابر با ۸۵/۰ است. در ادامه</span></strong><strong><span style="font-family:b nazanin;">،</span></strong><strong><span style="font-family:b nazanin;"> روش‌هایی برای تخمین دقیق‌تر این نرخ ارائه، و با روش هلمن مقایسه و در‌نهایت، ماتریس‌های هلمنی را معرفی کرده‌ایم که فقط از یک زنجیره تشکیل شده‌اند؛ ولی طول این زنجیره مقداری ثابت نیست و تا رسیدن به نخستین تکرار ادامه می‌یابد. به‌صورت نظری و عملی نشان داده‌ایم که احتمال موفقیت برای چنین ماتریس‌هایی بیشتر از روش هلمن است.</span></strong><br> &nbsp;</p> <p style="text-align: justify;"><strong>Hellman&rsquo;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.&nbsp; After that, all further analyses of researchers are based on this lower bound. </strong><br> <strong>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 </strong><strong>0.</strong><strong>85. In this process, we find out that there exists a gap between the Hellman&rsquo;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&rsquo;s lower bound. We showed that the given formula is closely match experimental data. </strong><br> <strong>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 </strong><strong>experimental </strong><strong>results.</strong><br> &nbsp;</p> مصالحه حافظه‌زمان, تابع یک‌طرفه, ماتریس هلمن, امید ریاضی نرخ پوشش Time-Memory Trade-off, one way function, Hellman matrix, Expected coverage rate 47 58 http://jsdp.rcisp.ac.ir/browse.php?a_code=A-10-1198-1&slc_lang=fa&sid=1 Naser Hosein Gharavi ناصرحسین غروی hgharavi@ihu.ac.ir 10031947532846006703 10031947532846006703 Yes IHU دانشگاه جامع امام حسین (ع) Abdorasool Mirqadri عبدالرسول میرقدری amrghdri@ihu.ac.ir 10031947532846006704 10031947532846006704 No IHU دانشگاه جامع امام حسین (ع) Mohammad Abdollahi azgomi محمد عبدالهی ازگمی azgomi@iust.ac.ir 10031947532846006705 10031947532846006705 No IUST دانشگاه علم و صنعت ایران Sayyed Ahmad Mousavi سید احمد موسوی s.a.mousavi@math.uk.ac.ir 10031947532846006706 10031947532846006706 No Nasr R&D دانشگاه شهید باهنر کرمان