.png){kind=icon}
.png){kind=icon}
Return
Improved BDD-based cryptanalysis of keystream generators with application to Trivium
.png){kind=icon}
PRE
AI
DOI：10.1007/s12046-026-03094-9.png)
.png){kind=icon}
Original request for help.png){kind=icon}
Share.png){kind=icon}
Save
Abstract
En 中文
The Binary Decision Diagrams (BDD) have played an important role in hardware verification, model checking, and logic synthesis, where they optimize the handling of complex Boolean expressions by reducing redundancy and ensuring canonical representation. Sahu et al. (IET. Inf. Secur. 11:159-167) gave a practical way to use the Reduced Ordered Binary Decision Diagrams (ROBDDs) to attack stream ciphers and compared different ways of operating AND operations between BDDs. We show that this method is not the universally fastest to perform a binary operation between any two objects. A successful attack requires the reduction of time and space complexity to the greatest extent possible. In this direction, we propose a new method that uses BDDs to attack any stream cipher with time complexity of O(n4M & strns;2)\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$O(\frac{n}{4}\bar{M}<^>2)$$\end{document}, and demonstrate its application to a well-known estream cipher, Trivium. Through comprehensive time and space analysis conducted via multiple experiments, we demonstrate that our method outperforms the previous approach in terms of time efficiency and, under specific conditions, in space efficiency as well.
Keywords:
Binary decision diagram
cryptanalysis
trivium
reduced ordered binary decision diagram (ROBDD)
Journal
S
IF:
1.4
Papers:
215
Citations:
0