SAT-based differential automatic search algorithm using divide-and-conquer strategy and its applications
To improve the efficiency of automatic search, an algorithm for searching the optimal differential characteristics based on SAT model was proposed by combining the divide-and-conquer strategy.The search space was divided into disjoint subsets by using the information from Matsui boundary conditions...
Saved in:
| Main Authors: | , , |
|---|---|
| Format: | Article |
| Language: | zho |
| Published: |
Editorial Department of Journal on Communications
2023-04-01
|
| Series: | Tongxin xuebao |
| Subjects: | |
| Online Access: | http://www.joconline.com.cn/zh/article/doi/10.11959/j.issn.1000-436x.2023082/ |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1841540011771559936 |
|---|---|
| author | Bin HU Xiao TAN Senpeng WANG |
| author_facet | Bin HU Xiao TAN Senpeng WANG |
| author_sort | Bin HU |
| collection | DOAJ |
| description | To improve the efficiency of automatic search, an algorithm for searching the optimal differential characteristics based on SAT model was proposed by combining the divide-and-conquer strategy.The search space was divided into disjoint subsets by using the information from Matsui boundary conditions of arbitrary continuous rounds.By analyzing the relationships between satisfiability of differential models based on SAT, a descending branch search chain model was proposed.Furthermore, at the model optimization level, the number of subsets that need to be searched and partitioned was decreased.At the level of algorithm implementation, the search space was reduced by utilizing the parallel technology.Finally, the accelerated algorithm was applied to SPECK family of ARX cryptographic algorithms.The 20, 14, 11-round optimal differential characteristics of SPECK-48, SPECK-96, SPECK-128 are obtained, which increase the previous best results by 1, 4, 2 rounds respectively. |
| format | Article |
| id | doaj-art-c71c842f622e424db9da0fe98ee03b4c |
| institution | Kabale University |
| issn | 1000-436X |
| language | zho |
| publishDate | 2023-04-01 |
| publisher | Editorial Department of Journal on Communications |
| record_format | Article |
| series | Tongxin xuebao |
| spelling | doaj-art-c71c842f622e424db9da0fe98ee03b4c2025-01-14T06:28:27ZzhoEditorial Department of Journal on CommunicationsTongxin xuebao1000-436X2023-04-014413714459390378SAT-based differential automatic search algorithm using divide-and-conquer strategy and its applicationsBin HUXiao TANSenpeng WANGTo improve the efficiency of automatic search, an algorithm for searching the optimal differential characteristics based on SAT model was proposed by combining the divide-and-conquer strategy.The search space was divided into disjoint subsets by using the information from Matsui boundary conditions of arbitrary continuous rounds.By analyzing the relationships between satisfiability of differential models based on SAT, a descending branch search chain model was proposed.Furthermore, at the model optimization level, the number of subsets that need to be searched and partitioned was decreased.At the level of algorithm implementation, the search space was reduced by utilizing the parallel technology.Finally, the accelerated algorithm was applied to SPECK family of ARX cryptographic algorithms.The 20, 14, 11-round optimal differential characteristics of SPECK-48, SPECK-96, SPECK-128 are obtained, which increase the previous best results by 1, 4, 2 rounds respectively.http://www.joconline.com.cn/zh/article/doi/10.11959/j.issn.1000-436x.2023082/differential characteristicblock cipherautomatic searchdivide-and-conquer strategy |
| spellingShingle | Bin HU Xiao TAN Senpeng WANG SAT-based differential automatic search algorithm using divide-and-conquer strategy and its applications Tongxin xuebao differential characteristic block cipher automatic search divide-and-conquer strategy |
| title | SAT-based differential automatic search algorithm using divide-and-conquer strategy and its applications |
| title_full | SAT-based differential automatic search algorithm using divide-and-conquer strategy and its applications |
| title_fullStr | SAT-based differential automatic search algorithm using divide-and-conquer strategy and its applications |
| title_full_unstemmed | SAT-based differential automatic search algorithm using divide-and-conquer strategy and its applications |
| title_short | SAT-based differential automatic search algorithm using divide-and-conquer strategy and its applications |
| title_sort | sat based differential automatic search algorithm using divide and conquer strategy and its applications |
| topic | differential characteristic block cipher automatic search divide-and-conquer strategy |
| url | http://www.joconline.com.cn/zh/article/doi/10.11959/j.issn.1000-436x.2023082/ |
| work_keys_str_mv | AT binhu satbaseddifferentialautomaticsearchalgorithmusingdivideandconquerstrategyanditsapplications AT xiaotan satbaseddifferentialautomaticsearchalgorithmusingdivideandconquerstrategyanditsapplications AT senpengwang satbaseddifferentialautomaticsearchalgorithmusingdivideandconquerstrategyanditsapplications |