Institutional Repository
| Utilizing Probabilistic Linear Equations in Cube Attacks | |
| Yao, Y; Zhang, B; Wu, WL | |
| 2016 | |
| Source | JOURNAL OF COMPUTER SCIENCE AND TECHNOLOGY
 |
| ISSN | 1000-9000 |
| Volume | 31Issue:2Pages:317-325 |
| English Abstract | Cube attacks, proposed by Dinur and Shamir at EUROCRYPT 2009, have shown huge power against stream ciphers. In the original cube attacks, a linear system of secret key bits is exploited for key recovery attacks. However, we find a number of equations claimed linear in previous literature actually nonlinear and not fit into the theoretical framework of cube attacks. Moreover, cube attacks are hard to apply if linear equations are rare. Therefore, it is of significance to make use of probabilistic linear equations, namely nonlinear superpolys that can be approximated by linear expressions effectively. In this paper, we suggest a way to test out and utilize these probabilistic linear equations, thus extending cube attacks to a wider scope. Concretely, we employ the standard parameter estimation approach and the sequential probability ratio test (SPRT) for linearity test in the preprocessing phase, and use maximum likelihood decoding (MLD) for solving the probabilistic linear equations in the online phase. As an application, we exhibit our new attack against 672 rounds of Trivium and reduce the number of key bits to search by 7.; Cube attacks, proposed by Dinur and Shamir at EUROCRYPT 2009, have shown huge power against stream ciphers. In the original cube attacks, a linear system of secret key bits is exploited for key recovery attacks. However, we find a number of equations claimed linear in previous literature actually nonlinear and not fit into the theoretical framework of cube attacks. Moreover, cube attacks are hard to apply if linear equations are rare. Therefore, it is of significance to make use of probabilistic linear equations, namely nonlinear superpolys that can be approximated by linear expressions effectively. In this paper, we suggest a way to test out and utilize these probabilistic linear equations, thus extending cube attacks to a wider scope. Concretely, we employ the standard parameter estimation approach and the sequential probability ratio test (SPRT) for linearity test in the preprocessing phase, and use maximum likelihood decoding (MLD) for solving the probabilistic linear equations in the online phase. As an application, we exhibit our new attack against 672 rounds of Trivium and reduce the number of key bits to search by 7. |
| Indexed Type | SCI |
| Keyword | Cube Attack Sequential Probability Ratio Test Maximum Likelihood Decoding Trivium |
| Department | Chinese Acad Sci, Inst Software, Trusted Comp & Informat Assurance Lab, Beijing 100190, Peoples R China. Univ Chinese Acad Sci, Beijing 100190, Peoples R China. |
| Language | 英语 |
| WOS ID | WOS:000372154100007 |
| Citation statistics | |
| Content Type | 期刊论文 |
| URI | http://ir.iscas.ac.cn/handle/311060/17344 |
| Collection | 中国科学院软件研究所 |
| Recommended Citation GB/T 7714 | Yao, Y,Zhang, B,Wu, WL. Utilizing Probabilistic Linear Equations in Cube Attacks[J]. JOURNAL OF COMPUTER SCIENCE AND TECHNOLOGY,2016,31(2):317-325. |
| APA | Yao, Y,Zhang, B,&Wu, WL.(2016).Utilizing Probabilistic Linear Equations in Cube Attacks.JOURNAL OF COMPUTER SCIENCE AND TECHNOLOGY,31(2),317-325. |
| MLA | Yao, Y,et al."Utilizing Probabilistic Linear Equations in Cube Attacks".JOURNAL OF COMPUTER SCIENCE AND TECHNOLOGY 31.2(2016):317-325. |
| Files in This Item: | There are no files associated with this item. | |||||
Items in the repository are protected by copyright, with all rights reserved, unless otherwise indicated.
Edit Comment