Further accelerating the search of differential characteristics based on the SAT method
Sun et al.’s method of using Matsui’s bounding conditions to accelerate the search of differential characteristics was reviewed.Matsui’s boundary conditions and Sun et al.’s method of using Matsui’s bounding conditions to accelerate the search of differential characteristics were improved for better...
Saved in:
| Main Author: | |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
POSTS&TELECOM PRESS Co., LTD
2022-10-01
|
| Series: | 网络与信息安全学报 |
| Subjects: | |
| Online Access: | http://www.cjnis.com.cn/thesisDetails#10.11959/j.issn.2096-109x.2022066 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1841529720531845120 |
|---|---|
| author | Zheng XU |
| author_facet | Zheng XU |
| author_sort | Zheng XU |
| collection | DOAJ |
| description | Sun et al.’s method of using Matsui’s bounding conditions to accelerate the search of differential characteristics was reviewed.Matsui’s boundary conditions and Sun et al.’s method of using Matsui’s bounding conditions to accelerate the search of differential characteristics were improved for better search efficiency.Then an improved method to search for the optimal differential characteristics in block ciphers was proposed.Besides, the accelerating effects of the number of threads and the query condition were investigated, and a strategy for choosing the number of threads and the query condition were proposed.STP and CryptoMiniSat were used to search for 8-round SPECK96 differential characteristics with probabilities of 2<sup>- 24</sup>, 2<sup>- 25</sup>, 2<sup>- 26</sup>and 11-round HIGHT differential characteristics with a probability of 2<sup>- 39</sup>, then the time-consuming of solving SAT/SMT problems under different number of threads and query conditions were compared.It was found that the number of threads has a great effect on the time consumption of searching for differential characteristics, while the query condition may have little effect on the time consumption of searching for differential characteristics.Then, a strategy on how to select the number of threads and the query condition was proposed.Furthermore, it was found that STP can affect the overall efficiency of the search.According to the proposed strategy, the 11-round optimal differential characteristics of HIGHT were searched by using the improved bounding conditions and improved method.A tight bound for the probability of the 11-round optimal differential characteristics of HIGHT was obtained for the first time, i.e.2<sup>- 45</sup>.To the best of our knowledge, the existing tightest bound of the optimal 11-round HIGHT is <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML"> <msubsup> <mi>P</mi> <mrow> <mtext>Opt</mtext></mrow> <mrow> <mn>11</mn></mrow> </msubsup> <mo>≥</mo><msup> <mn>2</mn> <mrow> <mo>−</mo><mn>45</mn></mrow> </msup> </math></inline-formula> .This means that using the existing tightest bound of the optimal 11-round HIGHT cannot give an accurate evaluation of the security of 11-round HIGHT against differential cryptanalysis.Therefore, the result is the best-known result. |
| format | Article |
| id | doaj-art-92490c417ef64b139617bf9e1a20e875 |
| institution | Kabale University |
| issn | 2096-109X |
| language | English |
| publishDate | 2022-10-01 |
| publisher | POSTS&TELECOM PRESS Co., LTD |
| record_format | Article |
| series | 网络与信息安全学报 |
| spelling | doaj-art-92490c417ef64b139617bf9e1a20e8752025-01-15T03:16:13ZengPOSTS&TELECOM PRESS Co., LTD网络与信息安全学报2096-109X2022-10-01812913959575615Further accelerating the search of differential characteristics based on the SAT methodZheng XUSun et al.’s method of using Matsui’s bounding conditions to accelerate the search of differential characteristics was reviewed.Matsui’s boundary conditions and Sun et al.’s method of using Matsui’s bounding conditions to accelerate the search of differential characteristics were improved for better search efficiency.Then an improved method to search for the optimal differential characteristics in block ciphers was proposed.Besides, the accelerating effects of the number of threads and the query condition were investigated, and a strategy for choosing the number of threads and the query condition were proposed.STP and CryptoMiniSat were used to search for 8-round SPECK96 differential characteristics with probabilities of 2<sup>- 24</sup>, 2<sup>- 25</sup>, 2<sup>- 26</sup>and 11-round HIGHT differential characteristics with a probability of 2<sup>- 39</sup>, then the time-consuming of solving SAT/SMT problems under different number of threads and query conditions were compared.It was found that the number of threads has a great effect on the time consumption of searching for differential characteristics, while the query condition may have little effect on the time consumption of searching for differential characteristics.Then, a strategy on how to select the number of threads and the query condition was proposed.Furthermore, it was found that STP can affect the overall efficiency of the search.According to the proposed strategy, the 11-round optimal differential characteristics of HIGHT were searched by using the improved bounding conditions and improved method.A tight bound for the probability of the 11-round optimal differential characteristics of HIGHT was obtained for the first time, i.e.2<sup>- 45</sup>.To the best of our knowledge, the existing tightest bound of the optimal 11-round HIGHT is <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML"> <msubsup> <mi>P</mi> <mrow> <mtext>Opt</mtext></mrow> <mrow> <mn>11</mn></mrow> </msubsup> <mo>≥</mo><msup> <mn>2</mn> <mrow> <mo>−</mo><mn>45</mn></mrow> </msup> </math></inline-formula> .This means that using the existing tightest bound of the optimal 11-round HIGHT cannot give an accurate evaluation of the security of 11-round HIGHT against differential cryptanalysis.Therefore, the result is the best-known result.http://www.cjnis.com.cn/thesisDetails#10.11959/j.issn.2096-109x.2022066differential cryptanalysisdifferential characteristicsautomatic searchSAT solver |
| spellingShingle | Zheng XU Further accelerating the search of differential characteristics based on the SAT method 网络与信息安全学报 differential cryptanalysis differential characteristics automatic search SAT solver |
| title | Further accelerating the search of differential characteristics based on the SAT method |
| title_full | Further accelerating the search of differential characteristics based on the SAT method |
| title_fullStr | Further accelerating the search of differential characteristics based on the SAT method |
| title_full_unstemmed | Further accelerating the search of differential characteristics based on the SAT method |
| title_short | Further accelerating the search of differential characteristics based on the SAT method |
| title_sort | further accelerating the search of differential characteristics based on the sat method |
| topic | differential cryptanalysis differential characteristics automatic search SAT solver |
| url | http://www.cjnis.com.cn/thesisDetails#10.11959/j.issn.2096-109x.2022066 |
| work_keys_str_mv | AT zhengxu furtheracceleratingthesearchofdifferentialcharacteristicsbasedonthesatmethod |