The Implementation and Complexity Analysis of the Branch Gröbner Bases Algorithm Over Boolean Polynomial Rings

Yao Sun () and Dingkang Wang ()
Additional contact information
Yao Sun: SKLOIS, Institute of Information Engineering, CAS
Dingkang Wang: KLMM, Academy of Mathematics and Systems Science, CAS

A chapter in Computer Mathematics, 2014, pp 157-169 from Springer

Abstract: Abstract A new branch of Gröbner basis algorithm over boolean ring has been presented in an earlier paper. In this paper, the detailed implementation and a rough complexity analysis is given. The branch Gröbner basis algorithm implements a variation of the F5 algorithm and bases on the ZDD data structure, which is also the data structure of the framework PolyBoRi. This branch Gröbner basis algorithm is mainly used to solve algebraic systems and attack multivariable cryptosystems, and its goal is to lower the complexity in each branch and expect better total complexity. An important proposition ensures the two original criteria of the non-branch F5 algorithm could still reject almost all unnecessary computations in this new branch algorithm. The timings show this branch algorithm performs very well for randomly generated systems as well as a class of stream ciphers which is generated by the linear feedback shift register (LFSR).

Keywords: Boolean Polynomial; Randomly Generated Systems; Linear Feedback Shift Register (LFSR); Stream Cipher; Algorithm Branches (search for similar items in EconPapers)
Date: 2014
References: Add references at CitEc
Citations:

There are no downloads for this item, see the EconPapers FAQ for hints about obtaining it.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:sprchp:978-3-662-43799-5_14

Ordering information: This item can be ordered from
http://www.springer.com/9783662437995

DOI: 10.1007/978-3-662-43799-5_14

Access Statistics for this chapter

More chapters in Springer Books from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().