Scholarlink

<p>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 <i>et al.</i> (<i>IET. Inf. Secur.</i> 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 <InlineEquation ID="IEq1"> <EquationSource Format="TEX">\(O(\frac{n}{4}\bar{M}^2)\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>O</mi> <mo stretchy="false">(</mo> <mfrac> <mi>n</mi> <mn>4</mn> </mfrac> <msup> <mrow> <mover accent="true"> <mrow> <mi>M</mi> </mrow> <mrow> <mo stretchy="false">¯</mo> </mrow> </mover> </mrow> <mn>2</mn> </msup> <mo stretchy="false">)</mo> </mrow> </math></EquationSource> </InlineEquation>, 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.</p>

错误：搜索内容不能为空，请输入英文关键词
错误：关键词超出字数限制，请精简
高级检索

Improved BDD-based cryptanalysis of keystream generators with application to Trivium

  • 期刊论文

  • 发表日期：

    2026年5月4日

查看全文
  • Yash Makwana,
  • Anupama Panigrahi,
  • S K Pal

摘要

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(\frac{n}{4}\bar{M}^2)\) O ( n 4 M ¯ 2 ) , 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.